T 1337/17 (Sort value indicator/AB INITIO) 02-04-2019

The invention

1. The application generally relates to computation graphs in which the vertices and the links define, respectively, "data processing elements" and the data flow between them (see paragraphs 2 and 3).

1.1 The invention means to propose a general procedure for the transformation of "serial computation graphs" into equivalent "parallel" ones (see figure 3 and paragraph 53).

1.2 The data flow in parallel computation graphs is represented using data flow elements referred to as "partition", "gather" and "interconnection" (see figures 1B and 1C, nos. 115 and 135; figures 2B and 2C, no. 225). Several types of each of these elements are anticipated (see paragraphs 30-32, 35 and 49).

2. The invention in this divisional application is specifically concerned with a "sorted merge" component disclosed in paragraphs 70-75 of the divisional application as filed.

2.1 Figure 2C depicts an "interconnection network" linking m parallel instances of A with n instances of B via m parallel 1:n partitioning elements (nos. 220, 221) and n parallel m:1 gathering elements (nos. 230, 231). In total, the network has m*n inputs and n*m outputs and, likewise, in total, n*m serial links (effectively, each A with each B; see paragraphs 38 and 39).

2.2 The "sorted merge" element (see paragraphs 70-75), "assumes" that its inputs are sorted according to a particular sort order and that the output should remain sorted in that way (see paragraph 70). The sorted merge element reads from its several inputs the next element according to the sort order and passes it to its output (still paragraph 70). The "sorted merge" element seems to be a gather element in accordance with figure 2C, even though this is not expressly disclosed in the application.

2.3 The application explains that a naive implementation of a sorted merge element may block (see paragraph 71). If, for example, there is no pending input at an input 1 of a sorted merge element, it may be impossible to pass through any work element pending at a different input because a late arrival at input 1 might take priority in the defined sort order. The sorted merge might thus be blocked until an "end-of-flow" indicator at input 1 (see paragraphs 71 and 72).

2.4 To reduce such blocking behaviour, a "sort value indicator" is sent along with the outputs of the hash partitioning elements "to indicate a value in the sort order that has been reached by at least one of its outputs" (see paragraph 73). This indicator "signals a downstream component that no work element with an earlier value n the sort order will be provided over this link" (loc. cit.).

Clarity, Article 84 EPC 1973, and claim construction

3. As explained above, the main problem addressed by the claimed solution is to avoid the described blocking behaviour of the downstream graph components, the central element of the solution being the sort value indicator.

3.1 To serve its purpose, the sort value indicator must relate to the sort order to be produced, i.e. the second key (see claim 1, line 7). Accordingly, the mention of the first key in line 17 of both requests is obviously an inaccuracy, the second key being intended instead. During the oral proceedings, the appellant confirmed this interpretation.

3.2 In broad terms, it is clear how the sort value indicator is meant to be processed by the downstream components. If a sort value indicator on any "first flow" is n, then work elements with a second key smaller than n may be received on other flows irrespective of whether there is a work element available on the first flow (see paragraph 73).

3.3 However, the details are not specified in the claims. It is only specified that a decision to pass a work element to the "merged outputs" is made "based on the sort value indicator", but not how that decision is made.

3.3.1 In this regard the claimed "sorted merge element" must still block in certain situations. For instance, when a sorted merge element has two inputs where the keys of the work elements received at input 1 are 1, 5, 7 and those at input 2 are 4, 6, 8. When element "1" has already been processed, element "4" has arrived at input 2, but no element is waiting at input 1, the sorted merge element would have to know whether the next element at input 1 will be smaller or larger than "4" (say, a "3" or a "5") in order to decide whether element "4" can be passed through at that point in time.

3.3.2 Because it is not expressly claimed how the sort value indicator is processed, it is all the more important for the clarity of the claims that the sort value indicator itself be properly specified.

3.4 However, the claim language is also deficient, in respect to how and when the sort value indicator is computed. More specifically, the following problems exist.

3.4.1 Firstly, the sort value indicator expressing an invariant about the "subsequent work elements" on a given flow may have to be recomputed at least whenever an element is received from that flow. This is confirmed by the appellant's own example submitted during the oral proceedings (and attached to the minutes of the oral proceedings) which shows the state of an inter-component link at two points in time with different sort indicator values. However, the fact that no recomputation is presently claimed constitutes a lack of an essential feature, Article 84 EPC 1973.

3.4.2 Secondly, the claims specify that the work elements provided to the "inter-component link" are sorted according to the first key (claim 1, line 5) but leave open whether they are also sorted by the second key. In the appellant's example, they are, with one partition element producing the work elements (value1, 2; value1, 6; value1, 8). If sorting by the second key were not a requirement, that partition element could also produce the values (value1, 2; value1, 8; value1, 6). For ease of reference, these examples are referred to below as V268 and V286, respectively.

3.5 During the oral proceedings, the appellant insisted that the input need not be sorted according to the second key, i.e. that the invention was meant to be able to deal with a situation such as V286. This assumption is not consistent with the description which discloses that a partial sort order is maintained by the sorted merge element.

3.6 However, if, for the sake of argument, the appellant's interpretation is accepted, how are the values arriving in the V286 order processed? Once the work element with second key "2" is received - and thus those with key "8" and "6" remain to be received - the pertinent sort value indicator would presumably have to be "6". If it were "8", then a "7" arriving at a different flow would be received before any further element from the V286 flow was received, and in particular before the "6". The desired order would thus be violated. This, however, would mean that the sort value indicator would have to be the minimal value ever to occur on the pertinent flow. Notably, if the work on a flow were sorted by the second key, the sort value indicator would only have to be the value of the second key of the next work element on that flow. If they are not sorted, the sort value indicator could only be generated once all second keys ever to occur on that flow are known - i.e. processed. This, however, is in tension with the idea that the computation graph is meant to be processed in parallel. Additionally, even if the work elements "occurred" on a flow in the V286 order (in particular, "8" before "6") they would still have to in the V286 situation, the values had to be passed to the merged outputs in the correct order (in particular "6" before "8"). That is, the claimed sorted merge element would not only have to wait for a "next" element to arrive on a flow but might have to wait for several such elements and select from them.

3.7 The appellant did not, during the oral proceedings, explain without any doubt which was the intended method for computing the sort value indicator and which assumptions had to be made so that the computation could be carried out. Nor did it file any clarifying amendments.

3.8 Weighing up the above considerations and in view of the disclosure in paragraph 70, the board considers that the intended interpretation is that the work elements on all flows are sorted by the second key and that the sort value indicator is meant to maintain that sorting.

3.9 However, as this essential feature is not in claim 1 of either request, claim 1 of both requests is unclear, Article 84 EPC 1973.

4. In its preliminary opinion, the board raised further clarity objections and issues relating to whether and under what conditions avoiding the mentioned blocking behaviour could be accepted as solving a technical problem. In the latter regard, it suggested that no such technical effect would be established without the claims specifying the execution on a parallel hardware (see point 5 of the summons).

4.1 In response to that objection, claim 1 of both requests was amended to include the feature that "different instances of the parallel partition elements and/or different instances of the parallel sorted merge elements are configured to be executed by respective different coprocessors of the computing system". As the basis for this amendment, paragraph 77 of the description was referred to (see the letter of 4 March 2019, page 2, paragraphs 4 and 5 from the bottom). However, paragraph 77 only makes the general statement that "The software may be implemented in a distributed manner in which different parts of the computation specified by the software are performed by different computers". The board doubts whether this general statement is sufficient basis for the more specific feature included in claim 1 of both requests.

4.2 That said, because the above deficiency under Article 84 EPC 1973 could not be resolved during the oral proceedings, the questions regarding original disclosure of the added feature or, in more general terms, the question of whether a technical effect can be ascribed to the claimed subject matter or why, were not discussed during oral proceedings and need not be decided.