T 2110/14 (Optimizing translation lookaside buffer entries / QUALCOMM … of 4.6.2020

Summary of Facts and Submissions

I. This appeal is against the decision of the examining division to refuse the European patent application No.06739038.5 pursuant to Article 97(2) EPC on the grounds of lack of novelty and lack of inventive step (Articles 54 and 56 EPC).

II. In this decision reference is made inter alia to the following document:

US2004/0117594 (D1)

III. In the statement setting out the grounds of appeal, the appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of the refused main request or one of auxiliary requests 1 and 2, all re-filed with the grounds of appeal.

IV. In a communication accompanying the summons to oral proceedings, the Board set out its preliminary opinion that the invention seemed to be novel (Article 54 EPC), but not to involve an inventive step (Article 56 EPC).

V. In a reply, the appellant filed arguments in favour of inventive step.

VI. Oral proceedings took place on 4 June 2020 by videoconference. At the oral proceedings, during a discussion about novelty and inventive step, the appellant filed two additional main requests by email. The one filed first was headed "main request", whereas the one filed thereafter was headed "new main request".

The Board concluded that the subject-matter of claim 1 of the latter request, referred to as the new main request, involved an inventive step and that the claims complied with the requirements of Article 123(2) EPC.

VII. Independent claim 1 of the new main request reads as follows:

"1. A processing system (100), comprising:

a translation lookaside buffer, TLB, (108) comprising an existing entry mapping a first page address of virtual memory to a first page address of physical memory (104), the entry further comprising a size attribute (206) indicating the size of the page of virtual memory; and

a processor (102) configured to: consolidate the existing entry with a proposed entry into a single larger entry having a corresponding size attribute, wherein the consolidating comprises checking the proposed entry for contiguity against the existing entry in response to a TLB miss, the checking comprising:

first, comparing most and least significant bit portions of the first page address of virtual memory to a corresponding portion of a second page address of virtual memory of the proposed entry;

second, comparing most and least significant bit portions of the first page address of physical memory to a corresponding portion of a second page address of physical memory of the proposed entry;

third, checking that the second page address of virtual memory and the second page address of physical memory are both either higher or lower than the first page address of virtual memory and the first page address of physical memory respectively;

fourth, checking that virtual and physical address ranges covered by the larger single entry are aligned on the boundary for the size of the larger single entry."

Reasons for the Decision

1. Background of the invention

1.1 The invention relates to translation lookaside buffers (TLBs) which are relatively small, high-speed caches that map the most often used virtual memory page addresses to their corresponding page addresses in physical memory. Commonly, each TLB entry maps one virtual memory page address to one page in physical memory. The number of addresses that can be represented by each TLB entry is limited, see paragraphs [0003] and [0004] of the application. When a processor needs to access memory, it searches the TLB for a virtual memory page address. If it finds one ("TLB hit"), it retrieves the corresponding physical memory page address and provides it to memory over the address bus. If it does not ("TLB miss"), it uses known processing functions to determine the physical memory page address, see paragraph [0017]. A new TLB entry may be created to handle future access to the same physical memory page.

1.2 The invention provides a more efficient approach which optimises TLB entries by consolidating page entries that happen to be next to each other, i.e. contiguous, into a single TLB entry, see paragraph [0004]. As shown in Figure 3, a TLB entry comprises a size attribute, indicating the number of pages represented by the TLB entry, a virtual page address (X1, Y1) and the corresponding physical memory page address (A1, B1). The virtual page address has a most-significant bit portion (X1), bits 31 to 13, and a least-significant bit (Y1), bit 12, while the physical page address has a most-significant bit portion (A1) and a least-significant bit (B1), see paragraph [0020]. Bits 11 to 0correspond to the offset of the addresses within the page and are not part of the TLB entry.

1.3 Before creating a new TLB entry after a TLB miss, the processor checks whether the proposed entry can be consolidated with an existing entry [0019]. Four conditions apply [0022]. First, the virtual memory page addresses of the proposed and the existing entry must be contiguous in virtual memory address space (X1=X2), second, the physical memory page addresses must be contiguous as well (A1=A2). In a third step, it is checked whether the proposed entry's virtual and physical memory page addresses are both either higher or lower than the existing entry's virtual and physical memory page addresses, respectively. In a fourth step, it is checked whether the virtual and physical page address ranges covered by the larger entry are aligned on the large size boundary. All four conditions must be met for consolidating the existing and proposed entries into a single TLB entry. After having consolidated the entries, the page size, which has increased by the consolidated entry, is updated.

2. Article 54 and 56 EPC

2.1 The Board agrees with the appellant that claim 1 of the refused main request is novel over D1, because D1 fails to disclose the feature "the processor is further configured to vary the size of the contiguous block of virtual memory by consolidating a first block of virtual memory with a second block of virtual memory when a translation lookaside buffer miss occurs and in response to a determination that both the first and second blocks of virtual memory are contiguous, and the corresponding physical memory is also contiguous".

2.2 This feature defines two conditions which must be met prior to the consolidation of a first and second block of virtual memory. The first condition being that the test is made at a translation lookaside buffer miss and the second condition being that the first and second blocks of virtual and physical memory blocks are contiguous.

2.3 Claim 1 of the new main request, replacing the refused main request, has been amended to define the differen-tiating feature in more detail, namely, how an existing entry is consolidated with a proposed entry into a single larger TLB entry, having a corresponding size attribute, see paragraph [0022] of the application, and the above-mentioned four conditions that must be met for consolidation. Importantly, the claimed method still attempts to consolidate a proposed entry with an existing entry at each TLB miss.

2.4 According to Article 111(1) EPC the Board may exercise any power within the competence of the examining division (which was responsible for the decision under appeal) or remit the case to that department for further prosecution. It is thus at the Board's discretion whether it examines and decides the case or whether it remits the case to the department of first instance. In the present case the Board is in a position to decide on the merits of the case.

2.5 D1 relates to a method for the management of memory resources with a TLB which dynamically translates the logical page number into a corresponding physical page number, see paragraph [0005]. It points out that entries in a TLB are limited, see paragraph [0006], page 1, right column first sentence, which may lead to the thrashing of memory, see paragraph [0016].

2.6 D1 also recognises that the problem of a limited number of TLB entries can be addressed by consolidating several TLB entries. This requires contiguous virtual and physical pages. In a situation, where the logical (i.e. virtual) pages and the corresponding physical pages are contiguous and, as a block, are aligned on a suitable logical boundary, see paragraph [0016], it is possible to employ larger page sizes, so that each translator [in the TLB] is able to map a significantly larger portion of the logical address space. It is then possible to use the same offset in the respective TLB entry, see paragraph [0039], last 8 lines.

2.7 As explained above, this is the principle behind the present invention. However, D1 employs a specifically allocated memory area of physical memory, called staging page, see [0039] of D1, into which the physical pages are copied. They are rendered contiguous by virtue of being moved into the paging area. This technique is called "clustering" in D1, paragraph [0036] to [0039]. A pre-condition of the clustering is that the virtual pages are contiguous prior to clustering.

2.8 The Board accepts the appellant's argument that the examples in D1 show that clustering is performed only when the TLB has reached its limits. Figures 7 to 11 illustrate that clustering is performed when a fourth entry is to be included in the TLB, which, in the examples given, can only accommodate a maximum of four translators, see paragraph [0011], but in a real system would be larger. D1 does not seem to exclude the possibility of naturally occurring contiguous blocks of physical pages in memory, but the clustering technique does not explicitly recognise this and take advantage of them.

2.9 The invention according to claim 1, on the other hand, takes advantage of "naturally" occurring contiguous physical pages each time a TLB miss occurs. Before a proposed new entry is added to the TLB, it is checked for contiguity with an existing entry according to the above mentioned four conditions (see point 1.3). The invention therefore operates at each TLB miss and attempts to consolidate two TLB entries, whereas D1 attempts always to consolidate all TLB entries.

2.10 In the Board's view, the inventiveness of the distin-guishing feature boils down to two questions. Firstly, whether the person skilled in the art would apply the D1 clustering technique irrespective of the status of the physical pages, that is, whether they are already contiguous or not, and, secondly, whether it would limit clustering to two TLB entries.

2.11 The skilled person considering D1 might include a check about the status of the physical pages prior to copying them to the staging page, which could render the copying process more efficient because blocks of contiguous pages could be copied. However, in a situation when clustering is performed once a TLB has reached its limits, it is rather unlikely that the respective physical pages are contiguous. A test for contiguity is therefore unlikely to bring any increase in efficiency. The person skilled in the art would probably rather adapt the cluster size N to render the use of the staging page more efficient.

2.12 D1 does disclose at paragraph [0036] that the clustering is attempted by the memory management process during the course of servicing not only each page fault, but also at each routine request for allocation of a memory block. However, clustering is performed for 2**(N) logical pages see paragraph [0018], lines 17 to 19, with N being an integer power of 2, paragraph [0020], last line. In the example given, the Board notes that the new clustering step, Figure 5, is performed once three of the logical pages, in a TLB of four possible entries, have already been mapped into the memory, see paragraph [0039], lines 15 to 20, and a fourth proposed entry is to be mapped. Clustering is therefore performed for 4 pages with N being 2.

2.13 The Board accepts the appellant's argument that the invention, according to claim 1, has the technical effect of a faster determination of the appropriate page size for TLB entries because a new proposed entry is checked for contiguity with an existing one at each TLB miss. The invention does not operate on page clusters, but on single pages. This allows the invention to take advantage of naturally occurring contiguous physical and virtual memory pages.

2.14 The Board cannot recognise any incentive for the person skilled in the art, when starting from D1, to limit the clustering technique to clusters of two pages and dispense with the staging page. It is therefore concluded that claim 1 involves an inventive step (Article 56 EPC) over D1.

Order

For these reasons it is decided that:

1. The decision under appeal is set aside.

2. The case is remitted to the examining division with the order to grant a patent on the basis of the new main request filed by email during the oral proceedings on 4 June 2020 and a description to be adapted thereto.