We propose a method for implementing “the election process” - finding an extrema of values computed in a multiprocessor network. It operates in an average time less than Log2(N), for a network of size N. It requires a single register, memory cell, or global buss into which all the processors can attempt to write, with the success of one guaranteed; and from which they may all read, in parallel. A second method is given which guarantees termination in O(Log2(MAX)) steps.

An algorithm is presented which permits any arbitrary subset of the cells of a content addressable tresselated automaton (CATA) to communicate with any other arbitrary subset.

Recently, while considering the connection of a 48 bit word computer to a 16 bit computer, we felt the need for a fast and inexpensive device that would multiply a binary address by a factor of three. Since 3N = N + 2N, there is an obvious solution of providing a normal adder circuit and presenting one set of inputs with N and the other with N-shifted left one place. But, there is a great deal of redundancy here since knowing one input we have complete knowledge of the other.

SOCRATES is a "Stack-Oriented Computer for Research and Teaching--an Exploratory System." It is designed around push down stacks as its main store. The structure of the machine is specified and several aspects of programming it are investigated.

This note investigates the increase in parallel execution rate as a function of the size of an instruction dispatch stack with lookahead hardware. Under the constraint that instructions are not dispatched until all preceding conditional branches are resolved, stack sizes as small as 2 or 4 achieve most of the parallelism that a hypothetically infinite stack would.

This note reports the results of an examination of seven programs originally written for execution on a conventional computer (CDC-3600). We postulate an infinite machine, one with an infinite memory and instruction stack, infinite registers and memory, and an infinite number of functional units. This machine wiU exectite a program in parallel at maximum speed by executing each instruction at the earliest possible moment.

This paper discussed a method for coupling a very high speed CPU to relatively slow storage devices. The method consists of treating storage references in the same fashion as multi-programming systems treat I/O references.

A method, called conditional interpretation, is proposed which will allow small computers to have as large a set of instructions as may be desired without using a large number of bits to hold the operation code. The method is based on the redundancy of machine language instruction sequences. Most machine language instructions have a limited number of "reasonable" successors. For example "load accumulator" hardly ever follows "enter accumulator." It turns out that if each instruction is allowed seven successors plus an "escape instruction," only about one out of every five instructions needs to be an "escape" to get to one of the less usual successors. Seventy-five percent of the time the desired "next instruction" is among the seven permitted successors. Since each instruction has its own, possibly unique, set of successors, the interpretation of the stored op-code is conditional upon the state of the machine.

The static and dynamic utilization of a set of machine op-codes is examined. Two measures of the effective use of machine instructions are discussed and applied to samples of hand-coded programs and object code.

A method of determining the number of responders to a search in an associative memory is presented. It is shown that less than one full adder per memory cell is required and that the maximum delay in establishing the count is proportional to n, where n is the log to the base 3 of the number of memory cells.

This paper presents an algorithm for sorting a collection of items that are already almost sorted. It is assumed that each item has a sorting key associated with it and that it is desired to arrange the items so that their keys are in ascending order. If duplicate keys are encountered only the item associated with the ‘latest’ occurrence of the duplicated key is preserved, earlier occurrences being discarded. The need for such an algorithm is most obvious in the case of on-line record editing in a time-sharing environment where most of the records or sentences will have been entered correctly, but occasionally there will be a replacement of an old record or the insertion of new ones into already entered text. This algorithm first constructs a table with one entry in the table for each part of the source text that is internally ordered. It then performs an N-way merge of the parts.

Abstract—The problem of resolving multiple responses to a search in an associative or content-addressable memory is considered. A resolver is presented whose maximum delay is proportional to the logarithm of the size of the memory.