Spatial footprint prediction

Details Spatial footprint prediction Spatial footprint prediction

1997-11-21

2003-03-18

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S213000, C712S207000

Reexamination Certificate

active

06535961

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates to computers and, more particularly, to spatial footprint prediction of usage of cache-lines from main memory by a computer.
2. Background Art
Caches hold a relatively small amount of data that can be accessed relatively quickly by a processor. By contrast, main memory holds a relatively large amount of data that is accessed relatively slowly by a processor. Caches are organized into cache-lines. Typically, the smallest replaceable unit in a cache is a cache-line. In many computer systems, a cache-line has 32 or 64 bytes. There are at least two advantages to having large cache-lines. First, a tag is used to identify each cache-line. Therefore, the larger the cache-line, the fewer the number of tags and associated resources that are used for a given amount of data stored in the cache. Second, there is substantial latency in fetching data from main memory. Therefore, it is desirable to reduce the number of fetches from memory. In most applications, there is spatial locality with respect to memory references used. That is, if a program uses data from a reference to address X, there is a fair likelihood that in the near future the program will also use data from a reference to adjacent addresses X+1 and/or X−1. Therefore, by fetching large cache-lines, there is a likelihood that fewer caches lines will need to be access from main memory.
In general larger cache-lines improve performance when spatial locality is available, but may hurt performance by prefetching unnecessary data when there is no spatial locality. For example, a piece of data requested by the processor may have only four bytes. If there is no spatial locality, there may be 28 wasted bytes, in the case of a 32-byte cache-line. Further, accessing the four bytes may have caused eviction of other bytes from the evicted line that would have been used resulting in another access from main memory. Because spatial locality may differ between different applications as well as between different sequences of memory references within a single application, cache designers generally choose a line size with the best average performance across a broad range of reference patterns. This approach wastes bandwidth when a sequence of memory references does not exhibit spatial locality. Further, the cache is polluted by cache-lines that are not needed because the cache-lines can be written over data that would be used.
The present invention is directed to overcoming or reducing the effect of one or more the above-recited problems with access to main memory.
SUMMARY OF THE INVENTION
A spatial footprint predictor includes a mechanism to measure spatial footprints of nominating cache-lines and hold the footprints. In some embodiments, the mechanism includes an active macro-block table (AMBT) to measure the spatial footprints and a spatial footprint table (SFT) to hold the spatial footprints. In other embodiments, the mechanism includes a macro-block table (MBT) in which macro-blocks may be active or inactive.


REFERENCES:
patent: 4774654 (1988-09-01), Pomerene et al.
patent: 4980823 (1990-12-01), Liu
patent: 5704053 (1997-12-01), Santhanam
patent: 5778436 (1998-07-01), Kedem et al.
patent: 5941980 (1999-08-01), Shang et al.
Przybylski, Steven, “The Performance Impact of Block Sizes and Fetch Strategies”, Proceedings of the 17th Annual International Symposium on computer Architecture, Seattle, Washington, May 28-31, 1990, pp. 160-169.
Seznec, Andre, “Decoupled Sectored Caches: Conciliating Low Tag Implementation Cost and Low Miss Ratio”, Proceedings of the 21st Annual International Symposium on Computer Architecture, Chicago, Illinois, Apr. 18-21, 1994, pp. 384-393.
Tyson, Gary et al., “A Modified Approach to Data Cache Management”, IEEE Proceedings of MICRO-28, 1995, pp. 93-103.

Affiliated with

Also associated with

Rating

Spatial footprint prediction does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Spatial footprint prediction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spatial footprint prediction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3072490