Processor Allocation for Horizontal and Vertical Parallelism and Related Speedup Bounds
Authors:
- BanerjeeBABanerjee
- 1 April 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-36 (4) , 410-420
Abstract
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.Keywords
This publication has 8 references indexed in Scilit:
- On program restructuring, scheduling, and communication for parallel processor systems1986
- HPSm, a high performance restricted data flow architecture having minimal functionalityACM SIGARCH Computer Architecture News, 1986
- Practical Multiprocessor Scheduling Algorithms for Efficient Parallel ProcessingIEEE Transactions on Computers, 1984
- Measuring the Parallelism Available for Very Long Instruction Word ArchitecturesIEEE Transactions on Computers, 1984
- Parallelism and Representation Problems in Distributed SystemsIEEE Transactions on Computers, 1980
- An Application of Bin-Packing to Multiprocessor SchedulingSIAM Journal on Computing, 1978
- Multiprocessor Scheduling with the Aid of Network Flow AlgorithmsIEEE Transactions on Software Engineering, 1977
- Validity of the single processor approach to achieving large scale computing capabilities1967