Browse Prior Art Database

Look Up for Logical Address Based Cache Directory

IP.com Disclosure Number: IPCOM000121924D
Original Publication Date: 1991-Oct-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 4 page(s) / 172K

Publishing Venue

IBM

Related People

Liu, L: AUTHOR

Abstract

Disclosed are techniques for reducing the number of comparators in resolving cache hit/miss/synonym conditions for IBM/3090*-type cache design. Background

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

Look Up for Logical Address Based Cache Directory

      Disclosed are techniques for reducing the number of
comparators in resolving cache hit/miss/synonym conditions for
IBM/3090*-type cache design.
Background

      In IBM/3090 systems the cache design utilizes a directory that
records real (absolute) addresses while the selection of congruence
class for an access is based on the logical address (virtual/real).
For instance, when a processor execution element issues an operand
fetch, certain lower order bits of the (logical) address of
associated cache line are used to index to the primary congruence
class (PCC).  Due to deterministic program behavior the cache access
most likely hits a line in the PCC, in which case the fetch can be
satisfied there without extra complication.  A cache miss condition
occurs when the physical cache line is not in the cache, for which
appropriate cache miss actions are triggered to bring a copy of the
line (e.g., from main memory) into the PCC via specific replacement
(e.g., LRU) algorithm.  However, there exists the chance of synonym
hit that the physical line resides in another (synonym) congruence
class while missing in the PCC.  It is not the focus of the current
invention as to what cache control should do when synonym hit occurs,
but rather on how such conditions can be determined effectively.
Such determination is further complicated by the fact that, for
virtual addressing, TLB translation results are needed to resolve the
status.  In the following we illustrate a design based on the
IBM/3090 approach (with 31-bit virtual/real addressing).  In order to
simplify the illustrations we will ignore the details on TLB misses
upon memory accesses with virtual addresses.

      Consider a 256KB cache with 128 bytes per line and 4-way set-
associativity.  There are 512 congruence classes. We also assume a
TLB with 4-way set-associativity.  (Total number of TLB entries is
not important here.)  Each address A (virtual or real) is 31-bits
(indexed as 1-31).  Let Ai-j be the address bits in between (and
including) bits i and j (where 1 & i & j & 31).  For each
logical address A of cache access bits A25-31 are within the cache
line boundary, and A16- 24 is the PCC index (selecting 1 out of 512
congruence classes).  Now, with 4K page size, the cache access has
the possibility of hitting any one of the 16 congruence classes due
to unpredictable translation results of the four (synonym) bits
A16-19 .  With the IBM/3090-type design approach, the directory
look-up for a cache access (with virtual address) may operate as
follows.  The real (line) addresses from the 64 (16x4) cache
directory entries of the 16 congruence classes are read out, and the
4 real (page) addresses are read out of the associated congruence
class of TLB.  Together with request address bits A20-24, these 64
real cache line addresses and the 4 real page addresses are matched
pair-wisely (via 256 comparators) to determine p...