Title :
MIMD versus SIMD computation: experience with non-numeric parallel algorithms
Author :
Breshears, Clay ; Langston, Michael A.
Author_Institution :
Dept. of Comput. Sci., Tennessee Univ., Knoxville, TN, USA
Abstract :
The authors study the design and implementation issues for nonnumeric parallel algorithms on multiple instruction/multiple data (MIMD) and single instruction, multiple data (SIMD) machines. Prototypical examples considered are time-space optimal merging and sorting routines. The representative MIMD and SIMD machines are the Sequence Symmetry SSI and the Connection Machine CM-2. The conversion of shared-memory parallel codes to the data parallel paradigm is described. The experiences are highlighted with examples obtained during the process of MIMD to SIMD program transformation. Unexpected events can occur when algorithms designed with one architectural style in mind are modified for execution on another. Timings and other measurements are useful in identifying important bottlenecks. Some relative strengths and weaknesses of the two competing models that have become evident during this transformation process are discussed
Keywords :
merging; parallel algorithms; shared memory systems; sorting; Connection Machine CM-2; MIMD computation; SIMD computation; Sequence Symmetry SSI; data parallel paradigm; nonnumeric parallel algorithms; shared-memory parallel codes; sorting routines; time-space optimal merging; Algorithm design and analysis; Computer architecture; Computer science; Concurrent computing; Contracts; Hypercubes; Merging; Parallel algorithms; Scalability; Timing;
Conference_Titel :
System Sciences, 1993, Proceeding of the Twenty-Sixth Hawaii International Conference on
Conference_Location :
Wailea, HI
Print_ISBN :
0-8186-3230-5
DOI :
10.1109/HICSS.1993.284098
