Evaluation of Programs and Parallelizing Compilers Using Dynamic Analysis Techniques

The dynamic evaluation of parallelizing compilers and the programs to which they are applied is a field of abundant opportunity. Observing the dynamic behavior of a program provides insights into the structure of a computation that may be unavailable by static analysis methods. A program may be represented by a dataflow graph generated from the dynamic flow of information between the operations in the program. The minimum parallel execution time of the program, as it is written, is the longest (critical) path through the dynamic dataflow graph. An efficient method of finding the length of the critical path is presented for several parallel execution models. The inherent parallelism is defined as the ratio of the total number of operations executed to the number of operations in the critical path. The effectiveness of a commercial parallelizing compiler is measured by comparing, for the programs in the Perfect Benchmarks, the inherent parallelism of each program, with the parallelism explicitly recognized by the compiler. The general method of critical path analysis produces results for an unlimited number of processors. Upper and lower bounds of the inherent parallelism, for the case of limite