Automatic synthesis of concurrent control for multiprocessor systems of general topology through fine-grain mapping
Liwen Shih · 1989
The design of a methodology of automatic fine-grain mapping for static installation of a computation algorithm onto a multiprocessor system is presented. This is motivated by attempts made by several researchers and developers to obtain better matches between the software computations and hardware structures, so that to better manage the resources of an existing multiprocessor system. The main objective of this work is to explore the parallelism at the fine-grain level, in contrast to the more common used course-grain or task level. Another objective is to test the feasibility of improving the system performance through fine-grain mapping techniques under the consideration of complex architecture parameters. General distributed MIMD multiprocessor systems, are considered as the base system architecture domain, which may feature processor heterogeneity in speed and/or function, and a processor connection scheme in an arbitrary network topology with possibly multiple data channels, different communication costs, and/or different directions in every data channel. A Fine-Grain Mapping System, FGMS, is proposed, as a solution to the automatic generation of low-level code, e.g., microcode, for coordinating among the given processors. In seeking to meet the high performance requirement of the final code, Data Flow Graphs DFGs are adopted as an intermediate computation model throughout the four transformation stages in the FGMS system, because of their capability in demonstrating the maximum concurrency. Among the four stages: Data-Flow Graph Generation, Vertical Mapping, Horizontal Mapping, and Fine-Grain Code Generation, the major emphasis of this work falls on the Horizontal Mapping, HM, stage which deterministically migrates a fine-grain computation onto a processor network of a static topology with completion time reported. The HM strategy is basically a best-first (greedy) heuristic of polynomial time complexity which can produce a valid, efficient processor scheduling as well as guarantee a speedup lower-bound for the given algorithm/machine pair. As a result, the FGMS maps the control sequence of the computation into a set of control sequences, running cooperatively, each as a subtask permanently allocated by one processor. The proposed FGMS system provides the users of multiprocessor systems with an easy and efficient way for comparing parallel algorithms, selecting parallel machines, developing programs, and generating execution control code. Besides the sample applications demonstrated to evaluate a computation/machine match and to select a parallel system for a computation, many other potential applications of the proposed FGMS can also be expected, such as parallel programming, performance evaluation, architecture synthesis, vertical-migration task selection, and code compaction.