Multistage interconnection networks are a popular class of interconnection architecture for constructing scalable parallel computers (SPCs). The focus of this paper is on the multistage network system which supports wormhole routed turnaround routing. Existing machines characterized by such a system model include the IBM SP-1 and SP-2, TMC CM-5, and Meiko CS-2. Efficient collective communication among processor nodes is critical to the performance of SPCs. A system-level multicast service, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is fundamental in supporting collective communication primitives including the application-level broadcast, reduction, and barrier synchronization. This paper addresses how to efficiently implement multicast services in wormhole-routed multistage networks, in the absence of hardware multicast support, by exploiting the properties of the turnaround switching technology. An optimal multicast algorithm is proposed. The results of implementations on a 64-node SP-1 show that the proposed algorithm significantly outperforms the application-level broadcast primitives provided by currently existing collective communication libraries including the public domain MPI.

Data decomposition across processors is critical to the performance of data parallel programs on distributed-memory machines. The data decomposition problem involves data alignment and data distribution. This paper addresses the data alignment phase, which can be classified into slope alignment and offset alignment. We propose a data reference graph (DRG) model, based on which a slope alignment heuristic algorithm and an offset alignment heuristic algorithm are proposed for the purpose of minimizing interprocessor communication. Such a DRG-based data alignment framework makes our work unique from other related work. The time complexity of both proposed algorithms are in the linear order of distinct references given in a program structure.>

A critical issue in achieving the performance of data parallel programs is how to efficiently decompose data across processors. On distributed-memory machines, a good data decomposition should increase processor workload balance and reduce interprocessor communication. Data decomposition consists of data distribution and data alignment. In this paper, we propose a trapezoid data distribution pattern and new data alignment algorithms using alignment graph (AG). Our AG-based alignment framework is unique from other related work because it takes advantage of the effect of optimal expression evaluation with regard to multiple assignment statements.

Multistage interconnection networks are a popular class of interconnection architecture for constructing scalable parallel computers (SPCs). The focus of the paper is on wormhole routed multistage networks supporting turnaround routing. Existing machines characterized by such a system model include the IBM SP-1, TMC CM-5, and Meiko CS-2. Efficient collective communication among processor nodes is critical to the performance of SPCs. A system level multicast service, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is fundamental in supporting collective communication primitives including the application level broadcast, reduction, and barrier synchronization. The paper addresses how to efficiently implement multicast services in wormhole routed multistage networks, in the absence of hardware multicast support, by exploiting the properties of the switching technology. An optimal multicast algorithm is proposed. The results of implementations on a 64-node SP-1 show that the proposed algorithm significantly outperforms the application level broadcast primitives provided by currently existing collective communication libraries including the public domain MPI.>

Multicast communication, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is being increasingly demanded in parallel computing. System supported multicast services can potentially offer improved performance, increased functionality, and simplified programming, and may in turn be used to support various higher-level operations for data movement and global process control. This paper presents efficient algorithms to implement multicast communication in wormhole-routed direct networks, in the absence of hardware multicast support, by exploiting the properties of the switching technology. Minimum-time multicast algorithms are presented for n-dimensional meshes and hypercubes that use deterministic, dimension-ordered routing of unicast messages. Both algorithms can deliver a multicast message to m-1 destinations in [log/sub 2/ m] message passing steps, while avoiding contention among the constituent unicast messages. Performance results of implementations on a 64-node nCUBE-2 hypercube and a 168-node Symult 2010 2-D mesh are given.>

Determining an appropriate data distribution among different memories is critical to the performance of data-parallel programs on distributedmemory machines. By analyzing the computational load of data arrays and the communication cornplexity of various data movement operations in a program, this paper suggests a first-order cost model for determining a small set of appropriate data distribution patterns among many possible choices. A new data distribution specification, name! y CYBLOCK, is proposed to enhance the expressiveness of data distribution specifications being proposed in High Performance Fortran. Cost analysis of two case studies: a linear system solver and a Purdue-set benchmark loop, are used to illustrate the proposed evaluation method. The model correctly predicts the relative performance of the case studies when implemented with various regular data distributions on an nCUBE- 2 multicomputer.

This paper examines some crtttcal tssues raised in the design of libraries for MPCS, such as scalability, portability, recompilation, and flexibility.we adUocate a layered structure of it brary design, comprising a high-level language layer, a machine-independent node layer, a machine-dependent node layer, and an object code layer for diflerent demands and requirements.We discuss the impact of various data decomposition strategies on program performance and the computation and communication analysts techniques employed at different layers.We also propose the concept of the range of scalability as a metric for selectzng the most appropriate implementation.A linear system solver based on the Gaussian elimination method is used as an example to illustrate various design alternates.nessee and Oak Ridge National Laboratory attempts to provide a scalable LAPACK package for dense and banded matrix computations [3].The ComPaSS library being developed at Michigan State University attempts to provide a set of scalable communication

Practical and efficient implementations of barrier synchronization for wormhole-routed hypercube multicomputers are presented. Both broadcast and multicast barrier synchronization are considered. For systems that do not support hardware broadcast or multicast, a software U-cube tree is proposed. This method generalizes to n-dimensional meshes. Performance measurements for several barrier synchronization techniques implemented on a 64-node nCUBE-2 are given.>

The authors describe the initial implementation of the ComPaSS communication library to support scalable software development in massively parallel processors. ComPaSS provides high-level global communication operations for both data manipulation and process control, many of which are based on a small set of low-level communication primitives. The ComPaSS library is unique in that these low-level operations are provably optimal for a class of architectures representative of many commercial scalable systems-in particular, those using wormhole routing and n-dimensional mesh network topologies. The authors concentrate on the multicast component of the ComPaSS library, which is useful in several data parallel operations. The design of the multicast primitive is described, and an example of its use in a data parallel application is given. Improvements in performance resulting from use of the library on a 64-node nCUBE-2 are presented.>