T 0386/12 (Multiprocessor delegation/MMAGIX) of 15.5.2015

European Case Law Identifier: ECLI:EP:BA:2015:T038612.20150515
Date of decision: 15 May 2015
Case number: T 0386/12
Application number: 03783831.5
IPC class: G06F 9/50
G06F 12/00
Language of proceedings: EN
Distribution: D
Download and more information:
Decision text in EN (PDF, 365.938K)
Documentation of the appeal procedure can be found in the Register
Bibliographic information is available in: EN
Versions: Unpublished
Title of application: APPARATUS, METHOD AND SYSTEM FOR A SYNCHRONICITY INDEPENDENT, RESOURCE DELEGATING, POWER AND INSTRUCTION OPTIMIZING PROCESSOR
Applicant name: MMagix Technology Limited
Opponent name: -
Board: 3.5.06
Headnote: -
Relevant legal provisions:
European Patent Convention 1973 Art 56
European Patent Convention 1973 Art 157
European Patent Convention 1973 Art 111(1)
European Patent Convention 1973 R 109
European Patent Convention R 137(4)
Keywords: Inventive step - after amendment (yes)
Lack of unity with originally claimed invention established (no)
Amended claims admissible under Rule 137(4) EPC (2007) (yes)
Remittal to the department of first instance - in view of statement by the examining division about unsearched subject matter (yes)
Catchwords:

-

Cited decisions:
-
Citing decisions:
-

Summary of Facts and Submissions

I. The appeal lies against the decision of the examining division, with reasons dated 30 September 2011, to refuse European patent application No. 03783831.5 for lack of an inventive step in view of, in particular, docu­ments

D3: EP 0 442 041 A2,

D4: EP 0 794 492 A2, and

D5: Verschueren A C et al., "Arbitration in a multi-processor to multi-coprocessor connection switch", Proc. of ProRISC 1999, 10th IEEE Annual Workshop on Circuits and Sys­tems and Signal Processing, STW, Technology Foundation, Utrecht, The Nether­lands, 1999, pages 563-567.

In its summons to oral proceedings, the exami­ning division had referred to a further relevant document:

D6: KR 2002 0020186 (published 14 March 2002) & US 6 829 697 (published 17 December 2004)

II. A notice of appeal was received on 8 December 2011, the appeal fee being paid on the same day. A statement of grounds of appeal was received on 10 February 2012. The appellant requested that the decision under appeal be set aside and that a patent be granted based on the claims according to the main request presently on file or, alterna­tively, according to claims according to one of the first to fifth auxiliary requests filed with the grounds of appeal. The further application documents on file are as follows:

description, pages

5-53 as originally filed

1-4, 54 as received with letter of 14 January 2009

drawings, sheets

1/29-29/29 as originally filed

A resumé of and a statement by the inventor Daniel O'Sullivan was attached to the grounds of appeal and it was requested that Mr. O'Sullivan be allowed to speak at the oral proceedings in the present case.

III. With its summons to oral proceedings, the board informed the appellant of its preliminary opinion, according to which the main request lacked clarity and an inventive step, Articles 84 and 56 EPC 1973, and the first auxil­ia­ry request was deficient under Articles 123(2) EPC and 84 EPC 1973, but the second and third auxiliary requests appeared to be allowable. The board however considered itself barred from ordering the grant of a patent, since the examining di­vision had stated that the claimed sub­ject matter had not been searched. The board there­fore indicated that it was minded to remit the case for fur­ther prosecution based on either the second or the third auxiliary request.

IV. In response to the summons, the appellant withdrew the main and first auxiliary requests and requested that the application be remitted to the department of first in­stance based on the second auxiliary request. In the ab­sence of any statement to the contrary, the board un­der­stands that the third to fifth auxiliary requests are maintained.

V. The oral proceedings were therefore cancelled.

VI. The sole independent claim 1 of the now highest-ranking second auxiliary request reads as follows:

"1. A method of execution-instruction delegation among multiple elemental processing resources of at least two different types, the multiple elemental processing resources comprising two or more elemental processing resources of a first type each sharing two or more elemental processing resources of a second type with at least one other of the two or more processing resources of the first type, and multiple program threads stored in memory accessible by the multiple elemental processing resources of the first type, the elemental processing resources of the first type each being configured to receive a program instruction from a thread in memory, the elemental processing resources of the second type having pipelines associated therewith and being configured to only receive and execute instructions that were delegated to their pipeline for execution by processing resources of the first type and by being shared by at least two elemental processing resources of the first type, the method comprising:

obtaining an execution instruction from the thread, wherein the execution instruction is obtained at one of the at least two elemental processing resources of the first type;

determining whether an operation-code within the execution instruction is incapable of being executed by the one elemental processing resource of the first type and thus should be delegated to an other [sic] elemental processing resource of the second type shared by the at least two processing resources of the first type;

executing the execution instruction within the first elemental processing resources of the first type, if the operation-code within the execution instruction should not be delegated to any other elemental processing resource;

if the execution instruction should be delegated, providing a specific elemental processing resource of the first type access to a specific elemental processing resource of the second type that it shares with another of the elemental processing resources of the first type based upon an arbitration request by the specific elemental processing resource of the first type; and

routing the execution instruction and an identifier for the specific elemental processing resource of the first type that delegated the execution instruction to a pipeline of the shared specific elemental processing resource of the second type that is capable of executing the operation code, if the operation-code within the execution instruction is to be delegated;

further comprising causing the delegating processing resource to sleep, and

broadcasting the result of executing the delegated instruction to each of the plurality of processing resources of the first type on shared result buses 144, 146, 148,

wherein each sleeping processing resource is arranged to look at the shared result buses for its identifier, and

when a match is detected, the processing resource wakes up from sleep to process the broadcast result."

VII. In view of the board's decision, the wording of the claims according to the third to fifth requests maintained by the appellant are immaterial.

Reasons for the Decision

The invention

1. The application proposes a microprocessor architecture which provides a variable number of specialised, so-called "elemental" processing units (in particular "in­teger processing units" IPUs, "mathematical pro­cessing units" MPUs and caches) and "intra-chip net­working" fa­cilities (see e.g. p. 12, lines 6-7), and a delega­tion scheme between the processing units. The specia­lised units determine when they cannot service a par­ti­cular instruction themselves and, if so, delegate that in­struc­t­ion to another unit (p. 12, lines 7-10; see also p. 30f. and esp. p. 30, lines 10-12). The pro­cessors provide pipelines for the incoming delega­tion requests (see e.g. fig. 3, and p. 16, 2nd para. - p. 17, 3rd para.). With a de­legation request, the requesting pro­cessor sends its identifier (p. 30, last para.); this identifier is used to mark the returned result so that the reques­ting pro­cessor can detect it when broadcast on a shared result bus. The requesting processor goes to "sleep" while wai­ting for the delegated instruction to return (p. 26, 2nd para. - p. 29, 1st para.).

Admitting the second auxiliary request, Article 12(4) RPBA and Rule 137(4) EPC (2007)

2. In the present case, a supplementary European search re­port under Article 157(2) EPC 1973 was carried out, based on claims amended under Rule 109 EPC 1973. As the supplementary European search report was transmitted on 12 Feb­ru­ary 2008, i.e. after the entry into force of EPC 2000, but before the entry into force of the further amen­d­ed Rule 137 EPC on 1 April 2010, the appli­cable regula­tion is Rule 137 EPC (2007) according to the per­ti­nent transitional provisions (see Article 1 of the Decision of the Administrative Council of 28 June 2001 on the transitional provisions under Article 7 of the Act revi­sing the EPC of 29 November 2000, Special edi­tion No. 4 OJ EPO 2007, 219; Article 2 of the Deci­sion of the Admi­nistrative Council of 7 December 2006 amen­ding the Im­ple­menting Regulations to the EPC 2000, Spe­cial edition No. 1 OJ EPO, 2007, 89; and Article 2(2) of the Decision of the Administrative Council of 25 March 2009 amending the Implementing Regulations to the Euro­pe­an Patent Con­ven­tion, OJ 2009, 299).

3. In the minutes of a telephone conversation, dated 18 Au­gust 2011, which was held on 11 August 2011 in prepa­ra­tion of the oral proceedings­­, it is noted that claim 14 "appear[ed] prima facie to relate to un­searched subject matter which is not unitary with the original claimed invention and therefore not allowable, Rule 137(5)". This statement is indicated as having been made "merely academi­cally", is not fur­ther rea­soned and does not specify which features or feature combinations in particular were considered to constitute unsearched subject matter. Moreover, the decision itself does not contain a corresponding objection, let alone any rea­so­ning in this regard.

4. The board has no reason to doubt that claim 14 lacks unity with the originally claimed invention.

4.1 The board considers that the mention in Rule 137(4) EPC (2007) - corresponding to Rule 137(5) EPC, second sen­tence - to "unsearched subject-matter" must be con­strued as referring to the subject matter covered by the Euro­pe­an search report. Therefore, the "origi­nally claimed invention or group of inventions" mentioned in that Rule must also be that on which the European search re­port is based. In the present case, the supplementary European search report takes the place of the European search report pursuant to Ar­ticle 157(1) EPC 1973.

4.2 Amongst the claims covered by the supplementary European search report, claims 7 and 8 already contained the transmission of the iden­ti­fier of the delegating pro­cessing resource, the IPU, and claim 15 spe­cified that the delegating processor might go to "sleep" waiting for the result.

4.3 The board is hence satisfied that the independent claims of the present second auxiliary request are unitary with the originally claimed invention and thus concludes­ that Rule 137(4) EPC (2007) does not preclude admittance of the second auxiliary request.

5. Independent claim 1 of the present highest-ranking se­cond auxiliary request limits independent claim 1 as re­fused by fea­tures specifying what the identifier of the delegating processor is meant to be used for and how it is used to direct the result to the right processor. The board therefore considers that the amendments made in the second auxiliary request address the main issue of controversy vis-à-vis the decision under appeal, name­­ly the inventive merit of transmitting ("routing") the iden­ti­fier of the delegating processor with the de­le­ga­tion request. Therefore, the board has no doubt that the claims of the second auxiliary request should be ad­mitted, pursuant to Article 12(4) RPBA.

6. In view of the present decision, the board need not address whether any of the further requests are to be admitted. In par­ti­cular, the board need not address the doubts about the admissibility of the fourth and fifth auxiliary requests, which it expressed in the annex to its summons to oral proceedings (point 7.2).

The prior art

7. D5 discloses a multi-processor in which a number of "pro­cessor cores" share a number of coprocessors. Work to be delegated from the former to the latter is dis­tri­­buted via an on-chip "command switch network", and results are returned via a corresponding "result switch network" (see fig. 1). Processor cores may have to wait for a free coprocessor to handle an instruction (p. 564, right col., pen­ult. para.). To this end, the copro­cessors provide pipelines (para. bridging pp. 564 and 565) to hold incoming requests. A command delegated to a coprocessor of suitable "type" contains an indica­tion of the initia­ting task (p. 564, left col., 2nd para.; p. 565, right col., 1st para.; p. 566, right col., last para.). When the coprocessor returns its result, which processor, if any, is running the perti­nent task is deter­­mined and the result transmitted to that processor (loc. cit.). If, however, the task is not running at this point, the result is redirected to the register set cache storing the environments of non-running tasks (see p. 564, left col., 2nd and 4th para., and p. 567, left col., 1st para.).

8. D3 discloses a special purpose "integrated [dual-pro­cessor] processing platform" for use in digital commu­nication systems such as a fax machine (see p. 1, lines 1-3 and 29-37; p. 2, lines 31-33). This platform inte­grates one general purpose processor (GPP) with one specia­­­lized digital signal processor (DSP; see fig. 2), to which the GPP may delegate the execution of certain ope­ra­tions (see p. 5, lines 27-30 and 36-38). When this happens, the DSP places the GPP in a "continuous wait state" and, upon completion, the DSP cancels the wait state for the GPP to continue execution (see p. 5, lines 43-49).

9. D4 discloses a multiprocessor system in which any one of several CPUs (fig. 1, no. 20-23; col 5. lines 1-14) can delegate in­structions to another one. The two CPUs involved are referred to as, respectively, the host CPU and the slave CPU (col. 8, lines 18-23). It is disclosed that the host CPU "instructs the slave to begin execution [...] while suspending its own execution of the task" and, "on receipt of the comple­tion signal triggered by the slave [...] resumes conventional exe­cution of the suspen­ded thread" (col. 4, lines 10-23).

10. The Korean and the US patent application jointly intro­duced above as "D6" claim priority of the same earlier application. Although only the Korean document is prior art for the present application, this decision will cite only passages of the post-published US document, on the assumption that the two documents share the relevant disclosure. In view of the outcome of this decision, the accuracy of this assumption need not be ascertained.

D6 discloses an embedded network processor complex con­taining one or more protocol processor units (PPU; see col. 1, lines 7-9 and 16-18). Each PPU contains one or more "core language processors" (CLP), each of which ha­ving "multiple code threads" and "a plurality of co­pro­cessors for executing specific [net­working] tasks for the PPU" (see col. 1, lines 61-66; col. 2, lines 45-50). Each coprocessor is iden­ti­fied by an ID within the PPU (col. 11, lines 8-9). For each coprocessor a bit in a "busy signal field" is pro­vi­ded to indicate whether the copro­cessor is busy or available (col. 12, lines 22-25; col. 13, lines 63-66). Each CLP may dele­gate command execu­tion to any of the copro­cessors (see col. 6, lines 23-26). After initiating a task in a copro­cessor, the CLP may either continue exe­cution of instructions in parallel with the copro­cessor, in par­ticular another thread (see col. 4, lines 16-19; col. 6, lines 45-46; col. 15, line 63 - col. 16, line 1; col. 17, lines 4-6 and 21-24), or a WAIT instruction may cause it to stall the execu­tion of further instructions until the comple­tion of the task on one more co­pro­cessors (see col. 4, lines 19-21; col. 13, lines 35-47). When the task com­pletes, the copro­cessor pro­vides a one-bit return code to the CLP to indi­cate whether the delegated task was successful or failed and deactivates its busy signal bit (col. 13, lines 63-66). The CLP polls this busy signal and when the selected coprocessor terminates it uses the return code to decide whether and with which instruction to re­sume execution (see col. 12, lines 27-33; col. 13, lines 47-54).

The issue at stake

11. The decision under appeal (reasons 2.2) identified as the only difference between the subject matter of then claim 1 and D5 that along with the delegation request an iden­tifier of the delegating elemental processing re­source is sent instead of an identi­fier of the task. The decision (reasons 2.3) finds this to be a "simple work­bench alternative" to the solution of D5 and further con­siders that D5 points to this so­lu­tion because "in the absence of a task stall [...] informa­tion concerning the task is actually information con­cer­ning the pro­cessor". The skilled person would there­fore, according to this argument (reasons 2.4), "routinely vary the teaching of D5" in a way which "achieves the same goals as D5 and moreover deals with task stalls as well", so that the claimed invention lacked an inventive step. With regard to then claim 14, the examining division re­marked in an obiter dictum (reasons 3) that the added fea­tures, in parti­cular the "sleep state of the delega­ting processor" and the "reading of the result", related to trivial de­tails which were well-known in the art, reference being made to D3 (p. 5, lines 43-52) and D4 (col. 4, lines 10-23). In the summons to oral procee­dings (point 3.2) the examining division had further expressed the opinion that the sleep state is a standard energy-saving option which was also known "from the iden­tical context of D6; see column 10, lines 54-65, and col. 13, lines 35-43."

12. The appellant disagrees that the difference is a mere "workbench alternative" (grounds of appeal, p. 2, 1st para.). In D5, results could not be re­turned to the same processor that ran the delegating task at the point of delegation, because that task might not run anymore or might run on a different processor. Hence, D5 required an "arbitration scheme" for locating the pertinent task and some associated hardware (p. 2, 2nd para.). Accor­ding to the invention, however, the result was to be returned to the delegating processor. As a consequence, the pro­cessor architecture according to the invention could be much simplified. To enable this, the delegating processor had to "sleep" until the required result be­came available (p. 2, 3rd para. - p. 3, 1st para.). The claimed invention was inventive over D5 because the skilled person "would have to ignore much of the focus of D5 and throw out an extensive portion of the hardware and arbitration scheme, in essence re­inventing what is proposed in D5 in a very different way" (p. 3, 2nd para.).

Inventive step of the second auxiliary request,

Article 56 EPC 1973

13. Claim 1 of the second auxiliary request, amended over claim 1 as subject to the refusal, differs from D5 in that

i) the identifier of the delegating elemental pro­cessing unit (rather than the identifier of the task) is routed to the shared elemental processing resource to which an operation is delegated;

ii) the delegating processor is put to sleep;

iii) the processing result is broadcast to all elemental processing units of the first type on a shared result bus; and

iv) each of the sleeping processors looks at this bus for its identifiers and wakes up in case of a match.

13.1 The idea to put all delegating processors to sleep until the respective result arrives (in particular difference features i) and iv)) simpli­fies the control of the dele­gation-based archi­tec­ture of D5, albeit at the cost of a loss of paralle­lism, because a sleeping pro­cessor cannot pro­cess other tasks while waiting for its re­sult. The claimed invention makes a different trade-off between simplicity and speed than D5.

13.2 The board thus considers that the claimed inven­tion by virtue of difference features i) to iv) repre­sents an alternative solution to the prob­lem addressed in D5, name­ly to provide "scalable (multi-)pro­­cessor power on a single chip" (see intro­duction, 1st para.).

13.3 However, the board also considers that the claimed in­vention goes beyond a mere "work­shop alternative" of D5 which would be obvious per se or from common knowledge in the art. The board agrees with the appellant that D5 does not contain any explicit or implicit prompt to modify D5 towards the invention. In particular, the fact mentioned by the examining divi­sion that the task identi­fier according to D5 constitutes "infor­ma­tion concer­ning the processor" if tasks do not "stall" is no such prompt, simply because D5 explicitly dis­clo­ses that a task may stop running on the delega­ting pro­cessor. That is, the task identifier of D5 is insuffi­cient in general to iden­ti­fy the delegating processor and the identifier of the delegating processor would normally not suffice to identify the pertinent task­­. D5 does not disclose or suggest to tie the delegating task to its processor while the de­le­­gated instruction is exe­cuted.

13.4 The board also agrees with the appellant that the idea of putting all delegating processors systematically to sleep would defeat the purpose of the elaborate parallel archi­tecture of D5.

13.5 The board therefore concludes that the subject matter of the independent claims according to the se­cond auxiliary request solve the problem mentioned above in a manner which is not obvious from D5 alone.

14. The board agrees with the examining division that the con­cept of putting a processor to sleep, i.e. difference feature ii) alone, is a commonly known measure to reduce the energy consumption of an idle processor.

14.1 The board takes D3 as an illustration of this idea, be­cause the GPP which is put to sleep during delegation to the DSP is idle anyway.

14.2 However, modifying the system of D5 based on this gene­ral concept would not yield the claimed invention. In par­ti­cular, the option might be provided to put to sleep an idle processor core without making the sleep state ob­li­gatory for all delegating processors.

14.3 The board therefore considers that the common knowledge about processor sleep states is insufficient to suggest the incorporation of the difference features into the system of D5, ­in particular difference feature ii). The board considers D3 insufficient for sub­stan­­tially the same reason.

15. D4 discloses (loc. cit.) that the host CPU may suspend and resume execution of a task or thread (see col. 4, lines 10-23). However, this statement does not imply that the CPU as a whole is put to sleep. In contrast, D4 explicitly discloses that "[t]he host CPU may execute other threads which may be present" (col. 10, lines 44-47). D4 thus does not disclose the difference fea­tures ii) or iv); in fact, D4 discloses none of diffe­rence features i) to iv).

16. As regards difference feature ii), D6 is the most pertinent piece of prior art on file. In particular, D6 dis­­closes the delegation of tasks by one of several multi-threaded CLPs to one of several coprocessors and suggests in this context explicitly that the delegating processor might be put to sleep.

16.1 However, even in D6 the delegating processor may or may not be put to sleep. As already argued above, an optional sleep state could be integrated into D5 without changing much else of the architecture according to D5. In particular, this change would not imply the routing of the processor identifier (difference feature i)) instead of the task identifier.

16.2 Moreover, even if arguendo the skilled person were to consider in view of D6 to put all delegating processors to sleep (difference feature ii)), this would not yield the claimed invention. D6 dis­closes its own elaborate way of communication between the CLPs and the copro­cessors, based on busy signal field, OK/K.O. field, and a parti­cu­lar WAIT instruction, which does not require the rou­ting of processor identifiers (difference feature i)) or a shared result bus (difference features iii) or iv)).

17. The board therefore concludes that the subject matter of claim 1 shows the required inventive step over D5, alone or in combination with any of D3, D4, D6 or the common knowledge in the art, Article 56 EPC 1973.

18. In view of this decision and the fact that it was arrived at without holding oral proceedings, the appellant's request to hear Mr. O'Sullivan as an expert at the oral proceedings has become moot.

Scope of the search and remittal to the first instance, Article 111(1) EPC 1973

19. As mentioned above (point 3), the examining division expressed the opinion that the subject-matter of claim 14 as filed on 8 August 2011 (and as subject to the refusal) related to unsearched subject matter.

19.1 The fact that the decision under appeal did reproduce this opinion, let alone rely on it, does not imply that the examining division changed its mind on this point. Rather, the minutes of the telephone con­versation of 11 August 2011 ("[m]erely academically") seem to suggest that the examining division considered only that the reasons for the refusal did not depend on this fact.

19.2 Independent claim 1 of the present se­cond auxiliary re­quest comprises features corresponding to sub­stan­tially all features of claim 14 as refused (consi­dering ­the fact that the latter is a system claim and the for­mer a method claim), and in particular both claims share the fea­ture that the delegating pro­cessor is put to sleep while the delegated in­struction is executed (difference feature ii)). In fact, present claim 1 is more limited than former claim 1 due to difference features iii) and iv)). Therefore, the board cannot exclude the possibi­li­ty that the examining divi­sion would have also consi­dered present claim 1 to re­late to unsearched subject-matter.

19.3 A patent cannot be granted based on subject-matter which has not been searched. Therefore, the board cannot remit the case to the department of first instance with an order to grant, but has to remit it for further prosecu­tion, during which the examining division has to estab­lish whether the subject-matter of the present second auxiliary request was searched and, if not, to have an additio­nal search performed.

Order

For these reasons it is decided that:

1. The decision under appeal is set aside.

2. The case is remitted to the department of first instance for further prosecution.

Quick Navigation