Browse Prior Art Database

Resolution of Cache Directory Collision

IP.com Disclosure Number: IPCOM000121762D
Original Publication Date: 1991-Sep-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 2 page(s) / 108K

Publishing Venue

IBM

Related People

Liu, L: AUTHOR

Abstract

Disclosed are techniques for satisfying multiple requests of cache directory lookup when contention on directory ports exists. The benefit is increased system performance without increased design complexity due to directory copying or pipelining.

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

Resolution of Cache Directory Collision

      Disclosed are techniques for satisfying multiple requests
of cache directory lookup when contention on directory ports exists.
The benefit is increased system performance without increased design
complexity due to directory copying or pipelining.

      In higher performance computers multiple cache accesses are
often active in the same cycles.  In conventional designs, the number
of such concurrent requests that can be handled is limited by the
amount of directory lookups affordable.  For instance, consider a
cache with 128 bytes per line and with arrays 4-way interleaved at
quadword (16 byte) unit.  In general, unless the directory can
support 4 lookups in the same cycle, the array capability may not be
fully utilized.  For instance, consider an extreme example in which 4
successive quadwords of the same cache line are being concurrently
requested independently.  Assume that the arrays can satisfy all 4
requests at the moment.  Unless the directory is multi-ported (e.g.,
with 4 copies), some of the requests cannot be handled due to the
lack of directory ports.  Multiple ports (or copies) for directory is
usually expensive and often to limited degree only.  In this
invention techniques are disclosed for combining directory requests
and provide possible concurrent resolutions upon conflict at
directory ports.

      Consider the above illustrated example.  It is clear that, if
the directory control is intelligent to recognize that all 4 cache
requests are for the same cache line, they may be resolved through a
single directory lookup.  It was also observed from trace analysis
that, at typical cache line size (e.g., 64-256 bytes), successive
memory accesses hit the same cache line at observable likelihood.
These observations motivate the usage of combining techniques for
resolving multiple directory requests.

      The invention will be illustrated using a sample directory
design, in which each port can only support 1 directory lookup per
cycle.  For instance, for the described cache with 4-way interleaved
arrays, the directory may consist of two partitions based on odd and
even line addresses.  Each directory partition can only perform
lookup for 1 request per cycle.  We also assume that the design
allows multiple requests to be active at each directory port.

      Now consider how multiple requests at a single directory port
(odd or even) may be handled together in a single directory cycle.
Among such multiple requests, one (e.g., the earliest) is the
"primary" and is used to retrieve directory entries for lookup in
normal fashion. There are two major methods considered in the
invention:
      METHOD I  -  The directory entry information (e.g., line ad
dresses) retrieved based on the primary...