Randomization and Associativity in the Design of Placement-Insensitive Caches

[摘要] 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.

[发布机构] HP Development Company

[学科分类] 计算机科学（综合）