Dynamic dependency analysis of ordinary programs
Authors:
- Todd M. AustinTATodd M. Austin
- Gurindar S. SohiGSGurindar S. Sohi
Open Access
- 1 April 1992
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGARCH Computer Architecture News
- Vol. 20 (2) , 342-351
Abstract
A quantitative analysis of program execution is essential to the computer architecture design process. With the current trend in architecture of enhancing the performance of uniprocessors by exploiting fine-grain parallelism, first-order metrics of program execution, such as operation frequencies, are not sufficient; characterizing the exact nature of dependencies between operations is essential. This paper presents a methodology for constructing the dynamic execution graph that characterizes the execution of an ordinary program (an application program written in an imperatibve language such as C or FORTRAN) from a serial execution trace of the program. It then uses the methodology to study parallelism in the SPEC benchmarks. We see that the prallelism can be bursty in nature (periods of lots of parallelism followed by periods of little parallelism), but the average parallelism is quite high, ranging from 13 to 23,302 operations per cycle. Exposing this parallelism requires renaming of both registers and memory, though renaming registers alone exposes much of this parallelism. We also see that fairly large windows of dynamic instructions would be required to expose this parallelism from a sequential instruction stream.Keywords
This publication has 8 references indexed in Scilit:
- Limits of instruction-level parallelism1991
- Single instruction stream parallelism is greater than two1991
- Monsoon1990
- Limits on multiple instruction issue1989
- Measuring parallelism in computation-intensive scientific/engineering applicationsIEEE Transactions on Computers, 1988
- Measuring the Parallelism Available for Very Long Instruction Word ArchitecturesIEEE Transactions on Computers, 1984
- Measurements of parallelism in ordinary FORTRAN programsComputer, 1974
- Detection and Parallel Execution of Independent InstructionsIEEE Transactions on Computers, 1970