Research and Advances

The method of storage allocation described herein, although new in a few respects, does not represent any sharp break from the past. Rather it is another step of development suggested by experience accumulated over several years with the 704,709 and 7090 FORTRAN systems. The storage assignment method proposed is, in principle, extremely simple and is not specific to FORTRAN or the 7090. Although the method depends only on rather general language aspects, the concrete detail will be illustrated in terms of the aforementioned systems or proposed extensions.

Multiprogramming is defined here as the use of a buffered processor by time-sharing its central control and its memory between two or more object programs under control of an executive system.

We are discussing a method of core allocation proposed for use in a large-scale, real-time, man-machine, data processing and display system.

A storage allocation scheme for a machine with a 2048-instruction core store and a magnetic drum is described. The use of the drum for storing program blocks and/or data must be directed by the programmer through auxiliary information in the ALGOL program. The administrative routines controlling the storage at run time are described in full. A detailed example is given.

The preplanned approach to the storage allocation problem involves using a fixed method of analysis of a problem to produce an efficient computer program incorporating all necessary transfers of information within the multilevels of storage of the computer throughout the running of the object program. The initial description of the problem may be in any suitable source language (FORTRAN, ALGOL, etc.) but should not require any recognition of the limitations caused by the number, size, and speeds of the computer's storage devices (core, tape, disc, number of data channels, etc.) by the programmer. The object program produced should contain all necessary implementing instructions to utilize all of the computer's storage devices in such a manner as to minimize the cost of the program (i.e. maximize the speed of problem solving).

The material presented in this paper is part of the design plan of the core allocation portion of the ACSI-MATIC Programming System. Project ACSI-MATIC is concerned with the application of computer techniques to the activities of certain headquarters military intelligence operations of the U.S. Army. In describing features of organization and record keeping there has been no attempt at completeness, but rather an exploration of the salient aspects of the system to some reasonable level of technical detail.1

Programming is the process of developing a scheme for solving a problem using a computer. The programmer's task is to minimize the cost of achieving a solution. This cost involves the interrelated factors of planning, coding, debugging, storage space, and computation time. The storage allocation problem is the subtask of assigning the space-taking objects (programs and data) to the available storage devices (core, drum, disc and magnetic tape).

Formalization of a general computer storage allocation process is attempted. With a given computer M is associated a fictitious computer M′ essentially identical to M except in respect to possession of unbounded primary storage. Mappings of the total storage set (internal and external) of M into the direct address set of M′ are introduced. A program sequence P for M′ is termed M-admissible (relative to a specific execution time period) if there is a mapping under which P and its effective data referents are all located in the direct address set of M. Storage allocation is considered as a process of establishing for an arbitrary M′ program a sequence of mappings, a decoupling of the program into M-admissible subprograms and a linking set of interludes. An existence proof in terms of a completely interpretive M program as indicated. Some special cases are discussed. Various restrictions on generality of M′ programs are considered under which more practical realization of allocation processes becomes tractable.