|European Case Law Identifier:||ECLI:EP:BA:2011:T031108.20110721|
|Date of decision:||21 July 2011|
|Case number:||T 0311/08|
|IPC class:||G06F 9/50|
|Language of proceedings:||EN|
|Download and more information:||
|Title of application:||A method of assigning objects to processing units|
|Applicant name:||SAP AG|
|Relevant legal provisions:||
|Keywords:||Original disclosure - yes
Clarity - yes
Inventive step - yes
Summary of Facts and Submissions
I. This is an appeal against the decision of the examining division, announced in oral proceedings held on 7 May 2007, with written reasons dispatched on 2 August 2007, to refuse patent application number 03 018 101.0. The reason for the refusal was the absence of claims on file, in violation of Article 78(1)(c) EPC. This situation had arisen because all of the applicant's requests were considered inadmissible under Rule 86(3) EPC 1973 owing to added subject-matter (Article 123(2) EPC) or lack of clarity (Article 84 EPC).
II. A notice of appeal was received on 2 October 2007. The fee was paid on the same day. A statement setting out the grounds of the appeal was filed on 20 November 2007 together with claim sets for a main and four auxiliary requests. Oral proceedings were conditionally requested.
III. The board issued a communication dated 21 February 2011. It raised a number of objections relating to a lack of clarity (Article 84 EPC). However it did not agree with the arguments put forward by the examining division in sections 4 to 5.3 of the summons to oral proceedings, dated 16 February 2007, that there was a lack of an inventive step. On the contrary, the board was of the opinion that the subject-matter of claim 1 of all requests appeared to be inventive with respect to the closest prior art document D2:
D2 E.G. Coffman, Jr., et al.: "APPROXIMATION ALGORITHMS FOR BIN PACKING: A SURVEY"; in "Approximation algorithms for NP-hard problems", D. Hochbaum (ed.), [Online] 1996, pages 1-53; XP002285343; retrieved from the Internet: http://www.ee.columbia.edu/~egc/webpapers/ BPchapter.ps.
IV. In a letter dated 6 June 2011, the appellant filed a new sole request in response to the board's comments.
V. The appellant requests that the decision under appeal be set aside (implicitly requested) and that a patent be granted on the basis of claims 1-3 filed with the letter dated 6 June 2011.
The further text on file is:
pages 1, 3, 4, 6-16 as originally filed,
pages 2, 2a filed with telefax on 4 September 2006,
page 5 filed with telefax on 2 April 2007;
drawing sheets 1-20 as originally filed.
VI. Claim 1 of the sole request is derived from a combination of original claims 1 to 4. It reads as follows (italics have been added to mark the additions to this combination, deletions in square brackets): "1. A computer implemented method of assigning a given set of data objects (1, 2, 3, ..., 20) to processing units of a cluster (100) of processing units (102), the data objects being tables, arrays, lists or trees, each one of the processing units being a blade server, each blade server having the same [a] storage capacity (104), the method comprising the steps of:
a) sorting of the data objects by size to provide a sequence of data objects;
b) for each processing unit of the cluster:
- assigning of one or more of the data objects to the processing unit starting with the largest data object in the sequence and continuing to assign the largest data object in the sequence that fits into the remaining storage capacity until a remaining storage capacity of the processing unit is below the smallest data object of the sequence;
- deleting of the data objects which are assigned to the processing unit from the sequence, whereby the remaining storage capacity is determined by the difference between the storage capacity of the processing unit and the aggregated size of data objects being assigned to the processing unit,
and wherein step 1b) is carried out repeatedly until the sequence is empty which provides a minimum number of the processing units,
and further comprising the steps of:
c) determining a largest gap between the aggregated size of data objects being assigned to one of the processing units and the storage capacity,
d) subtracting the gap divided by the minimum number of processing units from the storage capacity to provide a first threshold,
e) performing step 1b) again for performing an assignment procedure of the data objects to the processing units using the sequence of data objects provided in step la), whereby for the second execution of step 1b) the storage capacity is set to the first threshold, wherein step 1b) is carried out repeatedly until the sequence is empty again [the remaining storage capacity is the difference between the aggregated size of the objects being assigned to the processing units and the first threshold]."
VII. Independent claim 2 of the sole request essentially differs from claim 1 by replacing "A computer-implemented method of" by "A computer program product for".
VIII. Independent claim 3 differs from claim 1 only in the first paragraph:
"A blade server having data object size balancing means (110, 112) for assigning a given set of data objects to a plurality of blade servers, the data objects being tables, arrays, lists or trees, each one of the blade servers having the same storage capacity, the data object size balancing means being adapted to assign data objects to the blade servers by the steps of:" The rest of claim 3 is identical to claim 1 after having replaced "processing unit" by "blade server".
Reasons for the Decision
1. Admissibility of the appeal The appeal satisfies the requirements of the EPC for admissibility, see sections I and II above.
2. Original disclosure
2.1 The objection with respect to Article 123(2) EPC raised in the appealed decision, section 1.2 is not relevant to current claim 1 since the concerned wording "without the previous assignments found by the first execution of step 1b)" is no longer used.
2.2 As to the various amendments made in the current claims, the board finds that they satisfy the requirements of Article 123(2) EPC:
"Computer implemented method": See page 5, lines 9 to 11 of the description as originally filed;
"Data objects", "a given set of data objects" and "the data objects being tables, arrays, lists or trees": Page 5, lines 16 to 18 and line 24;
"Each one of the processing units being a blade server": Page 5, lines 8 and 9;
"Each blade server having the same storage capacity": Page 7, lines 23 to 25;
"... and continuing to assign the largest data object in the sequence that fits into the remaining storage capacity until ..." (step 1b)): Fig. 2;
(step 1e)): Fig. 11.
3.1 In the appealed decision, section 2.2, an objection was raised for claim 1 with respect to Article 84 EPC. A lack of clarity arose for the second assignment procedure since after the first assignment procedure the processing units were filled with data objects. This objection appears to have arisen from a misunderstanding of the application by the examining division. The description at page 11, lines 10 to 20, discloses that the second assignment step is "restarted from the beginning", without the sorting step if the sorted sequence had been stored. This and figures 11-13 clearly show that the assignments found by the first execution of step 1b) are not used in the second assignment, found by the second execution of step 1b) in step 1e). This seems to have been misunderstood. An assignment is in the first place a mapping that defines which data objects should be stored on which processing unit. The word "assignment" does not imply that the storing according to the assignment has already been done, as stated in the appealed decision, section 2.1, last sentence ("Therefore the previously used proces sing units still contain objects"). The present claim 1 also specifies "assignment" and is therefore clear in this respect.
3.2 The board considers that at least some of the amend ments made to the combination of original claims 1 to 4 were necessary for clarity. Claim 1 of auxiliary request ii submitted with the grounds of appeal already contained a number of clarifications which are all contained in current claim 1:
line 6: computer-implemented method (to distinguish the method from a mental act);
line 6: assigning a given set of data objects (to make the offline character of the algorithm clear);
line 8: the data objects being tables, arrays, lists or trees (to clarify the broad expression "data object");
line 9: the processing units being a blade (to clarify the expression "processing unit" which could also be a "micro-processor" without any associated memory for which such an assignment method does not make sense);
line 9: each blade having the same storage capacity (the "first threshold" which is the same for all blade servers only makes sense if all of them have the same storage capacity);
step 1e): "for performing an assignment procedure ... using the sequence of data objects provided in step 1a)" and "wherein step 1b) is carried out repeatedly until the sequence is empty again"- this makes clear that the second assignment procedure restarts from the beginning, reuses the sorted sequence of step 1a) and performs a complete assignment with a virtually reduced storage capacity, as disclosed from original description page 10, line 23 to page 11, line 20.
3.3 In its communication, the board raised a number of further clarity objections, in response to which the appellant filed the present claims incorporating the following further amendments:
line 9: The expression "blade" is a colloquial short form for "blade server" (see original description page 2, lines 7 and 13) but also designates many other things like a sword or a knife. Therefore the word "server" was added to any occurrence of the term "blade".
Step 1b) (first hyphen) now clearly expresses that the method not only starts with the largest data object in the sequence (line 18), but continues to assign the largest data object in the sequence that fits into the remaining storage capacity (original description page 8, line 22).
Step 1b) and step 1e) previously defined the "remaining storage capacity" differently, which led to an ambiguity in the second execution of step 1b). This was remedied by replacing the definition of the "remaining storage capacity" in step 1e), lines 9-11 with the following definition of "storage capacity":
"whereby the storage capacity for the second execution of step 1b) is set to the first threshold".
3.4 Corresponding clarifications were performed for the other independent claims 2 and 3.
3.5 The board concludes that after these amendments the claims of the current sole request are clear in the sense of Article 84 EPC.
4.1 The board agrees with the examining division in the determination of the closest prior art document (D2) and the difference of refused claim 1 from D2 (i.e. steps 1c)-e)), expressed in their summons to oral proceedings, dated 16 February 2007, section 5.1, page 4.
4.2 Current claim 1 has two further differences from D2: the processing units are blade servers; the data objects are tables, arrays, lists or trees.
4.3 However, the board disagrees with the examining division's assessment of inventive step (sections 4 and 5.1): the invention executes step 1b) a second time with a virtually reduced storage capacity (called first threshold in claim 1) in order to smooth the data distribution on the blade servers by a reassignment from the start. None of the available documents disclose this special use of the First Fit Decreasing bin packing algorithm (FFD) for that purpose. (FFD is the well-known name of the algorithm defined in step 1b).)
4.4 Reassignment from the start should not be confused with a repacking of bins as disclosed in D2, page 11, middle of the page and page 14, section 2.2.6. These two features were equated in the examining division's summons to oral proceedings, page 5, paragraph 2, hyphen 1. But they are actually different since the repacking disclosed in D2 tries to improve the bin packing in order to minimize the number of bins, whereas the reassignment in the invention tries to improve the distribution of the data within the same number of bins.
4.5 The board also takes a different view from that expressed in the summons to oral proceedings, page 5, paragraph 2, hyphen 3:
"Choosing a specific resource distribution optimisation algorithm over any other cannot be considered inventive, see section 4 above";
and in section 4.2:
"... the features in the independent claims seem to define a non-technical solution for solving an NP-hard problem. This solution cannot contribute to inventive step according to Article 56 EPC as the features are of a purely mathematical and theoretical nature (see e.g. D2), thus falling under the exclusion of Article 52(2)(a) EPC."
The board considers that the present case does not present a theoretical solution to a theoretical problem (NP-hardness), but rather a concrete technical solution to the technical problem of smoothing the distribution of data objects on a set of blade servers. This is done in an unusual way by using a well-known algorithm (FFD) from the different field of bin packing with a specially adapted input value (the virtually reduced storage capacity or first threshold).
4.6 This solution is not suggested by any of the documents on file. Therefore, the requirement of Article 56 EPC is fulfilled.
5. Adaptations The board notes that there are still a number of amendments which will have to be made before a patent can be granted.
5.1 The reference numbers of the first paragraph of claim 1 are missing in claim 2. There seems to be no reason for this omission.
5.2 Analogously, reference numbers should be added to the first paragraph of claim 3.
5.3 The description passages on page 3, paragraphs 3 and 4 start with the wording "In accordance with a preferred embodiment of the invention", but disclose steps c) and e) of the current independent claims in a reformulated way. Therefore, these features are not part of an embodiment but of the claimed invention itself, and said wording should be deleted from the description for the version to be granted.
5.4 The "further preferred embodiment" of the first paragraph of page 4 of the description would appear to lie outside the specification of the invention defined by the present independent claims.
5.5 The sentence on description page 7, line 24 "In the example considered here, all memories 104 have the same storage capacity." gives the impression that having the same storage capacity would be optional. But as mentioned above in section 3.2, the "first threshold" does not make sense without that feature.
For these reasons it is decided that:
1. The decision under appeal is set aside.
2. The application is remitted to the department of first instance for further prosecution on the basis of the sole request filed with the letter dated 6 June 2011.