An analysis of program execution : issues for computer architecture

Abstract

When a new computer architecture or a new method of code generation is proposed, the improvement in program execution achieved by the proposal has to be demonstrated. This demonstration takes the form of a test in which a small set of programs is run on two architectures. Each program in the set is run once on each architecture and the corresponding results are compared. Test programs are considered to be representative of a wider class of programs and logistical constraints keep the set size small. Characteristics of program execution depend on the base architectural factors as well as on a range of additional factors, like code generation, different inputs to test programs and changes in program encoding. It is difficult or impossible to maintain control over these additional variables. Estimates of sensitivity of measured characteristics to these factors enable us to qualify obtained results and generalize them from sample programs to other programs. Effects of these factors should be examined, if only to make sure that they are negligible. Yet reports of such tests usually do not include such an analysis. This thesis examines the sensitivity of several characteristics of program execution to the following factors: different inputs to the test program, procedure inlining and small optimizations of the code generator. We hypothesise that the sensitivity is such that conventional testing approach may be significantly questioned. The program execution characteristics analysed are: mean number of instructions between transfers of control, frequency of procedure calls, number of parameters on procedure call, procedure nesting, code locality and percentage of references to local, global and intermediate variables. The characteristics analysed here are pertinent to both architectural design and the compiler technology. The program sample consisted of seven non-trivial programs divided into three groups: compilers, numerical programs, and information processing programs. Each program was run with an extensive range of carefully prepared inputs and the values of the measured characteristics tabulated. Then one program within each group was selected for an examination of optimization effects when run with the same set of inputs The results of these experiments show that a wide variability of the values of the measured characteristics obtained for the same program is not only possible but highly likely. The values obtained, when running a program with different input data, can differ by a factor of two or more. The effects of procedure inlining and code generator optimizations affect these values similarly. The combined effects of optimizations and different inputs produced, in some cases, values of a. characteristic differing by an order of magnitude for the same program. Such results suggest that any estimates of a quantitative improvement based on a small sample of programs run once should be treated as a very rough estimates. This thesis describes also a set of techniques for monitoring program execution and analysis of obtained results. These techniques assure quality of obtained data. They allow also a significant compression of voluminous data obtained while tracing program execution and convenient processing and analysis of data obtained from experiments .