Incorporating purge history into least-recently-used states of a translation lookaside buffer

Patent metadata

Field	Value
Publication number	US-10387326-B2
Application number	US-201715811807-A
Country	US
Kind code	B2
Filing date	Nov 14, 2017
Priority date	Jun 15, 2017
Publication date	Aug 20, 2019
Grant date	Aug 20, 2019

Abstract

A computer-implemented method includes associating an initial use order with a plurality of target sets of a translation lookaside buffer (TLB), where the initial use order indicates an order of use of the plurality of target sets. The plurality of target sets are associated with an initial least-recently-used (LRU) state based on the initial use order. A new use order for the plurality of target sets is generated. Generating the new use order includes moving a first target set to a least-recently-used position, responsive to a purge of the first target set. The LRU state of the plurality of target sets is updated based on the new use order, responsive to the purge of the first target set. The first target set is identified as eligible for replacement according to an LRU replacement policy of the TLB, based at least in part on the purge of the first target set.

First claim

What is claimed is:

1. A computer-implemented method comprising:
associating an initial use order with a plurality of target sets of a translation lookaside buffer (TLB), wherein the initial use order indicates an order of use of the plurality of target sets;
associating the plurality of target sets with an initial least-recently-used (LRU) state based on the initial use order;
generating a new use order for the plurality of target sets, wherein the generating the new use order comprises moving a first target set of the plurality of target sets to a least-recently-used position, responsive to a purge of the first target set;
updating the LRU state of the plurality of target sets based on the new use order for the plurality of target sets, responsive to the purge of the first target set; and
identifying the first target set as eligible for replacement according to an LRU replacement policy of the TLB, based at least in part on the purge of the first target set.

2. The computer-implemented method of claim 1 , wherein the LRU state incorporates a purge history of the plurality of target sets.

3. The computer-implemented method of claim 1 , wherein the LRU replacement policy lacks access to a validity bit of the first target set of the plurality of target sets.

4. The computer-implemented method of claim 1 , wherein a second target set of the plurality of target sets was used less recently than the first target set, and further comprising replacing the first target set with a new translation prior to replacing the second target set, based on the purge of the first target set.

5. The computer-implemented method of claim 1 , wherein the new use order indicates that each purged target set of the plurality of target sets is less recently used than each valid target set of the plurality of the target sets.

6. The computer-implemented method of claim 1 , wherein the updating the LRU state of the plurality of target sets based on the new use order for the plurality of target sets, responsive to the purge of the first target set, comprises assigning to the plurality of target sets an LRU state to which the new use order maps.

7. The computer-implemented method of claim 1 , wherein the plurality of target sets comprise a plurality of page table entry (PTE) sets within a compartment of the TLB.

Assignees

• IBM

Inventors

• Brandt Uwe
• Helms Markus
• Köhler Thomas
• Lehnert Frank

Classifications

• G06F2212/681

  Multi-level TLB, e.g. microTLB and main TLB · CPC title

• G06F12/1063 Primary

  the data cache being concurrently virtually addressed · CPC title

• G06F12/123

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title

• G06F2212/1021

  Hit rate improvement · CPC title

• G06F2212/683

  Invalidation · CPC title