Browse Prior Art Database

Overflow Buffer for Translation Lookaside Buffer

IP.com Disclosure Number: IPCOM000122427D
Original Publication Date: 1991-Dec-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 90K

Publishing Venue

IBM

Related People

Liu, L: AUTHOR

Abstract

Disclosed is a technique for maintaining an overflow buffer for translation lookaside buffer (TLB). The benefit is reduction of TLB misses due to busy replacements of a few TLB congruence classes when programs execute in special patterns.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Overflow Buffer for Translation Lookaside Buffer

      Disclosed is a technique for maintaining an overflow
buffer for translation lookaside buffer (TLB).  The benefit is
reduction of TLB misses due to busy replacements of a few TLB
congruence classes when programs execute in special patterns.

      The Translation Lookaside Buffer (TLB) has been utilized in
processors for speeding up virtual address translations.  TLB is
typically organized as a set-associative directory in which each
entry records past translation results for a particular virtual page.
Each time TLB misses, the translation information is retrieved from
segment and page tables in a slower process, which normally takes
more than 20 machine cycles.  Since the granularity of a page is
bigger (e.g., 4K bytes) a TLB with few hundred entries can provide
very high hit ratios. However, in certain program executions there
can be busy replacements due to heavy collisions of virtual pages
within the same congruence classes.  Consider an extreme example of a
numeric program loop, in which five large matrices are accessed
closely.  Assume that, by coincidence, these matrices are aligned
such that they all hit the same congruence class of TLB in each loop
iteration.  There will then be very heavy replacements in a
particular congruence class during each iteration.  One way of
solving the problem is to increase the set-associativity of TLB
(e.g., to 8), which can introduce significant hardware complexity.
In this invention we propose an alternative solution which can be
simpler and more flexible in many implementations.

      The basic idea of this invention will be illustrated with an
exemplary design.  Consider a typical TLB with 256 congruence classes
and 2-way set-associativity.  We add an extra smaller overflow
directory OTLB, in which each entry may carry the same format as that
for the TLB.  OTLB has 4 congruence classes and 4-way
set-associativity, with typical LRU type replacements.  Generally
speaking, TLB and OTLB are disjoint, in the sense that the same
virtual page is not covered by both of them at the same time.  Each
time a virtual page...