HP Labs Technical Reports

Randomization and Associativity in the Design of Placement-Insensitive Caches

Schlansker, Michael S.; Shaw, Robert; Sivaramakrishnan, Sivaram

HPL-93-41

Keyword(s):

Abstract: This paper presents a design for a randomized, placement-insensitive, data cache and analyzes its performance, An address stream is randomized using a hash function which selects a set in an associative cache. The manipulation of large data structures is modeled by traversal of a cyclic sweep address sequence and the miss ratio is accurately determined for this sequence. A purely analytic approach to determine cache performance is developed. Analysis predicts regions in which a placement- insensitive cache operates with very few cache misses. A pseudo-random hash function is presented and used to randomize addresses into cache sets and a counting technique is used to determine miss ratios. Finally, an actual cache is simulated allowing comparison against theory. A matrix multiply program is studied demonstrating a close relationship between analysis and at least one real application.

Back to Index