Algorithm Partitioning Tools for a High-Performance Multiprocessor

摘要

Partitioning is the process of formulating a single application program so that it runs on a system of multiple cooperating processors. When cooperating in this fashion, the processors share the computational work of the problem. This dissertation investigates tools which a programmer may use to simplify the partitioning of algorithms for effective execution on a high-performance multiprocessor. The motivation for partitioning assumed is simple decrease in overall execution time, i.e. multiprocessor speedup of the algorithm. Focus is provided by emphasis on the structure of a particular system currently under construction, the S-1 multiprocessor. The S-1 consists of 16 very high-performance general-purpose uniprocessors connected to a uniformly addressed, fully shared memory. A large number of mechanisms, techniques,and environments are included in the set of tools useful in constructing a partitioned algorithm. The categories of tools considered in this dissertation are: (1) programming language mechanisms for specification and control of partitioning; (2) operating system mechanisms for controlling parallel execution; (3) hardware mechanisms for synchronization, communication, and sharing; (4) automatic aids for discovering and defining parallelism in algorithms; (5) simulation environments for studying aspects of parallel execution with various parameters; (6) debugging tools for use in real and simulated multiprocessing;and (7) performance monitoring and tuning tools. The tools proposed in this dissertation have been successfully applied to the task of partitioning a number of sample programs, which were selected as representative of realistic multiprocessor applications. The partitioning experiments helped discover potential performance difficulties, and also suggested ways to enhance the set of tools. (ERA citation 08:028765)