T 1730/11 (Graph-based Computation/AB INITIO) of 17.11.2014

Summary of Facts and Submissions

I. The appeal lies against the decision of the examining di­vision, with reasons dispatched on 23 March 2011, to refuse European patent application No. 03770720.5. The decision made reference inter alia to the documents

D1: Babaoglu O. et al., "Mapping parallel computations onto distributed systems in Paralex", Proc. 5th Annual European Computer Conference, pp. 123-130, IEEE Press, 1991,

D2: Gamma E. et al., "Design Patterns: Elements of Reusable Object-oriented Software", pp. 117-126 and 325-330, Addison Wesley, 1999, and

D3: US 6 314 114 B1,

and came to the conclusion that claim 1 according to the then main and first and second auxiliary requests did not involve an inventive step over D1, in view of D2 and D3, Article 56 EPC, and that independent claims of the first auxiliary request did not comply with Article 123 (2) EPC.

II. A notice of appeal was filed on 2 June 2011, the appeal fee being paid on the same day. A statement of grounds of appeal was received on 2 August 2011, together with amended sets of claims 1 to 25 according to a main and four auxiliary re­quests. The appellant requested that the decision under appeal be set aside and that a patent be granted based on one of the amended sets of claims. The board understands the remaining application documents to be as follows:

description pages:

1-3 as filed with the grounds of appeal

4-16 as published.

drawings, sheets:

1/7-7/7 as published.

The appellant further requested oral proceedings in case the board were minded to issue a decision adverse to the appellant.

III. Claim 1 of the main request reads as follows.

"A method of executing, on a computer system, graphs expressing computations including:

(a) providing at least two graph templates (310) each associated with a different computation graph (100), each computation graph (100) including a number of graph elements each associated with a corresponding computation;

(b) forming at least two pools of processes, each associated with a different type of processing; and

(c) processing multiple data streams concurrently, each associated with a different instance (300) of a corresponding computation graph, including for each of the data streams,

forming a graph instance (300) from the graph template (310) for the corresponding computation graph (100), including allocating memory for a runtime data structure for that graph instance and copying the graph template (310) into the allocated memory, wherein each runtime data structure includes a copy of the graph template (310), a buffer section (350) which holds work elements as work elements are passed between the graph elements and queued prior to processing, and input counts for each graph element initialized to the number of inputs for that graph element,

wherein each graph element of the graph instance (300) is associated with a corresponding one of the pools of processes, based on the type of processing associated with each pool of processes, wherein a first graph element is associated with a corresponding first pool of processes and a second graph element is associated with a corresponding second pool of processes,

for each graph element of the graph instance (300), assigning processes from the corresponding one of the pools of processes when at least some part of all of the inputs for the graph element are available according to the initialized input counts, wherein the processes read and write work elements from and to the buffer section (350) of the runtime data structure for the graph instance (300) during processing of the data stream, and

processing the data stream with the graph instance (300), including performing the computations corresponding to the graph elements of such graph instance (300) using the assigned processes;

wherein steps (a) and (b) are performed prior to step (c)."

Claim 25 of the main request reads as follows:

"A system for executing, on a computer system, graphs expressing computations including:

at least two graph templates (310) stored in data storage each associated swith a different type of graph-based computation, each template (310) comprising a number of graph elements each associated with a corresponding computation;

means for forming at least two pools of processes, each associated with a different type of processing; and

means for processing multiple data streams concurrently, each associated with a different instance (300) of a corresponding graph-based computation, including for each of the data streams,

forming a graph instance (300) from the graph template (310) associated with the corresponding type of graph-based computation, said graph instance (300) having graph elements corresponding to the graph elements of the graph template (310), including allocating memory for a runtime data structure for that graph instance and copying the graph template (310) into the allocated memory, wherein each runtime data structure includes a copy of the graph template (310), a buffer section (350) which holds work elements as work elements are passed between the graph elements and queued prior to processing, and input counts for each graph element initialized to the number of inputs for that graph element,

wherein each graph element of the graph instance (300) is associated with a corresponding one of the pools of processes, based on the type of processing associated with each pool of processes, wherein a first graph element is associated with a corresponding first pool of processes and a second graph element is associated with a corresponding second pool of processes,

for each graph element of the graph instance (300), assigning processes from the corresponding one of the pools of processes when at least some part of all of the inputs for the graph element are available according to the initialized input counts, wherein the processes read and write work elements from and to the buffer section (350) of the runtime data structure for the graph instance (300) during processing of the data stream, and

processing the data stream with the graph instance (300), including performing computations corresponding to the graph elements of such graph instance using the assigned processes;

wherein the system is configured to form the at least two pools of processes prior to processing the multiple data streams concurrently, each associated with a different instance (300) of a corresponding graph-based computation."

IV. The wording of the independent claims of the auxiliary requests is immaterial to the present decision.

Reasons for the Decision

1. The invention

1.1 The application relates to the efficient execution of computations expressed as data flow graphs (see p. 4, par. 38). The vertices (or nodes) in these graphs (illustrated in fig. 1) represent computational tasks and the links indicate the paths along which the data flows in chunks referred to as "work elements". A com­pu­ta­tion at a vertex can start as soon as (but also no earlier than when) a work element is available at each input link. When the com­pu­tation has terminated, the result is sent as a new working element along the out­put link.

1.2 It is disclosed that there are several "types of graphs" representing different types of "work flow" or transactions that might be needed. For example, in a banking context, there may be a different such graph for each necessary financial transaction (see par. 87).

1.3 The work is performed by processes which may be tai­lored to particular vertexes of particular types of graphs (see par. 63).

1.4 To "run" a work flow, a suitable graph data structure is created in a shared memory segment through which the processes can communicate, and each pool is asso­ci­ated with some of the vertices of the graph; this in­volves "an initialization procedure [on the process] which includes mapping the shared memory segment for the graph instances into the address space of the pro­cess" (see par. 58).

1.5 For each type of graph there is a "template" from which instances of graphs are created. It is possible to cre­ate and run several such instances concurrently (see par. 41). To create a graph data structure, the temp­late corresponding to the required type of graph is co­pied into the shared memory segment. In addition, buffer space is allocated to hold the work elements "queuing" at individual vertices (see fig. 3 and esp. pars. 55 and 67).

2. Prior art

2.1 Document D1 discloses a programming environ­ment, called Paralex, for the development and execution of data flow programs "on distributed systems as if the latter were uniform parallel multiprocessor computers" (ab­stract). Paralex is based on data flow graphs which ex­press the same sort of "coarse-grain" data flow as the applica­tion (see sec. 2.2, esp. 1st two pars.). A graph is also referred to as a "pro­gram", i.e. the graph can be executed. Before a Paralex pro­gram can be executed, the nodes of the graph must be asso­ci­ated with suitable hosts (sec. 2.4); it is said that the "com­putation graph" is embedded in the "system graph" (see sentence bridging pp. 125 and 126). For each node there are sets of hosts OHi and PHi defining those hosts on which node i can respectively should preferably be exe­cu­ted (see sec. 4, last par., and sec. 4.2). The require­ments and prefe­ren­ces expressed by these sets are taken into account when the nodes are mapped to the hosts of a gi­ven network. A set of nodes which have to be executed se­quen­tially - referred to as a "chain" - are mapped to the same host so as to mini­mize non-local data communi­cation (sec. 4.1). At the hosts, each node will be exe­cu­­ted as a Unix process (see sec. 2.4). Nodes at the same host communicate with each other via finite buffers (see sec. 4.6) so as to decouple computations proceeding at varying speed. D1 discloses that diffe­­rent graph in­stances can be exe­cu­ted in pa­rallel on diffe­rent hosts, either to achieve tolerance against node failure (sec. 4.4) or have pa­rallelism be­tween diffe­rent iterations in case of pipe­lined opera­tion (see sec. 4.6).

2.2 The book excerpt D2 discloses the idea of "prototype patterns" to create instances of classes by "cloning" - i.e. deep copying - a given "prototype" and initiali­sing it properly. Prototypes are introduced to avoid the need to replicate class hierarchies.

2.3 Document D3 discloses a distributed system of computing systems referred to as nodes. Each node which offers services to execute on request by (and on behalf of) other nodes, provides a "dedicated process pool" of varying size for each possible requesting node (see col. 1, lines 40-46; and col. 7, lines 4-9).

3. Article 123(2) EPC

3.1 The decision under appeal did not raise any objection under Article 123(2) EPC against the then main request, nor does the board have occasion to raise an objection of its own. Furthermore, the board is satisfied that the amendments made to the claims of the main request are based on the application as originally filed as indi­ca­ted by the appellant in its statement of grounds of appeal (see p. 1, 3rd par. - p. 2, 4th par.).

4. Article 56 EPC 1973

4.1 The appellant challenges the decision under appeal mainly on two grounds:­ firstly, it argues that the "sets of nodes" in D1 are so different from the "pools of processes" of the present invention that the skilled person would not have considered replacing the set of hosts with pools of processes (see grounds of appeal, esp. p. 6, penult. para.). Secondly, it points out with respect to the runtime graph data structure that "D1 is concerned with processing computations over a distributed system, and shared memory is not an obvious or compatible choice for the communications between hosts or work stations on a network" (see p. 7, last para. and p. 8, penult. para.).

4.2 The board agrees on the second point. D1 does not dis­close the use of physically shared memory. The board notes that the concept of shared distributed memory al­so exists but that this does not, according to con­ven­tional understanding, imply physically shared memory but only a shared address space which makes access to physically distributed memory transparent to applica­tions. Since the nodes of the computation graph are spread across the distributed system, so will be any data structure representing the computation graph. The board concludes in agreement with the appellant that the idea of copying a graph template data stru­cture into the suitably allocated memory is not compa­tible with - and thus not obvious in view of - D1 as it stands.

4.3 This copying would be compatible, however, with a single multiprocessor computer with shared memory. Al­though the abstract of D1 introduces Paralex as a "pro­gramming environment that allows parallel programs to be developed and executed on distributed system as if the latter were uniform parallel multiprocessor compu­ters" (emphasis by the board) and is thus speci­fi­cally targeted at distributed systems as distinct from multi­processor computers, the board deems it nonethe­less to be a realistic problem for the skilled person to con­tem­plate which modifications of the system of D1 might be required - and which simplifications achie­vable - if the system of D1 were adapted to a multiprocessor sys­tem. For example, the skilled person might have a sui­table microprocessor system at hand and want to assess the possible speed-up from adapting the system of D1 to it.

4.4 Doing this, the skilled person would realize that on a multiprocessor computer there would be no need for the sets of nodes or the chains of D1. D1 distinguishes between sets of hosts OHi and PHi which can or prefe­rably should execute a certain node i. Since a single multiprocessor would be a single "host", this distinc­tion would become void. Further, D1 groups nodes which lie along a "chain of data flow edges" and maps entire such chains to hosts so as to keep "all of the data communication along a chain local" (see sec. 4.2, 1st para.; sec. 4.3) and thus to achieve the overall goal of "maximizing parallel execution and minimizing remote communication" (see sec. 4, 1st para.).

4.5 The board considers that on a single multiprocessor com­­puter with shared memory it would be obvious for the Unix processes (see sec. 2.4) executing the individual nodes to communicate with each other via buffers in shared memory. As the data flow is deter­mined by each computation graph, the necessary buffers are effect­ive­ly implied by the computation graphs. Un­der these cir­cum­­stances, the board considers that the claimed crea­tion of a computation graph data structure by copying a suitable template representing the com­pu­tation graph and extending it with suitable buffer space (see also fig. 3) would be obvious for the skilled person, be it from first principles or from the prototypes according to D2.

4.6 The board further considers that the dynamic allocation of processes from a pool of processes to individual nodes of the computation graphs being executed would be obvious as a matter common programming practice.

4.7 However, the system so obtained would still diffe­r from the claimed invention in not having the features of "for­ming at least two pools of pro­cesses, each associ­a­ted with a different type of pro­cessing" (e.g. step b of method claim 1), "each graph element [being] associ­a­ted with a corresponding one of the pools of pro­cesses, based on the type of processing associated with each type of processes" (claim 1, step c, 3rd para.), prior to instantiating and processing a computation graph (claim 1, last line).

4.8 The decision denied (reasons 2.2.1) that the "for­ming of the pool and assigning of processes from the pools" had a technical effect because "[t]he technical effect of pools is usually obtained if" - and 'only if', as the board understands the argument - "the pooled re­source is reused". While the independent claims indeed do not literally specify that the pooled re­source is "returned" to the pool and may be "reused", the board notes that claims 1 and 25 disclose the dyna­mic allo­ca­tion of processes ("when ... inputs ... are avai­lable"). The board agrees with the appellant that al­ready the provision of pools of processes has a tech­nical effect, namely at least that of enabling the tech­­nical effect of "pooled resources" which the exami­ning division referred to. Hence, it can be left open whe­ther, as the board tends to think, the skilled per­son would even consider it implicit from the term "pool" in the given context that processes are re­turned to the pool and possibly reused once their task is finished and the used inputs are no longer avai­lable.

4.9 In summary, the board agrees with the appellant that the pre-computation of tools of processes dedicated to different types of processing and vertexes is not void of any technical effect but that it rather contri­butes to the efficient execution of computation graphs.

4.10 As argued above, the sets of hosts in D1 neither imply nor suggest these difference features, since they serve, as the appellant correctly argues, a different purpose which, moreover, is irrelevant on a single shared memo­ry machine. The board also considers that neither the other documents on file nor the common knowledge in the art discloses or suggests these features in the given context.

4.11 Therefore, the board comes to the conclusion that the independent claims 1 and 25 of the main request involve the required inventive step in the sense of Article 56 EPC 1973 over the prior art on file.

Further comments

5. The board has no occasion to raise any objection to the dependent claims 2-24.

6. The board notes however that the description does not conform with the amended claims according to the main request. For example, the very feature causing the board to acknowledge an inventive step (see points 4.7 and 4.9) above, is disclosed as optional in the present description: see paragraph 63, which discloses that different types of pools only "may be made of pro­cesses ... tailored to a particular vertex".

7. Since this decision allows the appellant's main re­quest, its conditional request for oral proceedings does not come into play.

Order

For these reasons it is decided that:

1. The decision under appeal is set aside.

2. The case is remitted to the department of first in­stance with the order to grant a patent based on claims 1-25 according to the main request as filed with the grounds of appeal with a description to be adapted.