April 1973 - Vol. 16 No. 4
Features
Implementation of a high level language machine
Computing machines which directly execute the statements of a high level language have been proposed in the past. This report describes the actual implementation of such a machine: it is a computer whose “machine language” is APL. The machine is fully operational and correctly executes almost all of the APL operations on scalars, vectors, and arrays. The machine automatically allocates memory, executes statements, calls functions, converts numbers from one type to another, checks subscripts, and automatically detects many types of programmer errors.
A study is presented of some of the system implications of memory hierarchies in which the backing or secondary store has a very small read time, relative to both the time required for writing and to the read time of conventional backing storage devices. Several analytic models are introduced, and it is shown that such hierarchies may operate in ways which differ from those of more conventional hierarchies. In particular, it is shown that it may not be necessary to multiprogram in such a situation.
In the past, backing storage devices have been roughly symmetric with respect to their read and write times. This situation may not continue, as several devices are currently under development which may have a very small read-time/write-time ratio. This study places particular emphasis on one such system—the RCA read/write holographic optical memory.
A statistical study of the accuracy of floating point number systems
This paper presents the statistical results of tests of the accuracy of certain arithmetic systems in evaluating sums, products and inner products, and analytic error estimates for some of the computations. The arithmetic systems studied are 6-digit hexadecimal and 22-digit binary floating point number representations combined with the usual chop and round modes of arithmetic with various numbers of guard digits, and with a modified round mode with guard digits. In a certain sense, arithmetic systems differing only in their use of binary or hexadecimal number representations are shown to be approximately statistically equivalent in accuracy. Further, the usual round mode with guard digits is shown to be statistically superior in accuracy to the usual chop mode in all cases save one. The modified round mode is found to be superior to the chop mode in all cases.
Some approaches to best-match file searching
The problem of searching the set of keys in a file to find a key which is closest to a given query key is discussed. After “closest,” in terms of a metric on the the key space, is suitably defined, three file structures are presented together with their corresponding search algorithms, which are intended to reduce the number of comparisons required to achieve the desired result. These methods are derived using certain inequalities satisfied by metrics and by graph-theoretic concepts. Some empirical results are presented which compare the efficiency of the methods.
A region coloring technique for scene analysis
A method of converting a picture into a “cartoon” or “map” whose regions correspond to differently textured regions is described. Texture edges in the picture are detected, and solid regions surrounded by these (usually broken) edges are “colored in” using a propagation process. The resulting map is cleaned by comparing the region colors with the textures of the corresponding regions in the picture, and also by merging some regions with others according to criteria based on topology and size. The method has been applied to the construction of cloud cover maps from cloud cover pictures obtained by satellites.
The design, implementation, and evaluation of a working set dispatcher
The behavior of a computer system is largely dependent upon the algorithms employed to allocate the system resources to the processes competing for them. Recent research in time-sharing paging systems has developed the working set model for program behavior, and a resource allocation strategy based on this model has been proposed. Two implementations along these principles have been reported, but it seems that in neither case have further results been announced. This report discusses the design and implementation of a dispatcher based on the working set principle, presents data to permit analysis of its behavior, and indicates future directions of research on methods of controlling a computer system.
Certification of algorithm 386 [A1]
Subroutine GCDN, Algorithm 386 as described in [1, 2], computes the greatest common divisor, IGCD, of n integers A(1), … , A(n) by using the Euclidean algorithm to compute first gcd(A(1), A(2)), then gcd(gcd(A(1), A(2)), A(3)), etc. It also computes integer multipliers Z(1), … , Z(n) such that IGCD = ∑ni=1 A(i)Z(i).
