THE UNIVER S ITY OF M I C H IGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Department of Communication Sciences Technical Report ITERATIVE CIRCUIT COMPUTERS: / / CHARACTERIZATION AND RESUME OF ADVANTAGES AND DISADVANTAGES John H. Holland ORA Project 03105 under contract with: DEPARTMENT OF THE NAVY OFFICE OF NAVAL RESEARCH CONTRACT NO. Nonr-1224(21) WASHINGTON, D.C. administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR February 1965

RESEARCH PROGRESS REPORT Title: "Iterative Circuit Computers: Characterization and Resume of Advantages and Disadvantages," J. H. Holland, University of Michigan Technical Report 03105-35-T, February 1965; Nonr-1224(21). Background: The Logic of Computers Group of the Communication Sciences Department of The University of Michigan is investigating the application of logic and mathematics to the design of computing automata. Studies of adaptation in an automaton framework forms a part of this investigation. Condensed Report Contents: This report begins with a revised characterization of the class of iterative circuit computers (i.c.c.), the various members of this class being determined by the substitution instances of a quintuple (A, A~, X, f, P) where A is any finitely generated abelian group, A~ is a selected subset thereof, X is any finite set, f and P are finite functions over extensions of X. A brief description of the relation of i.c.c.'s to universal embedding spaces follows. The report concludes with a discussion of some of the advantages and disadvantages of i.c.c. organization for computers constructed of microelectric modules. For Further Information: The complete report is available in the major Navy technical libraries and can be obtained from the Defense Documentation Center. A few copies are available for distribution by the author.

Tile discussion which follows is divided into two partso The first part presents a characterization of the various possible organizations for iterative circuit computers - a streamlined version of the 1960 characterization [4] o The second part comments on some advantages and disadvantages of these organizations for practical machines, particularly micromodular arrayso The class of iterative circuit computers is the set of all devices (automata) specified by theadmissible substitution instances of the quintuple (Ap A, Xg f, P)o Each particular quintuple designates a distinct iterative circuit computer organization- Intuitively the five parts of the quintuple determine the following features of the organization(i) selection of A determines the underlying geometry of the array, particularly the dimension - thus, among other things A determines whether the array is to be planar, 3-dimensional or higher dimensional; (ii) selection of A~ determines the standard neighborhood or connection scheme of modules in the array - this A determines the number and arrangement of modules directly connected to a given module; (iii) selection of X determines the storage register capacity of the module; (iv) selection of f determines the instruction set and related operational characteristics of the module; (v) selection of P determines the path-building (addressing) capabilities of the modules - see belowo More formally, the admissible substitution instances of each of the five quantities areo (i) A must be some finitely generated abelian group having a designated set of generators9 say go, gl oo09 gn, with the restriction 1 -

ti.a.t nio constraining relations involve go That is, the group is free o11 g o The positions of modules in the array are indexed by elements of the subgroup A' generated by g1, o, gn1'The time-step is given t jl by the exponent of g Thus a ^ g,' o,' alr ci.rl-le n'It of A, specifies time-step t at the module having coordinates (jl, 00, jn), By choosing the subgroup A' appropriately the modules can be arranged in a plane, or a torus, or an n-dimensional array, etc, For example, if A' is free on two generators gl g2, an infinite planar array is specified, If the constraining relations 100 gl = e 100 = e, where e is the group identity, are added, a 2-dimensional torus 100 modules in each diameter (10,000 modules total) is specified, (ii) A~ must be a finite set of elements, {al. oo00 ak}, belonging to the subgroup A' of Ao For a module at arbitrary location, A0 specifies the arrangement of directly connected moduleso Thus the t jl n modules directly connected to the module indexed by a = go gl oo gn'4+k. j +k. t jl+kil jn in will be the modules at a. a= gt g l 00o gn, where kil k. a. = g- ooi gn For example, if there is a module at (jl, j2) relative to generators gl, g2, and the directly connected modules are to be at coordinates (jl+l, j2), (jl, j2+l)9 (jl1l, j2), and (jl j22l1), a -1 -i -1. then A~ should be the set {gl g2, glr1 g2 }, where g is the group inverse of go 2 ~

(iii) X can be an arbitrary finite set, The set of internal states of the module is the set S = X x Y where Y is the cartesian product Ik Yi, Y = EIl {a U p} and a. e Aoo That is, Y is the set of k x k matrices with entry Y.. being a. or (o The set X corresponds roughly to the possible states of the module's storage register; the set Y consists of the possible gate configurations for the paths - see the transition equations below~ (iv) f can be an arbitrary finite function of the form f {S U )} k + S f deterimines the instruction set, that is, the permissible transitions of the storage register states - see the transition equations. (v) P can be an arbitrary finite function of the form P: S + Y P determines changes in path gating - see the transition equationso Hlaving chosen (A, A0~ X9 f- P), the behavior of the corresponding iterative circuit computer is completely determined by the following state transition schema: [Sta) will designate the element of S associated with a under the mapping defined recursively by the transition schema. Under interpretation S(a) designates the internal state of the module with space-time coordinates (t, jl, co, j) t Jc' corresponding to a = go g o gn This convention will also be used for the components of S and, in particular, Y. (a) will designate the value of element Y. ij Ij t+l Jl Jn in the matrix Y associated with a, Note also, that goa = go gl O gn designates the module at the e esame space coordinates as given by a, but at time t+1 rather than to] - 3

The transition schema for Y(g a) determines the path-gating at time t+l in the corresponding module in terms of the internal state of the module at time t, S(ca) Under interpretation, if Yij(a) = a. the gate is open so that information can be passed without a time-step delay from the module at a.a through the module at a to the module at ai a; if Yij(a) = 4 the gate is closedo In other words Y 3 9 i3 Y(a) tells how information is to be channeled through the module to its immediate neighbors; the matrices for these neighbors tell how the information is to be sent on from there, etCo (Details of the information transfer are given by the transition equations for S(g a) )o Y.(g) = Y.. (a) if Qij (a) = 0 and P (a) = a. = P..(a) otherwise 13 where Pij(a) is the matrix element (i,j) of P(S(a)) and Qij(a) = A =l qjh(aja) qjh(C) = 0 if Yjh(f) = 4 and Pjh(B) = ah I if Pjh() = =A =i qh(aha)otherwise k whereA x=l qjx is the conjunction of the qjx Under interpretation P. (a) specifies a proposed gate-setting for time t+l at the given module0 Qij(a) prohibits any change in the gate-setting, if there are any changes elsewhere in the path leading through that particular gateo This prohibition prevents the following unstable situations~ (i) a cycle of connections without delay (operation of modules belonging to such a cycle would in general be indeterminant)o m 4

(ii) an indefinitely long chain of connections without delay (otherwise a possibility in certain interesting infinite arrays), The transition equations for X(goa) are given in terms of a function I. B- S, defined for a subset B of Ao Under interpretation I represents input to the computer: X(gNa) = f (S'(ala, 1), o o S'(akak)) where fX is the restriction of f to X and S'(a, i) = S(C) if Yi(goB) = (4, ooo ) ) and I(B) is not defined = 1(B) if Yi(go1) = (), oo ) and I(B)e S = f(S'(Yil (1) "' 1), o, S'(Yik(C) o$, k) ) otherwise where 43= 4 and S'(4{ j) = o Before going on to the practical advantages and disadvantages of such organizations I would like to relate iterative circuit computers to the infinite automaton set down by von Neumann [9]. Von Neumann's cellular automaton is a natural generalization of the McCulloch-Pitts type of automaton (all primitive elements involve a unit delay):O it is an infinite 2-dimensional iterative array of an automaton of that type. In an analogous way iterative circuit computers are natural generalizations of the Burks-Wright type of finite automaton (all switches have negligible delay)o Kleene proved that any behavior realizable by a finite automaton of the Burks-Wright type (ioe. any regular event) can be realized by a McCulloch-Pitts automaton at the cost of a constant delay of two time-steps [6]. Thus there is a negligible difference behaviorally between these two types of finite automatao This is not true of the corresponding infinite generalizations There is no way of simulating finite automata in a von Neumann 5 -

array in such a way that the corresponding behaviors all occur with some constant change of time scale, to = kr + c; the more complex the finite automaton simulated, the slower the simulationo On the other hand, an arbitrary finite automaton can be simulated in an iterative circuit computer, preserving not only behavioral timing (k = 11 but also details of local structural and behavioral relationso Q(go, the simulation can reflect differences corresponding to realization of a switching function in termsof {A, V,"} vso realization in terms of the stroke function,{I}o) In fact, it can be shown such simulation is possible in iterated cellular arrays with locally finite information transfer characteristics only if there is provision for the "making" and "breaking" of non-delay pathso For development of these points the reader is referred to [5]o As a potential organization for computers constructed from micro= electronic components, iterative circuit computers (i0CoCo) exhibit two principal characteristics (1) the entire processing part of the computer can be made up of identical modules uniformly interconnected, (2) within limits of overall storage capacity, the resulting computer can execute an arbitrary number of different programs simultaneouslyo The first characteristic offers the following advantages(i) set-up costs can be spread over a large number of identical units, (ii) production, inventory and repair can all be centered on a single integrated component, (iii) short leads and simple inter-unit connection procedures can be used, (iv). interface between units can easily be kept standard so that improved units (even those involving new instructions) can be added, thus increasing capacity or capability, without shutdown - programs already written will run correctly on the modified device~ ~ 6

The second characteristic offers the following advantageso (i) high computation rates for calculations which can be executed in parallel fashion (many outstanding problems owe their computational difficulty to the fact that the underlying process is essentially parallel, forcing single sequence machines into a scanning procedure; in such cases parallel computations offer computation rates unobtainable by any feasibledecrease in the cycle time of a single sequence machine), (ii) space-sharing becomes possible, ioeo0 the computer can be divided into arbitrary independently-operating sub-computers as required (with store protect features, the sub-computers can be prevented from interaction under central control) and reorganization can be effected, upon demand, under program controlo (iii) because all units are identical and because programs can be executed simultaneously, diagnostic procedures can continually sample modules, with a negligible loss in efficiency- if faulty or failing modules are located9 it is possible to "program around" them until replacement, There are several important disadvantages to iococ organization, Perhaps the most serious disadvantage9 to the present time9 has been the number of active elements required in each moduleo several hundred for reasonable flexibility and ease of operation, Closely related9 is the low average use factor for some elements in the module, For example9 each module usually will have arithmetic capability,; yet at- any given time only a small fraction of the modules will be using this- capabilityo (It is worth noting that reduced use factors are tolerated even in contemporary single sequence machines as a matter of conveniences compiled programs for simulation of highly parallel systems can be 3 or 4 times slower than "handcrafted"' programs, resulting in a lowered effective use factor " 7

for the-arithmetic unit,) The importance of these disadvantages decreases as the average cost of a module dropso If the cost of production is largely set-up cost, it may be possible to produce complicated modules for what it presently costs to produce and assemble a few transistorso Should this happen, average use factor for individual elements is no longer a reasonable measure of overall machine efficiencyo Other potential disadvantages center on problems of internal access and broader problems of programming languages and programming convenienceo Some aspects of these problems have been investigated (see [2], [7)] and [8]), but they remain largely unexploredo The internal accessing problem stems from the procedure used to locate operands - an operand is accessed by "building a path" (opening a sequence of gates) to it0 Two difficulties ariseo One depends on the number of operands accessible to any module via a reasonable number of path-building operations, The other concerns path interference (crossover, multiple access9 etCo)o The first of these is less a problem than it seems at first sighto Assume that no more than 10 gates can be opened, for a given path extension, in one machine cycle (ibeo each path can be extended through at most 10 modules in one machine cycle), Still in two machine cycles, any of 400 modules can be accessed from any given module in a 2-dimensional machine where each module has four nearest neighbors0 The-problem of path interference is more serious; however there are at least two ways of'alleviating this problem: higher dimensionality [8] or path-building via trunk lines [3], Both can be used together and both also further reduce the first problemo Programming c9nvenience and the design of programming languages for an ioCoCo are extensive problems not likely to be solved in a fell swoopo One or two comments may show the scope of the problem and where hope lieso For some kinds <~8 -

of problems, programming is actually simpler than for conventional single sequence machineso The solution of partial differential equations in 3-space and time (the weather problem, etc,],, by conventional methods on a single-sequence computer, requires that about 90% of the program be given over to scanning logic, boundary manipulation, etCo These considerations are eliminated in an appropriate ioCoCo, since the basic grid-point sub-routine can simply be copied throughout - all grid-points are then updated simultaneously. In other contexts, because programs can be executed simultaneously, we face the usual difficulties of parallelismasynchrony and priority, Certain natural operations, such as association along paths, complicate the problemo Techniques used in the design of asynchronous circuits are useful here, For example, sub-programs can be written so that, when their part of the calculation is ready the corresponding output registers are assigned ready status; sub-programs go to execution status when all operands required are in ready statuso An example of an ioc0c. compiler, along somewhat different lines, appears in [1]0 There is a great class of highly-parallel problems intrinsically beyond the capability of any presently feasible single sequence machine: the unrestricted weather problem, magnetohydrodynamic problems, command and control problems, simulations of biological and ecological systems, and so on, Iterative circuit computers offer the possibility of treating these problems in parallel fashion - thus making them accessible to computationo On balance I would say that the feasibility of an ioCoCo rests upon resolution of the first-mentioned disadvantage: design and production of a module with several hundred active elements at a relatively low cost, The other problems will almost certainly be resolved sufficiently to permit useful computation if this can be accomplished, 9-9

ACKNOWLEDGMENT The work described here was in part supported by the Office of Naval Research under contract Nonr 1224(21). " 10

REFERENCES lo Comfort, Wo To, "Highly Parallel Machines," Workshop on Computer Organization, edo Barnum, Ao Ao, and Knapp, Spartan, 1963o 20 Comfort, We To, "A Modified Holland Machine," Proco 1963 Fall Joint Computer Conference IEEE, 1963o 3o Gonzalez, R,, "A Multi-Layer Iterative Circuit Computer," Transactions on Electronic Computers EC-12, 5, 781-790, 1963. 4. Holland, Jo Ho, "Iterative Circuit Computers," Proco Western Joint Computer Conference, 259-265, IEEE, 19600 5, Holland, Jo Ho, "Universal Spaces: A Basis for Studies of Adaptation," to appear in Automata Theory, ed. Caianiello, E, Ro, Academic Press, 1965, 60 Kleene, So C., "Representation of Events in Nerve Nets and Finite Automata," Automata Studies, 3-41, Princeton, 1956o 7o Newell, Ao, "On Programming a Highly Parallel Machine to be an Intelligent Technician," Proc, Western Joint Computer Conference, 267-282, IEEE, 19600 80 Squire, Jo So, and Palais, So Mo, "Programming and Design Considerations of a Highly Parallel Computer," Proco Spring Joint Computer Conference, IEEE, 1964o 9, von Neumann, Jo, "The Theory of Automata: Construction, Reproduction, Homogeneity, unpubo manuscripto - 11

DISTRIBUTION LIST (One copy unless otherwise noted) Technical Library Naval Electronics Laboratory Director Defense Res. & Eng. San Diego 52, California Room 3C-128, The Pentagon Attn: Technical Library Washington, D.C. 20301 Dr. Daniel Alpert, Director Defense Documentation Center 20 Coordinated Science Laboratory Cameron Station University of Illinois Alexandria, Virginia 22314 Urbana, Illinois Chief of Naval Research 2 Air Force Cambridge Research Labs Department of the Navy Laurence C. Hanscom Field Washington 25, D.C. Bedford, Massachusetts Attn: Code 437, Information Attn: Research Library, CRMXL R Systems Branch U. S. Naval Weapons Laboratory Director, Naval Research Laboratory 6 Dahlgren, Virginia 22448 Technical Information Officer Attn: G. H. Gleissner, Code K4 Washington 25, D.C. Asst. Dir. for Computation Attention: Code 2000 National Bureau of Standards Commanding Officer 10 Data Processing Systems Division Office of Naval Research Room 239, Building 10 Navy 100, Fleet Post Office Box 39 Washington 25, D.C. New York, New York 09599 Attn: A. K. Smilow Commanding Officer George C. Francis ONR Branch Office Computing Laboratory, BRL 207 West 24th Street Aberdeen Proving Ground, Maryland New York 11, New York Office of Naval Research Office of Naval Research Branch Branch Office Chicago Office 230 N. Michigan Avenue 495 Summer Street Chicago, Illinois 60601 Boston, Massachusetts 02110 Commanding Officer Naval Ordnance Laboratory ONR Branch Office White Oaks, Silver Spring 19 1030 E. Green Street Maryland Pasadena, California Attn: Technical Library Commanding Officer David Taylor Model Basin ONR Branch Office WashingtonD.C. 20007 1000 Geary Street Attn: Code 042, Technical Library San Francisco 9, California

DISTRIBUTION LIST (Concluded) The University of Michigan Lincoln Laboratory Department of Philosophy Massachusetts Institute of Technology Attn: Professor A. W. Burks Lexington 73, Massachusetts Attn: Library National Physical Laboratory Teddington, Middlesex, England Office of Naval Research Attn: Dr. A. M. Uttley, Supt. Washington 25, D.C. Autonomies Division Attn: Code 432 Commanding Officer Kenneth Krohn Harry Diamond Laboratories 6001 Dunham Springs Road Washington, D.C. 20438 Nashville, Tennessee Attn: Library Mr. Laurence J. Fogel Commanding Officer and Director General Dynamics/Astronautics U. S. Naval Training Device Center Division of General Dynamics Corp. Port Washington San Diego, California Long Island, New York Attn: Technical Library Department of the Army Office of the Chief of Research and Development Pentagon, Room 3D442 Washington 25, D.C. Attn: Mr. L. H. Geiger National Security Agency Fort George G. Meade, Maryland Attn: Librarian, C-332