Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-5, 10-11, 13 and 16-20 are rejected under 35 U.S.C. 103 as being unpatentable over US Patent Application Publication No. US 2017/0293567 Al (Bryant), in view of US Patent Application Publication No. US 2016/0170884 A1 (Eddy), in further view of US Patent Application Publication No. US 2013/0151777 A1 (Daly).
Regarding claim 1 and analogous claim 17:
Bryant teaches a storage management apparatus ([Fig. 1]), comprising: at least one translation look-aside buffer ((30) [0039]), configured to store a plurality of cache entries, wherein the plurality of cache entries comprises a first plurality of level 1 cache entries (32) and a second plurality of level 2 cache entries (34) ([0039]), wherein the number of entries of the first plurality of level 1 cache entries is less than or equal to the number of entries of the second plurality of level 2 cache entries (“the L2 TLB 34 may include a greater number of entries 36 than the L1 TLB”), and the cache entry comprises auxiliary information including a size flag indicating a quantity of valid bits of a virtual address tag of the cache entry (see [Fig. 5] and the discussion in [0065] that each entry contains a size indicator identifying a page size for that entry. As can be seen in [Fig. 6], the size flag indicates how many of the bits entry are logically compared rather than ignored in a lookup to that entry (i.e., a quantity of valid bits of a virtual address tag) [Fig. 6] [0066]); an address translation unit coupled to the at least one translation look-aside buffer, and adapted to translate, based on at least one of the first plurality of level 1 cache entries and the second plurality of level 2 cache entries, a virtual address specified by a translation request into a corresponding translated address (the address calculating unit (60)/(90) combined with the TLB lookup circuit (62)/(92) and the hit detection circuitry shown in [Fig. 6], which takes the input VA from the store or load request and translates the VA into a PA (i.e., translates a virtual address into a corresponding translated address [Fig. 2]), wherein the address translation unit is further adapted to: determine whether a virtual page number of the virtual address is consistent with the virtual address tag based on comparison of the quantity of valid bits of the virtual address tag with an equal quantity, as the quantity indicated by the size flaq, of bits of the virtual page number, and translate the virtual address specified by the translation request into the corresponding translated address when the virtual page number of the virtual address is determined to be consistent with a virtual address tag of one of the first plurality of level 1 cache entries, thereby indicating one of the first plurality of level 1 cache entries being hit (as seen in [Fig. 6], only the relevant number of bits of the virtual address (i.e., corresponding to the virtual page number) are compared corresponding to the size of the page of the entry when looking up a virtual address and comparing it to entries in the TLB. For a 64k page, only bits 48:16 are compared, for a 16k page, bits [48:14] are compared, and for a 4k page, bits [48:12] are compared to determine whether an entry is present in the TLB. This is because for a 64k page, bits [15:0] correspond to the offset, for a 16k page, bits [13:0] correspond to the offset, and for a 4k page, bits [11:0] correspond to the offset [Fig. 6] [0066]. If a hit is generated, the stored PA is returned as the translated address from the TLB. As can be seen in [Fig. 7], the size of the PA corresponds with the size of the VA [Fig. 7]. The offset portion is mapped directly, while the virtual page address portion is mapped by the TLBs [0046]) or when the translation request does not hit any one of the first plurality of level 1 cache entries, translate, based on one of the second plurality of level 2 cache entries, the virtual address specified by the translation request into a corresponding translated address (by teaching that if the requested virtual address does not hit in the L1 TLB, it is translated with the L2 TLB [0040]), and a control unit, coupled to the address translation unit, and adapted to: when the first plurality of level 1 cache entries are not hit and one of the second plurality of level 2 cache entries is hit: select one of the first plurality of level 1 cache entries based on a preset algorithm and move the L2 TLB entry into the selected L1 TLB entry (by teaching the address calculation circuitry (60)/(90), TLB lookup circuitry (62)/(92), and the victim selection circuitry (200) that determines if the L1 TLB (32) does not contain the required entry it sends a request to the L2 TLB (34), which may then send the entry to the L1 TLB (32) if there is a hit in the L2 TLB (34) [0040]. One of the L1 TLB (32) entries may be selected for to be replaced with the entry with the L2 TLB (34) based on any known replacement algorithm [0040] [0057] [0059]).
Bryant does not teach, but Eddy teaches, to evict the selected one of the plurality of level 1 cache entries to the level 2 cache while promoting the hit level 2 cache entry (by teaching that a hit in the L2 cache when there is a miss in the L1 cache results in the entry in the L2 cache being promoted to the L1 cache [0036]. In this case, the L1 cache may evict an entry in the L1 cache to be stored in the L2 TLB [0037] (i.e. one entry is promoted and one is demoted. The eviction policy may be based on an least recently used (LRU) policy [0007]).
It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the L1 entry selected for replacement with the hit L2 entry as taught by Bryant to include being demoted to the L2 TLB while the hit L2 TLB entry is promoted to the L1 cache, where the demoted entry from the L1 TLB is demoted according to the LRU eviction policy as taught by Eddy.
One of ordinary skill in the art would have been motivated to make this modification because a page table walk is a costly operation compared to an access to an L1 or L2 TLB, and evicting/demoting the entry to the L2 TLB may result in a later cache hit and prevent the need for a costly page table walk to access the translation at a later time as taught by Eddy in [0009] [0036-0038]. Furthermore, the use of the LRU policy would have only required the simple substitution of known elements according to known methods to yield predictable results. For example, Bryant teaches that any known replacement algorithm may be used, and Eddy teaches that LRU is a known replacement policy. Accordingly, one of ordinary skill in the art could have substituted the LRU replacement policy taught by Eddy with the any known replacement algorithm taught by Bryant and the results would have been predictable.
Bryant does not explicitly teach, but Daly teaches wherein each of the first plurality of level 1 cache entries is different from each of the second plurality of level 2 cache entries and the selected one of the plurality of level 1 cache entries is interchanged with the hit level 2 cache entry (by teaching that multi-level caches may function according to an exclusive policy. In an exclusive policy, data is guaranteed to be in at most one of the plurality of caches, but never both. In this case, when a L1 cache miss occurs, but an L2 cache hit occurs, the hitting cache line in the L2 cache is exchanged with a line in the L1 cache [0032]).
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have modified the multi-level TLB cache as taught by Bryant in view of Eddy to function with an exclusive policy, and to have modified promotion and demotion of cache entries in the L1 and L2 TLB as taught by Bryant in view of Eddy to include exchanging the promoted line with the demoted line in the L1 and L2 caches according to that exclusive policy as taught by Daly.
One of ordinary skill in the art would have been motivated to make this modification because the advantage of the exclusive cache policy is that it allows the caches to store more data as taught by Daly in [0032].
Regarding claim 2:
The storage management apparatus of claim 1 is made obvious by Bryant in view of Eddy in further view of Daly (Bryant-Eddy-Daly).
Bryant teaches wherein the address translation unit is further adapted to: generate a mismatch information based on the virtual address when the translation request does not hit any one of the second plurality of level 2 cache entries, wherein the mismatch information comprises the virtual page number of the virtual address, and provide the mismatch information to a control unit, wherein the control unit obtains a to-be-refilled entry (by teaching that the TLB lookup circuitry (62)/(92) will check if the L1 TLB (32) contains the required entry, if the L1 TLB (32) does not, then it sends a request to the L2 TLB (34). If the L2 TLB also does not include the required entry, then the L2 TLB (34) can trigger a page table walk to request the required entry from the page tables within main memory (28) [0040]. Triggering the page table walk can include a request for the translation of the virtual address from the page tables in memory (28) [0075]. A virtual address contains a virtual page address portion (i.e., VPN) and an offset portion, which vary in size depending on the size of the page [0039] [0046] [0066]. The entry returned from the page table walk is then entered into the L1 page table (i.e., to-be-refilled entry) [0040] [0075-0077]).
Regarding claim 3 and analogous claim 18:
The storage management apparatus of claim 2 is made obvious by Bryant-Eddy-Daly.
Bryant further teaches wherein each cache entry, of the plurality of cache entries, is stored in a plurality of registers, and wherein the plurality of registers comprises: a first register, configured to store the virtual address tag to indicate a virtual page mapped in the cache entry (see the virtual page address portion as opposed to the offset portion of the virtual address stored in the TLB in [Fig. 6], where that memory location stored in the TLB [see Fig. 5] is construed to be a register); and a second register, configured to store a translated address tag to indicate a translated page to which the virtual page is mapped (see [Fig. 5], where the PA is disclosed as storing the translated physical page address portion of the physical address (not the offset as that is untranslated from the virtual address [0046], where that memory location is interpreted as a second register)) wherein page sizes of the virtual page and the translated page mapped in each cache entry are consistent (the size field indicates that the size of the page for the VA and the PA are the same [Fig. 5], especially as the TLB specifically stores translations for specific page sizes [0065-0066]).
Regarding claim 4 and analogous claim 19:
The storage management apparatus of claim 3 is made obvious by Bryant-Eddy-Daly.
Bryant teaches wherein the control unit is further adapted to: when the virtual address specified by the translation request does not hit any one of virtual address tags in the plurality of cache entries, obtain, from a root page table, the to-be-refilled entry that matches the virtual address specified by the translation request; and write the to-be-refilled entry to the at least one translation look-aside buffer (by teaching that the page table walk is performed on the page table entries in the main memory (28) (i.e., root page table) only if necessary (miss in both TLBs) and then the returned entry is stored into one of the levels of the TLB [0040] [0075] [0093]).
Regarding claim 5 and analogous claim 20:
The storage management apparatus of claim 4 is made obvious by Bryant-Eddy-Daly.
Bryant teaches wherein the address translation unit is further adapted to: determine whether the virtual address specified by the translation request hits any one of the first plurality of level 1 cache entries; when one of the first plurality of level 1 cache entries is hit, translate, based on the hit level 1 cache entry, the virtual address specified by the translation request into a corresponding translated address ([0039]); when none of the first plurality of level 1 cache entries is hit, determine whether the virtual address specified by the translation request hits any one of the second plurality of level 2 cache entries ([0040]); and when one of the second plurality of level 2 cache entries is hit, translate, based on the hit level 2 cache entry, the virtual address specified by the translation request into a corresponding translated address ([0040]).
Regarding claim 10:
The storage management apparatus of claim 1 is made obvious by Bryant-Eddy-Daly.
Bryant-Eddy-Daly further make obvious wherein when the first plurality of level 1 cache entries are not hit and one of the second plurality of level 2 cache entries is hit, the control unit is further adapted to write the replaced level 1 cache entry as a level 2 cache entry to the at least one translation look-aside buffer (through the analysis performed for claim 1).
Regarding claim 11:
The storage management apparatus of claim 3 is made obvious by Bryant-Eddy-Daly.
Bryant further discloses, wherein the plurality of registers further comprises: a fourth register, configured to store a size flag to indicate the page size of the virtual page or the translated page (see the field “size” in [Fig. 5] of the TLB, where that memory location is interpreted as a fourth register).
Regarding claim 13:
The storage management apparatus according to claim 1 is made obvious by Bryant-Eddy-Daly.
Bryant teaches a processor, comprising the storage management apparatus according to claim 1 (see [Fig. 1], the components outside of the data store (22 or at least the main memory (28)) make up a processing pipeline of a processor [0037]).
Regarding claim 16:
The processor according to claim 13 is made obvious by Bryant-Eddy-Daly.
Bryant teaches a computer system, comprising: the processor according to claim 13; and a memory, coupled to the processor (see the datastore (22), including main memory (28) coupled to the processing pipeline of a processor pictured in [Fig. 1]).
Claims 7-9 are rejected under 35 U.S.C. 103 as being unpatentable over Bryant-Eddy-Daly in further view of US Patent No. US 5,644,748 A (Utsunomiya).
Regarding claim 7:
The storage management apparatus of claim 3 is made obvious by Bryant-Eddy-Daly.
Bryant-Eddy-Daly does not explicitly disclose, but Utsunomiya teaches wherein the plurality of registers further comprises: a third register, configured to store a reference flag to indicate whether the cache entry is a least recently hit cache entry (by teaching that each TLB entry includes an LRU flag storage register for storing priority information indicating which entry is to be evicted according to an LRU algorithm when there is a TLB miss, and are also updated on TLB hits to maintain priority order for evictions [Fig. 9] [Col 9: lines 4-60]).
It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the TLBs implementing the any known replacement algorithm as taught by Bryant-Eddy-Daly to include the LRU flag storage registers to implement the LRU priority order as taught by Utsunomiya because it would have only required the combination of known elements according to known methods to yield predictable results. Bryant-Eddy-Daly teaches use of the any known replacement algorithm/policy, but does not teach a structure to implement and enforce such a policy and Utsunomiya teaches a structure for enforcing an LRU priority order for a TLB cache replacement scheme. Accordingly, one of ordinary skill in the art could have combined the generic replacement policy taught by Bryant-Eddy-Daly with the TLB structures including the LRU flag storage register to implement an LRU replacement policy as taught by Utsunomiya according to known methods and the results would have been predictable. Furthermore, in combination, each element would continue to perform the same function that it did separately. Accordingly, it would have been obvious to one of ordinary skill in the art.
Regarding claim 8:
The storage management apparatus of claim 7 is made obvious by Bryant-Eddy-Daly.
Bryant-Eddy-Daly do not explicitly disclose, but Utsunomiya teaches wherein when selecting a to-be-replaced entry of the first plurality of level 1 cache entries based on the preset algorithm, the control unit is further adapted to select a least recently hit level 1 cache entry based on the reference flag of each level 1 cache entry (through the analysis performed for claim 7).
Regarding claim 9:
The storage management apparatus of claim 1 is made obvious by Bryant-Eddy-Daly.
Bryant-Eddy-Daly does not explicitly disclose, but Utsunomiya teaches wherein when selecting the one of the first plurality of level 1 cache entries based on the preset algorithm, the control unit is adapted to select a first written level 1 cache entry based on a sequence in which the first plurality of level 1 cache entries are written to the at least one translation look-aside buffer (through the analysis performed for claim 7).
Claims 12 is rejected under 35 U.S.C. 103 as being unpatentable over Bryant-Eddy-Daly in further view of US Patent Application Publication No. US 2018/0239714 A1 (Abhishek).
Regarding claim 12:
The storage management apparatus of claim 11 is made obvious by Bryant-Eddy-Daly.
Bryant-Eddy-Daly make obvious wherein when the first plurality of level 1 cache entries are not hit and one of the second plurality of level 2 cache entries is hit, where the size of an entry is indicated with a flag indicating the page size of the virtual page or the translated page (through the analysis performed for claim 11).
Bryant-Eddy-Daly does not explicitly disclose, but Abhishek teaches the control unit is further adapted to select the to-be-replaced level 1 cache entry based on a size of the pages, so that page sizes to which the hit level 2 cache entry and the to-be-replaced level 1 cache entry are mapped are equal (by teaching that ways of an address translation cache (TLB) may be reserved for pages of a specific size. In this way, pages that enter the address translation cache may only replace pages of the way of the address translation cache that correspond to pages of the same size [0024] [0041] [0053] [0071] [0084]).
It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the level 1 TLB (32) and level 2 TLB (34) with size flags that may have an address translation request hit in the level 2 cache and not in the level 1 cache, and then have the level 2 entry be promoted and swapped with an entry in the level 1 TLB as taught by Bryant-Eddy-Daly to include being segregated such that ways of each TLB correspond to reserved page sizes, so that a page entering the L1 TLB would only replace a page with the same size as taught by Abhishek.
One of ordinary skill in the art would have been motivated to make this modification because reserving a portion of the address translation cache for the larger page sizes increases the effective capacity of the address translation cache as taught by Abhishek in [0034] and prevents complicating the lookup process as taught by such that a quick lookup process can still be performed as taught by Abhishek in [0030] [0057-0058].
Claims 14-15 are rejected under 35 U.S.C. 103 as being unpatentable over Bryant-Eddy-Daly in further view of US Patent Application Publication No. US 2012/0227245 A1 (Gupta).
Regarding claim 14:
The processor of claim 13 is made obvious by Bryant-Eddy-Daly.
Bryant further teaches a fetch unit, wherein the instruction fetch unit provides the translation request to the address translation unit, wherein the translation request specifies a virtual address of a instruction (see [Fig. 1] where the instruction comes from the fetch unit (6)); and wherein the address translation unit communicates with a first translation look-aside buffer (interpreted as the L1 TLB storing L1 entries in the TLB (30)) in the at least one translation look-aside buffer, and provides a translated address of the instruction to the instruction unit based on a cache entry provided by the first translation look-aside buffer (see [Figs. 1, 2 and 6], and related discussions as previously cited in the rejection of claim 1).
Bryant-Eddy-Daly does not explicitly teach, but Gupta teaches wherein the unit is a prefetch unit and wherein the instruction is a prefetch instruction ([0035]-[0036]).
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the prefetch instruction unit and prefetch instruction of Gupta with the system of Bryant-Eddy-Daly because prefetching reduces latency as taught by Gupta in ([0007]).
Regarding claim 15:
The processor of claim 14 is made obvious by Bryant-Eddy-Daly in further view of Gupta.
Bryant teaches a load/store unit ((20) [Fig. 1]) wherein the load/store unit provides the translation request to the address translation unit, wherein the translation request specifies a virtual address of a memory access instruction; and wherein the address translation unit communicates with a second translation look-aside buffer (interpreted as the L2 TLB storing L2 entries in the TLB (30)) in the at least one translation look-aside buffer, and provides a translated address of the memory access instruction to the load/store unit based on a cache entry provided by the second translation look-aside buffer (see [Figs. 1, 2 and 6], and related discussions as previously cited in the rejection of claim 1).
Response to Arguments/Amendments
In response to the amendments to the claims, the previous 35 USC § 112(a) rejection has been withdrawn.
Applicant’s arguments with respect to the prior art rejection of the claims have been considered but are moot because the new ground of rejection does not rely on any reference applied in the prior rejection of record for any teaching or matter specifically challenged in the argument.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
US Patent No. US 5,946,716 A (Karp) which shows comparing variable numbers of bits of the VPN (26) to a tag (16) in the TLB entry (12) based on a size field (22) to determine whether or not a translation is present in the TLB. If the translation is present, a number of bits of the PPN (18) correspond to the number of bits of the VPN (26)as dictated by the size field (22) [Fig. 3]. Which is the exact same use of Applicant’s claimed size field and variably sized variable page numbers and physical/translated page numbers.
The revision Wikipedia page titled, “Victim cache” from 19 March 2019 – discusses a “victim cache” (level 2 cache). When a miss occurs in the “cache” (level 1 cache), an entry may be fetched from the victim cache if there is a hit in the victim cache, and swapped with an entry evicted from the cache. The benefit is that the victim cache incurs only a one cycle miss penalty instead of more for fetching from a backing memory, and causes an overall miss reduction rate [pg. 1, §Overview, ¶¶all] [pg. 1, §Implementation, ¶¶all – continued onto pg. 2].
The revision of the Wikipedia page title, “Cache inclusion policy” from 18 March 2019 – discusses an “Exclusive Policy,” which results in all of the memory capacity of a level 1 and level 2 cache being used to store unique cached data. This renders all cache entries from each cache to be different (unique) from one another. Furthermore, evicted entries from the level 1 cache are installed in the level 2 cache, such that a level 2 hit would be understood to swap data with the level 1 cache [pg. 1, §Exclusive Policy, ¶¶all] [pg. 2, Fig. 2] [pg. 2, §Comparison, ¶¶all].
Appendix L: Advanced Concepts on Address Translation by Abhishek Bhattacharjee from the Department of Computer Science, Rutgers University, on 11 September 2018 (Bhattacharjee) – teaches that multi-level TLBs may employ an exclusive inclusion policy that causes all entries across the TLBs to be unique (different) from one another [pg. 9] [pg. 18]
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to CURTIS JAMES KORTMAN whose telephone number is (303)297-4404. The examiner can normally be reached Monday through Friday 7:30 AM through 4:00 PM MT.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Reginald Bragdon can be reached at (571) 272-4204. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/CURTIS JAMES KORTMAN/Primary Examiner, Art Unit 2139
Prosecution Insights