T 0835/10 (Array transformation/MENTOR GRAPHICS) 03-09-2014

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[2], A[9]) 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 amend­ment 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 con­straints 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.

5. Inventiveness

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 under­standing 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.