Selected software issues for mapping tasks onto parallel processing systems

This dissertation describes selected software issues of mapping tasks onto parallel processing systems that are shown to have a strong effect on performance. It can be divided into two related categories: (1) parallel mapping studies, and (2) an analysis of dynamic task migration for fault-tolerance, load balancing, and various other administrative reasons. The first category consists of two application case studies, specifically, the computation of multiple quadratic forms and image correlation. The goal of this part of the work is to understand the relationship between parallel system features (e.g., mode of parallelism supported, number of processors available, communication speed, computation speed) and parallel algorithm characteristics (e.g., amount of data-parallelism available, amount of functional-parallelism available, amount of scalar computation present). The knowledge obtained from the parallel mapping studies provided the foundation necessary to investigate the second category, the task migration work. This research involved developing a method to migrate dynamically a task between a SIMD (single instruction stream-multiple data stream) machine and a SPMD (single program-multiple data stream) machine. It is assumed that the SIMD and SPMD machines only differ to support the different modes of parallelism, and that the program was coded in a mode-independent programming language. This area of research targets systems that are either a network of different types of computers or a single system that can support multiple modes of parallelism