Spiral cache memory and method of operating a spiral cache

Details Spiral cache memory and method of operating a spiral cache Spiral cache memory and method of operating a spiral cache

2008-11-13

2011-11-15

Rutz, Jared (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S118000

Reexamination Certificate

active

08060699

ABSTRACT:
A memory provides reduction in access latency for frequently-accessed values by self-organizing to always move a requested value to a front-most central storage element of a spiral. The occupant of the central location is swapped backward, which continues backward through the spiral until an empty location is swapped-to, or the last displaced value is cast out of the last location in the spiral. The elements in the spiral may be cache memories or single elements. The resulting cache memory is self-organizing and for the one-dimensional implementation has a worst-case access time proportional to N, where N is the number of tiles in the spiral. A k-dimensional spiral cache has a worst-case access time proportional to N1/k. Further, a spiral cache system provides a basis for a non-inclusive system of cache memory, which reduces the amount of space and power consumed by a cache memory of a given size.

REFERENCES:
patent: 5355345 (1994-10-01), Dickinson et al.
patent: 7107399 (2006-09-01), Bilardi et al.
patent: 2002/0116579 (2002-08-01), Goodhue et al.
patent: 2005/0114618 (2005-05-01), Lu et al.
patent: 2005/0132140 (2005-06-01), Burger et al.
patent: 2006/0212654 (2006-09-01), Balakrishnan
Akioka, et al., “Ring data location prediction scheme for Non-Uniform Cache Architectures,” International Conference on Computer Design, Piscataway 2008.
Jin, et al., “A Domain-Specific On-Chip Network Design for Large Scale Cache Systems,” 13thInternational Symposium on High-Performance Computer Architecture(HPCA-13). Phoenix, 2007.
Bilardi et al., “Optimal Organizations for Pipelined Hierarchical Memories”, SPAA '02, Aug. 2002, p. 109-116, Winnipeg, Manitoba, Canada.
Kwon et al., “A Scalable Memory System Design”, 10thInternational Conference on VLSI Design, Jan. 1997, p. 257-260.
Kim et al., “An Adaptive, Non-Uniform Cache Structure for Wire-Delay Dominated On-Chip Caches”, ASPLOS X, Oct. 2002, p. 211-222, San Jose, CA.
Baer et al., “On the Inclusion Properties for Multi-Level Cache Hierarchies”, IEEE, Feb. 1988, p. 73-80.
Dickinson et al., “A Systolic Architecture for High Speed Pipelined Memories”, IEEE, 1993, p. 406-409.
Beckmann et al., “Managing Wire Delay in Large Chip-Multiprocessor Caches”, 37th Annual IEEE/ACM International Symposium on Microarchitecture, Dec. 2004, p. 319-330, Portland, OR.
Chishti et al., “Distance Associativity for High-Performance Energy-Efficient Non-Uniform Cache Architectures”, 36th Annual IEEE/ACCM International Symposium on Microarchitecture, Dec. 2003, 55-66, San Diego, CA.
Dybdahl et al., “An Adaptive Shared/Private NUCA Cache Partitioning Scheme for Chip Multiprocessors”, 13th International Symposium on High Performance Computer Architecture, Feb. 2007, p. 2-12, Phoenix, AZ.
Foglia et al, “A NUCA Model for Embedded Systems Cache Design”, 3rd IEEE Workshop on Embedded Systems for Real-Time Multimedia, Sep. 2005, p. 41-46, New York, NY.
Huh et al., “A NUCA Substrate for Flexible CMP Cache Sharing”, International Conference on Supercomputing, Jun. 2005, p. 31-40, Boston, MA.
Muralimanohar et al., “Optimizing NUCA Organizations and Wiring Alternatives for Large Caches With CACTI 6.0”, 40th Annual IEEE/ACM International Symposium on Microarchitecture, Dec. 2007, p. 3-14, Chicago, IL.
Abella et al., “Power Efficient Data Cache Designs”, IEEE Computer Society, Oct. 2003, p. 3-8, San Jose, CA.
Gilbert et al., “Variable-Based Multi-Modual Data Caches for Clustered VLIW Processors”, IEEE Computer Society, Sep. 2005, p. 3-13, St. Louis, MO.
Gonzales et al., “A Data Cache with Multiple Caching Strategies Tuned to Different Types of Locality”, ACM, 1995, p. 338-347.
Lee et al., “Region-Based Caching: An Energy Delay Efficient Memory Architecture for Embedded Processors”, CASES, 2000, p. 120-127.
U.S. Appl. No. 12/264,682, filed Nov. 4, 2008, Li et al.

Affiliated with

Also associated with

Rating

Spiral cache memory and method of operating a spiral cache does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Spiral cache memory and method of operating a spiral cache, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spiral cache memory and method of operating a spiral cache will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4301044