Dynamic activity-creating data-driven computer architecture

Abstract

A computer architecture wherein data inputs causes the dynamic creation of appropriate activities employing stored functions as necessary to accomplish the desired end result for the data. The architecture employs a large scale multi-processing environment for parallel computation. A fast forward propagating queue structure and improved interfacing crossbar are employed.

Claims

Wherefore, having thus described my invention, I claim:

1. In a computer architecture of the Petri Net type wherein a plurality of pre-established sub-functions, defining a total function, process portions of the common input data asynchronously to generate a single combined output reflecting the total function as applied to input data, an improvement comprising:

(a) a plurality of data processors;

(b) means for subdividing said total function when said total function is beyond the capability of an individual one of said data processors.

(c) function library means coupled to said data processors for storing each unique sub-function in a storage area as a replicator which can be copied and used by said data processors as needed on a dynamic basis;

(d) data queue means for recirculating data to be processed by said data processors continuously past said data processors until data is removed from said data queue means by one of said data processors, and for supplying said data to selected data processors;

(e) activity queue means for storing a plurality of sets of instructions for operating on selected corresponding data by said data processors, and for recirculating said instructions past said data processors until one of said instructions is taken from said queue by one of said data processors, said activity queue means including means for supplying to all of said data processors, instruction codes, for causing said data processors, (1) to remove particular labeled data from the data queue means, (2) to perform a computational function on said data (3) to introduce output labelled data into said data queue means, (4) to retrieve from the function library stored generalized instruction sequences, and (5) to introduce additional instruction codes into the activity queue means;

(f) means for associating one of said sets of instructions from said activity queue with an idle one of said processors;

(g) means for applying selected data from said data queue to said one processor, said selected data corresponding to said instructions selected from said activity queue; and

(h) said means for subdividing including means for applying subdivided data to the data queue, means for applying sub-function instructions to the activity queue such that further processing by a plurality of idle ones of said data processors can be accomplished and means for recombining the separately processed sub-functions whereby the processing of said total function is accomplished.

2. A computer architecture as defined in claim 1 wherein said queue means includes a plurality stages of latch means for holding the data.

3. A computer architecture as defined in claim 1 including crossbar circuit means for accessing the function library.

4. A computer architecture as defined in claim 1 wherein auxiliary storage nodes are provided, and wherein said function library resides therein.

5. A computer architecture as defined in claim 1 wherein the data in said data queue is labelled data and forms part of the means for applying selected data corresponding to instructions selected by said data processor from said activity queue.

Description

BACKGROUND OF THE INVENTION

The present invention relates to large system computer architecture and, more particularly, to interfacing elements employed between devices in large computer systems for the transfer of data such as queues and crossbars.

Basic digital computing operates in the cycles shown on FIG. 1. In what is referred to as a Von Neuman computer a sequence of instructions are alternately fetched from their location in memory into an execution register and executed. The computational sequences begin by providing the computer with a first instruction address for execution. Thereafter, the address of the next instruction is automatically calculated byy the hardware as a result of the previous execution.

A simple Von Neuman system is shown in FIG. 2. The arithmetic and control unit 10 sequentially fetches and executes a series of instructions located in instructional memory 12. Typically, the instructions from memory 12 cause the arithmetic and control unit 10 to operate on data read in through input lines and/or maintained in data memory 14. The results of the calculations can be output to be seen by an operator on a device such as typewriter 16.

Certain computational projects of large magnitude have traditionally imposed severe time constraints on computational ability. Things such as major conversion problems and military command and control systems requiring repetitive, rapid, and immediate results fall into this category. To solve such problems, the Von Neuman type computer has been made bigger and bigger and faster and faster. Recently, much thought has been given to deviating from this approach and having the data drive the problem rather than the problem drive the data. Much of the impetus for research in this area has been as a result of recent developments in hardware wherein microprocessors and "smart" chips have been made available in smaller and smaller sizes and at lower and lower costs. Such an approach is shown in its simplest form in FIG. 3. In such a system, the driving data elements are referred to as tokens. The tokens cause the "firing" of an activity which generates results depending upon the value of the tokens. Assume that an activity is implemented by a separate chip, and that chip 18 has two inputs 20 and 22 and an output 24. Assume further that chip 18 in the presence of both inputs 20, 22 will produce their sum at the output 24. The activity of chip 18 is simply that of the summing of the inputs.

Such a series of activities can be hard-implemented as "activity chips" or can be treated as logical entities emulated by more general devices, such as microprocessors 26 which are shown interconnected in FIG. 4 in what is referred to as a Petri net. Each of the activities 26 performs a function (indicated as f.sub.1 -f.sub.5 respectively) on the input(s). Such Petri nets are pre-established and do not change during the course of a computation. Each of the activities 26 is independent and, therefore, the sequence of computations is a function of the arrival of the tokens. When tokens A and B are present and available for function f.sub.1, its output is available as a input to functions f.sub.2 and f.sub.4. Token C in the presence of the output of function f.sub.1 will cause function f.sub.2 to be calculated providing the second input for function f.sub.4 which, in turn, provides one of the two inputs required for function f.sub.5. The presence of tokens D and E cause the output of function of f.sub.3 to be made available as the second input for function f.sub.5.

Turning now to FIG. 5, a simplified drawing of a computer system of the Von Neuman type as used in real-time on-line systems is shown. The main memory 30 as accessed by the arithmetic and control unit (not shown) contains resident system programs 32, resident sub-routines 34 (usually re-entrant i.e., more than one program can be using them at a time), and a large section of available memory 36 wherein programs can be loaded for temporary execution. The majority of the programs and data are maintained on a mass storage device 38. When, as a result of an appropriate stimulus such as an interrupt, data arrival, or the like, the resident system program 32 requires the execution of a program on the mass storage device 38, that program is transferred from the mass storage device 38 into an unoccupied portion of available execution memory 36 as symbolized by the dotted area 40. When the program has been transferred into area 40, control is transferred to the first instruction and execution proceeds normally. During the execution procedure, the program within dotted area 40 can employ one or more of the sub-routines 34. When the program has completed its operation, dotted area 40 is merely returned to available status. That is, programs are not transferred back to mass storage 38. In the preferred mode of operation of such systems, the programs on mass storage device 38 are maintained in "dump" format and coded according to "run anywhere" techniques. Thus, a simple block transfer from mass storage 38 into execution memory 36 can be accomplished and the program will run wherever loaded. Moreover, the program can be located and operated simultaneously in more than one available area within memory 36.

A more exotic version of such a system is shown in simplified form in FIG. 6. Such a multi-processor system is typically found in military command and control systems wherein such a large quantity of functions must be accomplished that no single processor (e.g. computer) can accomplish the entire task. In such a system, one or more mass storage devices 38 containing programs and data are interfaced with a communication bus 42. The processors 44 are also interfaced with the communication buss 42. In such manner, the processors 44 can communicate between one another along the buss 42 as well as accessing the mass storage 38. When operating in a task oriented mode, a common task list or queue is maintained and tasks are assigned to the next available processor 44 in response to an initiating stimulus.

Communication crossbar circuits and fast propagating first in, first out (FIFO) queues have been postulated for use in such large systems in order to eliminate potential bottlenecks. That is, when one entity needs to communicate with another, a bottleneck can occur if a communication path between the two cannot be established immediately. In such case, a communication crossbar circuit is proposed. In like manner, when a large number of items are placed on a queue having many stages, a potential bottleneck can occur if the next piece of available data is many stages away from the requester and a considerable period of time and clock pulses must be occupied in order to shift the data to the user.

The proposed devices to date either exist on paper only or, if built, only operate as a stand-alone device. This is because of the inability of the designer of such apparatus to recognize the limitations which must be included within such apparatus when working in the given environment. For example, a common technique is to make such devices operate asynchronously to the system. The patents to Faustini (U.S. Pat. No. 3,757,231), Mallerich, Jr. (U.S. Pat. No. 3,736,575), and Derickson, III, et al (U.S. Pat. No. 3,972,034) are examples of such apparatus. Faustini describes an asynchronous unclocked FIFO which shifts stage by stage. Mallerich describes an improvement over Faustini which operates in the same manner, but with fewer components. The Derickson patent includes the description of a FIFO as part thereof beginning with the description in column 3. That FIFO also is asynchronous.

In a single computer of the Von Neuman type, the problem cannot occur because any word in memory will always be completely accessed. That is, a word in memory will always be written into completely or read completely. In an interrupt-operated system having different priority levels, recognition of the potential problem being discussed herein is recognized by the technique of "re-entrant" coding which must be employed whenever common data can be accessed by multiple programming levels. Still in all, even in that case, reading and writing are on a complete word basis.

By contrast, if a common memory location is being accessed asynchronously, it is possible for one device to be accessing a particular memory location as, for example, by reading from it simultaneously with another device reading into it. Such an occurence can result in completely garbled and unintelligible data. The reason that this is not normally considered or accounted for is that, typically, it only happens on rare occasions. Thus, the designer running a short test case probably does not have the event occur or, if it does, it is not recognized. As a practical matter, however, it is something which does occur and must be accounted for.

Thus, any crossbar or FIFO operating within a computer architecture as to be herein described must be synchronized to the clock driving the system so that appropriate preventive measures can be incorporated to prevent such potentially catastrophic events from occurring.

It is the object of the present invention to provide a data driven computer architecture having the benefits of data driven initiation with the flexibility of more traditional Von Neuman computers.

It is a further object of the present invention to provide such an architecture with interfacing mechanisms which maximize the flow rate of data between elements and minimizes the time delays inherent therein.

SUMMARY

The foregoing objectives have been met in a computer architecture of the Petri Net type wherein pre-established sub-functions, defining a total function, process portions of common input data asynchronously to generate a single combined output reflecting the total function as applied to the input data by the improvement comprising, each unique sub-function existing in a storage area as a replicator which can be copied and used by a processor as needed on a dynamic basis; and, each replicator when copied and used having the ability, when presented with data to be processed by it, of determining if the data is within its present processing power and, if it is, processing it and presenting the results to its output; otherwise, subdividing the data, making copies of itself and spawning a combining logic having the original output destination as its output destination, designating the input of the combining logic as the output designation of the copies, presenting the subdivided data to respective ones of the copies for processing, and terminating itself, whereby a sequence of replicator copies and combining logic will be automatically generated at run-time which has the capability of processing the data input thereto and then be discarded when finished with its processing of that data.

In the preferred embodiment, the copies of the replicators and the spawned combining logic are placed as activities in a queue structure according to a unique embodiment described herein and accessed by a plurality of processors through a unique cross bar structure described herein whereby each activity is processed asynchronously on a processor-available basis.

The activities are disposed in a queue or FIFO comprising a plurality of stages into which data can be placed at input points and from which data can be removed at output points upon the occurrence of respective clock pulses of a clock line to which it is synchronized and by which it is driven, wherein the improvement comprises, status means interconnecting the stages for passing each stage's status to the stage in front of it and behind it between the clock pulses; and, shifting means interconnecting the stages for shifting data between stages towards output points over unused stages between clock pulses at combinatorial logic speeds whereby the availability of data at the output points during the clock pulses is maximized.

The basic crossbar circuit shown for selectively connecting between respective ones of a plurality, M, of inputs and respective ones of a plurality, N, of outputs comprises, M input bar circuit means disposed in spaced, non-intersecting relationship for respectively conducting signals as applied to respective ones of the input bar circuit means; N output bar circuit means disposed in spaced, non-intersecting relationship to one another and in close adjacent spaced relationship to the input bar circuit means for respectively conducting signals as supplied to respective ones of the output bar circuit means, each of the output bar circuit means being oriented to intersect each of the input bar circuit means once; and, a plurality (M.times.N) of control interfaced circuit means connecting the input bar circuit means to the output bar circuit means at each of respective ones of the intersections of the bar circuit means for recognizing its associated input bar circuit means number, m, in a signal applied to the M input bar circuit means and responding thereto, for recognizing its associated output bar circuit means member, n, in a responded-to signal, for establishing a connection along input bar circuit means, m, and output bar circuit means, n, through the intersection thereof and flagging the bar circuit means, m and n, as "in use" if not previously in use, sending an "in use" signal back along input bar circuit means m if "in use", and flagging the bar circuit means m and n as "not in use" when use of the established connection is completed.

DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of a prior art computing cycle of the Von Neuman type wherein the operating instructions are alternately fetched and executed.

FIG. 2 is a block diagram of a prior art computer system of the Von Neuman type.

FIG. 3 is a simplified block diagram showing a basic prior art approach to data driven computing.

FIG. 4 is a block diagram of a prior art activity driven structure referred to as a Petri Net.

FIG. 5 is a simplified drawing of a prior art computer system of the Von Neuman type as used in real-time on-line systems.

FIG. 6 is a block diagram of a prior art multi-processing system.

FIG. 7 is a simplified block diagram demonstrating the basic premise of the present invention wherein data is presented to a copy of a replicator defining a basic function which has the capability of spawning additional activities and copies of itself as necessary to accomplish the computational task necessary on the data presented.

FIG. 8 is a simplified block diagram showing the computer architecture of the present invention in its basic form.

FIG. 9 is a simplified diagram of the computer architecture of the present invention in an improved form.

FIG. 10 is a diagram of the computer architecture according to the present invention in yet a further refined form for improved operation.

FIG. 11 is a diagram of the computer architecture of the present invention in its most refined and preferred form.

FIG. 12 is a basic block diagram showing the necessity for an interface between senders and receivers of messages and signals.

FIG. 13 is a simplified drawing of the internal workings of the interface network shown as a block in FIG. 12.

FIG. 14 is a simplified drawing showing how the horizontal rows of the interface network of FIG. 13 could be produced on individual horizontal bar circuits.

FIG. 15 is a simplified drawing showing how the vertical rows of the interface network of FIG. 13 could be produced as individual vertical bar circuits.

FIG. 16 is a simplified drawing showing how the horizontal and vertical bar circuits of FIGS. 14 and 15 could be combined to create the interface structure of FIG. 13.

FIG. 17 is an enlarged block diagram of one intersection of the structure of FIG. 16 showing how logic would be incorporated therein to allow the horizontal and vertical bar components to communicate with one another.

FIG. 18 is a simplified drawing showing how the basic crossbar structure as shown in FIG. 16 can be stacked with additional input and output interfaces to create an improved crossbar structure having the same number of inputs and outputs but with an improved probability of creating a successful path therethrough.

FIG. 19 is a simplified drawing showing how a number of basic crossbar circuits according to the present invention as shown in FIG. 16 can be interconnected to create a crossbar circuit with an increased number of input and output lines.

FIG. 20 is a simplified block diagram of several stages in a queue or FIFO according to the present invention.

FIG. 21 is a detailed block diagram of one stage from FIG. 20.

FIG. 22 is a table showing the four states possible in the stage of FIG. 21 according to the present invention and what action should be taken.

FIGS. 23-101 comprise detailed drawings of the implementation of the crossbar and queue FIFO circuits employed in the present invention and, in particular:

FIG. 23 shows circuit M-1 which is the P-bit rotating one-bit circuit.

FIG. 24 shows circuit M-2 which is the break-in switch circuit.

FIG. 25 shows circuit M-3 which is the arbitration signal generator circuit.

FIG. 27 shows circuit M-4 which is the innermost crossbar multiplexer circuit.

FIG. 28 shows circuit M-5 which is the innermost path latch circuit.

FIG. 29 shows circuit M-6 which is the want decoder circuit.

FIG. 30 shows circuit M-7 which is the P-Y compete four row circuit.

FIG. 31 shows circuit M-8 which is the P-compete 2.sup.r s path-latching broadcast crossbar circuit.

FIG. 32 is a block diagram showing the memory system crossbar facility.

FIG. 33 shows circuit M-9 which is a free-memory queue master bit internal signal circuit.

FIG. 34 shows circuit M-10 which is also a free-memory queue master bit internal signal circuit.

FIG. 35 shows circuit M-11 which is the free-memory queue master bit circuit.

FIG. 36 shows circuit M-12 which is the free-memory queue slate bit circuit.

FIG. 52 shows circuit M-25 which is incorporated into, for example, the interface to M-8/M-22: sender.

FIG. 53 shows circuit M-26 which is incorporated into, for example, the interface to M-8/M-22: receiver.

FIG. 54 shows circuit M-27 which is the memory code circuit.

FIG. 55 shows circuit M-28 which is the memory code for input-output circuit.

FIG. 56 shows a shorthand notation for the M-8 circuit.

FIG. 57 shows the bit fields of the address.

FIG. 58 is a block diagram showing the synthesis of larger crossbars.

FIG. 59 is a shorthand nnotation for an expanded M-8 circuit.

FIG. 60 is a shorthand notation showing one possible configuration of address bit-field "C".

FIG. 61 shows the special case of an M-8 circuit which results when there are alpha address bits on the inputs and 2.sup.alpha outputs.

FIG. 62 is an informal designation for the circuit of FIG. 61.

FIG. 63 is a block diagram of the inner connection between the M-13 circuits output routing to the memory nodes.

FIG. 64 shows circuit Q-1 which is a parallel preparator circuit.

FIG. 65 shows circuit Q-2 which is a claimant circuit.

FIG. 66 shows circuit Q-3 which is an input port claimant circuit.

FIG. 67 shows circuit Q-4 which is a priority select circuit.

FIG. 68 shows circuit Q-5 which is a row-wise comparison network circuit.

FIG. 69 shows circuit Q-6 which is a token position proper circuit.

FIG. 70 shows circuit Q-7 which is an RD field multiplexer circuit.

FIG. 71 shows circuit Q-8 which is a processor input port latches circuit.

FIG. 72 shows circuit Q-9 which is a row absorption network circuit.

FIG. 73 shows circuit Q-10 which is a processor output port circuit.

FIG. 74 shows circuit Q-11 which is an output port K-group multiplexer circuit.

FIG. 75 shows circuit Q-12 which is an output port K-group circuit.

FIG. 76 shows circuit Q-13 which is an output-gating multiplexer circuit.

FIG. 77 shows circuit Q-14 which is a K-group merged onto token queue.

FIG. 78 shows circuit Q-15 which is a token queue row complete circuit.

FIG. 79 shows circuit Q-16 which is a self-switching wait stage master bit circuit.

FIG. 80 shows circuit Q-17 which is a self-switching wait stage slave bit circuit.

FIG. 81 shows circuit Q-18 which is a token-wide wait stage circuit.

FIG. 82 shows circuit Q-19 which is a wait stage block circuit.

FIG. 83 shows circuit Q-20 which is a crossing switch circuit.

FIG. 84 shows circuit Q-21 which is a token-wide crossing switch circuit.

FIG. 85 shows the circuit of FIG. 84 in symbolic form.

FIG. 86 shows circuit Q-22 which is an accordian store balancing stage circuit.

FIG. 87 shows circuit Q-23 which is an accordian store circuit.

FIG. 88 shows circuit Q-24 which is a token queue proper circuit.

FIG. 89 shows circuit Q-25 which is a token queue complete circuit.

FIGS. 90-95 are improvement circuits on circuits 79-82 to remove inherent delays.

FIG. 96 is a block diagram showing the improved FIFO of FIG. 9 hooked up to form a longer FIFO.

FIGS. 97-99 are symbolic representations of the circuits of 92-94.

FIG. 100 is the symbolic representation of the circuit of FIG. 96.

FIG. 101 is a table provided to show how a basic stage responds to the three independent variable TSF, FWS, and CONT.

DESCRIPTION OF THE PREFERRED EMBODIMENT

Referring first to FIG. 7, the basic premise of the computer architecture of the present invention is shown in simplified form. Only the initial portion of the computation's Petri net is initially present in the mashine as indicated by activity group ROOT within box 52. The Petri net for the entire computation is a function of the data entering this initial portion, and, therefore, cannot be pre-established as in the traditional data driven computer.

Assume now that initial ROOT of 52 is the initial step in generating a Petri net execution graph which will sum all elements of an incoming vector (of any length) into a single scalar. FIG. 7 shows the introduction of a four-element vector 50 borne on a token 46 to initial ROOT 52. ROOT 52 responds dynamically to this vector, in simple terms, in this way: the ROOT activity group sees that vector 50 is "too large" and, therefore, spawns a second group of activities called the THEN group, also within box 52. The ROOT group of box 52 then vanishes. That is, the activities of the ROOT group have "fired" once and thereafter immediately vanish. The initial THEN group of 52 itself sets up more of the Petri net as follows: it generates an addition ("+") activity 58; it absorbs the original vector 50 and breaks it into two halves 54 and 56; and it spawns two new ROOT activity groups in boxes 55 and 57, and guides the split vector 54 to the new ROOT group of 55, and split vector 56 to the new ROOT group of 57. Having done its work, the initial THEN activity group of box 52 vanishes.

Except for its position in the overall Petri net (which is dynamically generated piecemeal), the ROOT group of 55 is behaviorally identical to the original ROOT group of 52. The two groups are, in fact, isomorphic, built according to a single master blueprint. The blueprint designated a "REPLICATOR" (and not shown in FIG. 7) is the fundamental for of stored program in the present invention. A replicator is a blueprint for an activity group. When the THEN group of 52 "spawned" the two ROOT groups of 55 and 57, the static replicator defining a ROOT group was called on as the pattern for construction.

Continuing with the example, the left ROOT of 55 operates on its input vector 54 independently of the right ROOT 57 operating on its vector 56. This is the parallelism consequential of any Petri net scheme. One can also see that the original ROOT of 52 led to the generation of the two new ROOTs 55 and 57, so that the overall computation was recursively defined. Single activities fire once, only once, and them immediately vanish. This forces the synamically generated activity groups to be acyclic and, viewed as a unit, also vanishing once they have been used. This, in turn, means the overall dynamically-generated Petri net will be acyclic; that is, without "loops" in which any activity is traversed twice (since activities vanish on their first traversal). These characteristics are fundamental to the present invention.

The ROOT group of 55 examines its incoming vector 54 and determines that the vector is "small enough". That ROOT group then spawns an ELSE group of box 55 which creates a waiting addition activity 64, absorbs incoming vector 54 and breaks it into isolated scalars "a" and "b" shown as inputs to activity 64, guiding those scalars to the prepared activity. The ROOT group of 55 vanishes after spawning the ELSE group of 55 and the ELSE group vanishes above the above steps. It should be seen that the right-hand ROOT group of box 57 undergoes similar behavior (behavior which is isomorphic to the left-hand group) but due to its context (that is, its global placement in the overall Perti net), it is not identical. The right-hand group absorbs its own vector as determined by its context, has its own local behavior as affected by that incoming vector and produces its own result destined ultimately for the right-hand input of the waiting addition activity 58. The linkage mechanisms cause the overall computation to be deterministic. That is, there is no ambiguity as to which activity will absorb which token, nor where a result will go once produced.

The computation proceeds to the point where only the four isolates scalars "a", "b", "c", and "d" (each on its own token), along with the three addition activities 64, 66, and 58, are the only entities remaining in the system. The linkages completely determine their interaction, as indicated by the arrows. Activity 64 absorbs the "a" and "b", produces the sum "a+b" and vanishes. Activity 66 produces "c+d" and the single activity 58. The ultimate posture should be clear: a single token "a+b+c+d" and no activities.

It is a fundamental feature of the present invention that the creation of new activities can be initiated (if not totally carried out) by existing activities in the system. The new activities are built having a very specific relationship to one another and to the context thay are introduced into. These new activities and their interrelationships constitute a "sub-graph" (referred to as a "group" in the above text). A sub-graph is itself a Petri net. Existing activities, under stimulus of the data they are currently processing, may choose to initiate construction of an activity group (a Petri net sub-graph of new activities which are properly interrelated) according to a pre-established pattern. The pattern, called the replicator, is accessed and used by the existing activity to establish the new activities. The existing activity also provides the information needed to interface ("concatenate") the new sub-graph properly to the existing overall Petri net. This latter information needed to link the new sub-graph to its context is provided by the "parent" activity (the activity initiating the creation) and not by the replicator. The replicator only indicates how that information must be applied. It is here that one should begin to see the detailed interaction of data (leading to decisions as to whether or not an activity group is to be created and, if so, according to which replicator's pattern), context (providing the linkage data needed to interface the new sub-graph properly to the existing Petri net), and replicators (which are the analog of a Von Neumann "program"; that is, the static descriptiors which are stored to effect the computation intended by the programmer or the "code" as distinct from the execution of the code).

Note that in the simplified example of FIG. 7, the activities are dynamic and the basic elements (i.e., the functions) are allocated on an as-needed basis. Once utilized, the functions are merely discarded. It is envisioned that the functions would be operated and executed in a manner similar to that discussed with respect to FIGS. 5 and 6 above and, therefore, no greater detail is to be set forth herein in this regard.

Turning now to FIG. 8, certain aspects of the computer architecture of the present invention can be seen. As envisioned, the computational facilities, as indicated by the dotted box 68, comprise a multitude of individual computer processors 70. It is not inconceivable with modern technology that in a large computational system according to the present invention there could be thousands of computer processors 70 comprising facilities 68. The system is stimulated by tokens 72. These are placed onto a token queue, generally indicated as 76, by action of executing activities in the computing facilities 68 ("input" and "output" activities guide data between external devices and the token queue 76). The token queue 76 can be accessed by all the processors 70. Activities 78 are generated by executing activities involved in the "spawning" process discussed earlier, according to patterns stored in replicator storage; activity generation, with the replicator store, is generally indicated at this time as box 80. As activities 78 are generated, they are placed on an activity queue, generally indicated as 82, which is also accessible by all the processors 70. As facilities 68 become available, the activities 78 are removed from the activity queue 82 and assigned to appropriate facilities 68, as symbolized by the arrow 84. The activity needs data (generally speaking) in order to fire and, therefore, it expects to find that data on tokens 72 in the token queue 76. The scheme used to establish token flow through the dynamically-generated Petri net takes the form of "labels" on both tokens and activities which are supported by the architecture. As a match between a token 72 label and a label on an activity 78 within facilities 68 is recognized, the token 72 is provided to the activity 78, as symbolized by the arrow 86. That token 72 is removed from the token queue 76 and effectively attached to the activity 78 to effect the process called "absorption" in earlier text. Subsequent generation of a result token 72 will cause it to be placed on the token queue 76, as symbolized by the arrow 88.

It is contemplated that in a highly active system a virtual swarm of tokens and activities will be occupying the respective queues 76, 82. Making the tokens 72 and activities 78 available to the facilities 68 and to one another in the most expedient manner is, therefore, a major concern of the computer architecture of the present invention.

As shown in FIGS. 9-11, several constructions according to the architecture concept of the present invention will be described.

In implementing the novel computer architecture of the present invention, there are two major areas of concern requiring consideration and apparatus for implementation beyond the scope of anything available presently in the art in order to make the architecture an achievable reality operating in a manner which totally realizes the desired objective. Those considerations are, of course, a practical interface system between the various physical components and a practical and time-efficient queueing structure for holding the waiting activities, tokens, and replicator descriptors (within the function library) in a manner which allows them to be readily and easily accessible to the facilities requiring them. Both these requirements have been addressed by the applicant herein and solutions are described hereinafter. Both the novel cross-bar circuitry and the accordian-store queue structure will be described functionally, and, thereafter, described with particularity with reference to a specific design.

Turning first to FIG. 12, the problem is shown in its simplest form. At any particular time, the elements of the system fall into a plurality of senders, generally indicated as 200, who wish to communicate with a plurality of receivers, generally indicated as 202. What is desired is an interface network 204 to which the senders 200 and receivers 202 can be connected such that any sender 200 can call for and obtain a direct path to any receiver 202 connected to the interface network.

Turning now to FIG. 13, the internal workings of the interface network 204 are broken down to a functional level. The interface network 204 is contained within the dotted box so indicated. A series of input lines 206 (labelled "I.sub.1 " to "I.sub.6 ") enter interface network 204 and a plurality of output lines 208 (labelled "O.sub.1 " through "O.sub.5 ") leave interface network 24. As can be seen, the input lines 206 connect to internal columns labelled "1" through "6", respectively. Likewise, the output lines 208 connect to internal rows labelled "1" through "5", respectively. Assume that each intersection of a row and column has a control logic 210 associated therewith. The problem to be solved, therefore, can be seen to be one of establishing the control logic 210 in a workable manner to accomplish the desired objectives. Assume, for example, that it is desired to effect an inter-connection between input I.sub.1 206 and output O.sub.3 208. The control logic 210 at the junction of column 1, row 1, must recognize that the desired address resides on row 3. Control, therefore, must be passed through the control logic 210 at row 1, column 1, to the control logic 220 at row 2, column 1. That control logic 210 must, of course, make the same type of evaluation. Upon the request signal arriving at control logic 210 for row 3, column 1, the address identity must be recognized. The function of control logic 210 for row 3, column 1, then becomes one of requesting forward for control of the row 3 output line 108 (i.e., output O.sub.3). Each control logic block 210 along row 3 must be asked whether it has taken control of the row 3 output line 208. If any one of them has, this must be signaled back across row 3 to the control logic block 210 at row 3, column 1 which is initating the horizontal request. This lack of availability, then, is sent vertically along the control logic blocks 210 of column 1 to the requester. In the event that no control logic block 210 along row 3 has control of the row 3 output line 208, control logic block 210 must then be so informed and, itself, cause the row 3 output line 208 to be in a "occupied" state and a successful path message sent vertically along the control logic block 210 of column 1 to the initiater on line I.sub.1 206.

As can be seen, such logic capability as must, thefefore, be incorporated in each control logic block 210 is fairly complex. That is only part of the problem. Cross-bar circuits effecting the above-described interconnecting logic are not completely unknown in the art as previously mentioned. On the other hand, known cross-bar circuits are hard wired and unflexible so as to not be easily adaptable to a large system as wherein the cross-bar circuit of the present invention must operate.

Turning now to FIG. 14, one can envision how the five rows of interface network 204 could be produced on five individual horizontal bar circuits 212 having control logic chips 214 thereon. Likewise, with reference to FIG. 15, one can invision how the interface network 204 could be divided into six vertical bar circuits 216 having control logic chips 218 thereon.

If, then, the horizontal bar circuits 212 of FIG. 14 were interposed over the vertical bar circuits 216 of FIG. 15, a composite circuit 204' would be created if each control logic 214 and 218 contained complementary portions of the totally required control logic of control logic 210 and was connected to intercommunicate one with another. Such construction would make a highly flexible cross-bar circuit in that each horizontal bar circuit 212 would be identical to every other horizontal bar circuit 212 and likewise for the vertical bar circuits 216. If each horizontal bar circuit 212 contained X positions of control logic 214 and each vertical bar circuit 216 had Y positions of control logic 218, any combination up to X by Y could be created by merely adding more or less bar circuits 212, 216. Such is the intent and achieved objective of the cross bar circuit of the present invention.

The interconnection forming control logic 210' at the intersection between each vertical bar circuit 216 and horizontal bar circuit 212 is shown diagramatically in detail in FIG. 17. Each horizontal bar circuit 212 contains a horizontal electrical bus 220. Correspondingly, each vertical bar circuit 216 contains a vertical electrical bus 222. At the intersection between each horizontal bar circuit 212 and vertical bar circuit 216 a bus interface 224 provides access to both buses 220, 222. Also provided are vertical logic 226 and horizontal logic 228. Vertical logic 226 and horizontal logic 228 can intercommunicate with one another and with the bus interface 224. Additionally, vertical logic 226 can sense signals travelling along vertical electrical bus 222 and inject signals into vertical bus 222. Likewise, horizontal logic 228 can both read signals from and inject signals into horizontal electrical bus 220. The signals read and injected by vertical and horizontal logic 226, 228 is, of course, described above with reference to FIG. 13.

To provide the flexibility and the expandability necessary for a cross-bar operating in the architecture of the present invention, two additional features not possible by cross-bars of the prior art and accomplished by the cross-bar of the present invention are required. The first is shown diagramatically in FIG. 18. To this point, the cross-bar circuit as described is one of flexibility in a single plane. As defined, the interfaced network 204 and 204' comprise six columns and five rows. While the numbers used for pusposes of description are small, one can envision how with a large number (X) of columns and large number (Y) of rows interconnected along a single plane the achieving of a path between a single input I.sub.i and a single output O.sub.o might run into problems of achievability within time constraints. This is, as the rows and columns became busy, the testing and retesting procedure along the columns consuming. In such case, more paths between the same number (X,Y) of inputs and outputs could help alleviate the problem. FIG. 18 diagramatically shows such a solution. That is, the cross-bar interfaced network 204" within the dashed box still has input lines I.sub.1 through I.sub.6 and output lines O.sub.1 through O.sub.5 so as to appear to the outside world identical to the cross-bar 204 and 204' previously described. Internally, however, one can see that a plurality of identical cross-bar boards 204' have been placed in parallel and interconnected along their inputs by input interconnecting logic 230 and along their outputs by output interconnecting logic 232.

The other case of expandability is one of requiring more input and output lines 206, 208. This problem and its solution according to the present invention is shown in simplified form in FIG. 19. Due to size limitations in the drawings, the cross-bar elements 204' are shown with three inputs and two outputs. By interconnecting in the manner shown, an enlarged planar structure 204"' having nine inputs and four outputs is constructed. As should be understood, since, for example, the cubic crossbar 204" of FIG. 18 appears to the outside world as if it were any planar cross-bar 204, such a structure could be incorporated within the enlarged planar cross-bar 204"' of FIG. 19 to create a composite cross-bar with both increased numbers of inputs and outputs along with greater through paths for achieving rapid interconnections between the inputs and outputs when requested.

A specific example of such cross-bar circuits as could be implemented according to the present invention is described hereinafter.

Before turning to specifics, however, the problem of queue storage according to the novel techniques of the present invention will be shown and discussed in simplified form.

Turning now to FIG. 20, a segment from a queue or FIFO is shown. Those skilled in the art will recognize that the principles being described are identical and merely depend on whether the final output is wrapped around to the input or not. That is, a queue as employed in the present invention and as described in detail hereinafter is circular in nature, to circulate its data past various points of inquiry until such time as they are individually removed. By contrast, a FIFO propogates its data from the input towards the output such that that which is first in is first out. A FIFO has one sampling point (the output) while the queue structure described and used in the architecture of the present invention has many sampling points.

In the conventional queue or FIFO, a plurality of stages 234 are connected to a clock line 236. Upon each clock pulse on clock line 236, data, as represented by the large arrows 238, moves from one stage 234 to the next, if the next stage 234 is (or will be) empty, or does not shift forward if the next stage 234 is (and will remain) full. In a slowly operating system with one or two accessing entities, this does not pose a problem. By contrast, in a system such as the architecture of the present invention, data must be made rapidly available to any and all users. Because of the vast numbers of tokens and activities which will be swarming in the queues, a movement of data from stage to stage at single clock pulse intervals is intolerable. What is required is the heretofor non-existent concept of interconnected stages which rapidly skip or slid forward over unused positions at combinatorial logic speeds between clock pulses so to always have data available for sampling at each sampling station rather than empty positions offering only wasted time. In this regard, the queue of FIFO structure of the present invention is like the bellows of an accordian (and, therefore, is oftimes referred to thusly) in that empty stages will virtually fold to place actual data stages in virtual proximity to one another on a time scale basis. That is, because the data will skip over unused positions between clock pulses, to the user, the data will appear to have shifted in from the previous stage in one clock pulse time where, in fact, it may have shifted in from a stage many positions removed.

With additional reference now to FIG. 21 with particularity, the mode of operation according to the present invention and an enlarged block diagram view of a single stage 234 thereof is shown. Each stage 234 of the queue or FIFO of the present invention contains a plurality of data lines 240, each carrying a unit of circulating data. In conventional structures, the data lines 40 pass into and out of latches 242. Each stage 234 according to the present invention also contains latches 242 on the data lines 240. Additionally, however, the latches 242 are contained within by-pass logic 244. Each latch 242 has a by-pass line 246 around the latch 242 controlled by by-pass logic 244. As symbolized by the arrows 248 and 250, the stages 234 communicate backward and forward, respectively. The stages 234 are interconnected by signal paths represented by the lines 252 and 254 in FIG. 21. Each stage 234 contains forward logic 256 and backward logic 258 capable of impressing signals on the line 252, 254 and reading signals therefrom in order to control the action of the stage 234. The bypass logic 244 and the two logics 256, 258 are combinatorial logic circuits whereby numerous signals can be sent and received and appropriate actions taken at the stages 234 between clock pulses on line 236 so as to effect the objectives of the present invention.

Each stage 234 can be in one of four states and will take appropriate action depending upon its state. These four states, the significance thereof, and the actions to be taken are descirbed in the Table of FIG. 22. In state number 1, there is valid data present in the latches 242. If backwards logic 258 senses that the next stage in sequence will accept data, it means that data in the latches 242 of this stage can be shifted forward to the next stage and, therefore, the backwards logic 258 of this stage can signal the stage preceding it that it will accept data. As a result, the data in the latches 242 is shifted out, the clock coming in on line 236 is enabled, and the incoming data is sent to the latches 242 of this stage.

In state number 2, valid data is once again contained in the latches 242 of this stage. By contrast, the next stage is signalling that it will not accept data under those conditions. This stage 234 can do nothing except maintain the data presently in its circuits. The clock on line 236 is inhibited for this stage, any incoming data is not accepted, and nothing is shifted out.

In state number 3, this stage 234 has no valid data. The next stage, however, is signalling that it will accept data. Under such conditions, there is no need for the latches 242 of this stage to become involved. Consequently, the by-pass logic 244 connects the by-pass line 246 between the input and output on each line such that the incoming data is propagated directly to the output, thus bypassing the latches. This, of course, is the novel fast propagation forward feature of the present invention.

In state number 4, this stage 234 contains no data and the next stage is signalling that it will not accept data. This stage, therefore, can accommodate any available data and so signals. Nothing is shifted out but the clock is enabled and any incoming data is sent to the latches 242 of this stage.

Thus, not only has the computer architecture according to the present invention been described, but additionally, the functional design for novel and necessary cross-bar and queue structures as would be employed in such a computer architecture have been described. The construction of the cross-bar circuit and the queue circuits will now be described with reference to particular embodiments thereof so as to completely describe them sufficiently for those skilled in the art to build them as necessary. It is to be understood that the following design is only one possible approach to turning the principles of the present invention into a real machine. It is probably the most literal interpretation in the sense that one can identify a swarm of tokens and a swarm of activities, and can also see that the physical location of both is not only insignificant but, in fact, is continuously changing. Tokens are absorbed by activities when the two "happen" to meet. There is no concerted effort to bring tokens directly to the corresponding waiting activities (or vice versa). Instead, activities scan the swarm of tokens looking for those tokens which apply to them. When the activities find those, they remove those tokens from the swarm. The circuits insure that, eventually, activities will find their tokens. The probability of an activity never finding its tokens is virtually zero.

Other additional architecture could be provided to take more deliberate means to bring tokens together with their activities. Recall in this concept, it is possible for either the tokens or the corresponding activity to appear first in time. Associative circuits, then, must manage either contingency. Those skilled in the art should recognize an associative approach in the following design, although the associative function is not concentrated into a well-defined "associative functional block", "associative memory", "associative switching network", or whatever. Instead, the associative function is distributed throughout the entire machine.

The basic logical machine of FIG. 9 consists of four elements. These are (a) the token queue 76, (b) the activity queue 82, (c) the processors 70, and (d) the function store 90.

The token queue 76 is the novel shift register (FIFO) which moves the tokens 72 past the processors 70. The tokens 72 are in constant motion. Gating is provided to permit the processors 70 to "absorb" tokens 72 from the token queue 76 as they pass by. Tokens 72 that are not absorbed while passing over the processors 70 simply return over the closed-loop path and pass over the processors 70 again. In a properly designed machine where deadlocks are avoided, each token 72 will eventually be absorbed by the activity 78 that is expecting it. Note, this also assumes the machine is properly programmed as well.

The activity queue 82 is of the same novel construction and carries descriptors of activities 78. As is clear from the conceptual description above, the activity descriptors are a set of rules which must be "executed" to achieve execution ("firing") of an activity 78. One can think of an activity descriptor as a "program" which is to be executed by a processor 70. Therefore, the activity descriptors are brought into processors 70, which are capable of decoding the implied instructions in the descriptors and carrying them out. As activities 78 give birth to new activities 78, these new activities 78 are ejected onto the activity queue 82 where they follow the closed path, find their way into a processor 78, and ultimately fire. When an activity 78 has fired, its descriptor is simply erased, meaning that the processor 70, which was executing it will eventually simply declare itself free, i.e. the activity 78 which was executing in it has died. This free processor 70 is now available to accept a new activity descriptor from the activity queue 82 and being its "execution". Remember of course, that the activity 78 may not be able to proceed until it has absorbed necessary tokens 72 from the token queue 76.

The function store 90 is a memory which can be read-accessed by all of the processors 70. At some initialization time, the user's replicators ("function library") are moved into the function store 90. Once this is done, together with causing some initial activity to appear on the activity queue 82, the machine can "bootstrap" itself and begin executing the program. Note, this program could actually be an "operating system" and not merely a user program.

The processors 70 themselves, then, are independent computers which interface to the overall system as shown. It should be recognized that a conventional computer, whether it be microprocessor or an enormous mainframe containing dozens of central processors, can be considered a single "processor" 70 in this machine. Exactly what the processor 70 looks like is not directly relevant to the present invention, which is more concerned with the interconnection of functionally-specified processors and the overall scheme used to co-ordinate them to work on a single specific user program. The processors 70 must be capable only of carrying out activities 78. Exactly how they do this is actually a "soft" specification, as almost any conventional computer can be programmed to perform that function, qualifying it for a position in this invention. More likely, however, a new design will emerge for these processors 70 for each new implementation of the present invention, disguising this "soft" specification as a "hardware" one. This is rhetorical, as the equivalence of one conventional computer to another is well understood in the art. The present invention encompasses any device which is capable of causing the effective functional " firing" of activities 78. It is sufficient here to note that a conventional computer can do this job.

Those skilled in the art will appreciate that such a logical structure assumes that there is sufficient capacity in each position of the token queue 76 to accomodate an entire token, both the label and the data (which could be very large structures such as matrices and higher-order arrays). This is not yet completely practical, so some "extension" of the token queue 76 will most likely be needed for implementation in the near future. It should be noted, though, that the machine will perform most effectively when any "extension" can be bypassed. That is, when, in fact, an entire logical token 72, can fit into a position in the token queue 76. Depending on the implementation, this is not an always/never proposition. Some tokens 72 will fit, and some tokens 72 won't. Individual tokens 72, then, may be provided with the ability to call on the "extension". Those that don't need it then, would not have to deal with it.

A similar argument applies to the activity descriptors. Of particular concern is the specification of "constants" in activity descriptors. Constants can be very large structures as well.

Finally, the replicator store 90, in a real machine, will have to deal with contention problems of one form or another from the continuous reproductive activity of the activities 78 in the processors 70.

Deadlocks can appear at several points. The two most obvious are running out of capacity in the token queue 76, and running out of capacity in the activity queue 82. For example, an activity 78 (in a processor 70) wanting to give birth to a new activity 78 may find that the "activity queue out" cannot accept the new "son", so the activity 78 will have to wait until the room appears. Until then, it occupies a processor 70. If enough processors 70 are tied up this way, the full activity queue 82 will have no processor 70 to shift into, insuring that the activity queue 82 will have no capacity and producing deadlock. The same thing can happen in the token queue 76.

Assuming that the queues 76, 82 can be built with enough capacity to accomodate new tokens 72 and activity descriptors, deadlocks can still occur. Processors may be filled with a subset of the activities which are waiting on tokens 72, and those tokens 72 will be produced only if some of the activities 78 which are not in the processors 70 are allowed to execute. Those occupying the processors 70 stay there waiting for tokens 72 which, simply because they are sitting there waiting, can never be generated by the activities 79 which are not yet in the processors 70. This can be monitored, with some difficulty, by noting when all the processors 70 have become full. Each processor 70 can be programmed to give a logic signal indication of a "wait for token" condition. If the logical AND of all of these signals from all the processors 70 ever emerges as TRUE, then all the processors 70 are waiting. At that moment, the token queue 76 can be monitored. When it is clear that the token queue 76 has rotated around enough times without a token absorption having taken place (again, the processors can provide the signals necessary to determine this) then a deadlock has occurred. Then the processors 70 have to be freed.

Toward eliminating some of the problems mentioned above, the improved machine of FIG. 10 consists of (a) a token queue 76 with a buffer 92, (b) an activity queue 82 with a buffer 94 and addressing circuits 96, (c) processors 70 as before, and (d) a memory subsystem, generally indicated as 98, which not only provides the function needed to implement the replicator store, but also the effective extensions of the token and activity descriptors.

The token queue 86 is improved by placing in it an expandable buffer 92, the above-described FIFO element which functionally swells and shrinks. The activity queue 82 also contains one of these accordion buffers 94.

The memory subsystem 98 consists of (a) many memory nodes 100 which will be defined below, (b) crossbar communications circuits 102 (to be discussed in detail hereinafter) which permit any processor 70 to communicate to any memory node 100, vice-versa, and permit any memory node to communicate with any other memory node, and (c) (not shown in the figure), a free-memory rotating queue which is connected to all memory nodes 100 and all processors 70, into which a memory node 190 places its own address when it considers itself "free" and from which either a processor 70 or a memory node 100 may remove such names in order to claim free memory for its own use.

Memory nodes 100 are processors themselves and, therefore, any conventional computer can serve this purpose. Unlike the activity processors 70, however, memory nodes 100 perform different functions. The only real difference between memory nodes 100 and activity processors 70 is that functional one. Activity processors 70 are expected to execute activities 78, while memory nodes 100 are expected to manage auxiliary memory functions required by actions initiated by the activity processors 70. Implementors will probably find that activity processors 70 and memory node computers 100 will be different from each other, but that (with a few exceptions) all activity processors 70 are alike, and all memory nodes 100 are alike. In this way, the benefits of mass-production can be gained in producing the thousands of processors of each type which are envisioned as being integrated as components of the present invention.

All processors 70 each have a unique "processor address" and all memory nodes 100 each have a unique "memory node address". These addresses are required in order for the processors 70 and memory node computers 100 to direct messages to each other.

The function library 90 can now be contained in one or more distinguishable memory nodes 100. Although each memory node 100 is able to write as well as read into its internal memory, the function library 90 is never to be altered once it is placed into the machine during execution of its functions. However, the writability of that memory permits the initial function library load.

Memory nodes 100 can be viewed as being intelligent storage areas, each providing some minimum amount of memory capacity which is available for allocation and use by the other processors 70 in the system. If one thinks in terms of the machine's logical quanta ("words," which are logical data units, not physical, so that they need not be fixed-length physically) there is an apparent capacity of NODE LENGTH words. Memory nodes 100 will require enough physical memory to provide this minimum capacity as seen by outside units, and additional storage as well, in order to contain the control program and scratch storage for internal operations.

Input-output is also achieved through the memory subsystem 98 by attaching peripheral devices to memory nodes 100 and modifying the control programs of those nodes. Activities 78 can be informed, via the supplied program, of the address of these memory nodes 100, so that the addresses of those nodes become I/O addresses. Input and output generic activities (which in this machine require one and two input tokens to "fire" respectively) are supplied this "format" information (containing the I/O address) on one of its input tokens. The second input token of the OUTPUT generic activity is the data to be output, which is passed to the memory node which manages all formating as per predefined rules OUTPUT then, produces an "acknowledge" output token. INPUT does not permit the input data token to enter the system until it absorbs a "format" token which describes where the input is to come from. At that point, the activity 78 gathers a token from that memory (I/O node) whose address was specified in the format token, and outputs the data token into the token queue 76.

Some additional benefits can be gained for the configuration of FIG. 11. The problem of contention for the function library 90 can be taken care of by brute-force. As it is a read-only structure, it can be copied by all of the processors 70 out of the memory subsystem 98 and into their own internal storage, so that processors 70 about to require information from the function library 90 do not have to invoke the memory subsystem 98 to obtain it. The processors 70 can be instructed to make this copy during a reset sequence initiated after the function library 90 has been moved into the memory subsystem 98. Logically, as all copies are identical, it is still the same function store (i.e. a "virtual" function store).

Any processor 70 has to be prepared to execute any activity descriptor with any possible combination of variables. Therefore, every processor 70 will have pretty much the same internal control program which contains the detailed rules and definitions for each generic activity 78 defined in the system, as well as the rules for how to declare itself "idle", what to do when it is idle, what to do if system deadlock is declared, and so forth. This control program can be burned-in to ROM, for example, making the soft definitions much less easily altered. Alternatively, the same previous described technique can be used, during an initialization sequence, of loading the control program into the memory subsystem 98 and then instructing all activity processors 70, which are executing some minimal "bootstrap", to make a copy of it. In this way the very "instruction set" of the machine can be quickly modified, providing for rapid definition of new generic activities or other functions. This is a soft approach to "microcoding" in the sense that these control programs support the user's applications code described in terms of tokens 72, activities 78, and function libraries 90.

Most important, though, is that tokens 72 which do not "fit" into the token queue 76 can have part of themselves reside in the memory subsystem 98. The same is true for activities 78 and constants. Once this is done, it leads to tremendous advantages in the very important operations of duplicating, splitting, and concatenating structures simply by managing "use counts" in the memory subsystem 98 and replicating pointers into the memory. Memory nodes 100, within certain restrictions, should be permitted to re-organize the structures which they may contain so as to keep them as balanced as possible. This represents no overhead to activity executions unless the memory node 100 is unable to service requests while it is performing such an internal reorganization, and very often it will be able to service external requests during such operations as the requests might not always require access into the structure itself. The benefits of keeping structures as "balanced" as possible is clear in the context of "splits", which try to divide sequences roughly in the middle. If this is not achieved, logarithmic algorithms could deteriorate into linear ones (in terms of their execution time) or even worse. This is one reason for memory nodes 100 each having their own data processing capability, to manage such reorganizations automatically.

The processors 70 of the machine are arranged, logically, as a matrix of X rows with Y processors 70 in each row. The token queue 76 moves over the processors 70 parallel to this Y-axis, that is, from row to row. Processors 70 are assumed to have NIP physical input ports each, and NOP physical output ports. The number of input ports in one row is NIP.multidot.Y=NI, and the number of output ports per row is NOP.multidot.Y=NO. The token queue 76 actually moves L token positions over each row in parallel. The ratio (NO/L) is assumed integral, L is assumed even and X is assumed even. (NO/L)=K.

A physical token position is TW parallel bits. These break down into one "PA" bit, NCL "CL" bits, and NRD "RD" bits. "PA" indicates presence/absence, "CL" corresponds to the (present) token's call address, and "RD" accounts for the "remaining data".

A physical activity queue position is AW parallel bits. These break down into one "PA" bit, ADW "address" bits, and the remaining bits. AP=(AW-1), so these remaining bits are AP-ADW in number.

The activity queue 82 is, physically, J activity positions "wide" so that J activity positions move toward the processors 70 on each queue shift. J is assumed even. The activity queue 82 moves in the direction of the x-axis, that is, across the columns of the processor matrix. It is logically at right angles to the token queue 76.

The memory subsystem 98 consists of mu (.mu.) memory nodes 100, each of which provides an apparent memory resource of NODE LENGTH words to the rest of the system. Therefore, the address of a memory node 100 (MNODE=X) can be described in roof (log.sub.2 .mu.) bits. Processors 70 also have addresses (PROC=x) and can be described in roof (log (X.multidot.)) bits.

Using a massive crossbar circuit 100 of novel design (to be discussed shortly), the path between any two intercommunicating points is MTW bits in parallel, and sequential transfers at this parallel width are assumed. MTW does not correspond to any logical quantum (necessarily), such as a "word". Additional address lines and crossbar control lines are also included.

The memory subsystem 98 also includes the "free memory queue" (not shown) which has .mu.+XY positions.

Processors 70 in the X-Y matrix are assumed to have one activity input port and one activity output port each. They also interface to the memory subsystem 98 and the free memory queue, and to the token queue 76 as indicated above.

All autonomous (physically) processors 70 may have their own internal clock, provided their operation is synchronous with the external circuits to the degree that adverse behavior is avoided. Beyond this, there are three system clocks, which drive the (synchronous) circuits of the token queue 76, activity queue 82, and memory subsystem arbitration networks respectively. These clocks may also be independent. The token queue clock is assumed to run as fast as possible. The activity queue clock should be also as fast as possible. The memory clock should be as fast as reasonable in view of achievable transfer rates into the activity processors 70 and the memory node processors 100.

Finally, an overseeing "monitor" processor is necessary as a sort of machine "front panel" which senses adverse condition signals generated by the subsystems, takes care of generating resets, alarming the machine operator, and otherwise managing the "watchdog" function over the machine proper.

The drawings of the figures which are described herein are logical schematics only. They do not delve into the details of gate delays and fanouts, as any designer skilled in the art knows how to modify the designs to handle these properly. The design is also committed to no particular technology. This is positive logic, 1=true, 0=false.

MEMORY AND INPUT-OUTPUT SUBSYSTEM DETAILED CIRCUITS

M-1: P-bit Rotating One-bit

Generally indicated as 300 in FIG. 23.

Given an integer "p" (p>0) there is some integer n such that 2.sup.n .gtoreq.p>2.sup.(n-1). Then the circuit shows an n-bit binary up-counter 302 with these properties: (a) the output of the counter changes after an appropriate delay from the rising edge of the positive-duty clock, as shown; (b) the counter cycles through the values 0, 1, . . . , (p-1), then follows (p-1) with 0, 1, . . . ; (c) if ENB=0 on the rising edge of the clock pulse, the output of the counter will not change after the pulse has passed. Construction of such a counter is straightforward and should be obvious to those skilled in the art (consider for example, TTL 161 circuits).

The n-bits of the counter are input to an n-in, 2.sup.n -out decoder 304 which always has one output line true (1) and all other lines false. The line which is true corresponds to the binary value represented on the n lines from the counter; therefore the decoder will present T.sub.1 =1 (and all other T.sub.i =0), then (on the next clock pulse which changes the counter) T.sub.2 =1 (and all other T.sub.i =0) and so on. T.sub.1 corresponds to counter output=0, T.sub.2 corresponds to counter output=1, . . . , and T.sub.p =1 corresponds to counter output=(p-1).

The result is a circuit 300 which (assume ENB=1) has a one-bit rotating around the p outputs, with all the other outputs zero.

M-2: Break-in Switch

Generally indicated as 306 in FIG. 24.

This circuit, if H=1, passes input I to STAT, and a logic 1 to output "O". If H=0, input I is copied to output "O" and STAT is a logic zero.

M-3: Arbitration Signal Generator

Generally indicated as 308 in FIG. 25.

This circuit is presented without further comment than to note that only one of the P M-2 circuits 306 will have its H-input=1, so that the AC output is simply equal to the inverse of the STAT of that M-2 306 having H=1. Note also that the "I" and "O" lines are grouped together such that the "O" output of any given M-2 306 is associated with the "I" input of the next M-2 306, except for the output of the p.sup.th M-2 306, which is associated with the input of the first M-2 306. It should be readily recognized that the designations of 1, 2, . . . , p are somewhat irrelevant, as the circuit 308 defines a ring where no one M-2 306 is more important than another.

M-4: Innermost Crossbar Multiplexer

Generally indicated as 310 in FIG. 27.

Each box 312 is a 2:1 MUX. Output lines LTO, VDO, EO ("s" parallel lines) and MDO ("mtw" parallel lines) are copies of corresponding LT, VD, E, and MD if LOC=1, else (LOC=0) are copies of corresponding LTT, VDT, ET, and MDT. "s" may equal zero. That is, "E" lines are not always needed.

M-5: Innermost Path Latch

Generally indicated as 314 in FIG. 28.

This circuit is complex enough to be best described simply by Table 1 which is a truth table of five independent variables. However, the circuit shows a J-K flipflop 316. As always herein, this is meant only to indicate any appropriate memory device having the properties in this circuit: (a) inputs J and K are sampled on the rising edge of the clock pulse, but output Q does not change until after an appropriate delay; (b) if J=1 and K=O on the rising edge, then Q will be 1 after the pulse has passed; (c) if J=0 and K=1 on the rising edge, then Q will be zero after the pulse has passed. (d) if J and K are both O, then Q will remain as it was before the clock pulse arrived. Note that, in this circuit, it is not possible for both J and K to equal 1 at the same time.

A systemwide reset pulse (not shown) causes these J-K flipflops in all M-5 circuits 314 in the system to output a zero (Q=0).

There are actually six independent variables (one of them being input signal ACKI) but Table 1 is in terms of five, with ACKI appearing in the table itself and meant to indicate 1 if ACKI=1, or 0 if ACKI=0, whenever ACKI appears in the truth table as a dependent variable output.

    __________________________________________________________________________
                  LCHED prior
                          (prior to clock)
                                          LCHED after
    WANT ARBI
             HOLDI
                  to clock pulse
                          LT IGOT
                                 WANTF
                                      ATW clock pulse
    __________________________________________________________________________
    1    1   1    1       1  1   1    ACKI
                                          0
    1    1   1    1       0  1   1    ACKI
                                          ACKI
    1    1   1    0       1  0   0    0   0
    1    1   1    0       0  0   0    0   0
    1    1   0    1       1  1   1    ACKI
                                          0
    1    1   0    1       0  1   1    ACKI
                                          ACKI
    1    1   0    0       1  1   1    ACKI
                                          0
    1    1   0    0       0  1   1    ACKI
                                          ACKI
    1    0   1    1       1  1   1    ACKI
                                          0
    1    0   1    1       0  1   1    ACKI
                                          ACKI
    1    0   1    0       1  0   0    0   0
    1    0   1    0       0  0   0    0   0
    1    0   0    1       1  1   1    ACKI
                                          0
    1    0   0    1       0  1   1    ACKI
                                          ACKI
    1    0   0    0       1  0   0    0   0
    1    0   0    0       0  0   0    0   0
    0    1   1    1       1  1   0    0   0
    0    1   1    1       0  1   0    0   1
    0    1   1    0       1  0   0    0   0
    0    1   1    0       0  0   0    0   0
    0    1   0    1       1  1   0    0   0
    0    1   0    1       0  1   0    0   1
    0    1   0    0       1  0   0    0   0
    0    1   0    0       0  0   0    0   0
    0    0   1    1       1  1   0    0   0
    0    0   1    1       0  1   0    0   1
    0    0   1    0       1  0   0    0   0
    0    0   1    0       0  0   0    0   0
    0    0   0    1       1  1   0    0   0
    0    0   0    1       0  1   0    0   1
    0    0   0    0       1  0   0    0   0
    0    0   0    0       0  0   0    0   0
    __________________________________________________________________________

                  TABLE 2
    ______________________________________
                                 source
                                       source give
                                 of    of     to
    R    Q     G      T   TSUP   TSUP  FQ     D     GA
    ______________________________________
    1    1     1      1   1      G     Q      R     1
    1    1     1      0   0      dc    Q      R     0
    1    1     0      1   1      Q     R      0     0
    1    1     0      0   0      dc    Q      R     0
    1    0     1      1   1      G     R      0     1
    1    0     1      0   0      dc    G      R     1
    1    0     0      1   1      R     Q(=0)  0     0
    1    0     0      0   0      dc    R      0     0
    0    1     1      1   1      G     Q      R(-0) 1
    0    1     1      0   0      dc    Q      R     0
    0    1     0      1   1      Q     R(-0)  R     0
    0    1     1      1   0      dc    Q      R     0
    0    0     1      1   1      G     Q(-0)  R(-0) 1
    0    0     1      0   0      dc    G      R     1
    0    0     0      1   0      dc    R(-0)  R     0
    0    0     0      0   0      dc    Q(-0)  R     0
    ______________________________________