Browse Prior Art Database

M-Way Set Associative Prefetch/Stream Buffer Design

IP.com Disclosure Number: IPCOM000119156D
Original Publication Date: 1997-Dec-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 4 page(s) / 102K

Publishing Venue

IBM

Related People

Geiger, PD: AUTHOR [+6]

Abstract

Disclosed is a prefetch/stream buffer design that is M-set associative, where M denotes the number of streams. Each stream buffer is fully associative; thus, the prefetch array consists of multiple stream buffers. This array is used to prefetch cache lines that are most likely to be accessed in the future. The idea is that future data references can be satisfied from the prefetch buffers rather than from memory, which improves system performance. This is most useful in scientific applications where data references are sequential.

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

M-Way Set Associative Prefetch/Stream Buffer Design

      Disclosed is a prefetch/stream buffer design that is M-set
associative, where M denotes the number of streams.  Each stream
buffer is fully associative; thus, the prefetch array consists of
multiple stream buffers.  This array is used to prefetch cache lines
that are most likely to be accessed in the future.  The idea is that
future data  references can be satisfied from the prefetch buffers
rather than from  memory, which improves system performance.  This is
most useful in scientific applications where data references are
sequential.

      This design uses a tagged prefetch method in hardware.  A set
of bits in the address field of a transaction (i.e., Read) are used
to determine if prefetching is desired, the stream id, and the
direction of  prefetching.  A prefetch bit is used to denote that a
prefetch of the next N addresses is desired.  Another set of bits are
used to denote which stream those prefetch addresses should be
allocated to. Therefore,  if a Read with address = A, N prefetch
addresses A+1 ...  A+N (ascending  direction) will be generated for
the stream indicated by the stream id  bits.  The direction bit
dictates whether descending or ascending prefetch addresses will be
generated by the prefetch array.  The number  of streams and depth of
the stream buffer will vary with system requirements.  Fig. 1 shows a
prefetch array with four stream buffers,  each consisting of two
entries.
  stream0  stream1  stream2  stream3
  -------  -------  -------  -------
  |     |  |     |  |     |  |     | <- buffer entry
  -------  -------  -------  -------
  |     |  |     |  |     |  |     | <- buffer entry
  -------  -------  -------  -------

              Fig. 1 A Prefetch Array with Four Streams

      The buffers in each stream are fully associative.  M-way set
associative denotes M streams, with buffers that are fully
addressable, i.e., the prefetch address(es) generated can go anywhere
in the stream  if the entry is not reserved.  This allows prefetching
of data that is  non-sequential.  This method uses comparators on all
the buffer entries  to allow hits or matches on any entry in the
prefetch array.  Since the  prefetch array is fully addressable,
entry deallocation is simple. If  data has returned for the entry and
an invalidation or deallocation condition is present, the entry can
transition to an "unreserved" state  the next cycle.  With this
scheme one or more buffer entries may be freed  when a new stream is
allocated without flushing the entire stream. This  is required if
using First In/First Out (FIFO) buffers.

      A buffer e...