Memory architectures for vector processing
Ramanathan Raghavan · Deep Blue (University of Michigan) · 1991
Vector supercomputers, which can process large amounts of vector data efficiently, are among the fastest computers available today. For efficient memory access, these machines use interleaved memories in which sets of consecutive addresses are assigned to separate memory banks. However, when several memory requests access the same bank simultaneously, they interfere with one another causing a significant performance loss. Our thesis addresses this problem of memory interference in vector computers with the goal of analyzing the behavior of current interleaved memory designs and finding ways in which higher performance can be achieved. Using an analytical model for modular interleaved memories, we first derive a new and complete set of conditions for placing multiple vectors in memory so that several vectors can be accessed concurrently without conflict. Meeting these conditions becomes harder as the number of concurrent vector accesses increases. An alternative technique is to place buffers at the individual memory banks to hold conflicting requests. Both methods are shown to be useful only when the bank cycle time is low relative to the number of banks. We then analyze an interleaving method recently proposed in which regular address sequences are mapped into pseudo-random sequences, and show that it leads to avoidable memory conflicts. To remedy this problem, we construct a new and practical class of random interleaving schemes that use multiplicative hashing for randomization. We present simulation results showing that our schemes result in significantly higher efficiency than those proposed by others. Finally, we employ both probabilistic and deterministic analyses to determine the scaling properties of modular interleaved memories. These properties provide general guidelines for building the memory systems for future vector computers.