14-15 November 2018
|European Case Law Identifier:||ECLI:EP:BA:2014:T083510.20140903|
|Date of decision:||03 September 2014|
|Case number:||T 0835/10|
|IPC class:||G06G 7/62
|Language of proceedings:||EN|
|Download and more information:||
|Title of application:||ARRAY TRANSFORMATION IN A BEHAVIORAL SYNTHESIS TOOL|
|Applicant name:||Mentor Graphics Corporation|
|Relevant legal provisions:||
|Keywords:||Amendments - added subject-matter (yes)
Claims - clarity (no)
Inventive step - (no)
De-automation is not per se inventive (see 5.1.8, 5.1.9 and 5.1.6).
Summary of Facts and Submissions
I. The appeal is directed against the decision of the examining division, posted on 27 November 2009, to refuse the application 03721348 for lack of inventive step over document:
D1 H. Schmit et al.: "Synthesis of Application-Specific Memory Designs"; IEEE Transactions on Very Large Scale Integration (VLSI) Systems, volume 5, no. 1, March 1997, pages 101-111; IEEE USA; ISSN: 1063-8210; XP002321169.
II. A notice of appeal was received on 22 January 2010. The fee was received the same day. A statement of the grounds of appeal was received on 6 April 2010. Claim sets of a main and four auxiliary requests were filed.
III. In its summons to oral proceedings, the board gave reasons for its preliminary opinion with respect to Articles 123(2), 84 and 56 EPC.
IV. In a letter dated 20 August 2014, the appellant announced that it would not be represented at the oral proceedings.
V. Oral proceedings were held on 3 September 2014 in the absence of the representative, as announced. At their end, the board announced its decision.
VI. The appellant requests that the decision be set aside and a patent be granted on the basis of claims 1-23 of a main, first or second auxiliary request or claims 1-20 of a third auxiliary request or claims 1-19 of a fourth auxiliary request, all filed with the grounds of appeal (the main and second to fourth auxiliary requests being identical with the corresponding refused requests). The further text on file is: description pages 1, 3-19 as originally filed, pages 2, 2a as filed on 7 February 2006; drawing sheets 1-18 as originally filed.
It is further requested to reimburse the appeal fee.
VII. Claim 1 of the main request reads as follows:
"1. A method of reorganizing an array layout in a behavioral synthesis tool used to design an integrated circuit, comprising:
reading a source code description associated with the integrated circuit into the behavioral synthesis tool, the source code description having multiple arrays;
storing the source code description in an intermediate data structure within the behavioral synthesis tool, the intermediate data structure including one or more memory allocation constraints associated with one of the arrays in the source code description, the one or more memory allocation constraints indicating that the one of the arrays is allocated to one or more memories of the integrated circuit according to a first layout format;
displaying to a user a report of circuit area and speed with the one of the arrays allocated according to the first layout format;
allowing a user to modify at least one of the memory allocation constraints via a graphic user interface, wherein the graphic user interface displays the name of the one of the arrays and allows the user to modify any one or more of the memory allocation constraints associated with the one of the arrays; and
responsive to the user modifications, transforming the array layout of the one of the arrays from the first layout format to a second layout format,
wherein the act of transforming comprises updating the intermediate data structure to include the modified memory allocation constraints, and
wherein the acts of displaying, allowing, and transforming are performed while the source code description is stored within the behavioral synthesis tool and prior to the source code description being synthesized into a register-transfer level description of the integrated circuit."
VIII. Claim 1 of the first auxiliary request differs from claim 1 of the main request by adding "independently of the others of the plurality of arrays" at the end of the step of "allowing the user to modify".
IX. Claim 1 of the second auxiliary request differs from claim 1 of the main request in that the fourth step starts (additions in italics style):
"allowing a user to select the one of the arrays and to modify at least one of the memory allocation constraints ..."
X. Claim 1 of the third auxiliary request differs from claim 1 of the second auxiliary request in that the steps 2-5 read (amendments in italics style):
"storing the source code description in an intermediate data structure within the behavioral synthesis tool, the intermediate data structure including one or more memory allocation constraints associated with each of the arrays, one of the memory allocation constraints indicating the word width for a respective one of the arrays, the one or more memory allocation constraints indicating that the respective one of the arrays is to be allocated to one or more memories of the integrated circuit according to a first layout format;
displaying to a user a report of circuit area and speed with the respective one of the arrays allocated according to the first layout format;
allowing a user to select the respective one of the arrays and modify at least one of the memory allocation constraints associated with the respective one of the arrays, including the one of the memory allocation constraints indicating the word width for the respective one of the arrays, the user modification being performed through a graphical user interface without the user manually editing the source code description or the intermediate data structure; and
responsive to the user modifications, transforming the array layout of the respective one of the arrays from the first layout format to a second layout format,".
XI. Claim 1 of the fourth auxiliary request differs from claim 1 of the third auxiliary request in that the steps 2-5 read (amendments in italics style; deletions [deleted: struck through]):
"storing the source code description in an intermediate data structure within the behavioural synthesis tool, the intermediate data structure including one or more memory allocation constraints for a respective array indicating that the respective array is allocated to one or more memories of the integrated circuit according to a first layout format, the one or more memory allocation constraints including constraints for setting an array length of the respective array, an array width of the respective array, and a format for packing the respective array to a resource;
displaying to a user a report of circuit area and speed with the at least one array allocated according to the first layout format;
allowing a user to modify any one of the constraints for setting the array length of the respective array, the array width of the respective array, or the format for packing the respective array, the user modification being performed via a graphic user interface and without the user manually editing the source code description or the intermediate data structure; and
responsive to the user modifications, transforming the array layout of the respective [deleted: one of the] array from the first layout format to a second layout format,".
Reasons for the Decision
1. Overview of the invention
1.1 The application relates to a method of using a behavioural synthesis tool to design integrated circuits. The tool reads a (behavioural) source code description (in a programming language like C or Pascal, or in a behavioural hardware description language like VHDL or Verilog; see original description page 5, lines 12-17) of a circuit designed by a user (figure 2 (30)).
This description contains arrays, i.e. memories modeled in the source code language (page 1, lines 26-33), and a default set of memory allocation constraints (page 6, lines 2-3; step of "storing" in claim 1 of all requests). A constraint can designate the array length and width (page 17, lines 15-20), the memory type (on-/off-chip, single-/multi-port, synchronous/asynchronous; see original claim 21), the packing mode or the format (page 7, lines 31-33). Note that in original claims 31-33, "format" designates little/big endian or interlacing, whereas on page 9, lines 16-18 and page 10, lines 3-4, "format" designates the size, i.e. array length and word width.
The tool generates from the read source code description an "intermediate data structure" in a kind of internal format, called "synthesis intermediate format" ("SIF", page 5, 17-20; page 6, lines 5-13; page 3, lines 9-12; figure 2 (32)), and stores this data structure.
Now, the tool calculates and displays a report of area and speed of the current array allocation in the memories of the circuit (figure 2 (36)).
The user can then modify the constraints, whereupon the tool re-allocates the arrays (figure 2 (34)). There are two way of modifying: either directly by editing the constraints in the source code description (figure 16(c); claim 4 of the main request; original claim 6; page 3, lines 2-4; sentence bridging pages 7 and 8) or indirectly by using a graphical user interface (GUI) like in figure 13 (see also page 10, lines 1-5).
After the constraints have been modified, the tool displays an updated report of area and speed and waits for some unspecified kind of user satisfaction input (page 8, lines 23-24; page 10, lines 4-5). After the user has expressed his satisfaction, the tool transforms/updates the intermediate data structure (in the SIF format) to represent the modified constraints (the step of "transforming/updating" in claim 1 of all requests; see also page 8, line 24 to page 9, line 9).
All this is done before the register-transfer level description (RTL code; figure 2 (40)) of the circuit is generated.
1.2 According to original description page 2, lines 10-19, it is the advantage of the invention to avoid the prior art method of re-editing the source code and re-reading it into the tool in case the user is not satisfied with the array allocation. Another passage (page 9, lines 16-30) further specifies that when re-editing the source code description, it is the re-calculation of the array addresses for every code segment which accesses an array element (figure 16(b): A, A) which "requires substantial editing time" and is "error-prone".
2. Overview of the decision
2.1 Claim 1 of all requests does not satisfy the requirements of Article 123(2) EPC.
2.2 The application suffers from a lack of clarity of claim 1 of all requests (Article 84 EPC).
2.3 Claim 1 of all requests lacks an inventive step (Article 56 EPC).
3. Original disclosure
The examining division did not raise any objections under Article 123(2) EPC in its decision. However, the board finds that the following amendment is not originally disclosed:
3.1 Claim 1 of all requests recites "responsive to the user modifications" at the beginning of the "transforming" step. This amendment was introduced with the first letter of reply to the examining division, dated 7 February 2006. The letter (page 1) indicates passages in the original description supporting this amendment. However, none of these passages show that the transformation of the intermediate data structure is done in response to the user modifications: Two steps are missing in the claim, in fact after the modification of the constraints and before the transformation of the intermediate data structure:
- a second displaying step of the circuit area and speed (the second pass through block 36 in figure 2; see also page 3, lines 2-5);
- an input by the user indicating his satisfaction with the memory allocation, see page 8, lines 23-24: "After the designer is satisfied with the memory allocation, the designer directs the GUI to apply the memory allocation information to the SIF." (emphasis added);
see also page 10, lines 3-5: "The designer then changes a size constraint for the array indicating the array should be transformed to a 50 by 64 format. Once confirmed, the constraint within the SIF for the size of array A is changed to reflect the designer's desired change, ..." (emphasis added).
This means that the method first displays an evaluation of the design and then - apparently - waits for another user modification or for a user satisfaction input, before it applies the confirmed modification to the intermediate data structure. The user modification is only a necessary condition for the transformation of the intermediate data structure, but not a sufficient one. To summarise, the transformation is started only in response to a user satisfaction input, and not already in response to the user modification.
3.2 Thus claim 1 of all requests does not comply with Article 123(2) EPC.
3.3 For this reason alone, the appeal must be dismissed. However, the board will also consider the question of inventive step (and of clarity as a prerequisite of inventive step), since inventiveness was the only reason of the appealed decision to refuse the application, and the above objection concerning Article 123(2) EPC could have been easily overcome.
4. Clarity of claim 1
The expression "source code description" in claim 1 of all requests is unclear. According to the description (page 5, lines 12-17), such a description may be written in hardware description languages like Verilog or VHDL. It is generally known that the latter also allow to formulate circuit descriptions at the RTL level. Thus a source code description could be at the RTL level. However, it follows from description page 5, lines 10-14 that a behavioural source code description is meant, and not an RTL source code description.
In the following, the claims are interpreted in the way indicated in 3.1 and 4.
5.1 Main request
5.1.1 The board considers D1 to be the closest prior art, as it was in the appealed decision (Reasons, 1.1). This was accepted in the grounds of appeal "for the sake of argument" (A.2, first paragraph).
5.1.2 According to the appealed decision (page 4), claim 1 of the refused main request (corresponding to the current main request) differs from D1 in that a graphical user interface (GUI) is used for modifying the constraints, and a report of the estimated circuit area/speed is displayed. The objective technical problem is how to modify D1 in order to allow a user to manually influence the design space exploration process. To solve this problem, a skilled person would provide input means for manually overriding the parameters manipulated by the succeeding optimisation process, e.g. array width, length and grouping (page 5, paragraph 3). He would also provide displaying the results of the manipulation, because interactive design and manual correction is a standard procedure in computer-aided design. GUIs are an obvious implementation choice.
5.1.3 According to the grounds of appeal (page 3, first paragraph), the technical problem formulated in the decision points to the solution, since the problem of allowing a user to manually influence the design space exploration is achieved in the claim by "allowing a user to modify ...". The technical problem without an "ex post facto analysis" as used by the examining division is "the need to provide a method for re-organising an array layout to achieve more efficient memory designs more quickly using customisable design options" (paragraph 4). The automated approach of D1 leads the skilled person in a completely different direction than the application: It teaches that optimisation must involve a thorough evaluation of each design possibility relative to the system cost (last paragraph). Based on D1, a fully automated design optimisation is preferable and desirable (grounds, page 4, paragraph 4).
5.1.4 The board agrees with the view of the examining division. It cannot see that the problem formulated in the decision would point to the the solution: The feature of the claim which allows the user to manually influence the design is the provision of a GUI and not the "allowing a user to modify ... constraints". The latter cannot be considered as a technical feature in the proper sense. It is more an aim that is achieved by the GUI and by storing the entered values.
5.1.5 The technical problem formulated in the grounds is less appropriate than that of the decision: "Achieving more efficient memory designs" (page 3, paragraph 4; emphasis added) is stated to be a technical effect of the claimed method and contained in the problem formulation.
5.1.6 However, a more efficient design is not a result of the computer-implemented method itself, but (if achieved) of the design decisions taken by a human designer which are merely entered via a GUI and then cognitively evaluated by the designer with the help of a report. Moreover compared to D1, it is unlikely that the claimed method finally achieves a more efficient memory design, since D1 apparently evaluates exhaustively all the possibilities in an automatic way. So, one can only say that the method aids the designer to manually find a good memory design (therefore the expression "computer-aided design"), but such a good memory design cannot be seen as a technical effect of the method itself.
5.1.7 The other alleged technical effect of "re-organising an array layout more quickly" (emphasis added) can also not be recognised. D1 explicitly mentions the re-organisation of the array layout (page 104, left column, paragraphs 3, 4):
"The dimensions of an array, the word width and word depth, as specified in the behavioral description, should, in some cases, be transformed to create a better array-memory mapping. These transformation, which we call array widening and array narrowing, are illustrated in Fig. 7.
When an array is widened, n consecutive words are placed in a single, wider word of the new array. ..."
This re-organisation of the array layout is done automatically in D1 (see page 106, left column, third sentence: "Other basic moves are the widening and the narrowing of the array." in combination with page 105, left column, last complete sentence: "All three procedures are based on ... and the same set of design state manipulations, called the move set."), in contrast to the application where the user has to enter the values of the array layout.
However, the board cannot see why a manual computation and entering of optimisation values would be quicker than an automatic computation of these values. The human designer also would have to spend considerable time to compute appropriate values by hand.
5.1.8 The board is of the opinion that the method of D1 is characterised by maximally automating the memory allocation design process, whereas the application aims to provide the designer with a half-automated tool for the same purpose, leaving to the designer the determination of important parameters for allocating arrays in memories.
However, as little as merely automating human behaviour is usually considered to be inventive (see for example section 6. from decision T634/01 of a different board, or section 5.4 from T1937/09 of this board in a different composition), the inverse - i.e. "de-automating" or undoing (in a computer-implemented method) the automation performed by a prior art software - cannot in general be considered to be inventive.
5.1.9 In particular in the present application, the board cannot see an inventive activity in leaving the optimisation task mainly to the designer and providing him with the necessary aid to perform that task (reporting the evaluation parameters for the current design and providing him with a GUI for modifying the design).
5.1.10 Therefore, claim 1 of this request is not inventive in the sense of Article 56 EPC.
5.2 First auxiliary request
5.2.1 Claim 1 of the newly filed first auxiliary request differs from claim 1 of the main request by adding "independently of the others of the plurality of arrays" at the end of the step of "allowing the user to modify". The board considers this to be an explicit formulation for a feature which is already implicitly present in the main request.
5.2.2 Therefore, claim 1 of this request is not inventive in the sense of Article 56 EPC.
5.3 Second auxiliary request
5.3.1 According to the decision (2.), claim 1 of this request is essentially identical to claim 1 of the main request, differing in overcoming minor clarity objections which are no longer maintained.
5.3.2 The grounds (C.) do not give further reasons why this claim should involve an inventive step.
5.3.3 The board shares the view of the decision.
5.3.4 Therefore, claim 1 of this request is not inventive in the sense of Article 56 EPC.
5.4 Third and fourth auxiliary request
5.4.1 Claim 1 of these requests specify the kind of constraints (array word width, array length or format for packing) and that the constraints can be modified without the user manually editing the source code description or the intermediate data structure.
5.4.2 According to the decision (3., paragraph 2; 4., paragraph 2), these examples of constraints are disclosed in D1. Furthermore, D1 "clearly teaches" manipulating the binary trees without editing the source code file (3., paragraph 3).
5.4.3 According to the grounds (D., page 6, paragraph 4), D1 makes references to binary trees only in the context of the automated design method, e.g. in sections III. and IV of D1. Therefore, D1 does not disclose manual manipulation of the binary trees.
5.4.4 The board agrees with the examining division that the constraints specified in these claims are disclosed in D1. This is not contested in the grounds.
5.4.5 As to the feature "without manually editing ...", the board considers this to be an aim or an result to be achieved rather than a technical feature. The means for implementing this aim (i.e. a GUI, temporarily storing the values of the constraints and then automatically transforming/updating the intermediate data structure according to them) are already present in claim 1 of the main request.
5.4.6 As to the statement in the grounds that D1 makes references to binary trees only in the context of the automated design method, the board agrees with the appellant, but does not consider the idea of manually manipulating a data structure like a binary tree to be inventive.
5.4.7 Therefore, claim 1 of each of these requests is not inventive in the sense of Article 56 EPC.
6. Request for reimbursing the appeal fee
6.1 Rule 103(1)(a) EPC provides as preliminary requirement for the reimbursement of the appeal fee that the appeal is deemed allowable.
6.2 Since the appeal is not allowable for the afore-mentioned reasons, it follows that the request for the reimbursement of the appeal fee has to be rejected.
6.3 The board adds that the alleged procedural violations were not substantiated. According to the grounds (page 4, last paragraph to page 5, first paragraph), the decision contains "several broad statements about what is well-known without providing any evidence". This happened "on numerous occasions" (page 7, paragraph 3).
In fact, the appellant made general statements without pointing out any reasons in the decision where the examining division used a general knowledge for which evidence needed to be provided. The appealed decision gave a technical interpretation of D1 with its own understanding of the technical field at variance with the appellant's interpretation, but this is a matter of substantive merits and not of procedural violation. The appellant had the possibility in its appeal to dispute the examining division's findings.
6.4 According to the grounds (page 6, paragraphs 5, 6; page 7, paragraph 3), the decision presented new arguments in relation to the third and fourth auxiliary request without giving the applicant an opportunity to respond.
6.5 The alleged new line of argumentation, set out only in the written decision, in fact amounts to explanations given by the examining division about the features of D1. That the appellant does not agree with this interpretation, again, is not a matter of a violation of the right to be heard, but a final assessment of the prior art, preliminarily discussed during the oral proceedings. The minutes in this respect give a summary of what was discussed, they did not have to expand the different steps of the reasoning given in writing later (see for instance T437/98, section 43.). The present case is not comparable to T1123/04 quoted by the appellant where in particular the examining division gave no reasoning why the objection pertaining to lack of inventive step against the former set of claims would apply to the new set of claims.
6.6 Thus, the board considers the decision to be reasoned and the right to be heard to have been fulfilled.
For these reasons it is decided that:
1) The appeal is dismissed.
2) The request for reimbursement of the appeal fee is rejected.