Browse Prior Art Database

Arbitrary Congruence Class Assignment

IP.com Disclosure Number: IPCOM000104420D
Original Publication Date: 1993-Apr-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 4 page(s) / 200K

Publishing Venue

IBM

Related People

Rechtschaffen, R: AUTHOR

Abstract

A Table mechanism which is accessed with the virtual addresses and contains pointers to the position of a line in both the directory and data arrays of a cache allows for an ability to assign CONGRUENCE CLASSES arbitrarily. This can be used to reduce cache misses.

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

Arbitrary Congruence Class Assignment

      A Table mechanism which is accessed with the virtual addresses
and contains pointers to the position of a line in both the directory
and data arrays of a cache  allows for an ability to assign
CONGRUENCE CLASSES arbitrarily.  This can be used to reduce cache
misses.

      Any TABLE whose entries are pointers to the position in the
cache of the line being accessed can place the line arbitrarily if it
can mange collisions,

      DEFINITION OF A COLLISION:  A collision in a TABLE is said to
occur if the table entry is valid and the result of accessing the
directory with the information derived from the TABLE entry results
in an unequal comparison between the REAL ADDRESS TAG found in the
directory and the DLAT output.

      COLLISION MANAGEMENT - The ability of handling a collision on a
mismatch involves the realization that the incorrect line pointed to
by the table entry is not an arbitrary incorrect line.  It is the
line with which the line currently accessed is colliding.

      The tautological aspect of this comment belies its true
significance.  The fact that a collision occurs is the basis for the
proper handling of the collision.  If the line being accessed is not
in the cache then the collision occurrence instructs the mechanism
that will manage the collision to add this line to the search list
that will resolve the collision.  If the line being accessed is in
the cache then the former action on misses will guarantee than the
collision mechanism will find the line on the search list.  All in
all, the tautological comment suggest that if misses, which are the
primordial collisions, are handled properly, then all collisions will
be handled properly.

      FINDING OF A LINE FOLLOWING A MISMATCH - The position of the
line in the cache needs to be found in the following general
circumstances:

o   There is no relationship between congruence class and real
    address.

o   There can be collisions in the TABLE.

o   The line may being accessed may be in the cache (valid or
    invalid) or not be in the cache (a miss has occurred).

      All that is required is a field in the cache directory which
can accommodate a pointer.  This field establishes a link to the
other lines that are in the cache and potential sources of
collisions.

      A good way to grasp some of the complexity that is to follow is
to consider a simpler case and its implications.  Consider a 128 KB
cache comprised to 1K lines each of size 128 B. The TABLE used to
contain the position in the cache of these lines has 4 K entries and
is accessed using bits 13 - 24, B(13-24), of the processor generated
address.  Now to simplify the problem for the purpose of initial
exposition let all the addresses generated by the processor be real.
Each line that is in the cache has a specific and unique table entry
thru which it can be accessed.  Multiple lines in the cache with the
same B(...