Electrical computers and digital processing systems: memory – Address formation – Hashing
Reexamination Certificate
2007-10-30
2007-10-30
Bragdon, Reginald (Department: 2189)
Electrical computers and digital processing systems: memory
Address formation
Hashing
C711S003000, C711S130000, C711S202000
Reexamination Certificate
active
10881714
ABSTRACT:
An apparatus and method for mapping memory addresses to reduce or avoid conflicting memory accesses in memory systems such as cache memories is described in connection with a multithreaded multiprocessor chip. A CMT processor reduces the probability of hot-spots in cache operations by hashing certain bits of a physical cache address to form a hashed cache address. By using exclusive OR functionality to hash the index bits, an efficient address transformation is achieved for indexing into an L2 cache memory.
REFERENCES:
patent: 5446854 (1995-08-01), Khalidi et al.
patent: 5465337 (1995-11-01), Kong
patent: 5479627 (1995-12-01), Khalidi et al.
patent: 5596293 (1997-01-01), Rogers et al.
patent: 5712791 (1998-01-01), Lauterbach
patent: 5717885 (1998-02-01), Kumar et al.
patent: 5742792 (1998-04-01), Yanai et al.
patent: 5761511 (1998-06-01), Gibbons et al.
patent: 5761707 (1998-06-01), Aiken et al.
patent: 5802341 (1998-09-01), Kline et al.
patent: 5802561 (1998-09-01), Fava et al.
patent: 5828860 (1998-10-01), Miyaoku et al.
patent: 5842225 (1998-11-01), Kohn
patent: 5860147 (1999-01-01), Gochman et al.
patent: 5862450 (1999-01-01), Mandal et al.
patent: 5895487 (1999-04-01), Boyd et al.
patent: 5899994 (1999-05-01), Mohamed et al.
patent: 5900011 (1999-05-01), Saulsbury et al.
patent: 5911071 (1999-06-01), Jordan
patent: 5918005 (1999-06-01), Moreno et al.
patent: 5933627 (1999-08-01), Parady
patent: 5953010 (1999-09-01), Kampe et al.
patent: 5956756 (1999-09-01), Khalidi et al.
patent: 5991790 (1999-11-01), Shah et al.
patent: 6016542 (2000-01-01), Gottlieb et al.
patent: 6044446 (2000-03-01), Joy et al.
patent: 6092154 (2000-07-01), Curtis et al.
patent: 6098169 (2000-08-01), Ranganathan
patent: 6105127 (2000-08-01), Kimura et al.
patent: 6141692 (2000-10-01), Loewenstein et al.
patent: 6199142 (2001-03-01), Saulsbury et al.
patent: 6247121 (2001-06-01), Akkary et al.
patent: 6272520 (2001-08-01), Sharangpani et al.
patent: 6295600 (2001-09-01), Parady
patent: 6308279 (2001-10-01), Toll et al.
patent: 6311261 (2001-10-01), Chamdani et al.
patent: 6314563 (2001-11-01), Agesen et al.
patent: 6374349 (2002-04-01), McFarling
patent: 6408368 (2002-06-01), Parady
patent: 6415356 (2002-07-01), Chaudhry et al.
patent: 6449694 (2002-09-01), Burgess, Jr. et al.
patent: 6493819 (2002-12-01), Mahurin et al.
patent: 6535905 (2003-03-01), Kalafatis et al.
patent: 6578137 (2003-06-01), Parady
patent: 6609193 (2003-08-01), Douglas et al.
patent: 6625654 (2003-09-01), Wolrich et al.
patent: 6633984 (2003-10-01), Susser et al.
patent: 6647458 (2003-10-01), Glynn
patent: 6671707 (2003-12-01), Hudson et al.
patent: 6700410 (2004-03-01), Ebergen
patent: 6700825 (2004-03-01), Ebergen
patent: 6715057 (2004-03-01), Kessler et al.
patent: 6718438 (2004-04-01), Lewis et al.
patent: 6718494 (2004-04-01), Jamil et al.
patent: 6732143 (2004-05-01), Saulsbury
patent: 6751655 (2004-06-01), Deutsch et al.
patent: 6766428 (2004-07-01), Saulsbury et al.
patent: 6772369 (2004-08-01), Smith et al.
patent: 6779087 (2004-08-01), Saulsbury et al.
patent: 6802039 (2004-10-01), Quach et al.
patent: 6816961 (2004-11-01), Rice et al.
patent: 6854075 (2005-02-01), Mukherjee et al.
patent: 6862027 (2005-03-01), Andrews et al.
patent: 7003648 (2006-02-01), Chrysos et al.
patent: 7130967 (2006-10-01), Arimilli et al.
patent: 2001/0047468 (2001-11-01), Parady
patent: 2002/0052926 (2002-05-01), Bush et al.
patent: 2002/0087840 (2002-07-01), Kottapalli et al.
patent: 2002/0129309 (2002-09-01), Floyd et al.
patent: 2002/0162092 (2002-10-01), Ravichandran
patent: 2002/0199070 (2002-12-01), Chaudhry et al.
patent: 2003/0088610 (2003-05-01), Kohn et al.
patent: 2003/0088713 (2003-05-01), Mandal et al.
patent: 2003/0097518 (2003-05-01), Kohn et al.
patent: 2003/0105756 (2003-06-01), Daynes
patent: 2003/0105907 (2003-06-01), Kohn et al.
patent: 2003/0120825 (2003-06-01), Avvari et al.
patent: 2003/0149861 (2003-08-01), Becker
patent: 2003/0163645 (2003-08-01), Tremblay et al.
patent: 2003/0191927 (2003-10-01), Joy et al.
patent: 2003/0196066 (2003-10-01), Mathews
patent: 2003/0212874 (2003-11-01), Alderson
patent: 2004/0002974 (2004-01-01), Kravitz et al.
patent: 2004/0003208 (2004-01-01), Damron
patent: 2004/0003211 (2004-01-01), Damron
patent: 2004/0006633 (2004-01-01), Chandra et al.
patent: 2004/0034853 (2004-02-01), Gibbons et al.
patent: 2004/0073906 (2004-04-01), Chamdani et al.
patent: 2004/0088487 (2004-05-01), Barroso et al.
patent: 2004/0098496 (2004-05-01), Wolrich et al.
patent: 2004/0117600 (2004-06-01), Bodas et al.
patent: 2004/0123028 (2004-06-01), Kanai et al.
patent: 2004/0148472 (2004-07-01), Barroso et al.
patent: 2005/0114856 (2005-05-01), Elckemeyer et al.
patent: 2005/0193283 (2005-09-01), Reinhardt et al.
R. Heald et al., “A Third-Generation SPARC V9 64-b Microprocessor,” IEEE JSSC, Nov. 2000, pp. 1526-1538.
“Introduction to Throughput Computing,” Sun Microsystems whitepaper, Feb. 2003.
D. Wendell et al., “A 4 MB On-Chip L2 Cache for a 90nm 1.6GHz 64 bit Microprocessor,” IEEE JSSC (Feb. 2004).
G. Konstadinidis et al., “Implementation of a Third-Generation 1.1GHz 64b Microprocessor,” 2002 IEEE Journal of Solid-State Circuits, vol. 37, No. 11, pp. 1461-1469 (Nov. 2002).
K. Krewell, “Sun Weaves Multithreaded Future,” Microprocessor Report, Reed Electronics Group (Apr. 14, 2003).
“UltraSPARC® IV Processor,” User's Manual Supplement, Sun Microsystems, version 1.0 (Apr. 2004).
“The UltraSPARC® IIIi Processor” Architecture Overview, Technical Whitepaper, Sun Microsystems, version 1.2 (Apr. 2004).
“UltraSPARC® IV Processor,” Architecture Overview, Technical Whitepaper, Sun Microsystems, Version 1.0 (Feb. 2004).
R. Ronen, “VLSI Architecture Design Course,” Lecture #10, Multithreaded Architectures (dated May 2003).
K. Mai et al., “Smart Memories: A Modular Reconfigurable Architecture,” Stanford University Proceedings of the 17thISCA (Jun. 2000).
L. Hammond et al., “The Standford Hydra CMP,” IEEE Micro, pp. 71-84, (Mar.-Apr. 2000).
L. Hammond et al., “Considerations in the Design of Hydra: A Multiprocessor-on-a-Chip Microarchitecture,” Technical Report No.: CSL-TR-98-749, pp. 1-10 (Feb. 1998).
K. Privitt, et al., “Threading: Connecting the Pieces, System Architecture, Application, OS and Tools,” Intel Developer Forum (Feb. 17-19, 2004).
M. Kharbutli et al., “Using Prime Numbers for Cache Indexing to Eliminate Conflict Masses,” 10thAnnual Symposium on High Performance Computer Architecture (Feb. 14-18, 2004).
Mukherjee, S. et al., “Detailed Design and Evaluation of Redundant Multithreading Alternatives,” Computer Architecture, 2002, Proceedings 29th Annual International Symposium, pp. 1-12.
Reinhardt, S.K. et al., “Transient Fault Detection via Simultaneous Multithreading,” Computer Architecture, 2000, Proceedings of the 27th International Symposium, 12 pages.
Kalla, R. et al., “IBM Power5 Chip: A Dual-Core Multithreaded Processor,” Published by the IEEE Computer Society, Mar.-Apr. 2004, pp. 40-47.
Watanabe, K. et al., “Exploiting Java Instruction/Thread Level Parallelism with Horizontal Multithreading,” IEEE, 2001, pp. 122-129.
Chen, S. et al., “Out-of-Order Memory Accesses Using a Load Wait Buffer,” http://www.ece.cmu.edu/˜schen1/18-741—final—report.pdf, pp. 1-8, published Feb. 2003.
“Igniting a Computing Revolution! Throughput Computing,” Sun Microsystems Brochure, published Sep. 2003.
“UltralSPARC® IV Processor,” Datasheet, Sun Microsystems, published Jan. 2004.
Hennessy, J. et al., “Computer Architecture: A Quantitative Approach,” Morgan Kaufmann, third edition, 2002, pp. A-68 to A-77.
Hoe, J.C. “Superscalar Out-of-Order Dernystified in Four Instructions,” 2003, http://www.ece.cmu.edu/˜jhoe/distribution/2003/wcae03.pdf, pp. 1-6.
Chen, S. et al.,
Davis John D.
Fu Cong
Gibson Jeff
Grohoski Greg F.
Iyengar Venkatesh
Bragdon Reginald
Darby & Darby PC
Flournoy Horace L.
Ream M. David
Sun Microsystems Inc.
LandOfFree
Level 2 cache index hashing to avoid hot spots does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Level 2 cache index hashing to avoid hot spots, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Level 2 cache index hashing to avoid hot spots will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3854485