Performance study of a clustered shared memory multiprocessor.

A shared memory multiprocessor having clusters of processing elements and memory modules is proposed. Since the delay through a multistage interconnection network, which increases logarithmically, can be large when the number of processors is large, clustering helps reduce the average delay to access a memory module. Each cluster has two others as its neighbors. The clusters are interconnected in such a way that the memory modules of a cluster can also be accessed by the processors of the neighboring clusters besides its own processors via its interconnection network. The coupling between the clusters provides flexibility for the scheduling of tasks. The processors and memory modules of all clusters are also connected to a shared interconnection network allowing the processors to access memory modules of the non-neighboring clusters. Generalized multistage interconnection networks are considered for both cluster and shared interconnection networks. The time required to access memory modules is reduced by scheduling tasks which share large data with each other on neighboring clusters or on the same cluster thereby providing a low latency path through the cluster interconnection network. The time to access memory modules in the non-neighboring clusters also decreases due to reduced contention and because of the reduction of requests through the shared interconnection network. Since the memory modules of a cluster are the main memory modules, an additional level of cluster memory is not required. This alleviates the data coherence problem. Average memory access time and b and width for the system are evaluated. A Markov chain model is developed for the circuit switching strategy and queueing models are used for the packet switching strategy. The circuit switching model is extended to include synchronized memory accesses. It is observed that updating of shared variables should not be unnecessarily delayed for the sake of desired task granularity. Simulations are performed to validate these models and to study the behavior of the architecture by relaxing some assumptions made for the analytic models. Sharing of network ports by the processors is also considered. A scheduling algorithm is proposed to assign tasks from directed acyclic task graph to processors using 0-1 integer programming and a lookahead technique. (Abstract shortened with permission of author.)PhDComputer scienceElectrical engineeringUniversity of Michiganhttp://deepblue.lib.umich.edu/bitstream/2027.42/162103/1/8907112.pd