|European Case Law Identifier:||ECLI:EP:BA:2011:T048608.20111007|
|Date of decision:||07 October 2011|
|Case number:||T 0486/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. The appeal is directed against the decision, posted on 2 August 2007, of the exa mi ning division, to refuse the application 03 026 773.
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 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.
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 the auxiliary requests appeared to be inventive with respect to the closest prior art document D1, e.g. when combined with D7:
D1 W. Leinberger, et al.: "Multi-Capacity Bin Packing Algorithms with Applications to Job Scheduling under Multiple Constraints"; TR 99-024; pages 1-23; XP002285342; retrieved from the Internet: http://www-users.cs.umn.edu/~karypis/publications/Papers/PDF/mrbinpack.pdf.
D7 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 claims for a new sole request.
V. The board issued a summons to attend oral proceedings to be held on 26 October 2011. It raised objections relating to a lack of support (Article 84 EPC) and lack of inventive step (Article 56 EPC).
VI. In a letter dated 22 September 2011, the appellant filed a new sole request.
VII. After consultation with the board, the rapporteur contacted the appellant by telephone on 4 October 2011 to point out further minor problems to be overcome before grant of a patent could be ordered. In response, the appellant filed, with a letter dated 7 October 2011, another new set of claims and new description pages 3, 4, 6 and 8.
VIII. On 7 October 2011, the board cancelled the oral proceedings to be held on 26 October 2011.
IX. 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-5 filed on 7 October 2011.
The further text on file is:
pages 1, 5, 7, 9-19 as originally filed,
pages 2, 2a filed with telefax on 5 September 2006,
pages 3, 4, 6, 8 filed with telefax on 7 October 2011;
drawing sheets 1 to 21 as filed with a letter dated 22 December 2003.
X. Claim 1 of the sole request reads as follows:
"1. A computer implemented method of assigning a given set of data objects (1, 2, 3,..., 20) to processing units (B1, B2, B3, ... BN) of a cluster (100) of processing units, each one of the data objects (1, 2, 3,..., 20) having an data object size and a data object load, the data object load being indicative of a mean number of access operations per time unit to the respective data object, the data objects (1, 2, 3,..., 20) being tables, arrays, lists or trees, each one of the processing units being a blade server, each blade server having the same storage capacity and the same load capacity, the method comprising the steps of:
- a) calculating (200) an index based on data object size and data object load for each one of the data objects (1, 2, 3,..., 20),
- b) sorting (201) of the data objects by index to provide a sequence of data objects (1, 2, 3,..., 20);
- c) for each processing unit of the cluster:
- assigning (206) of one or more of the data objects (1, 2, 3,..., 20) to the processing unit in the order of the sorted sequence until a remaining storage capacity or a remaining load capacity of the processing unit is too small for remaining data objects of the sequence, wherein the first data object of the sequence has the largest index;
- deleting (216) of the data objects (1, 2, 3,..., 20) that are assigned to the processing unit from the sequence,
whereby step 1c) is carried out repea tedly until the sequence is empty in order to provide a minimum number of the processing units, whereby the remai ning storage capacity is determined by the difference between the storage capacity and the aggregated size of data objects being assigned to the processing unit, whereby the remaining load capacity is determined by the difference between the load capacity and the aggregated loads of data objects being assigned to the processing unit,
and further comprising the steps of:
- d) determining (800) a first largest gap between the aggregated size of data objects being assigned to one of the processing units and the storage capacity,
- e) determining (800) a second largest gap between the aggregated load of data objects being assigned to one of the processing units and the load capacity,
- f) subtracting (802) the first largest gap divided by the minimum number of processing units from the storage capacity to provide a first threshold,
- g) subtracting (802) the second largest gap divided by the minimum number of processing units from the load capacity to provide a second threshold,
- h) performing (806) step 1c) again for performing an assignment procedure of the data objects to the processing units using the sequence of data objects (1, 2, 3,..., 20) provided in step lb), whereby for the second execution of step c) the storage capacity is set to the first threshold and the load capacity is set to the second threshold, wherein step 1c) is carried out repeatedly until the sequence is empty again.
XI. Independent claim 3 of the sole request essentially differs from claim 1 by replacing "A computer implemented method of" by "A computer program product for".
XII. Independent claim 5 differs substantively from claim 1 only in the first paragraph:
"5. A blade server having balancing means for dynamically assigning a given set of data objects (1, 2, 3,..., 20) to a plurality of processing units of a cluster (100) of processing units, the processing units being blade server servers (B1, B2, B3,..., BN), each one of the data objects (1, 2, 3,..., 20) having an assigned index that is based on data object size and data object load, the data object load being indicative of a mean number of access operations per time unit to the respective data object, the data objects being tables, arrays, lists or trees, each one of the processing units having the same storage capacity and the same load capacity, the balancing means being adapted to assign data objects to the blade server servers by the steps of:"
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. Clarity and original disclosure
2.1 In the appealed decision, sections 1.2 and 1.3, 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 original description at page 14, lines 16-22, discloses that the second assignment step is "performed again with the reduced thresholds", without the sorting step (i.e. starting at step 204) if the sorting indices and the original object sequence have been saved. This and figure 18 clearly show that the assignments found by the first execution of step 1c) are not used in the second assignment which is created by the second execution of step 1c) in step 1h). 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 1.2, last sentence ("Therefore the previously used proces sing units still contain objects"). Current claim 1 also specifies "assignment" and is therefore clear in this respect.
2.2 The current independent claims are based on claim 1 of auxiliary request ii submitted with the grounds of appeal. This claim is itself based on a combination of original claims 1-5 and contains additionally the following clarifications [indications for the original disclosure of these amendments are put in brackets]:
"computer-implemented method": to distinguish the method from a mental act [original description page 8, lines 9, 10];
"assigning a given set of data objects": to make the offline character of the algorithm clear [figure 3; page 10, lines 16-22];
"the data object load being indicative of a mean number of access operations per time unit to the respective data object": to define the data object load [page 3, lines 10-13; page 10, lines 26-29];
"the data objects being tables, arrays, lists or trees": to clarify the broad expression "data object" [page 6, line 27];
"each one of 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 [page 8, line 12];
"each blade having the same storage capacity and the same load capacity": the "first threshold" and the "second threshold" which are the same for all blade servers make only sense if all of them have the same storage and load capacity [page 8, lines 12-15];
"whereby step 1c) is carried out repeatedly until the sequence is empty in order to provide a minimum number of processing units": otherwise the assign ment can consist of only one data object and does not have to be complete; see also the summons to oral proceedings in examination, dated 16 February 2007, section 4.1 [original claim 2];
step 1h) "for performing an assignment procedure ... using the sequence of data objects provided in step 1b)" and "wherein step 1c) is carried out repeatedly until the sequence is empty again": this makes clear that the second assignment procedure restarts from beginning, reuses the sorted sequence of step 1b) and performs a complete assignment with virtually reduced storage and load capacities [page 14, paragraph 4].
2.3 In its communication, the board raised a number of further clarity objections, in response to which the appellant filed the current claims incorporating the following further amendments:
"blade server": the expression "blade" is a colloquial short form for "blade server" but also designates many other things like a sword or a knife [original description page 2, lines 5, 10];
step 1c) "in the order of the sorted sequence" (instead of "in sequential order"): this refers back to the sequence defined some lines before in the claim;
step 1c) "or" (instead of "and"): the negation of the fitting test [figure 2 (212)] is fulfilled if one of the two capacities is too small;
step 1c) "for remaining data objects of the sequence": the term "consecutive" was misleading since it could induce that the data objects assigned to the same processing unit must directly follow each other in the sequence, without an object in between them; this would even result in another known bin-packing algorithm, the so-called Next-Fit Decreasing (NFD) algorithm for which there is no support in the description; [original description page 9, line 23 reads: "it is determined whether there is a next object in the ordered sequence that fits into both gaps"; see also figure 2 (212)];
step 1c) "wherein the first data object of the sequence has the largest index": to clarify that the data object with the largest index is tried first [page 9, line 7: "... processing of the object sequence starts with the first data object of the sequence, i.e. the object having the largest sorting index value"];
step 1f) "minimum number of processing units" [see original description page 14, line 14 in combination with page 10, line 10];
step 1h) "whereby for the second execution of step c) the storage capacity is set to the first threshold and the load capacity is set to the second threshold": claim 1 of auxiliary request ii defines the "remaining storage capacity" and the "remaining load capacity" differently, which leads to an ambiguity in the second execution of step 1c) [figure 18].
2.4 Corresponding clarifications were performed for the other independent claims 3 and 5.
2.5 As to the amendments filed on 22 September 2011, beside some reference numerals added, they concern only steps 1c), 3c) and 5c) where the expression "wherein the first data object of the sequence has the largest index" had been added [original description page 9, lines 7, 8].
2.6 As to the amendments filed on 7 October 2011, in the claims the only substantive changes concern reference numerals. In the description, the expression "a preferred embodiment of" was deleted before "the invention" on page 3, 4, 6 and 8, since the details described in these passages concern the invention as defined in the independent claims and not an embodiment thereof. Furthermore, on page 8, the expression "a preferred embodiment" was replaced by "an alternative" since figures 19 and 20 describe a variant different from the subject-matter of the independent claims.
2.7 The board concludes that after these amendments the claims of the current sole request fulfil the requirements for clarity of Article 84 EPC and for original disclosure of Article 123(2) EPC.
3.1 The board agrees with the examining division in the determination of the closest prior art document (D1) as expressed in their summons to oral proceedings, dated 16 February 2007, page 3, section 5.1.
3.2 Current claim 1 thus has the following differences from D1: a second execution of step 1c) with virtually reduced storage/load capacities; the data object load being indicative of a mean number of access operations per time unit to the respective data object; the processing units are blade servers; the data objects are tables, arrays, lists or trees.
3.3 However, the board disagrees with the examining division's assessment of inventive step (sections 4.2 and 4.3): The invention executes step 1c) a second time with virtually reduced storage/load capacities (called first and second thresholds in the claims) in order to smooth the data distribution on the blade servers by a reassignment from the start. None of the available documents appears to 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 1c).)
3.4 Reassignment from the start should not be confused with a repacking of bins as disclosed in D7, 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, section 5.3, hyphen 4. But they are actually different since the repacking disclosed in D7 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.
3.5 The board also takes a different view from that expressed in the summons to oral proceedings, page 2, section 4:
"Choosing a specific resource distribution optimi zation algorithm as defined by the independent claims does not provide any surprising effect over any other resource distribution optimi zation algorithm as e.g. disclosed by D1 or D7."
and in section 4.3:
"... 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. D1 or D3), 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/load capacities or first/second thresholds).
3.6 This solution is not suggested by any of the documents on file. Therefore, the requirement of Article 56 EPC is fulfilled.
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 with the order to grant a patent on the basis of claims 1-5 of the sole request filed on 7 October 2011, the description pages 1, 5, 7 and 9-19 as originally filed, pages 2 and 2a as filed on 5 September 2006, pages 3, 4, 6 and 8 as filed on 7 October 2011, and the drawing sheets 1 to 21 as filed with a letter dated 22 December 2003.