Research and Advances
Advertisement
Multiprogram scheduling: parts 1 and 2. introduction and theory
In order to exploit fully a fast computer which possesses simultaneous processing abilities, it should to a large extent schedule its own workload. The scheduling routine must be capable of extremely rapid execution if it is not to prove self-defeating.
The construction of a schedule entails determining which programs are to be run concurrently and which sequentially with respect to each other. A concise scheduling algorithm is described which tends to minimize the time for executing the entire pending workload (or any subset of it), subject to external constraints such as precedence, urgency, etc. The algorithm is applicable to a wide class of machines.
A technique for counting ones in a binary computer
Standard methods of counting binary ones on a computer with a 704 type instruction code require an inner loop which is carried out once for each bit in the machine word. Program 1 (written in SAP language for purposes of illustration) is an example of such a standard program.
The etymology of the word code is most interesting. It seems evident that in its original form it has reference to the paginated format of a book as distinguished from the earlier scrolls. Books with leaves fastened together at a common edge were apparently used in Roman times to record compilations of laws, and this is the basis for the original meanings of code, as a systematic collection, compilation, or formulation of laws, principles, rules or regulations.
A start on automatic storage assignment
This technique outlines a method whereby equation sets can be ordered in computational order and checked for compatibility. The technique also allows one to note what equations can be computed in parallel (provided one has parallel arithmetic capabilities) or can be considered a logical entity, i.e., segment. Furthermore, the technique will assist one to intelligently allocate high-speed memory (HSM) so that memory is reassigned to other duties as soon as its present duties are fulfilled. Last, the technique appears to be simple and fast to implement.
For centuries the decimal number system reigned supreme, except, perhaps, among the Mayan Indians, until the advent of digital computers brought the binary and octal systems into the limelight. This paper introduces another number system which may prove useful for manipulating complex numbers on machines.
Syntactic and semantic augments to ALGOL
The purpose of this paper is to propose a set of syntactic and semantic augments to ALGOL. The proposed extension are designed to facilitate the description of “string” manipulation in that language; they do not constitute a comprehensive language for symbol manipulation. Several such languages (LISP, IPL, …) already exist—many more will be designed and advantageously used in the future. It is felt that such languages belong in the repertoire of some language-system which contains a hierarchy of languages as well as nested “continua” of languages. In such systems, new languages may be embedded, appended, extracted at will. The fact that ALGOL is, implicitly, such a language-system seems to be only dimly recognized, even by designers. In any event, what is proposed in the sequel is not a language for symbol manipulation—qua language; but rather, a set of obvious extensions to the “algebraic-language” portion of ALGOL. To be sure, these extensions are complete in the sense that they are sufficient to describe symbol manipulations, but after all, the same statement holds for machine-language. Moreover, the extensions do not constitute a minimal set of primitives for string or symbol manipulations—in the sense that complementation, shifting, … are primitives for machine arithmetic. Such primitives are essential only to machine designers (including designers of “augmented machine”, the basic machine augmented by subroutines for arithmetics not included in the hardware); to append only such primitives to ALGOL is to visit the omissive sins of the machine designers upon the users of ALGOL.
Decoding combinations of the first n integers taken k at a time
The following problem arose in connection with some studies involving game programming: the representation of any position in the game tree was formed by a sequence of k different integers selected from the first n integers. It was desired to decode any of these representations to a unique memory address such that all such addresses formed a compact group in the memory. Mathematically, the problem was to find a transformation of the representation such that any of the n!/(n - k)! sequences transformed uniquely to one of the set of integers from 0 to [n!/(n - k)! - 1]. A procedure for this is described here.
Macro instruction extensions of compiler languages
Macroinstruction compilers constructed from a small set of functions can be made extremely powerful. In particular, conditional assembly, nested definitions, and parenthetical notation serve to make a compiler capable of accepting very general extensions to its ground language.
A control system for logical block diagnosis with data loading
This paper describes a section of an integrated diagnostic monitor system which facilitates the checking of sections of instructions or subroutines anywhere in the object program. A new method of specifying all diagnostic operations in a format similar to a computer program makes the system convenient to use and relatively simple to understand. The paper also describes a number of other novel diagnostic features which can be included in the system.
A note on the use of the Abacus in number conversion
Conversion of integers in both directions between the base ten and any desired base can be accomplished with remarkable simplicity by use of the abacus. In fact, the conversion procedures are far more cumbersome on the electric desk calculator, for reasons which will be apparent.
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