Design and analysis issues for mixed-mode and heterogeneous parallel systems

Mixed-mode parallel processing systems are capable of executing in either the SIMD or MIMD mode of parallelism and are capable of switching between modes at instruction level granularity. This research develops architectural models and studies computational characteristics that impact the performance of mixed-mode systems. To attain high performance in the SIMD mode of parallelism, the computational power of both the control unit and processing elements should be used effectively to execute a single task. This research demonstrates how to increase the effectiveness of an SIMD architecture by allowing overlapped operation between the control unit and processing elements. The goal is to develop a model of overlapped operation so that the actual maximum possible performance of the SIMD machine can be attained. A model for an asynchronous message passing system is developed for a non-shared memory based machine operation in MIMD mode. This research develops an efficient asynchronous message passing system that can provide a broad scope of process interaction capability. To exploit the capability of intermixing both SIMD and MIMD operations within a single program, the optimum mapping of an algorithm to the mixed-mode architecture must be determined. One method of determining the optimum mapping is investigated by presenting a detailed study of a practical image processing application, the Edge Guided Thresholding algorithm, and its mapping to the PASM prototype, a mixed-mode system. An asynchronous implementation to trace the boundaries of regions in a segmented image is also developed using MIMD mode of parallelism. An algorithmic study examining the optimal parallelization method for computing multiple quadratic forms within the context of an adaptive beamformer calculation is presented. Specifically, coupled, uncoupled, and optimal parallel approaches are investigated, where coupling relates to the degree of interaction of processors. In addition to the mixed-mode related research, a model of a heterogeneous supercomputing environment is presented. It is shown how this model can be used to map tasks onto a suite of heterogeneous supercomputers. For complex tasks with various computational characteristics, performance can be maximized using a suite of heterogeneous machines. Specifically, the optimal selection theory for mapping subtasks to machines is augmented in this research