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 memory usage calculated for an outside iteration. This has lead to the principle of maximizing size of loop scopes in a program as a means to attaining a more efficient program for present-day sequential computers. The automatic design of efficient programs is also essential in use of very high level languages. The use of very high level languages offers many benefits, such as less program coding, less required proficiency in programming and analysis, and ease in understanding maintenance and updating of programs. All these benefits are conditioned on whether the language processor can produce satisfactorily efficient program. The dissertation reports the design and implementation of a new version of the MODEL language and processor which incorporates algorithms for producing more efficient programs. The dissertation describes briefly the MODEL non-procedural language and the analysis, scheduling, and code generation tasks