Extending memory hierarchy into multiprocessor interconnection networks
Haim Mizrahi, J.-L. Baer · Proceedings of the International Conference on Parallel Processing · 1988
The speed with which processors can access memory is critical to the performance of scaleable, shared-memory parallel computers. An important factor in the effective memory access time is the interconnection network that connects processors and memories. In this dissertation we propose and analyze a novel interconnection network in which data is stored at each switch of the network and may change location dynamically in response to the processors' request patterns. By allowing dynamic routing capabilities and by putting memory into each switch element we create a hybrid network offering the best features of uniform and non-uniform memory distance architectures. In contrast to uniform distance networks, locality of reference can be exploited by placing a data item near the processors currently referencing it. In contrast to static mapping of data onto non-uniform distance networks, the dynamic movement mechanism allows the system to accommodate efficiently software that exhibits phases with differing reference patterns or for which the reference pattern may depend heavily on the data. Finally, in contrast to multiple copy caching schemes, there is only a single copy of any data item in the system, and so there is no need for coherency protocols. Of course, some price must be paid for the additional power of this network. In particular, there are increases in design complexity and dynamic overhead (cycle times) of the switch elements. The major focus of this study is the determination of the performance benefits that can be realized by such a network, taking into account the runtime overheads. Possible implementations of the switch elements, the associated protocols, and their relative cost and performance, are also presented. The suggested architecture requires memory which is beyond the capabilities of current technology, but it will become feasible in the near future. The dissertation's conclusion is that the suggested architecture is expected to perform much better than conventional networks over a wide range of assumptions about reference behavior.