Partitioning programs for parallel execution
Milind Girkar, Constantine D. Polychronopoulos · ACM International Conference on Supercomputing (ICS) · 1988
The ability of parallel computers to execute multiple instruction streams (tasks) simultaneously gives rise to the problem of partitioning a program into a set of tasks that can be assigned to different processors. The degree to which parallelism can be exploited, the amount of overhead involved during parallel execution of a program and a number of other factors depend directly on partitioning. A good partitioning scheme must take into account all these factors. In this paper we present algorithms to compute optimal partitions in diverse models of the problem. Both directed and undirected graph representations of a parallel program are considered. For some instances of the problem where practical optimal schemes are not possible we suggest simple and efficient heuristics. Finally, a polynomial time algorithm to compute optimal partitions for chains is given.
Cited by 32 works. doi:10.1145/55364.55386 Open-access PDF
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Bounds on Multiprocessing Timing Anomalies
- Optimal scheduling for two-processor systems
- Multiprocessor Scheduling with the Aid of Network Flow Algorithms
- An Application of Bin-Packing to Multiprocessor Scheduling
- Guided Self-Scheduling: A Practical Scheduling Scheme for Parallel Supercomputers
- Partitioning problems in parallel, pipeline, and distributed computing
- On program restructuring, scheduling, and communication for parallel processor systems
- Program partitioning and synchronization on multiprocessor systems
- Optimal partitioning of randomly generated distributed programs