Browse Prior Art Database

Method to Invalidate History Tables in Tightly Coupled Multiprocessors

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

Publishing Venue

IBM

Related People

Liu, L: AUTHOR

Abstract

A technique is described whereby history tables may be invalidated for tightly coupled multiprocessor applications. The design provides the storage control element (SCE) with an effective method of managing store invalidates.

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

Method to Invalidate History Tables in Tightly Coupled Multiprocessors

      A technique is described whereby history tables may be
invalidated for tightly coupled multiprocessor applications. The
design provides the storage control element (SCE) with an effective
method of managing store invalidates.

      Generally, in tightly coupled multiprocessor applications, the
control of cross invalidates can be performed in various ways.  The
concept described herein is concerned with a facility at the SCE for
the management of cross invalidates, especially for store-thru
designs.

      With BIAS type designs, such as with the IBM 3033, a filter
table is used for each processor to record those cache lines that
have been recently invalidated.  This is done so that repeated remote
stores will not cause unnecessary invalidate actions.  In BIAS type
designs, a fetch will cause the corresponding line entry in the table
to be invalidated. The concept described herein provides a design
that manages cross invalidates in a different manner.

      Consider the lines in the memory to be partitioned into blocks,
each of which covers a fixed number of lines.  For our purpose and
for illustration, the invalidate history table (IHT) is structured as
a set-associative table. Access to IHT is through hashing on the
block addresses. Each entry represents appropriate information for a
block. Let there be K lines per block.  Also, let there be N central
processors (CPs) in the system.  The nth CP is denoted as Pn .  The
fields at each IHT entry are as follows:
   < V, BADDR, TAG1, ..., TAGK >
where V is the valid bit; BADDR is the address of the block currently
represented; and TAGk (1&k&K) represents a bit-vector of length N
representing history information for the kth line in the block.  The
N bits in a TAGk vector indicate which CPs might possibly have copies
of the kth line in their caches.

      The operation of the IHT design is as follows:
     1.  Initially all V bits are cleared, representing null history.
   2.  When a store from Pn to the kth line of block B observes a
block miss in IHT (i.e., a valid entry for B is not found in the
table) - A new entry for B is created (with appropriate replacements
in the congruence class).  In the new entry, the following are
initialized:
    -          The address of B is put into BADDR.
    -          Except for TAGk, all bits in other TAGj vectors are
turned ON (representing that those lines could be in any of the
caches).
    -          TAGk is initialized so that the nth bit is
               turned ON and the rest are turned OFF.  At this time,
the SCE broadcasts signals to all remote CPs for invalidations of the
line being stored.

      The new block entry is made the most recently used (MRU) in its
congruence class.
     3.  When a store from Pn on the kth line of block B observes a
block hit at the IHT - The T...