Search
Join ACM

Computing Profession

Advertisement

Research and Advances Sep 1 1969

On multiprogramming, machine coding, and computer organization

The author feels that the interrupt feature which is available in most modern computers is a potent source of programming pitfalls and errors, and that it therefore may heavily contribute to the unreliability of programs making use of it. A programming scheme is presented which avoids the concept of the interrupt and permits the specification of concurrent (or pseudoconcurrent) activities in a supposedly more perspicuous manner. It is intended to serve as a basis for the construction of operating systems, which are prime examples of programs with concurrent activities. The scheme includes a set of basic instructions for the generation, termination, and synchronization of parallel processes. A set of routines representing these instructions and thereby simulating a hypothetical machine organization has been implemented and tested on the IBM System/360. Two programs using these instructions, written in PL360, are presented.
Research and Advances Sep 1 1969

Compact list representation: definition, garbage collection, and system implementation

Compact lists are stored sequentially in memory, rather than chained with pointers. Since this is not always convenient, the Swym system permits a list to be chained, compact, or any combination of the two. A description is given of that list representation and the operators implemented (most are similar to those of LISP 1.5). The system garbage collector attempts to make all lists compact; it relocates and rearranges all of list storage using temporary storage. This unique list-compacting garbage collection algorithm is presented in detail. Several classes of the macros used to implement the system are described. Finally, consideration is given to those design factors essential to the success of a plex processing system implementation.
Research and Advances Aug 1 1969

The MAD definition facility

One of the first definition facilities for higher level languages is described. Users of the language can define new operators and/or data types into the MAD language, so that their use appears as if they were predefined. Information is given on how one writes definitions, as well as on much of the motivation behind the form in which definitions are written. Some conclusions are drawn about future definitional facilities.
, , and
Research and Advances Aug 1 1969

Computing capabilities at Argentine and Chilean universities

The author reports on a trip to universities in Argentina and Chile during November 1968, describing university conditions and computing activities. As elsewhere, these universities are experiencing student discontent with the status quo and the solutions they are attempting contrast: Argentina is excluding students from participating in university government; Chile is allowing such participation. University computing service and academic activities are limited. The number of computers is small and so is the capacity, none larger than an IBM 360/40; with some exception, computing science academic programs are rare. This situation is by no means attributable to those responsible for computing developments, who strive for excellence; rather the “system” is hard to overcome. Universities, especially those with strong European traditions, adapt slowly to new academic resources and disciplines; superimposed are the severe technological and economic constraints of the developing nation. Consequently, in the absence of conscious government emphasis on strengthening computing capabilities, future progress may be retarded.
Research and Advances Jul 1 1969

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.
Research and Advances Jun 1 1969

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.
and
Research and Advances Jun 1 1969

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.
, , , and
Research and Advances Jun 1 1969

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.
, , and
Research and Advances May 1 1969

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.
and
Research and Advances May 1 1969

Time-sharing and batch-processing: an experimental comparison of their values in a problem-solving situation

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.
Research and Advances May 1 1969

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.
Research and Advances May 1 1969

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.
, , and
Research and Advances May 1 1969

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.
Research and Advances May 1 1969

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.
and
Research and Advances Apr 1 1969

Analysis of boolean program models for time-shared, paged environments

Directed graphs or their associated matrices are frequently used to represent the logical structure of sequences of computer instructions. Such techniques are used and, in addition, data references are represented in a nondirected model. The complete structural specification of a program is represented by a combined model. A transformation of the combined model yields a new model in which additional timing information is also contained. Analysis of these models prior to execution yields information valuable in determining segmentation of instructions and data for a time-shared environment, as well as for initial page loading; during execution, the analysis may be used for “look ahead” control of page turning.
Research and Advances Mar 1 1969

Organizing matrices and matrix operations for paged memory systems

Matrix representations and operations are examined for the purpose of minimizing the page faulting occurring in a paged memory system. It is shown that carefully designed matrix algorithms can lead to enormous savings in the number of page faults occurring when only a small part of the total matrix can be in main memory at one time. Examination of addition, multiplication, and inversion algorithms shows that a partitioned matrix representation (i.e. one submatrix or partition per page) in most cases induced fewer page faults than a row-by-row representation. The number of page-pulls required by these matrix manipulation algorithms is also studied as a function of the number of pages of main memory available to the algorithm.
and

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 Involved

Communications 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