Performance study of shift-folding skewing schemes for interleaved memory systems

If computer system main memory modules can be arranged so that they constitute several independently working modules, then it would allow overlapping of multiple memory accesses and the simultaneous sharing of memory among several processors and peripherals. To take full advantage of this parallelism, addresses must be distributed across the modules in a way that minimizes congestion. Functions of the form f : A→M, where A is the domain of addresses and M is the domain of module numbers, are called skewing functions. The correct choice of f can satisfy the need of minimal congestion. Skewing schemes of a particular type are shown to be similar to shift-folding hashing functions. A recent proposal by researchers at Rice University is extended and shown to be a shift-folding function. The scheme was evaluated using the codes from the Livermore Fortran kernels with the help of a general memory module simulator. The results seem to indicate a 50% utilization of the potential parallelism, in situations similar to this code where the programs are not fully vectorizable