Properties of the Augmented Data Manipulator Network in a SIMD Environment.
Abstract
The demand for computers with ever greater throughput coupled with the decreased costs accompanying advances in semiconductor technology has created a great deal of interest in parallel processing systems. Single instruction stream - multiple data stream (SIMD) machines and multiple instruction stream - multiple data stream (MIMD) machines are two types of parallel processing system architectures. PASM is a partitionable SIMD/MIMD parallel processor, intended to operate in either mode of parallelism, being developed at Purdue University. The interconnection network chosen for this system will greatly influence its performance. The Generalized Cube and the Augmented Data Manipulator (ADM) are two networks being considered for use in PASM. This work is primarily concerned with the capabilities of the ADM network in SIMD mode. The number of data permutations passable by the ADM network is explored. Routing tag schemes are described for both the Generalized Cube and ADM networks. Algorithms for determining permutation passability in the ADM network using three related types of routing tags for distributed network control are presented. Correctness proofs are given and algorithm complexity determined. To further investigate ADM network capabilities in SIMD mode, group theory is used to derive additional properties. It is shown that the ADM network cannot pass all even permutations when N > or = 8.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1980
- Accession Number
- ADA096399
Entities
People
- George B. Adams Iii
- Howard Jay Siegel
Organizations
- Purdue University