Electrical computers and digital processing systems: memory – Addressing combined with specific memory configuration or... – Addressing cache memories
Reexamination Certificate
2011-06-21
2011-06-21
Bragdon, Reginald G (Department: 2189)
Electrical computers and digital processing systems: memory
Addressing combined with specific memory configuration or...
Addressing cache memories
C711S125000, C711S126000, C711S216000, C711SE12016, C726S023000
Reexamination Certificate
active
07966442
ABSTRACT:
In general, this disclosure describes techniques of storing data in and retrieving data from a cache of a computing device. More specifically, techniques are described for utilizing a “perfect hash” function to implement an associative cache within a computing device. That is, the associative cache implements a fully associative map between a predetermined set of addresses and data values, employing only a single tag fetch comparison.
REFERENCES:
patent: 5530958 (1996-06-01), Aggarwal et al.
patent: 5694567 (1997-12-01), Bourekas et al.
patent: 6161166 (2000-12-01), Doing et al.
patent: 6275919 (2001-08-01), Johnson
patent: 7290116 (2007-10-01), Grohoski et al.
patent: 7743200 (2010-06-01), Panwar et al.
patent: 2003/0196026 (2003-10-01), Moyer
patent: 2006/0004995 (2006-01-01), Hetherington et al.
F. C. Botelho et al., “A New Algorithm for Constructing Minimal Perfect Hash Functions,” Technical Report TR004/04, Department of Computer Science, Federal University of Minas Gerais, 2004.
F. C. Botelho et al., “A Practical Minimal Perfect Hashing Method,” 4th International Workshop on Efficient and Experimental Algorithms (WEA05), Springer-Verlag Lecture Notes in Computer Science, vol. 3503, Santorini Island, Greece, May 2005, 488-500.
Z.J. Czech et al., “An optimal algorithm for generating minimal perfect hash functions,” Information Processing Letters, 43(5):257-264, 1992.
E.A. Fox et al., “A Faster Algorithm for Constructing Minimal Perfect Hash Functions,” In Proc. 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 266-273, 1992.
Bob Jenkins, “An order preserving minimal perfect hashing algorithm,” available at http://burtleburtle.net/bob/hash/perfect.html (last visited Apr. 4, 2007).
Hallnor, Erik G. and Steven K. Reinhardt, “A Fully Associative Software-Managed Cache Design,” Jun. 2000, ACM, ISCA 2000.
Beale, Jay; Renaud Deraison; Harron Meer; Roelof Temmingh; and Charl Van Der Walt, Snort 2.0 Intrusion Detection, Mar. 1, 2003, Syngress, Section 1.2.
Vandierendonck, Hans; Philippe Manet; and Jean-Didier Legat, “Application-Specific Reconfigurable XOR-Indexing to Eliminate Cache Conflict Misses,” Mar. 2006, IEEE 2006.
Hogg, Robert V. and Elliot A. Tanis, Probability and Statistical Inference, 2001, Prentice-Hall Inc. 6th ed. pp. 5-8.
Panwar Ramesh
Thomas Philip A.
Bragdon Reginald G
Juniper Networks, Inc.
Sadler Nathan
Shumaker & Sieffert P.A.
LandOfFree
Cache using perfect hash function does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cache using perfect hash function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache using perfect hash function will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2724636