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.