June 1969 - Vol. 12 No. 6
Features
Degree of multiprogramming in page-on-demand systems
A simple stochastic model is described which offers a base for understanding the relationship between the number of programs permitted to share memory (the degree of multiprogramming), drum traffic rates, and central processing unit utilization in page-on-demand, multiprogrammed, time-shared computer systems. The model preserves, as a key feature, the property of page-demand statistics which implies a “burst” of page demands at the beginning of any job or quantum execution.
The model, a Markov chain, is analyzed numerically and the results are presented graphically for a wide range of key environment-descriptive parameters. Implications of the results to time-shared system design and programming are discussed, and a calculation of the optimal degree of multiprogramming for a wide range of parameters is presented graphically.
Three-dimensional computer display
A stereographic display terminal has been produced using the raster display (BRAD) recently developed at Brookhaven. The system uses a rotating refresh memory to feed standard television monitors.
To produce a stereographic display the computer calculates the projected video images of an object, viewed from two separated points. The resulting video maps are stored on separate refresh bands of the rotating memory. The two output signals are connected to separate color guns of a color television monitor, thus creating a superimposed image on the screen. Optical separation is achieved by viewing the image through color filters.
The display is interactive and can be viewed by a large group of people at the same time.
Simulation of traffic flows in a network
A computer simulation program which deals with traffic flows in the network of a large area is described. Each road is segmented into blocks of several ten-meter lengths and is represented by a bidirectional list in computer memory. The movement of cars, i.e. the transfer of cars from one block to the next, is expressed by a proper formula. This formula is based on the supposition that the speed of cars in a block is determined only by the density of cars in the block, and this speed-versus-density curve is empirically given the numerical values.
This simulation scheme has its excellent point in that it makes it possible to trace the dynamic behavior of traffic flows in a variety of situations, some examples of which are given for an actual area of the city of Kyoto, Japan.
Introducing computing to smaller colleges and universities—a progress report
By technical means that are now routine, computer service for smaller colleges and universities can be provided by remote terminals of a central facility. Access, however, is not enough—effective organizational and educational methodology for introducing computing at such institutions must also be developed. The experience of two years with a statewide network involving 41 institutions is discussed. Lessons include the importance of a separate organization representing the small colleges, the necessity for on-campus training for the institutions, the need for some special programming and documentation to support such users, and the development of curriculum by evolutionary means.
Spline function methods for nonlinear boundary-value problems
The solution of the nonlinear differential equation Y″ = F(x, Y, Y′) with two-point boundary conditions is approximated by a quintic or cubic spline function y(x). The method is well suited to nonuniform mesh size and dynamic mesh size allocation. For uniform mesh size h, the error in the quintic spline y(x) is O(h4), with typical error one-third that from Numerov's method. Requiring the differential equation to be satisfied at the mesh points results in a set of difference equations, which are block tridiagonal and so are easily solved by relaxation or other standard methods.
A recursive relation for the determinant of a pentadiagonal matrix
A recursive relation, relating leading principal minors, is developed for the determinant of a pentadiagonal matrix. A numerical example is included to indicate its use in calculating eigenvalues.
Generation of optimal code for expressions via factorization
Given a set of expressions which are to be compiled, methods are presented for increasing the efficiency of the object code produced by first factoring the expressions, i.e. finding a set of subexpressions each of which occurs in two or more other expressions or subexpressions. Once all the factors have been ascertained, a sequencing procedure is applied which orders the factors and expressions such that all information is computed in the correct sequence and factors need be retained in memory a minimal amount of time. An assignment algorithm is then executed in order to minimize the total number of temporary storage cells required to hold the results of evaluating the factors. In order to make these techniques computationally feasible, heuristic procedures are applied, and hence global optimal results are not necessarily generated. The factorization algorithms are also applicable to the problem of factoring Boolean switching expressions and of factoring polynomials encountered in symbol manipulating systems.
A computer system for transformational grammar
A comprehensive system for transformational grammar has been designed and implemented on the IBM 360/67 computer. The system deals with the transformational model of syntax, along the lines of Chomsky's Aspects of the Theory of Syntax. The major innovations include a full, formal description of the syntax of a transformational grammar, a directed random phrase structure generator, a lexical insertion algorithm, an extended definition of analysis, and a simple problem-oriented programming language in which the algorithm for application of transformations can be expressed. In this paper we present the system as a whole, first discussing the general attitudes underlying the development of the system, then outlining the system and discussing its more important special features. References are given to papers which consider some particular aspect of the system in detail.
An anomaly in space-time characteristics of certain programs running in a paging machine
The running time of programs in a paging machine generally increases as the store in which programs are constrained to run decreases. Experiment, however, have revealed cases in which the reverse is true: a decrease in the size of the store is accompanied by a decrease in running time.
An informal discussion of the anomalous behavior is given, and for the case of the FIFO replacement algorithm a formal treatment is presented.
