Search

This paper introduces the notion of usage counts, shows how usage counts can be developed by algorithms that eliminate redundant computations, and describes how usage counts can provide the basis for register allocation. The paper compares register allocation based on usage counts to other commonly used register allocation techniques, and presents evidence which shows that the usage count technique is significantly better than these other techniques. [ABSTRACT FROM AUTHOR]

The problem of scheduling two or more processors to minimize the execution time of a program which consists of a set of partially ordered tasks is studied. Cases where task execution times are deterministic and others in which execution times are random variables are analyzed. It is shown that different algorithms suggested in the literature vary significantly in execution time and that the B-schedule of Coffman and Graham is near-optimal. A dynamic programming solution for the case in which execution times are random variables is presented. [ABSTRACT FROM AUTHOR]

A simulation model of a time-sharing system with a finite noncontiguous store and an infinite auxiliary store is used to study the variation of system parameters such as store size, number of jobs allowed to execute simultaneously, job-scheduling algorithm, etc. The effects of these variations on a measure of system performance is used to ascertain which of the parameters controllable by the job-scheduling algorithm, including the scheduling itself, require optimization, and which of the parameters not normally controllable by the scheduling algorithm have a marked effect on system performance. System performance is based upon the mean cost of delay to all jobs processed. It is shown that significant improvements in the measure of system performance can be obtained by using variable time-slice techniques and by selecting the optimum round-robin cycle time. It appears that these features would benefit from optimization whereas other parameters controllable by the scheduling algorithm affect system performance in a predictable manner and would not benefit from optimization. Features not normally under the control of the scheduling algorithm can also have a marked effect on the measure of performance; in particular, supervisor overheads, the size of the store, and the speed of the CPU. A comparison is made between the results of the simulation model and two analytical equations for quantum-oriented nonpreemptive time-sharing systems. The comparison is found to be very favorable. [ABSTRACT FROM AUTHOR]

There are situations in the natural sciences and medicine (e.g. in electron microscopy and X-ray photography in which it is desirable to estimate the gray levels of a digital picture at the individual points from the sums of the gray levels along straight tines (projections) at a Few angles. Usually, in such situations, the picture is far from determined and the problem is to find the "most representative" picture. Three algorithms are described (all using Monte Carlo methods which were designed to solve this problem. The algorithms are applicable in a large and varied number of fields. The most important uses may he the reconstruction of possibly asymmetric particles from electron micrographs and three-dimensional X-ray analysis. [ABSTRACT FROM AUTHOR]

A method of optimizing the computation of arithmetic and indexing expressions of a Fortran program is presented. The method is based on a linear analysis of the definition points of the variables and the branching and DO loop structure of the program. The objectives of the processing are (1) to eliminate redundant calculations when references are made to common sub-expression values, (2) to remove invariant calculations from DO loops, (3) to efficiently compute subscripts containing DO iteration variables, and (4) to provide efficient index register usage. The method presented requires at least a three-pass compiler, the second of which is scanned backward. It has been used in the development of several FORTRAN compilers that have proved to produce excellent object code without significantly reducing the compilation speed. [ABSTRACT FROM AUTHOR]