Browse Prior Art Database

Scalable Reservation Mechanism for a Linked List Cache Structure

IP.com Disclosure Number: IPCOM000118450D
Original Publication Date: 1997-Feb-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 2 page(s) / 70K

Publishing Venue

IBM

Related People

Johnson, RE: AUTHOR [+5]

Abstract

Disclosed is a means for supporting split-access atomic update primitives (e.g., Load-and-Reserve, Store-Conditional) in a multiprocessor that uses a double-linked list for a cache-coherence structure such as (*).

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

Scalable Reservation Mechanism for a Linked List Cache Structure

      Disclosed is a means for supporting split-access atomic
update primitives (e.g., Load-and-Reserve, Store-Conditional) in a
multiprocessor that uses a double-linked list for a cache-coherence
structure such as (*).

      The disclosure invention augments (*) to support split-access
atomic updates.  There is also direct application to similar
coherency mechanisms using linked data structures for the
representation of sharing  lists.  Logic is added to the processor to
do one of the following:
  o  ensure that a cache line is not evicted while a reservation
      is held, or,
  o  if the cache line is evicted, then a buffer is dedicated to
      hold the sharing-list entry data (2 pointers + state in the
      case of SCI).

Either of these ensure that a sharing list entry is maintained until
a Store-Conditional can be executed.

The logic maintaining the sharing lists includes the following
function:
  o  If any other processor is placed at the head of the sharing
      list and purges the sharing list, then any reservation held
      on that cache line is cancelled and the sharing list entry
      for the processor holding the reservation may be deleted or
      invalidated.
  o  When the processor executed a Store-Conditional instruction,
      the following actions will be carried out:
     1.  If the processor is already the head entry of the list,
          then the Store-Conditional succeeds, the reservation is
          cancelled, and the processor remains at the head of the
          list (and purges the list if appropriate).
     2.  If the processor is not at the head of the sharing list,
          then the processor requests access to the head of the
          list while keeping its existing sharing list entry
          intact.  Once the head entry is obtained, the processor
          is responsible for purging the sharing list.  During the
          purging, t...