Computing Applications
Advertisement
Copying list structures using bounded workspace
Two new algorithms are presented for list structure copying using bounded workspace. The first, of primarily theoretical interest, shows that without cell tag bits the task can be performed in time n2. The second algorithm, assuming one tag bit in each cell, delivers attractive practical speed. Any noncyclic structure is copied in linear speed, while cyclic structures are copied in average time less than n log n. No foreknowledge of cycle absence is necessary to achieve linear speed. A variation of the second algorithm solves an open problem concerning list structure marking. That result demonstrates that marking can be done in average time n log n without the aid of supplemental tag bits or stacks.
Execution characteristics of programs in a page-on-demand system
h show the execution characteristics of two types of commonly used programs in a large-scale, time-shared computer system. A software monitoring facility built into the supervisor was used for data collection during normal system operation. These data were analyzed, and results of this analysis are presented for a Fortran compiler and an interactive line file editor.
Probability distribution functions and other data are given for such things as CPU intervals, I/O intervals, and the number of such intervals during execution. Empirical distributions are compared with simple theoretical distributions (exponential, hyperexponential, and geometric). Other data show paging characteristics of tasks as a function of the number of pages those tasks have in core.
An improved program-synthesizing algorithm and its correctness
An improved program-synthesizing algorithm based on the algorithm proposed by Waldinger and Lee in 1969 is given. In the old algorithm, the program-synthesizing problem is translated into a theorem-proving problem, and a program is obtained by analyzing a proof. For the improved algorithm, the analysis is not necessary, and a program is obtained as soon as the proof is completed. This is achieved by using a modified variable tracing mechanism invented by Green in 1969. The correctness of the improved algorithm is also proved; i.e. the program thus obtained always satisfies the specification.
Scalar- and planar-valued curve fitting using splines under tension
The spline under tension was introduced by Schweikert in an attempt to imitate cubic splines but avoid the spurious critical points they induce. The defining equations are presented here, together with an efficient method for determining the necessary parameters and computing the resultant spline. The standard scalar-valued curve fitting problem is discussed, as well as the fitting of open and closed curves in the plane. The use of these curves and the importance of the tension in the fitting of contour lines are mentioned as application.
On Lion’s counter example for Gotlieb’s method for the construction of school timetables
The timetable problem is an essentially discrete problem. Although the discrete problem may have no feasible solution, there may exist a solution to the equivalent continuous problem. An example, is given, for which the nondiscrete solution can be interpreted as a set of timetables, differing from week to week, which together satisfy the long-term requirements of the timetable problem.
Two methods for employing parallelism in tape-sorting are presented. Method A is the natural way to use parallelism. Method B is new. Both approximately achieve the goal of reducing the processing time by a divisor which is the number of processors.
A simple linear model of demand paging performance
Predicting the performance of a proposed automatically managed multilevel memory system requires a model of the patterns by which programs refer to the information stored in the memory. Some recent experimental measurements on the Multics virtual memory suggest that, for rough approximations, a remarkably simple program reference model will suffice. The simple model combines the effect of the information reference pattern with the effect of the automatic management algorithm to produce a single, composite statement: the mean number of memory references between paging exceptions increases linearly with the size of the paging memory. The resulting model is easy to manipulate, and is applicable to such diverse problems as choosing an optimum size for a paging memory, arranging for reproducible memory usage charges, and estimating the amount of core memory sharing.
A probabilistic model of a multiprogramming system is exercised in order to determine the conditions under which the dynamic repacking of main memory is beneficial. An expression is derived for the maximum interference that a repacking process may introduce before the original performance of the system is degraded. Alternative approaches to repacking are discussed, and the operating conditions that lead to improved system throughput through repacking are delineated.
Emotional content considered dangerous
I had hoped that Moorer's rebuttal to my short communication in the November 1972 Communications would close the debate on a topic which, like the computer itself, has provoked an inordinately large quantity of unqualified argument. Unfortunately, the short communications by McMorrow and Wexelblat in the May 1973 Communications lead me to believe that my position is still grossly misunderstood. Therefore, allow me to clarify these matters.
Scan conversion algorithms for a cell organized raster display
Raster scan computer graphics with “real time” character generators have previously been limited to alphanumeric characters. A display has been described which extends the capabilities of this organization to include general graphics.
Two fundamentally different scan conversion algorithms which have been developed to support this display are presented. One is most suitable to noninteractive applications and the other to interactive applications. The algorithms were implemented in Fortran on the CDC6400 computer. Results obtained from the implementations show that the noninteractive algorithms can significantly reduce display file storage requirements at little cost in execution time over that of a conventional raster display. The interactive algorithm can improve response time and reduce storage requirements.
Quadratic search for hash tables of sizes P n
It has previously been claimed [1 and 2] that the quadratic hash table search method of Maurer cannot usefully be applied to tables of size 2n. This is not so; the method can in fact be applied to tables of size pn for any prime p. It is shown below that rather simple conditions on the coefficients suffice to guarantee that all table locations will be examined once and only once. Specifically, if the equation is k + bi2 + ai mod pn (*) where k is the initial hash address and 0 ≤ i < pn, then, if p divides b but not a, the range of values is all the least positive residues of pn. To prove that all values are covered, we consider some fixed value, say k + bi20 + ai0 mod pn and ask, what conditions must be true if the congruence equation k + bi2 + ai ≡ k + bi02 + ai0 mod pn is to have solutions i, 0 ≤ i < pn, other than i0?
Optimal space allocation on disk storage devices
When the amount of space required for file storage exceeds the amount which can be kept online, decisions must be made as to which files are to be permanently resident and which mountable. These decisions will affect the number of mount requests issued to the operators. This is often a bottleneck in a computing facility, and reducing the number of mounts thus decreases turnaround time. An optimization model for the assignment of files to disk packs, and packs to either resident or nonresident status is presented. Heuristics are suggested for those cases in which it is Inefficient to compute the actual optimum.
On the construction of a representative synthetic workload
A general method of constructing a drive workload representative of a real workload is described. The real workload is characterized by its demands on the various system resources. These characteristics of the real workload are obtained from the system accounting data. The characteristics of the drive workload are determined by matching the joint probability density of the real workload with that of the drive workload. The drive workload is realized by using a synthetic program in which the characteristics can be varied by varying the appropriate parameters. Calibration experiments are conducted to determine expressions relating the synthetic program parameters with the workload characteristics. The general method is applied to the case of two variables, cpu seconds and number of I/O activities; and a synthetic workload with 88 jobs is constructed to represent a month's workload consisting of about 6000 jobs.
Shape the Future of Computing
ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.
Get InvolvedCommunications of the ACM (CACM) is now a fully Open Access publication.
By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.
Learn More