Computing Applications
Advertisement
Block structures, indirect addressing, and garbage collection
Programming languages have included explicit or implicit block structures to provide a naming convenience for the programmer. However, when indirect addressing is used, as in SNOBOL, naming constraints may be introduced. Two modifications to SNOBOL are described, resulting in two desirable consequences: (1) naming constraints disappear even when there is indirect addressing within function definitions; and (2) there is a significant saving in the number of calls to the garbage collector, because some garbage is collected, at little expense, each time a function returns to its calling program. These modifications have been implemented as an extension to a SNOBOL dialect.
Some techniques for using pseudorandom numbers in computer simulation
An alogorithm is described by which uniform pseudorandom integers may be used to construct binary “numbers” in which the probability that each bit in the word is a 1-bit and can assume any desired parameter value.
Techniques for making use of such “numbers” in simulation programming are described.
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.
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.
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.
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.
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.
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.
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.
Dynamic space-sharing in computer systems
A formalization of relationships between space-sharing, program behavior, and processor efficiency in computer systems is presented. Concepts of value and cost of space allocation per task are defined and then value and cost are combined to develop a single parameter termed value per unit cost.
The intent is to illustrate a possible analytic approach to the investigation of the problems of space-sharing and to demonstrate the method on sample problems.
An experimental comparison of problem-solving using time-sharing and batch-processing computer systems conducted at MIT is described in this paper. This study is the first known attempt to evaluate two such systems for what may well be the predominant user population within the next decade—the professionals who, as nonprogrammers, are using the computer as an aid in decision-making and problem-solving rather than as a programming end in itself.
Statistically and logically significant results indicate equal cost for usage of the two computer systems; however, a much higher level of performance is attained by time-sharing users. There are indications that significantly lower costs would have resulted if the time-sharing users had stopped work when they reached a performance level equal to that of the batch users. The users' speed of problem-solving and their attitudes made time-sharing the more favorable system.
Automated printed circuit routing with a stepping aperture
A computer program for routing interconnections on a two-sided printed circuit board with a regular pattern of lines, pins (terminals), and vias (feed-through holes) is described.
In this program, each interconnection is given a planned routing—typically, down from the upper pin, through a via, and horizontally to the lower pin. From the top, a virtual aperture (i.e. a long horizontal slit) is stepped down the board. The planned routing is the basis for rerouting interconnections within the aperture to resolve conflicts for lines and vias below the aperture and to maximize the effective line usage. If a conflict has not been resolved before the aperture arrives at the lower pin, interconnections are deleted to resolve the conflict.
Extensions of this technique to the control of crosstalk between routed interconnections and to the problem of obtaining 100 percent interconnect are also discussed.
A note on reliable full-duplex transmission over half-duplex links
A simple procedure for achieving reliable full-duplex transmission over half-duplex links is proposed. The scheme is compared with another of the same type, which has recently been described in the literature. Finally, some comments are made on another group of related transmission procedures which have been shown to be unreliable under some circumstances.
Clarification of Fortran standards—initial progress
In 1966, after four years of effort, FORTRAN became the first programming language standardized in the United States. Since that intital achievement, study and application of the standard specifications have revealed the need for maintenance of the standards. As the result of work intiated in 1967, as initial set of clarifying interpretations has been prepared. The nature of the maintenance, corrections to the standard specifications, and completed interpretations are reported.
An automatic grading scheme for simple programming exercises
A discussion is given of alterations that were made to a typical university operating system to record the results of programming exercises in three different languages, includeing assembly language. In this computer-controlled grading scheme provision is made for testing with programmer-supplied data and for final runs with system-supplied data. Exercises run under the scheme may be mixed with other programs, and no special recognition of exercises by the operators is necessary.
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