THE UNIVERSITY OF MICHIGAN INDUSTRY PROGRAM OF THE COLLEGE OF ENGINEERING A UNIVERSAL COMPUTER CAPABLE OF EXECUTING AN ARBITRARY NUMBER OF SUB-PROGRAMS SIMULTANEOUSLY John Holland January, 1960 IP-412

TABLE OF CONTENTS Page 1. INTRODUCTION..............................................o 1 2. GENERAL DESCRIPTION.............................. 2 3o PATH-BUILDIN G.................................... 4 4. EXECUTION................................................ 8 5. INPUT...o........................................ o 13 6. SUMMARY OF ORGANIZATION AND SYMBOLS................... 14 7. COMMENT.................................................. 1 ii

LIST OF FIGURES Figure Page 1 A Module. a,. a o........ o o.... a 18 2 Lines of Predecessors...o.....................o.. 19 3 Modules Used in the Execution of an Instructiono o 20 4 Control of Module by Storage Register.o...00000o. 21 5 Two Interacting Subroutines...o.........o.... 22 iii

1, INTRODUCTION This paper describes a universal computer capable of simultaneously executing an arbitrary number of sub-programs, the number of such sub-programs varying as a function of time under program control or as directed by input to the computer. Three features of the computer are: (1) The structure of the computer is a 2-dimensional modular (or iterative) network so that, if it were constructed, efficient use could be made of the high element density and "template" techniques now being considered in research on microminiature elements. (2) Sub-programs can be spatially organized and can act simultaneously, thus facilitating the simulation or direct control of "highly-parallel" systems with many points or parts interacting simultaneously (e.g., magneto-hydrodynamic problems or pattern recognition). (3) The computer's structure and behavior can, with simple generalizations, be formulated in a way that provides a formal basis for theoretical study of automata with changing structure (cf. the relation between Turing machines and computable numbers). The computer presented here is one example of a broad class of universal computers which might be called universal iterative circuits. This class can be rigorously characterized and formally studied (the characterization will be published in another paper). The present formulation is intended as an abstract prototype which, if current component research is successful, could lead to a practical computer. -1

2. GENERAL DESCRIPTION The computer can be considered to be composed of modules arranged in a 2-dimensional rectangular grid; the computer is homogeneous (or iterative) in the sense that each of the modules can be represented by the same fixed logical network. The modules are synchronously timed and time for the computer can be considered as occurring in discrete steps, t = 0, 1, 2,.o a Basically each module consists of a binary storage register together with associated circuitry and some auxiliary registers (see Figure 1). At each time-step a module may be either active or inactive. An active module, in effect, interprets the number in its storage register as an instruction and proceeds to execute it. There is no restriction (other than the size of the computer) on the number of active modules at any given time. Ordinarily if a module M(i,j) at coordinates (i,j) is active at time-step t, then at time-step t+l, M(i,j) returns to inactive status and its successor, one of the four neighbors M(i+l,j), M(i,j+l), M(i-l,j), or M(i,j-l), becomes active. (The exceptions to this rule occur when the instruction in the storage register of the active module specifies a different course of action as, for example, when the instruction is the equivalent of a transfer instruction). The successor is specified by bits sl, s2 in M(i,j)?s storage register. If we define the line of successors of a given module as the module itself, its successor, the successor of the successor, etc., then a given sub-program in the computer will usually consist of the line of successors of some module. Since several modules can be active at the same time the computer can in fact execute several sub-programs at once. -2

-3We have noted parenthetically that there are orders which control the course of action - there are also orders equivalent to store orders which can alter the number (and hence the instruction) in a storage register. Therefore, the number of sub-programs being executed can be varied with time, and the variation can be controlled by one or more sub-programs. The action of a module during each time-step can be divided into three successive phases~ (1) During phase one, the input phase, a moduleVs storage register can be set to any number supplied by a source external to the computer. The input phase will be discussed in Section 5. (2) During phase two, an active module determines the location of the operand, the storage register upon which its instruction is to operate. This the module does by, in effect, opening a path (a sequence of gates) to the operand. Phase two, called the path-building phase, will be discussed in Section 3. (3) During phase three, the execution phase, the active module interprets and executes the operation coded in its storage register. The execution phase will be discussed in Section 4.

3. PATH-BUILDING An active module determines the location of the storage register upon which its instruction is to operate by, in effect, opening a path to it. The path-building action depends upon two properties of modules First, by setting bit p in its storage register equal to 1, a module may be given special status which marks it as a point of origination for paths; the module is then called a P-module. Secondly, each module has a neighbor, distinct from its successor, designated as its predecessor by bits ql, q2 in its storage register; the line of predecessors of a given module MO is then defined as the sequence of all modules [M0,M1,.,o,Mk,...] such that, for each k, Mk is the predecessor of Mk_l and Mk_l is the successor of Mk (see Figure 2). Note that the line of predecessors may in extreme cases be infinitely long or non-existent. The line of predecessors of an active module ordinarily serves to link it with a P-module (through a series of open gates). During the initial part of phase two the path specification bits yo,...-yn and dl, d2, in the storage register of an active module MN, are gated down its line of predecessors to the nearest P-module (if any) along that line. The path specification bits are then used by the P-module to open a path to the operand (the storage register addressed by the active module). Each path must originate at a P-module and only one path can originate at any given P-module. The path originating at a P-module is gated by means of a sequence of auxiliary registers called *-registers. Each module possesses 4 *-registers and if the module belongs to a path in direction (b1, b2) the appropriate "*-register, (b1, b2)*, is turned -4

-5one When (bl, b2)* is on it gates lines (to be described) from the module M(i,j) to its neighbor M(i+bl, j+b2) permitting certain signals coming into M(i,j) to be passed on to M(i+bl, j+b2) and vice-versa. Since each *-register gates a separate set of lines, a module may (with certain exceptions) belong to as many as four paths. Once a *-register is turned on it stays on until turned off thus a path, once marked, persists until erased. The modules belonging to a given path can be separated into subsequences called segments. Each segment of the path is the result of the complete phase two action of a single active module. A segment consists of y modules extending parallel to one of the axes from some position (i,j) through positions (i+bl, j+b2), (i+2bl, j+2b2),..., (i+(y-l)bl, J+(y-l)b2), where b1 - + 1 or 0 and b2 = + (1 - Ibll); the module at (i+ybl, j+yb2) will be called the termination of the segment (note that the termination of the segment is not a member of the segment). The segments are ordered so that the first segment constructed has as its initial module the P-module. The kt segment constructed as part of the path has as its initial module the termination of the k-lth segment~ If the path consists of n segments, the termination of the nh segment (the last segment constructed) will be called the path termination (see Figure 3). As noted, the path specification bits yn, eo y0 and dl, d2 are gated down the line of predecessors from the storage register of the active module to the nearest P-module at the start of phase two. If yn = 0, bits Yn-l,.o', yo and dl, d2 determine the length and direction,

-6respectively, of the new segment. The total number of digits Yn.. o, y0 equal to 1 gives the length of the segment - if j of the digits are equal to 1 then the segment will be j modules long. The digits dl,d2 turn on and set an auxiliary register, the direction register, in the initial module of the new segment. This gives the direction bl,b2 of the segment. The direction registers of the other modules belonging to the segment are all off, but each of the modules belonging to the segment (including the initial one) has its (bl,b2)* register turned on. When Yn=l, the final segment of the path originating at the P-module is erasedo That is, the direction register in the initial module of the last segment is turnedoff and, as a consequence, all *-registers marking the last segment are turned off. If the path consists of a single segment or none at all the effect of y nl is to turn off the direction register in the P-module thereby making the P-module the termination of the path. That is, in this latter case, the path has no segments but it does have a termination - the P-module itself (note that the status of the P-module is unchanged). The following additional rules apply to paths~ (1) When a given module is the termination of several paths and direction register on-pulses arrive over more than one path at the same time, t, the result is no action - the direction register is not turned on and none of the paths are extended. (2) Only one path can proceed through a module in which the direction register is on. Whenever the direction register of a given module M is turned on or given a new setting, any paths already running through that module will now have it as their terminationo Furthermore,

-7for each such path, the portion lying between M and the previous path termination is at once erased - the *-registers and direction registers marking that portion of the path are turned off. (3) No P-module can belong to any part of a path other than its origin. If a path in the process of construction reaches a P-module then all construction ceases and the P-module becomes the termination of the path regardless of the value of digits Yn, Yn-l,.,~ YO- Further extension of the path will not be carried out unless the P-module's status is changed (its p bit set to zero).

4. EXECUTION Three modules play an important role during the execution phase of an active module: the active module itself holds the order code in bits ii1 i2, i3 of its storage register; the storage register of the nearest path termination contains the word to be operated on (the operand); finally there must be a module which serves as accumulator (see Figure 3)0 In order to serve as an accumulator, the storage register of a module must first have bits (p,a) in it set to the value (0,1), giving the module special status - A-module status. (Note that this means a module in Pmodule status, p = 1, cannot be an A-module)o If M(i,j) is an active module then the first A-module along its line of predecessors serves as the accumulatoro An A-module serves, in effect, to terminate a line of predecessors, since it can have no designated predecessor (see the rules at the end of this section)o In the present formulation there are eight basic orderso (1) The arithmetic operation ADD. Execution of ADD causes the number in the storage register at the nearest path termination (the operand) to be transferred to the nearest A-module and there added to whatever number is in the storage register of the A-module. (By using complements and iteration all the arithmetic operations, such as subtraction and multiplication, can be accomplished by means of this operation)o (2) The storage operation STORE. Execution of STORE causes the number in the storage register of the nearest A-module to be transferred to the storage register at the operand. -8

-9(3) The transfer operation TRANSFER ON MINUSa Execution of TRANSFER ON MINUS depends upon the number in the storage register in the nearest A-module. If Yn = 0 in this number then the active module, after completing phase two, becomes inactive and its successor becomes activeo If Yn = 1 then the module at the nearest path termination, rather than the successor, becomes activeo (4) The index operation ITERATE SEGMENTo If yn = 0 in the nearest A-module, execution of ITERATE SEGMENT (upon completion of phase two) reduces the number in the A-module by 1 and the active module remains active without causing its successor to become activeo If yn = 1 then execution of the order simply causes the successor to become active and the active module inactive at the completion of phase oneo This operation provides a convenient means of building long paths in a given direction since, if N is the number in the nearest A-module, the path building phase of the active module is iterated N times0 (5) SET REGISTERS causes the first 9 bits of the number in the nearest A-module to be used to set all 9 auxiliary registers at the nearest path termination, the jth register being set on if the jth bit is a one (see Section on Summary of Organization and Symbols)o It is important that the SET REGISTER order can give the operand module active status by setting the appropriate auxiliary registera In this case the active module gives rise to two active modules on the next time-step, its successor and the operand module0 By this means one sub-program can initiate activity in another0

-10(6) RECORD REGISTERS causes the state of the 9 auxiliary registers at the nearest path termination to be recorded in the first 9 bits of the nearest A-module (in the same order as used by the SET REGISTERS instruction) (7) NO ORDER causes the execution phase to pass without the execution of an order. (8) STOP causes the active module to become inactive without passing on the activity to its successor at the next time-stepo With the exception of the STOP, ITERATE SEGMENT, and TRANSFER orders, the active module becomes inactive and its successor becomes active at the conclusion of the execution of an ordero It is possible for a given active module to have no nearest P-module (or A-module) for any one of three reasons~ (1) the module does not have a line of predecessors, (2) none of the modules along the line of predecessors is currently designated a P-module (or A-module), (3) there is no P-module along the line of predecessors between the active module and the nearest A-moduleo If there is no nearest P-module then there is neither pathi:building nor execution of instruction with respect to the active module (regardless of the content of its storage register)0 If there is no nearest A-module along the line of predecessors then the instruction of the active module is not executed although the path building phase will be carried out (assuming a nearest P-module)o The following additional rules apply to active modules and their action with respect to P-modules and A-modules~

-11(1) If MO belongs'to the line of predecessors of MI, if the nearest P-module of MO is also the nearest P-module of Mn, and if Mo and Ml are both active, then the action of MQ proceeds normally but Ml's action is as if it had no nearest P-moduleo (2) If MO and M1 are situated as in rule (1) except that they have the same nearest A-module, without sharing the same P-module, then the action of MO proceeds normally but M1 acts as if it -were executing a NO ORDER instruction0 (3) As mentioned earlier, a module can be given A-module status by setting the pair of bits (pa) to the value (0 1)o This turns on an auxiliary register in the module, the A-registero At the same time the bits of another auxiliary register pair, the (Di, D2)- register, are set to match the bits sl, s2 in the module's storage register; ioeo, when the A-register is on the (D1, D2)- register indicates the successor of the A-module o Once a module is given A-module status it can be returned to normal status only in one of two restricted ways. The first way requires that a STORE order be executed by an active module which has the given Amodule as its operand module (nearest path termination)~ Then, if bit a is 0 or bit p is 1 in the number being stored, the A-module reverts to normal status and the word in its storage register is that specified by the STORE instruction. Otherwise the A-module is unchanged, the STORE order not being executed. The other way of returning an A-module to normal status requires that the A-module receive external input during phase one

-12(see Section on Input ) The above restrictions prevent the A-module from changing status when numbers are placed in its storage register during the normal course of its operation as an accumulator. During the time a module is an A-module the bits in its storage register are not interpreted in any way except as the digits of a binary numberO (4) A module in A-module status can become part of a path (or several paths) so long as it is not to be the initial module of a path segment. In this latter case the path building action, which would make the A-module the initial module of a segment is not carried out - the A-module remaining the termination of the patho (5) A given module can be acted upon simultaneously by 2, 3, or even 4 STORE instructions if it is the termination of more than one pathO Some provision must then be made to resolve conflicts when the numbers being stored are not identicalO In the present formulation the conflict is resolved digit by digit~ a 1 is stored at bit j in the storage register if and only if at least one of the incoming numbers has a 1 at position jo (6) When a STORE instruction changes the word in the storage register of a module it is assumed that this change does not take place until the completion of phase threeo Thus, for example, there is no conflict when the STORE instruction of an active module acts upon that module's own line of predecessors or, for that matter, upon the module itselfo (7) If an active module has an A- or P-module as successor then, at the next time-step, the successor of the A- or P-module becomes active, rather than the A- or P-module itself (unless, of course, the instruction just executed specifies otherwise)o

5. INPUT During phase ones the initial phase of each time-step, a module's storage register can be set to any arbitrarily chosen value and its auxiliary registers to any desired condition~ The numbers and conditions thus supplied are the computer's inputo Although the number in the storage register can be arbitrarily changed at the beginning of each time-step, it need not be; for many purposes the majority of modules will receive input only during the first few moments of time (?"storing the program") or only at selected times tl1 t29 o,, ("data input"), Of courses some modules may have a new number for input at each time-step; in this case the modules play a role similar to the inputs to a sequential circuito -15

6. SUMMARY OF ORGANIZATION AND SYMBOLS As noted in the general description of Section 2, each module consists of a storage register plus some auxiliary registerso The discussions of Sections 3, 4, and 5 indicate that the auxiliary registers required are1) the E-register, a one bit register which is on if and only if the given module is active; 2) the A-register, a one bit register which is on if and only if the given module is an A-module (see rule (3) of Section 4 ); 3) the D-register, a one bit register which is on if and only if the given module is the initial module of a path segment; 4) the (DiJ D2)-register, a register, with two bits of storage, which indicates the direction (bl, b2) of a segment if and only if the D-register is on and which indicates the direction of the modulets successor if and only if the A-register is ono 5) the (b1, b2)*-registers, each is a one bit register which is on if and only if the given module is a member of a path segment with direction (bl, b2)o For formal purposes we can symbolize the state of a given register, X, at coordinates (i,j) and time t by the predicate X(i,j,t) with X(i,j,t)=l if the given register is on at time to The storage register of each module in the present formulation consists of n+12 bits (see Figure 4) labelled in the following ordero bit number: n+12 n+1 oo 12 11 10 9 8 7 6 5 4 3 2 1 label: Yn Yn-1 y~~ Y do d2 i2 i2 i3 Sl S2 l q2 p a -14

-15The bits sl' s2 and qpl q2 designate the successor and predecessor, respectively, of the module. If bit p is 1 the module has P-module status~ If the pair of bits (pa) are set to the value (091) as the result of input or a STORE operation, the module has A-module status. During the path building phase bits Yn,,,. yo and dig d2 in an active module are interpreted as segment length and direction respectively. During the execution phase bits il, i2^ i3 in an active module are interpreted as the operation to be performed, The word in the storage register of an A-module is treated strictly as a binary number with yn being the sign bit and the other n+ll bits being arranged as indicated with Yn-l being the high order bit and a being the low order bite

7, C OMENT A universal machine in which the programs have a -spatial organization has several properties over and above those usually associated with Turing machines and their concrete counterparts. For example, cycles in the program can actually be stored as cycles (of successors) in the rectangular grid (see Figure 5). This, in effect, provides each cyclic sub-program with an instruction address counter which counts modulo the number of instructions in the sub-program (cfo, an index register which can be set to cycle modulo any base number), Furthermore, each sub-program can be allotted a certain area in the grid and this allows the spatial arrangement of the sub-programs to match, for example, the structural organization of a process which is being simulated - each subprogram in this case directly simulating one of the components of the processo Efficient programming of certain types of problem will require techniques similar to those required for asynchronous operation. That is, when several subprograms are operating simultaneously, each subprogram will from time to time require results from other subprograms, however these results will not in general be available at just the time desired, In problems like this, usually arising in the control or simulation of "highlyparallel" systems with many points or parts interacting simultaneously, the programmer will employ many of the techniques of the logical designero Problems such as the one just discussed emphasize the desirability of a computer formulation amenable to theoretical investigation, The present formulation is one example of a broad class of computers which can be -16

-17rigorously characterized and investigated by abstract deductive techniqueso Actually, the definition of this class of computers comes as part of an effort to provide a formal basis for the study of growing automata. By considering the rectangular grid to be infinite (or potentially infinite) in each of its dimensions (in analogy to the infinite tape of a Turing machine) many problems of automata theory can be expressed in a formal fraamework similar to that provided by Turing machines for problems of computabilityo Thus, for example, models of various processes can be stated as programs, or classes of programs, for the machine and investigated both directly and theoretically. There are several variants of the formulation given here which yield computers which are either more flexible or have simpler moduleso As a single instance, the path building procedure could be altered to make branching paths possible; in this way the same subprogram could operate on several storage registers simultaneouslyo A. final word about concrete realization of such a computer~ a partial rendering of the logical diagrams for a module in the described computer indicates that a module with a 40 bit storage register could be constructed with approximately 1000 basic elementso If this is actually the case and if switching is accomplished with micromodular densities, say 108 elements per cubic foot, then the basic portion of a computer with 100,000 modules should be realizable within a volume of a few cubic feet (exclusive of input-output equipment, power supply, etco )

-18M(i+l,j) STORAGE REGISTER AUX. REGISTERS M(ij-I) l M(i,j+I) - ^ (i ~MJ) I —[ _I I M(i-I, i) -* ACTION LINES | — PATH LINES Figure 1. A Module.

-19t - * SUCCESSOR --- PREDECESSOR I ft-l ACTIVELY CONNECTED --- - LINE OF PREDECESSORS Figure 2. Lines of Predecessors.

-20P X I T X AIE M E (I — NSTR X ACTIVE MODULE ("INSTRUCTION") P MODULE IN P - STATUS T PATH TERMINATION ("OPERAND") A MODULE IN A-STATUS ("ACCUMULATOR") EH —5- LINE OF PREDECESSORS -E- - -- PATH Figure 3. Modules Used in the Execution of an Instruction.

-21Yi Yn-i yo y di d2 i'12 13 14 s s2 ql q2 P o [I I I ~ I I [Ir r I 61 11 1' 1 Figure. Control of Module by Storage Register. Figure 4. Control of Module by Storage Register.

-22A II iE> —B —— 5 —EE1 - I- I PP I - D I I " mA ~I P A P MODULE IN P-STATUS A MODULE IN A- STATUS <Hf -H3 LINE OF PREDECESSORS -F} —FJ- PATH Figure 5. Two Interacting Subroutines.