Distributed shared memory multiprocessors using multistage bus networks

Abstract

Distributed shared memory (DSM) multiprocessors rely heavily on the interconnection network performance. The Multistage Bus Network (MBN) is analyzed in this thesis for a DSM environment. The MBN avoids some of the shortcomings of the conventional multistage interconnection networks(MINs), single bus and hierarchical bus interconnection networks. A switch in a MBN is similar to that in a MIN switch except that there is a single bus connection instead of a crossbar. MBNs support bidirectional routing and there exists a number of paths between any source and destination pair. Four self routing techniques are reviewed and an algorithm to route a request along the path with minimum distance is presented. An analysis of the probabilities of a packet taking different routes is also derived. Further, the performance analysis of a synchronous packet switched MBN in a distributed shared memory environment is derived and comparison of the results with those of an equivalent bidirectional MIN (BMLN) is discussed. The queueing analysis is verified by exhaustive cycle-by-cycle simulations with a synthetic workload. The execution time of various applications on the MBN and the BMIN is obtained through an executiondriven simulation. The MBN is shown to provide similar performance to BMIN while offering simplicity in hardware and more fault-tolerance than a conventional MIN. To further improve the performance of the DSM multiprocessor, memory management policies based on static page allocation are studied. Different techniques to determine the position of a page based on the processor that generates the page fault are presented. Two different interleaving policies, high-order and low-order with the page placement policies are used to try and better distribute the traffic in the system and reduce the average message latency and execution time. By incorporating these policies into an execution-driven simulator, it is shown that the page placement policy with low-order interleaving performs best for most of the applications. The suggested page placement policies are shown to be effective techniques for distributing the data over the shared memory and reducing the execution time by a certain degree.