Browse Prior Art Database

Handling Reservations in Multiple-Level Cache

IP.com Disclosure Number: IPCOM000106780D
Original Publication Date: 1993-Dec-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 6 page(s) / 250K

Publishing Venue

IBM

Related People

Simpson, RO: AUTHOR [+2]

Abstract

Disclosed are extensions to a multiprocessor's cache and cache protocols, for a system with load-and-reserve and conditional-store instructions, to maintain a reservation when a location is evicted from cache.

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

Handling Reservations in Multiple-Level Cache

      Disclosed are extensions to a multiprocessor's cache and cache
protocols, for a system with load-and-reserve and conditional-store
instructions, to maintain a reservation when a location is evicted
from cache.

      The use of the special instructions, load-and-reserve and
conditional-store, is in a sequence of the following form:

o     Load-and-reserve location X

o     Calculate a new value of X

o     Conditional store new value to location X

The conditional-store operation is performed only if the processor
holds a reservation for the location.  (In the IBM PowerPC, the
architecture does not require that the reservation address be checked
for equality with the target address of the store, but
implementations are permitted to require this equality.)  The
reservation is cleared when the processor performs a conditional
store, when the processor performs a load-and-reserve, or when
another processor stores to the same cache line.  In a typical use of
such a code sequence, the conditional-store instruction is followed
by a test for success of the store and a branch, in the case of
failure of the conditional store, back to the beginning of the
sequence for another attempt.  Such a code sequence is termed a
conditional loop.

      During calculation of the new value of X, the cache line in
which X resides may be subject to eviction from the cache.  While
calculating X, the processor may access other locations in memory.
Such an access may require eviction of a line from a cache at some
level of the memory hierarchy, in order to bring into the cache the
line containing the accessed location.  If the calculation requires
access to a set of distinct cache lines that cannot all be present in
the cache at once, it may be necessary to evict from the cache a line
for which the processor holds a reservation.  If a reservation is
associated with the cache line, eviction of the line requires
clearing the reservation.  This can result in an execution scenario
in which the processor always cancels its own reservation, and never
exits from a conditional loop.

      It might seem that software can avoid the problem by limiting
the number of accesses inside a conditional sequence to the number of
lines that can be guaranteed to be maintained simultaneously by the
hardware.  However, for software to be portable across a variety of
processors, this number is zero, because with a direct-mapped cache
any location accessed inside conditional sequence might be mapped to
the same line as that in which X resides This severely restricts the
uses of the special instructions.

      In some circumstances an adroit replacement strategy can
guarantee that no line for which the processor holds a reservation
will ever be evicted from the cache.  For example, if each cache is
set-associative with two or more sets, and if the processor can hold
at most one reservation, then each ca...