Compile-time selection of parallel modes in an SIMD/SPMD heterogeneous parallel environment

This document examines the effects of computational mode on the performance of parallel applications. The purpose of this work is two-fold. First, the way in which differences in computational mode can be exploited are examined. This is done by analyzing language elements and algorithm segments executed on the PASM (PArtitionable SIMD/MIMD) machine. Selected examples of how tasks can be mapped onto PASM are surveyed, demonstrating how PASM\u27s reconfigurability can be used. The Explicit Language for Parallelism (ELP), a mode-independent language that serves as an example programming model needed for automatic computational mode selection, is overviewed, and recent efforts in the language development are summarized. Second, the knowledge gained by this analysis is used to determine ways in which the advantages of each mode can be quantified, so that beneficial mode-mapping decisions can be made by automatic analysis tools during the compilation of parallel programs. A framework is proposed for the compile-time analysis of execution time for data-independent algorithms written in a mode-independent language, to be implemented in an SIMD/SPMD heterogeneous environment with constant mode-switching costs. The framework is then extended to include heterogeneous environments where the cost of switching between modes carries a high cost, dependent upon the amount of data that is required to move from one mode/machine to another as a result of a mode change. A feasibility study of the decision process is included to provide a proof-of-concept argument for this approach. Also included is an algorithm study for the segmentation of range data images that illustrates some of the challenges that must be addressed when mapping serial algorithms onto a mixed-mode parallel machine