Browse Prior Art Database

Filter for Directory Look-Aside Table Search

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

Publishing Venue

IBM

Related People

Liu, L: AUTHOR

Abstract

A technique is described whereby a filter is provided for directory look-aside table (DLAT) so as to speed up set storage key (SSK) like operations.

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

Filter for Directory Look-Aside Table Search

      A technique is described whereby a filter is provided for
directory look-aside table (DLAT) so as to speed up set storage key
(SSK) like operations.

      Typically, computer architecture enables a real (absolute) page
frame to be translated from different virtual addresses.  Often DLAT
needs to be searched to check whether a real page frame is covered.
An example is the execution of an SSK instruction.  Such searches may
be costly on performance, especially when there are more processors
in the system.  Also, a great majority of such searches do not find
the real (absolute) page ID in the DLAT.  The concept described
herein provides a relatively simple mechanism to filter out most of
the futile DLAT searches.

      Consider a DLAT with C congruence classes and S sets in each
congruence class (i.e., there are CxS real page entries).  Consider
another hash array H with CxSxK entries. Normally all of C, S and K
are powers of 2.  Each H entry is a counter with a fixed number of
bits.  H is used to approximate the real page frame coverage in the
DLAT.  For any given real (absolute) page, the hash entry is
determined via certain fixed bits (e.g., lower order bits) in the
page address.  For a real page address P, H[P] is used to indicate
the value at the hashed entry. We want to guarantee that when a real
page P is covered in the DLAT, H[P] will be bigger than zero.  Hence,
when H[P] is zero, we know immediately that P is not covered in the
DLAT.  The maintenance of H is as follows:
   (1) Initially, when DLAT is empty (i.e., all entries are invalid),
and H is set to all zeros.
     (2) When a translation is done and a real page addressed P is
inserted into the DLAT, H[P] is incremented by one.
     (3) When a real page addressed P is replaced out of the DLAT, H
P is decremented by one by passing the H coordinate to its control.

      The counter at each H entry may be implemented as a fixed point
integer, or it may simply be implemented as a bit vector operated
with shift operations.  In practice, it is beneficial to use very few
bits (e.g., 1-4) at each H entry.  Overflow conditions must be
considered (i.e., the number of real pages in the DLAT hashed to the
same entry exceeds the capacity of the counter).  There is an
overflow condition represented at each H entry.  Such an overflow
condition may be represent...