Mechanism for improving the randomization of cache accesses utilizing abit-matrix multiplication permutation of cache addresses

摘要

An electronic computer system including a central processor and a hierarchical memory system having a large relatively low speed random access system memory and a small high speed set-associative cache memory including a data store section for storing lines of data from the system memory and a cache directory for indicating, by means of line identifier fields at any time, the lines of the system memory data currently resident in cache, is provided with a way to improve the distribution of data across the congruence classes within the cache. A mechanism is provided for performing a permutation operation on an M bit portion (X) of the system memory address, which permutation determines the congruence class into which the address will map. The permutation mechanism performs a bit-matrix multiplication of said M-bit address with an M×M matrix (where M is a real positive integer greater than 1) to produce a permuted M-bit address (X'). The directory controls utilize the permuted M-bit address (X') to determine the congruence class of any given memory access and automatically access the congruence class of the permuted address (X') subsequent to the permutation operation to determine if one of the line identifiers which identifies, every member of a congruence class currently stored in the directory, matches an identifier field from the memory access request from the CPU. If the match is successful the data store portion of the cache is accessed at the permuted M-bit address (X') and the requested data line is accessed at the address field specified by the CPU.