Language, compiler, and architectural modeling aspects of reconfigurable parallel processing systems

Several parallel machines exist that have the ability to reconfigure various facets of their architectures at execution-time. Specific facets include the ability to reconfigure the mode of parallelism for machine execution (i.e., a mixed-mode system) and the ability to partition the machine into independent or cooperating submachines (i.e., a partitionable system). This work addresses language, compiler, and architectural modeling aspects relevant to such reconfigurable systems. The contributions made by this research can be put toward the overall goal of improving the design of languages and compilers for reconfigurable systems. The SPMD (Single Program - Multiple Data) mode of parallelism is a subset of the MIMD mode where all processors execute the same program. By providing all aspects of an explicitly parallel programming language with both SIMD mode and SPMD mode interpretations that are syntactically and semantically equivalent, the language can facilitate experimentation with and exploitation of hybrid SIMD/SPMD machines. Features of such a language targeted for reconfigurable systems, where the machine\u27s processors are capable of operating in both the SIMD and SPMD modes of parallelism, are described. Many advantages, e.g., support for fault tolerance, can be exploited when a compiler is capable of generating code for more than one mode of parallelism. Efficient data layout is an important part of compilation for a parallel target machine. The major constraint on solving this problem with respect to user-specified partitionable SIMD and/or partitionable SPMD tasks is based on the single program nature of both the SIMD and SPMD modes of parallelism. Specifically, it is assumed all PEs within the same submachine use identical addresses to access corresponding data items in each of their local memories. A method (adhering to this addressing constraint) to create fragment-free memory maps for any task executed on a partitionable SIMD/SPMD machine is provided. This result can be applied to commercial machines whose partitionability is based on interconnection networks. By overlapping the operation of the control unit and processing elements within an SIMD machine, the execution times of SIMD programs can be reduced. An architectural model for achieving such overlapped operation is presented. The required structure of the control unit is formally defined and a framework for obtaining a balanced work load between the control unit and processing elements is provided. A study examining various single-mode and mixed-mode mappings of complete sums image correlation algorithms onto a mixed-mode parallel processing system is provided. It is demonstrated that both the synchronization inherent to interprocessor communication in MIMD mode and the overlapped operation of the control unit and processing elements in SIMD mode have the greatest effect on the experimental results