International Business Machines Corporation

Evelyn A Melton

Vern A Norton

Gregory Francis Pfister

Kimming K So

Keven P McAuliffe

Scott P Wakefield

Gregoty F Pfister

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.times.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.

Mechanism for improving the randomization of cache accesses utilizing

An aperiodic mapping procedure for the mapping of logical to physical addresses is defined as a permutation function for generating optimized stride accesses in an interleaved multiple device system such as a large, parallel processing shared memory system wherein the function comprises a bit-matrix multiplication of a presented first (logical) address with a predetermined matrix to produce a second (physical) address. The permutation function maps the address from a first to a second address space for improved memory performance in such an interleaved memory system. Assuming that the memory has n logical address bits and 2.sub.d separately accessible memory devices (where d.ltoreq.n) and a second address that utilizes n-d bits of the first address as the offset within the referenced device node. The procedure includes performing a bit matrix multiplication between successive roows of the said matrix and bits of the first address to produce successive d bits of the second address.

Aperiodic mapping system using power-of-two stride access to interleaved

Growing community of inventors

Poughkeepsie, NY, United States of America

Evelyn A Melton