Syntax oriented analysis of the run time performance of programs
Luis Felipe Cabrera · 1981
In this thesis we consider the problem of finding efficient ways to determine, given the values for the input variables, the values of various performance indices associated with a program. For most purposes, we may concentrate on reproducing efficiently the dynamic profile of the program, i.e., on obtaining the exact profile for any run of the program as a function of the values of the input variables. Using the profile together with a data base of program performance information enables us to find the actual values of most of the desired performance indices. To achieve this, we describe several kinds of performance representations of programs which express the profile equations of the program we are analyzing. We show that it is often possible to represent the profile equations by program performance formulae, whose evaluation time is linear in the length of their expressions. This is easily seen to be the best one can hope to obtain. We also delimit the cases in which an optimal performance representation can be found, and propose some alternative methods for the other cases. In fact, our skeleton procedure can always be used, in the case of sequential programs, to represent the profile equations of a program. It is seen that, for compute bound sequential programs, the running time of the skeleton can be substantially shorter than that of running an instrumented version of the original program. Nevertheless, we also present examples which show that the running time of the skeleton need not be linear in the length of its text and in some cases is very close to the running time of the actual program. A variety of solutions, and theoretical results which guide their usage, are presented to overcome the different problems due to the possible slowness of the skeleton, on the one hand, and to the non-applicability of the program performance formulae, on the other hand. It is recognized that most of the definability problems are caused by the iterations (loops). In particular, alternations (conditional statements) within iterations often cause a program not to exhibit an optimal performance representation. We examine in full detail the case when the actions on the control variables of an iteration are linear functions. In this case, we see that at run time we are even able to determine the exact pattern of truth values that a predicate has. We have yet to implement a system which can build performance representations for us. However, we have discovered that known techniques used in data flow analysis suffice to obtain all the information we need about the variables in a program. Performance representations could be built by an intelligent programming while a program is being edited. Our methods can also be used to obtain traces of programs efficiently. In fact, with minor modifications, the skeleton approach can be used to generate instruction traces of programs. A further refinement yields data traces. Moreover, those of our techniques which find faster performance representations can also be utilized to generate condensed traces, which can then be analyzed using a postprocessor. Once the trace representation of a program is built, obtaining several traces (corresponding to different sets of input data values) should be much more economical than actually running an appropriately instrumented version of the program several times. When analyzing parallel programs, the problem of determining performance indices is much more complex since modeling the computational environment of the program is much harder. However, we show how our techniques for sequential programs can be used to aid this study.