Program optimization based on a non-procedural specification
Kang-Sen Lu · 1981
Program Optimization Based on a Non-Procedural Specification This dissertation deals with two related problems: development of a methodology for achieving memory and computation efficiency of computer programs, and the use of this methodology in very high-level programming and associated automatic program generators. Computer efficiency of programs has many aspects. Usually additional memory saves computation by avoiding the need to recompute certain variables. Our emphasis has been on reducing memory use by variables sharing memory space, without requiring recomputation. It will be shown that this also reduces computation overhead. The most significant savings are due to sharing memory in iterative steps. This is the focus of the reported research. The evaluation of memory use of the many possible alternatives for realizing a computation is highly complex and requires lengthy and expensive computations. We have developed a heuristic approach, which has been very effective in our experience, and which is practical and economical in use of the computer. Basically it consists of evaluating global memory usage altertnatives on each level of nested iteration loops, starting with the outside level and moving inwardly. Thus we neglect the rare impact of a nested iteration loop on the