Requirements for optimal execution of oops with tests

ABSTRACT

Both the efficient execution of branch intensive code and knowing the bounds on same are important issues in computing in general and supercomputing in particular. In prior work, it has been suggested, implied, or left as a possible maximum, that the hardware needed to execute code with branches optimally, i.e., oracular performance, is exponentially dependent on the total number of dynamic branches to be 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 1), it is shown that the hardware necessary varies from exponential to polynomial in the length of the dependency 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 dependencies.

REFERENCES

• 1: Alexander Aiken , Alexandru Nicolau, Perfect Pipelining: A New Loop Parallelization Technique, Proceedings of the 2nd European Symposium on Programming, p.221-235, March 21-24, 1988
• 2: Baneajee, U. and Gajski, D. Fast Execution of Loops With IF Statements. IEEE Transactions on Computers C-33(11):1030-1033, November, 1984.
• 3: Cytron, R. G. Doacross: Beyond Vectorization for Multiproc~ssors (Extended Abstract). In Proceedings of the 1986 International Conference on Parallel Processing, pages 836-844. Pennsylvania State University and the IEEE Computer Society, August, 1986.
• 4: Kemal Ebcioğlu, A compilation technique for software pipelining of loops with conditional jumps, Proceedings of the 20th annual workshop on Microprogramming, p.69-79, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255317]
• 5: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 6: Constantine Demetrios Polychronopoulos, On program restructuring, scheduling, and communication for parallel processor systems, 1986
• 7: Riseman, E. M. and Foster, C. C. The Inhibition of Potential Parallelism by Conditional Jumps. IEEE Transactions on Computers :1405-1411, December, 1972.
• 8: Bogong Su , Shiyuan Ding , Jian Wang , Jinshi Xia, GURPR—a method for global software pipelining, Proceedings of the 20th annual workshop on Microprogramming, p.88-96, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255322]
• 9: Tomasulo, R. M. An Efficient Algorithm for Expoiting Multiple Arithmetic Units. IBM Journal :25-33, january, 1967.
• 10: Augustus Kinzel Uht, Hardware extraction of low-level concurrency from sequential instruction streams (parallelism, implementation, architecture, dependencies, semantics), 1985
• 11: Uht, A. K. and Wedig, R. G. Hardware Extraction of Low-level Concurrency from Serial Instruction Streams. In Proceedings of the International Conference on Parallel Processing, pages 729-736. IEEE Computer Society and the Association for Computing Machinery, August, 1986.
• 12: A. K. Uht, Incremental performance contributions of hardware concurrency extraction techniques, Proceedings of the 1st International Conference on Supercomputing, p.355-376, March 1988, Athens, Greece
• 13: Augustus K. Uht , Constantine D. Polychronopoulos , John F. Kolen, On the combination of hardware and software concurrency extraction methods, Proceedings of the 20th annual workshop on Microprogramming, p.133-141, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255331]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

General Terms:
Design