Browse Prior Art Database

List Management in a Non-Cache Coherent Environment

IP.com Disclosure Number: IPCOM000112771D
Original Publication Date: 1994-Jun-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 87K

Publishing Venue

IBM

Related People

Van Fleet, JW: AUTHOR

Abstract

The concept presented in this article is to provide a mechanism, in a non-cache coherent environment, which minimizes the negative performance aspects associated with the requirement to flush/invalidate "stale" data in a read mostly list or in a list that is write mostly by one processor and read mostly by the others. This mechanism will, of course, perform correctly regardless of the frequency of reads and writes, but the optimizations are potentially detrimental in an environment for which they are not designed.

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

List Management in a Non-Cache Coherent Environment

      The concept presented in this article is to provide a
mechanism, in a non-cache coherent environment, which minimizes the
negative performance aspects associated with the requirement to
flush/invalidate "stale" data in a read mostly list or in a list that
is write mostly by one processor and read mostly by the others.  This
mechanism will, of course, perform correctly regardless of the
frequency of reads and writes, but the optimizations are potentially
detrimental in an environment for which they are not designed.

      The rules for managing lists which are write mostly by a single
processor or read mostly by multiple processors:

1.  The list is accessed while locked.  We need to keep the list
    locked to maintain list consistency.

2.  The list header must always be pre-invalidated.  (An optimization
    can occur if the lock manager returns an indicator that reports
    yes or no to the question "was this the last processor which held
    the lock?"  Based on the lock and flush technique, if this
    processor was the last processor to own the lock, then the data
    in the header is not stale.)

3.  Traversal must always occur starting at the initial element in
    the list "pointed" to by the list header.

4.  The list header contains:

    o   A pointer to the first element in the list.

    o   A bit mask of processors required to invalidate as they
        traverse the list.  (The bit mask is set to "all" when it is
        set.  Since the bit mask is examined by each processor only
        as required, it is easier to set it to all rather than
        selectively decide the active processors.  This also allows
        for processors to add themselves to the processor list
        without fear of being out of sync because of initialization
        timing.)

5.  If the invalidate bit is on for a processor, it must invalidate
    as it follows the list pointers AND MUST traverse the entire
    list.  (This is where the performance trade-offs come.  If it is
    mostly read, the whole list will not often be traversed.  If it
    is mostly write by multiple CPUs, the entire list must be
    traversed on most list accesses.)

6.  If the bit is not on for this processor, it need not flush
    anything in the list.

7.  When anything in a list element changes, the changing processor
    must flush changes to memory and set the bit indicators for the
    other processors.  A single processor can maintain consistency in
    its cache without invalidating the entire list. ...