![Sample our Computer Science journals, sign in here to start your access, latest two full volumes FREE to you for 14 days]({"type":"image" , "src" : "/sda/5928/TOC-Subject-Sample-2021-Computer-Science.jpg"})
Abstract
We focus on differences inherent in the design and implementation of non-numeric parallel algorithms on MIMD and SIMD architectures. We take as our prototypical examples time-space optimal merging and sorting routines. Our representative MIMD and SIMD machines are the Sequent Symmetry S81 and the Connection Machine CM-2, respectively. In addition to the contrast provided by their differing execution philosophies, this choice of machines allows us to compare results from both shared-memory and distributed-memory models.
Unlike many numerical parallel algorithms, non-numeric parallel programs are rarely well structured with respect to inter-processor cooperation, memory access and communication patterns. This is particularly apparent when one must deal with delicate issues such as process synchronization in the MIMD model and coding variations in the SIMD model.
Our 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 arc useful in identifying important bottlenecks. We discuss some relative strengths and weaknesses of the two competing models that have become evident during this transformation process.
Notes
∗ A preliminary version of this paper was presented at the 26th Hawaii International Conference on System Sciences, held on the island of Maui, Hawaii, in January, 1993.
†This research has been supported in part by the National Science Foundation under grant MIP-8919312 and by the Office of Naval Research under contract N00014-90-J-1855.