Browse Prior Art Database

Selective Invalidation Scheme for Software MP Cache Coherence Control

IP.com Disclosure Number: IPCOM000109328D
Original Publication Date: 1992-Aug-01
Included in the Prior Art Database: 2005-Mar-23
Document File: 3 page(s) / 137K

Publishing Venue

IBM

Related People

Peir, J: AUTHOR [+2]

Abstract

Disclosed are techniques for maintaining cache coherence in a MP environment. The central idea is to allow temporal inconsistent cache lines in multiple caches as long as each processor will not access any stale data. Selective invalidation is performed at the synchronization points to invalidate those lines which have been updated.

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

Selective Invalidation Scheme for Software MP Cache Coherence Control

       Disclosed are techniques for maintaining cache coherence
in a MP environment.  The central idea is to allow temporal
inconsistent cache lines in multiple caches as long as each processor
will not access any stale data.  Selective invalidation is performed
at the synchronization points to invalidate those lines which have
been updated.

      An important issue in MP cache design is to maintain cache
coherence, that is, the data to be fetched from a cache should be the
latest data stored by any processor to the same address. The existing
hardware solutions to this problem either maintain a global directory
or use a snoopy bus. Both methods invalidate a cache line whenever
any portion of the line is updated in any other cache. In scientific
and engineering applications, more than one processor may be used to
solve a single problem in parallel.  In such environment, two or more
processors may compute on the same data array. Different parts of the
array computed by different processors may share the same cache line.
Although each processor accesses a distinct portion of the cache
line, the hardware coherency control may invalidate the cache line
because of the update from other processors.  This undesirable
invalidation may cause a 'ping-pong' phenomenon.

      In software-control cache coherence schemes, the invalidation
is done through software instructions.  Therefore, a cache line can
be inconsistent temporarily among multiple caches as long as the
processor does not fetch a stale data.  The easiest software-control
scheme is to invalidate the entire cache whenever the processor has a
potential of fetching a stale data.  Apparently, this indiscriminate
invalidation causes unnecessary cache misses.  To increase the cache
hit ratio, each processor should invalidate only the cache lines that
have been updated by other processors.  However, this scheme requires
to search the entire cache for those cache lines.  The disclosed
technique allows fast selective invalidation while maintaining high
hit ratio.

      A parallel model of computation with three key aspects is
considered.
.  a fork-join type of parallel construct,
.  a mixture of parallel and sequential computational regions,
.  no communication and synchronization among parallel tasks.
Each region, called an epoch is the basic unit of scheduling, which
can be executed on one or more processors.  Since data communication
and synchronization is not allowed among parallel tasks, each
processor cannot read or write data which is written by any other
processor in the same epoch.  A barrier type synchronization is
assumed at the end of every parallel epoch.
The Basic Scheme

      To selectively invalidate caches lines/words according to the
above observations, we propose to attach two bits to each cache line:
line-valid and read-only in the cache directory; and two bits to each
cac...