February 1979 - Vol. 22 No. 2
Features
Production and employment of Ph.D.’s in computer science—1977 and 1978
This brief report summarizes the results of the third and fourth annual surveys on the production and employment of Ph.D.'s in computer science. Responses were solicited from department chairmen, and aggregated for presentation. Results of the previous surveys were reported in [1] and [2]. Tabular results of the two latest surveys are presented in Tables I-VII. Numbered years in the tables refer to calendar years. Comparisons are made with corresponding data from previous years, and discussion is limited to comments on changes and trends.
Employment characteristics of doctoral level computer scientists
A recent report from the National Research Council contains a detailed profile of doctoral level scientists and engineers, as well as doctorates in the humanities [1]. This paper summarizes those portions of the report that pertain to the employment characteristics of Ph.D.'s in computer science, and other Ph.D. scientists and engineers working in computer science. Our purpose is to verify the common folklore concerning employment opportunities in computer science, academic vs. business/industry employment of doctoral level computer scientists, work activities at the doctoral level, and the relative numbers of Ph.D.'s working in the various subdisciplines of computer science.
Recursive data structures in APL
A mathematical study of three approaches for defining nested arrays in APL is presented. Theorems exhibiting the relationships between the definitional systems are given and illustrated through graph representations. One of the approaches is used to define an APL array to be a recursive data structure equivalent to a tree structure in which all data is stored at the leaves as homogeneous arrays of numbers and characters. An extension of APL is proposed that includes new primitive functions to manipulate the nesting level of arrays and new operators to assist in the construction of data-driven algorithms.
Global optimization by suppression of partial redundancies
The elimination of redundant computations and the moving of invariant computations out of loops are often done separately, with invariants moved outward loop by loop. We propose to do both at once and to move each expression directly to the entrance of the outermost loop in which it is invariant. This is done by solving a more general problem, i.e. the elimination of computations performed twice on a given execution path. Such computations are termed partially redundant. Moreover, the algorithm does not require any graphical information or restrictions on the shape of the program graph. Testing this algorithm has shown that its execution cost is nearly linear with the size of the program, and that it leads to a smaller optimizer that requires less execution time.
Thoth, a portable real-time operating system
Thoth is a real-time operating system which is designed to be portable over a large set of machines. It is currently running on two minicomputers with quite different architectures. Both the system and application programs which use it are written in a high-level language. Because the system is implemented by the same software on different hardware, it has the same interface to user programs. Hence, application programs which use Thoth are highly portable. Thoth encourages structuring programs as networks of communicating processes by providing efficient interprocess communication primitives.
Synchronization with eventcounts and sequencers
Synchronization of concurrent processes requires controlling the relative ordering of events in the processes. A new synchronization mechanism is proposed, using abstract objects called eventcounts and sequencers, that allows processes to control the ordering of events directly, rather than using mutual exclusion to protect manipulations of shared variables that control ordering of events. Direct control of ordering seems to simplify correctness arguments and also simplifies implementation in distributed systems. The mechanism is defined formally, and then several examples of its use are given. The relationship of the mechanism to protection mechanisms in the system is explained; in particular, eventcounts are shown to be applicable to situations where confinement of information matters. An implementation of eventcounts and sequencers in a system with shared memory is described.
Optimal storage allocation for serial files
A computer system uses several serial files. The files reside on a direct-access storage device in which storage space is limited. Records are added to the files either by jobs in batch processing mode, or by on-line transactions. Each transaction (or job) generates a demand vector which designates the space required in each file for record addition. Whenever one file runs out of space, the system must be reorganized. This paper considers several criteria for best allocating storage space to the files.
