×

Partitioning and scheduling parallel programs for multiprocessors. (English) Zbl 0679.68056

Research Monographs in Parallel and Distributed Computing. London: Pitman Publishing. 201 p. £17.95 (1989).
This dissertation elaborated at Stanford University is published in the series consisting of research monographs in parallel and distributed computing. The primary theme of the series is the effective and transparent exploitation of parallelism through the algorithmic solutions and their evaluations. The book presents two approaches to automatic partitioning and scheduling parallel programs for execution on multiprocessors. The first approach is based on a macro-dataflow model, where the program is partitioned into tasks at compile-time and tasks are scheduled on processors at run-time. In the second approach both the partitioning and scheduling are performed at compile-time. The central issue in partitioning and scheduling field is the trade-off between parallelism and overhead required mainly for communication and synchronization. The goal of this book is to explore this problem and to present methods for its automatic optimization. Abstract models of a program and a multiprocessor constitute the framework for the algorithms. It is assumed that the programs for which abstract models are developed, are written in SISAL single-assignment language. The input of the partitioning and scheduling algorithms is a graphical representation of the program and the parameters describing the target multiprocessor.
An abstraction of the program is defined as a set of function definitions: \(PROG=\{g_ i,f_ i\}\), where \(g_ i\) is a GR graph and \(f_ i\) is a frequency count which gives the average number of calls to function i in a single execution of program PROG.
A GR graph is defined as a 6-tuple \(G=(N,\top,\perp,E_ c,F_ c,F_ T)\), where:
N is a set of objects called nodes which may be of four types-simple, function call, parallel and compound;
\(\top\) and \(\perp\) are distinguished top and bottom simple nodes in \(N;\)
E\({}_ c\) is a set of acyclic edges enforcing preceding constraints among \(nodes;\)
F\({}_ c\) is a communication size cost function giving the average data size transferred along communication \(edges;\)
F\({}_ T\) is the execution time cost function giving the average sequential execution time of a node.
Defined as above, a GR graph contains information on program structure, parallelism, execution frequencies and costs for communication and execution time. To derive average frequency values for functions and subgraphs of parallel and compound nodes, as well as average data sizes for all communication edges - execution profile information is used. The average execution times are computed according to the algorithm give in the book.
The abstraction of MIMD multiprocessor organization is a 6-tuple \(M=(P\), \(R_ c\), \(W_ c\), \(D_ c\), \(F_ s\), \(T_{sched})\), where:
P is the number of \(processors;\)
R\({}_ c\) is the communication overhead function for reading data, i.e. the execution time incurred by a processor to receive data from another \(processor;\)
W\({}_ c\) is the communication overhead function for sending \(data;\)
D\({}_ c\) is the communication delay overhead \(function;\)
F\({}_ c\) is the simple node execution time cost \(function;\)
T\({}_{sched}\) is the scheduling overhead incurred by a processor when it begins execution of a new taks.
Both the macro-dataflow an compile-time scheduling problems are expressed as optimization problems, which are proved to be NP-complete in the strong sense. Therefore the dissertation presents efficient approximation algorithms for these problems. The effectiveness of the partitioning and scheduling algorithms is studied by multiprocessor simulations of various benchmark programs, such as matrix multiplication, parsing, sorting, FFT, fluid dynamics, heat flow and radiation field determination.
Reviewer: A.Michalski

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68-02 Research exposition (monographs, survey articles) pertaining to computer science
68N25 Theory of operating systems
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite