Requirements for optimal execution of loops with tests
- 1 January 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 3 (5), 573-581
- https://doi.org/10.1109/71.159040
Abstract
Both the efficient execution of branch intensive code and knowing the bounds on the same are important issues in computing in general and supercomputing in particular. In prior work, it has been suggested that the hardware needed to execute code with branches optimally is exponentially dependent on the total number of dynamic branches executed, this number of branches being proportional at least to the number of iterations of the loop. For classes of code taking at least one cycle per iteration to execute, this is not the case. For loops containing one test (normally in the form of a Boolean recurrence of order one), it is shown that the hardware necessary varies from exponential to polynomial in the length of the dependence cycle L, while execution time varies from one time cycle per iteration to less than L time cycles per iteration; the variation depends on specific code dependences. These results bring the eager evaluation of imperative code closer to fruition.Keywords
This publication has 13 references indexed in Scilit:
- A theory of reduced and minimal procedural dependenciesIEEE Transactions on Computers, 1991
- The Cydra 5 departmental supercomputer: design philosophies, decisions, and trade-offsComputer, 1989
- Incremental performance contributions of hardware concurrency extraction techniquesLecture Notes in Computer Science, 1988
- GURPR---a method for global software pipeliningPublished by Association for Computing Machinery (ACM) ,1987
- A compilation technique for software pipelining of loops with conditional jumpsPublished by Association for Computing Machinery (ACM) ,1987
- On the combination of hardware and software concurrency extraction methodsPublished by Association for Computing Machinery (ACM) ,1987
- Advanced compiler optimizations for supercomputersCommunications of the ACM, 1986
- Fast Execution of Loops with IF StatementsIEEE Transactions on Computers, 1984
- The Inhibition of Potential Parallelism by Conditional JumpsIEEE Transactions on Computers, 1972
- An Efficient Algorithm for Exploiting Multiple Arithmetic UnitsIBM Journal of Research and Development, 1967