T 1139/15 (Lock acquisition based on deterministic progress index/SAMSUNG) of 16.1.2018

Summary of Facts and Submissions

I. The appeal is against the decision of the examining division, with reasons dispatched on 9 March 2015, to refuse European patent application No. 11 174 341.5. The decision was delivered as a so-called "decision on the state of the file" and, for its reasons, referred to the summons to oral proceedings before the examining division, which had raised objections under Articles 83 and 84 EPC.

II. A notice of appeal was filed on 15 May 2015 along with the statement of grounds of appeal, the appeal fee being paid on the same day. The appellant requested that the decision be set aside and that a patent be granted on the basis of application documents on file, i.e. claims 1-15 and description page 1 as filed on 13 September 2012, in combination with description pages 2-23 and drawing sheets 1-14 as originally filed.

III. By way of an annex to the summons to oral proceedings, the board informed the appellant of its preliminary opinion that the decision would have to be confirmed on both grounds, Articles 83 and 84 EPC.

IV. In response to the summons, by letter dated 12 December 2017, the appellant replaced the pending sets of claims by amended claims 1-15 according to a main and two auxiliary requests.

V. Claim 1 of the main request reads as follows:

"A lock controlling apparatus, based on a deterministic progress index, DPI, the apparatus comprising:

a core DPI generator (510) adapted to generate a core DPI by accumulating thread DPIs of a predetermined thread group executed in the core, wherein the DPI of a thread indicates only a time of execution of a deterministic section of the thread;

a loading unit (530) adapted to load (1010, 1020) a DPI of a first core and a DPI of a second core among DPIs of a plurality of cores at a lock acquisition point in time of each thread, the first core for reference and the second core corresponding to a neighbor core;

a comparison unit (540) adapted to compare (1030) the DPI of the first core and the DPI of the second core; and

a controller (550) adapted to assign (1080) a lock to a thread of the first core when the DPI of the first core is less than the DPI of the second core and when the second core corresponds to a last core to be compared."

Claim 1 of auxiliary request 1 is identical to claim 1 of the main request, except that the phrase explaining the DPI reads as follows:

"... wherein the DPI of a thread indicates only a time of execution of a deterministic section of the thread, wherein the execution of the thread includes the deterministic section and a non-deterministic section; ..."

Claim 1 of auxiliary request 2 further clarifies that the DPI is "measured and stored". All differences over claim 1 of the main request are in the paragraph defining the "core DPI generator", which now reads as follows:

"... a core DPI generator (510) adapted to generate a core DPI by accumulating thread DPIs of a predetermined thread group executed in the core, wherein the DPI of a thread indicates only a time of execution of a deterministic section of the thread; ..."

VI. The oral proceedings were held on 16 October 2018. At their end, the chairman announced the board's decision.

Reasons for the Decision

The invention

1. The application relates to the scheduling of multiple threads in a multi-processor (or multi-core) environment (see paragraphs 3 and 30). More specifically, the application proposes a way of selecting which thread will be "assigned" a lock protecting a "critical section", such as the access to a shared memory (see the black boxes in figures 4A, 4B and 6, and paragraph 35 of the description).

1.1 The proposed method relies centrally on a so-called "deterministic progress index" DPI, which is said to "measur[e] the progress state" of each thread and the accumulated "progress" of all threads executing in each core (see e.g. paragraphs 31 and 57).

1.2 In fact, the DPI is only meant to "indicate" the "deterministically executed, that is predictable execution period" (see paragraph 76); hence "D"PI. It is disclosed that the instructions of each thread may belong either to a "deterministic execution scheme" or to a "non-deterministic execution" scheme, and it is suggested that an instruction, or instruction group, may belong to the deterministic execution scheme if its execution has a "regular cycle", and to the non-deterministic execution scheme if it has an "irregular cycle" (see paragraph 30). The meaning of terms "regular cycle" and "irregular cycle" in the given context is not further defined. In the figures 4A, 4B and 6, the "deterministic" sections of each thread are indicated as white regions, the "non-deterministic" ones as hatched ones.

1.3 The DPI can be generated "using" what is called a "deterministic progress counter (DPC)". The DPC itself may possibly constitute the DPI (see paragraphs 31 and 58, last sentence). The DPC may be "suspend[ed]" when a "scheduling event occurs" in the running thread, which indicates that "a non-deterministic execution is performed". "Scheduler events" may "include an input/output waiting, a non-deterministic function call, and the like" (see paragraphs 92).

1.4 When a thread requests a lock (see double hatched regions in figures 4A, 4B and 6) it is blocked until the lock is assigned to it. When, at that point, another thread (on the same core) has a smaller DPI, the former thread may "yield execution" to the latter thread until, eventually, both may "request [...] lock acquisition" (see e.g. page 11, lines 9-13). It would seem that the first thread may, in this case, have to request the lock acquisition again (see paragraph 51, page 11, last two lines).

Clarity, Article 84 EPC

2. Claim 1 of the main request specifies that "the DPI of a thread indicates only a time of execution of a deterministic section of the thread". Claim 1 of auxiliary request 1 adds that a thread may have a "deterministic" and a "non-deterministic section", and claim 1 of auxiliary request 2 adds in particular that it is "measured".

2.1 The board agrees with the examining division that the term "DPI" has no established meaning in the art, and the appellant did not point out any. The board also considers that the term is insufficiently descriptive to imply a clear meaning on its own. While it is clear that the DPI is a value (an "index") representing the "deterministic progress" of a thread (or a core), the term "progress" is ambiguous (in principle, it could relate to how much of a thread has already been executed or to how much there is left to execute; see below) and it is a priori unclear what "deterministic progress" means.

2.2 Claim 1 of all requests attempts to define the DPI by reference to a "deterministic section" of a thread and its "time of execution". Also the term "deterministic section" does not, in the board's view, have an established meaning in the art. A common use of the term "deterministic", when applied to programs (as are defined by the claimed threads), is that the program produces the same result whenever it is executed. In this sense, the skilled person would normally understand a "deterministic section" of a thread to be one which produces a deterministic, i.e. reproducible result. This is not, however, the intended meaning of the term, as the application seems to call "deterministic" a "section" of a thread which has a "predictable" execution time. These notions are actually different - for example a function producing a random number will be non-deterministic in the former sense but will need the same execution time whenever called, i.e. it will be "deterministic" in the latter sense - but the claim lacks an indication as to which is the intended meaning.

2.3 The board therefore considers that the term "deterministic section of a thread" is at least ambiguous, and thus unclear.

2.4 During oral proceedings, the appellant indicated its willingness to limit the reference to the "time of execution of a deterministic section of a thread" to a "time of deterministic execution of a deterministic section of a thread" (and similarly, in the auxiliary requests, for the non-deterministic section). The board however considers that the term "deterministic execution" is ambiguous in the same way as "deterministic section" so that the amendment would not overcome the objection. Knowing that, the representative refrained from filing correspondingly amended claims.

3. Even if, for the sake of argument, the board assumed it to be clear that the "deterministic section of a thread" is one with a somehow "predictable execution period" (see paragraph 76), it would remain unclear what precisely this means for the claimed lock controlling apparatus.

3.1 Firstly, the board notes that only claim 1 of auxiliary request 2 specifies a "measurement unit" measuring the "DPI of a thread". However, even this claim 1 does not specify how the measurement unit "measures" the DPI, so it "indicates only a time of execution of a deterministic section of [a] thread". It may be assumed, but is not claimed, that the unit will have to distinguish the "deterministic section" from the "non-deterministic section". It is not detailed in the claims (or the description), how it does this.

3.2 Secondly, it is not clear from the claim language whether the "DPI of a thread" will, once computed, remain fixed for each thread or will represent, at any point in time, a measure of "time" a thread has spent on its "deterministic section" after its last suspension. Although the mention in the description of the "progress state of a thread" might suggest the latter (see paragraph 31, but also paragraph 49, page 11, line 8, indicating that a DPI will occasionally be reset to 0), the description also refers to four threads as having "the same DPI size", even though with two cores only two of them can execute at any given point in time (see paragraph 49, page 10, last two lines; and figure 4A).

4. During the oral proceedings, the board tried to gain an understanding of the invention as a whole, especially as it appears in the claims, in an attempt to understand the DPI and the "deterministic sections" via the intended effect of using it for thread scheduling. A number of central issues, however, could not be clarified.

4.1 Claim 1 refers to several cores (a "first", "second" and possibly more cores, since the "second core" may not the "last" one) and threads executing in the cores but lacks several other details. For instance, claim 1 fails to specify whether the number of threads per core is fixed or not, and whether thread execution involves iteration or whether threads will be executed more than once. The first question arose during the oral proceedings in the context of figure 4B, which shows a situation in which core 1 does not wait when thread 1 requests the lock, but waits when thread 2 also requests the lock (see especially item number 430). Instead of waiting, it seems that core 1 could just as well have switched to a further thread "5". As regards the second question, it is noted that the measurement of the past execution time of a thread seems to be immaterial for a thread that will be executed only once.

4.2 Claim 1 fails to define at which point in time the claimed "lock controlling apparatus" makes its decision as to which thread to assign a lock. Inter alia, it does not specify which threads of which cores must have requested lock acquisition before a decision is made. Claim 1 does not even require any such request to have taken place. Also, it seems reasonable to assume that it may happen that only threads of the second core have requested lock acquisition; if the first core happens to have a smaller DPI, claim 1 prescribes the assignment of the lock to "a thread of the first core" even though none of them has requested it.

4.3 Claim 1 leaves it open as to how a specific thread in the first core is selected to assign the lock. It is undefined whether, if only one thread has requested a lock, that thread is to be selected, and how, if several threads have requested a lock, a choice is made between them.

4.4 Finally, claim 1 leaves it open as to what happens to a thread which has requested but not been assigned a lock.

4.5 The board leaves open the issue as to whether any of these issues in themselves render the claims unclear. It does, however, conclude that the apparently intended use of the DPI for thread scheduling does not shed light on the meaning of DPI or "deterministic section of a thread".

5. The board thus finds that the term "deterministic section of a thread" is insufficient to clarify what the DPI represents, or how precisely it is "measured", and thus renders the subject-matter of claim 1 unclear, which thus does not comply with Article 84 EPC.

Order

For these reasons it is decided that:

The appeal is dismissed.