INSTRUCTION WINDOW SIZE TRADE-OFFS AND CHARACTERIZATION OF PROGRAM PARALLELISM

Detecting independent operations is a prime objective for computers th at are capable of issuing and executing multiple operations simultaneo usly. The number of instructions that are simultaneously examined for detecting those that are independent is the scope of concurrency detec tion. This paper presents an analytical model for predicting the perfo rmance impact of varying the scope of concurrency detection as a funct ion of available resources, such as number of pipelines in a superscal ar architecture. The model developed can show where a performance bott leneck might be: insufficient resources to exploit discovered parallel ism, insufficient instruction stream parallelism, or insufficient scop e of concurrency detection. The cost associated with speculative execu tion is examined via a set of probability distributions that character ize the inherent parallelism in the instruction stream. These results were derived using traces from a Multiflow TRACE SCHEDULING(TM) compac ting FORTRAN 77 and C compilers. The experiments provide misprediction delay estimates for 11 common application-level benchmarks under scop e constraints, assuming speculative, out-of-order execution and run ti me scheduling. The throughput prediction of the analytical model is sh own to be close to the measured static throughput of the compiler outp ut.