October 1973 - Vol. 16 No. 10
Features
Multiple terminals under user program control in a time-sharing environment
User-written programs on the Dartmouth Time-Sharing System can communicate with many remote terminals simultaneously and can control the interactions between these terminals. Such programs can be written using standard input and output instructions in any language available on the system. This paper describes how this multiple-terminal facility was implemented without requiring any changes in the system executive or in any of the system's compilers or interpreters.
A model and stack implementation of multiple environments
Many control and access environment structures require that storage for a procedure activation exist at times when control is not nested within the procedure activated. This is straightforward to implement by dynamic storage allocation with linked blocks for each activation, but rather expensive in both time and space. This paper presents an implementation technique using a single stack to hold procedure activation storage which allows retention of that storage for durations not necessarily tied to control flow. The technique has the property that, in the simple case, it runs identically to the usual automatic stack allocation and deallocation procedure. Applications of this technique to multitasking, coroutines, backtracking, label-valued variables, and functional arguments are discussed. In the initial model, a single real processor is assumed, and the implementation assumes multiple-processes coordinate by passing control explicitly to one another. A multiprocessor implementation requires only a few changes to the basic technique, as described.
General performance analysis of key-to-address transformation methods using an abstract file concept
This paper presents a new approach to the analysis of performance of the various key-to-address transformation methods. In this approach the keys in a file are assumed to have been selected from the key space according to a certain probabilistic selection algorithm. All files with the same number of keys selected from this key space will be suitably weighted in accordance with the algorithm, and the average performance of the transformation methods on these files will be used as the potential of these methods. Using this analysis, methods with the same overall performance can be classified and key distributions partial to certain transformations can be identified. All this can be done analytically. The approach is applied to a group of transformation methods using files whose keys are selected randomly.
A note on the confinement problem
onfining a program during its execution so that it cannot transmit information to any other program except its caller. A set of examples attempts to stake out the boundaries of the problem. Necessary conditions for a solution are stated and informally justified.
A class of dynamic memory allocation algorithms
A new dynamic memory allocation algorithm, the Fibonacci system, is introduced. This algorithm is similar to, but seems to have certain advantages over, the “buddy” system. A generalization is mentioned which includes both of these systems as special cases.
Using page residency to select the working set parameter
Denning's method for selecting the working set parameter, which uses interreference intervals, is examined. Several omissions in his model are noted, and new assumptions are introduced to overcome these omissions. Using this modified model, Denning's results on page residency are rederived and reconsidered for selecting the working set parameter.
Control structures in Illiac IV Fortran
As part of an effort to design and implement a Fortran compiler on the ILLIAC IV, an extended Fortran, called IVTRAN, has been developed. This language provides a means of expressing data and control structures suitable for exploiting ILLIAC IV parallelism. This paper reviews the hardware characteristics of the ILLIAC and singles out unconventiona features which could be expected to influence langluage (and compiler) design. The implications of these features for data layout and algorithm structure are discussed, and the conclusion is drawn that data allocation rather than code structuring is the crucial ILLIAC optimization problem. A satisfactory method of data allocation is then presented. Language structures to utilize this storage method and express parallel algorithms are described.
Addendum to a multiple-precision division algorithm
In [1] Mifsud presented a generalized division algorithm for positive integral operands. The uniqueness of the method was advertised as causing each trial cipher in the quotient to be either equal to or one greater than its final replacement. The method of describing the algorithm was intended to stress the simple mathematical facts that were the basis of the algorithm. However, some difficulty arises with the programming and implementation of the algorithm. Article [1] addressed itself to the calculation of the trial cipher by using the first two digits of the partial dividend (step 6); i.e. it formed [pr+1pr/dr], with pr+1 < dr, where the bracket is used to indicate the integral part of its content. Thus the paper conveniently avoided the possibility of overflow which would happen if pr+1 = dr.
