Processor Allocation for Horizontal and Vertical Parallelism and Related Speedup Bounds
Polychoronopoulos, Banerjee · IEEE Transactions on Computers · 1987
The main aim of the paper is to study allocation of processors to, parallel programs executing on a multiprocessor system, and the resulting speedups. First, we consider a parallel program as a sequence of steps where each step consists of a set of parallel operations. General bounds on the speedup on a p- processor system are derived based on this model. Measurements of code parallelism for the, LINPACK numerical package are presented to support the belief that typical numerical programs contain much potential parallelism that can be discovered by a good restructuring compiler. Next, a parallel program is represented as a task graph whose nodes are do across loops (i.e., loops whose iterations can be partially, overlapped). It is shown how processors can be allocated to exploit horizontal and vertical parallelism in such graphs. Two processor allocation heuristic algorithms (WP and PA) are presented. PA is the heart of the WP and is used to obtain efficient processor allocations for a set of independent parallel tasks. WP allocates processors to general task graphs. Finally, a general formula for the speedup of a DO across loop is given that is more accurate than the known formula.
Cited by 59 works. doi:10.1109/tc.1987.1676923
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Validity of the single processor approach to achieving large scale computing capabilities
- Computer and job-shop scheduling theory
- The Structure of Computers and Computations
- Multiprocessor Scheduling with the Aid of Network Flow Algorithms
- Optimizing supercompilers for supercomputers
- An Application of Bin-Packing to Multiprocessor Scheduling
- Speedup of ordinary programs
- Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing
- Measuring the Parallelism Available for Very Long Instruction Word Architectures