Browse Prior Art Database

Random Access Memory Bit Select with Imbedded Table Lookup

IP.com Disclosure Number: IPCOM000105448D
Original Publication Date: 1993-Aug-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 4 page(s) / 105K

Publishing Venue

IBM

Related People

Liu, L: AUTHOR

Abstract

This invention provides techniques for optimizing late-select operations on Random Access Memory (RAM) devices. The key idea is to overlap row-access with proper table lookup.

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

Random Access Memory Bit Select with Imbedded Table Lookup

      This invention provides techniques for optimizing late-select
operations on Random Access Memory (RAM) devices.  The key idea is to
overlap row-access with proper table lookup.

      It is often desirable to provide certain features to RAM
devices to select array cells based on the result of table lookup.
For example, consider the implementation of a set-associative cache.
The late-select of cache element in a set is often done after cache
directory search is done.  In some recent proposals the late-select
is determined through the lookup of certain history tables (e.g.,
providing the predicted associativity for access).  One
straightforward way of implementing such schemes is to carry out
array access and table lookup separately (in parallel), and then use
the table lookup results to perform late-select on multiple data
output groups.  In this invention techniques are proposed to further
integrate such table lookup with RAM array access so that better
timing can be achieved through parallelism.  The proposal can be
useful particularly for certain custom designs.

      Fig. 1 depicts a for conventional SRAM chip organization.  The
array cells are divided into 8 independent sub-arrays.  Each
sub-array is a 2-dimensional bit table with 128 rows and 32 columns.
The chip has total of the 32K data bits.  Assuming that each access
to the chip is at 16-bit granularity, with 2 bits from each
sub-array.  The A address input (11-bits) for an access consists of 7
R-bits for row-select and 4 C-bits for column-select.  Upon receiving
A (e.g., for a read) the R-bits will trigger row decode and
row-select.  The row-select causes a 32-bit row to be read out of
each sub-array.  The 32-bit row may be viewed as 8 bit-pairs.  The
C-bits triggers column decode and column-select (bit-select).  The
column-select causes 1 bit-pair to be selected for output from each
of the 8 selected rows.  From timing point of view, row-select occurs
ahead of column select.

      Fig. 2 depicts a new SRAM organization that is enhanced with
table lookup.  An extra table T is added to the chip, with additional
control circuits.  For the purpose of illustration we consider T as a
1-dimensional hash table with 1K entries and 4 bits recorded per
entry.  For each access T is indexed via certain address T-bits
(which may overlap with or be part of the R&C-bits).  The 4-bits from
the indexed T entry will now be used for the column-select, instead
of the originally...