Randomization and Associativity in the Design of Placement-Insensitive Caches
Michael Schlansker, Robert Shaw, Sivaram Sivaramakrishnan · 1993
cache memory, associative, stride, random, hashing, set lookup, data placement 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.