Time and Parallel Processor Bounds for Fortran-Like Loops
Authors:
- Shyh-Ching ChenSCShyh-Ching Chen
- KuckKUKuck
- TowleTOTowle
- 1 September 1979
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-28 (9) , 660-670
Abstract
The main goal of this paper is to show that a large number of processors can be used effectively to speed up simple Fortran-like loops consisting of assignment statements. A practical method is given by which one can check whether or not a statement is dependent upon another. The dependence structure of the whole loop may be of different types. For each type, a set of time and processor upper bounds is given. We also show how a loop can sometimes be transformed to change its dependence structure. Finally, we give a result on the possible splitting up of a given recurrence system into a number of smaller subsystems. These results can be used to modify and sometimes improve the bounds for the loops as demanded by special circumstances.Keywords
This publication has 15 references indexed in Scilit:
- A Survey of Parallel Machine Organization and ProgrammingACM Computing Surveys, 1977
- Time Bounds on the Parallel Evaluation of Arithmetic ExpressionsSIAM Journal on Computing, 1975
- The Parallel Evaluation of General Arithmetic ExpressionsJournal of the ACM, 1974
- The parallel execution of DO loopsCommunications of the ACM, 1974
- New algorithms and lower bounds for the parallel evaluation of certain rational expressions1974
- Bounds on the parallel evaluation of arithmetic expressions using associativity and commutativityActa Informatica, 1974
- Measurements of parallelism in ordinary FORTRAN programsComputer, 1974
- On the Number of Operations Simultaneously Executable in Fortran-Like Programs and Their Resulting SpeedupIEEE Transactions on Computers, 1972
- On the Time Required to Perform MultiplicationJournal of the ACM, 1967
- On the Time Required to Perform AdditionJournal of the ACM, 1965