Operation Sequencing Mechanism

1. Field of the Invention

This invention relates to operation sequencing mechanisms. More particularly, it relates to data flow or distributed data processors.

2. Description of the Prior Art

The requirement for speed and efficiency of digital computing has increased over the years, and so has the complexity of digital computers increased. Switching speed has been increased to the point where incremental changes in such speeds does not provide the desired increases in the overall computing speed.

To substantially reduce the overall computing time, processors involving multiple operational or functional units have been designed. The functional units are intended to operate in parallel to thereby reduce the computing time. Such systems have been very successful but have suffered from extreme complexity and high cost.

Another prior art design that has greatly reduced overall computing time is that of the so-called pipeline computer where the computer is extremely fast in performing vector computations. However, highly sophisticated software is required to take advantage of the speed of these pipeline computers and in fact, there are certain classes of problems that are not efficiently run on such computers.

A relatively recent step forward in increasing speed of operation is that described in U.S. Pat. No. 3,962,706. The special purpose computer of that patent has an active memory that contains instructions and operands in so-called cells or instruction packets. No instruction is executed until its corresponding operands have been provided within its cell. A cell is made up of an instruction (specifies a functional unit and a specialized capability of that unit) and two operand registers. When the operands have been provided, the packet is sent to an arbitration unit and from there to the specified functional unit. From the functional unit, the resultant packet is sent to a distribution unit and back to the active memory. This type of specialized computer lends itself extremely well to small scale computers for doing specialized tasks such as fast Fourier transforms. Its distributed control, within the active memory, the arbitration unit, the distribution unit, etc., however, does not permit full scale implementation. A weather model, for example, which utilizes a million or more instructions is not feasibly capable of being implemented using this technique.

Another recent innovation is described in U.S. Pat. No. 3,978,452. The novelty described is in a plurality of function modules, each having its own arithmetic logic and memory. A module will not operate until all required inputs have been received by the module. It is a sophisticated technique, but requires a great deal of hardware. To reduce the hardware requirement, serial transmission and arithmetic is employed.

To overcome these disadvantages, the invention set out herein utilizes central control and a passive memory which can be extremely large. Also, the sequencing mechanism of this invention is adopted for use with a general purpose computer and is readily assembled from available integrated circuits.

An operation sequencing mechanism is structured to perform parallel operations, each operation depending upon the completion of predecessor operations and not upon a sequencing instruction register. The sequencer has a random access memory for storing the operations to be performed. A digital operation packet in the memory is divided into a successor address portion having provision for at least one address, a specification portion for storing at least one specification of an operation to be performed, a predecessor state portion for storing an updated state of predecessor operations required to be completed before the current operation can be performed, and a restore state portion for storing the original state of the predecessor state portion. The operation packet can be of variable length. The variable length feature permits greater flexibility in handling double precision arithmetic, multiple additions, etc. An operational unit, typically including a data memory, receives the specification from the random access memory and performs the operation. Such operation is performed only when all of the predecessor operations have been performed. This can be determined, for example, by setting the number of predecessor operations to be performed in the predecessor state portion and then decrementing such portion until it is equal to zero. Then the operation associated with such a decremented portion is ready for execution. It may well be that more than one operation at any one time is ready for execution and all such operations are sent into an operation address list.

After an operation has been completed, the associated successor addresses are read out of a successor address list and their predecessor state portions are updated. In a preferred embodiment, the predecessor state portion is a count of the predecessor operations. This count is updated by decrementing until a zero is reached, indicating that all predecessor operations have been completed and that the current operation may now be performed. If, during the update, a zero is reached, then the operation at the successor address is ready for execution and is sent into the operation address list. Also, when the predecessor state portion reaches zero, the original predecessor state portion indication, which is retained in the restore state portion, is then written into the predecessor state portion so that the operation is again available. Associated with each of the successor addresses is an indicator, which permits skipping the updating of the packet at such address if an inactive status is indicated.

FIG. 1 is a block diagram illustrating the interconnection between the components of this invention.

FIG. 2 illustrates the sequencing logic.

FIG. 3 shows the gating logic.

FIG. 4 illustrates the makeup of a digital operation packet in the instruction memory.

FIGS. 5a and 5b make up a flowchart to illustrate the operation of the invention.

FIG. 1 shows the processor 10 in block form. All of the components shown in FIG. 1 are readily available from, for example, Texas Instruments Incorporated, Dallas, Texas, the assignee of this invention.

The memory 11 is a Texas Instruments Type SN74S209 random-access read/write memory described in Texas Instruments Incorporated "The Semiconductor Memory Data Book for Design Engineers" beginning at Page 172. The output of random access memory (RAM) 11 goes to successor address list queue 13, operational register 12 and decrementer 14. Successor address portion queue 13 is a Texas Instruments Type SN74S225 16.times.5 asynchronous first-in-first-out memory described in Texas Instruments "Bipolar Microcomputer Components Data Book for Design Engineers" dated January 1977 beginning at Page 39, Section 4. Operational register 12 is a Texas Instruments Type SN74173 Register and decrementer 14 is a Texas Instruments SN7483A Adder, both described in the Texas Instruments Incorporated "The TTL Data Book for Design Engineers," copyrighted 1973, beginning on Page 360 and Page 198, respectively. The output of successor address portion queue 13 is connected to the input of successor address select 19 and the output of RAM 11 together with the output of decrementer 14 is connected to the input of new count selector 22. Successor address select 19 and new count selector 22 are both Texas Instruments Type SN74157 Quadruple 2-line-to-1-line Data Selectors/Multiplexers described in Texas Instruments Incorporated "New TTL MSI for Design Engineers" beginning at Page 34. The output of successor address select 19 is connected to the input of operation address queue 17 made up of the above-mentioned SN74S225 device. The output of successor address select 19 is also an input to operation address select 21 which has another input from the output of operation address queue 17. Operation address select 21 is made up of type SN74157 devices mentioned above. The output of decrementer 14 is also connected to NOR circuit 15 which provides an indication that decrementer 14 has reached a zero count. The output of new count selector 22 serves as an input to new count register 16 which is made up of the Type SN74173 devices and has an output connected to the input of RAM 11. he operational unit 18 is shown with its input connected to the output of operation register 12. The operational unit of this preferred embodiment is comprised of a Texas Instruments Type SN74S481 Microprocessor and a Texas Instruments Type SN74S482 Control Element described in Texas Instruments Incorporated "Bipolar Microcomputer Components Data Book" dated January 1977" starting at Page 1 of Section 1 and Page 41 of Section 5, respectively. Appropriate read-only memories such as Texas Instruments Type SN74S288, described in Texas Instruments Incorporated "The Semiconductor Memory Data Book" beginning at Page 182 of Section 4 may be used in conjunction with the SN74S481 and SN74S482. The makeup of the operational unit 18 is not important to this invention per se, and sequencing of, for example, numerically controlled machine tools is contemplated. Furthermore, while a single operational unit is shown, it is contemplated that a plurality of functional units, identical or different, may be contained therein and/or operational units may be added. A system utilizing a plurality of processing elements (functional units) is set out in U.S. Pat. No. Re. 26,171. In this embodiment, the operational unit 18 must provide a signal "operation request" (OR) and "operation complete" (OC).

A system clock (not shown) is provided. In this preferred embodiment, a Texas Instruments Type SN74LS124 dual voltage-controlled oscillator, described in Texas Instruments Incorporated "Supplement to the TTL Data Book for Design Engineers," First Edition, beginning at Page S-62, is used. Of course, the sequencer may be designed to operate totally or partially asynchronously.

Referring now to FIG. 2, sequencing logic 30 is illustrated. The result of this logic is to provide state signals S0-S4. A state transition requires the use of sequential pulses from the clock.

OR circuits 31 and 35 are identical and receive identical inputs. One, ORF, is received from inverter 58 of FIG. 3 and the other, OA, is received from an output of inverter 23 of FIG. 1. The signal A from OR circuit 31 is ANDED by AND circuit 32 with the S0 signal, the operation complete flag (OCF) signal from flip flop 59 of FIG. 3 and the first successor active (1SA) signal from successor address portion queue 13 of FIG. 1. AND circuit 32 provides output signal C which in turn serves as the set input of flip flop 33 whose Q output is signal S1 and which serves as an input to NOR circuit 34.

The output signal A from OR circuit 35 is ANDED by AND circuit 36 with signal S0, signal OCF and the signal indicating that the first successor is not active (1SA). AND circuit 36 has an output signal D which, together with signal S1, serve as the inputs to OR circuit 37 whose output is a set input to flip flop 38 whose Q output is signal S2 and which also serve as another input to NOR circuit 34.

Signal S2 and signal "second successor select" (2SS), the output from OR circuit 60 of FIG. 3, are the inputs to AND circuit 39 whose output signal F is the set input to flip flop 40 whose Q output is signal S3 and which serves as a third input to NOR circuit 34.

AND circuit 41 has input signals S2 and 2SS from inverter 62 of FIG. 3. The output of AND circuit 41, together with signal S3 are the inputs to OR circuit 42 whose output signal G is the set input to flip flop 43 whose Q output is signal S4 and which is another input to NOR circuit 34. The output of NOR circuit 34 is signal S0. The reset input to flip flops 33, 38, 40 and 43 are provided by signals S1, S2, S3 and S4, respectively.

The gating logic 50 of FIG. 3 provides the following gating signals:

Operation Fetch Gate (B);

Operation Enable Gate (OE);

Predecessor Memory Write Gate (PM);

Operation Request Flag (ORF); (ORF);

Second Successor Selected (2SS); (2SS);

Operation Complete Flag (OCF);

Update Complete Gate (S4 or UC).

Signal B, the operational fetch signal is developed by ANDING, through AND circuit 55, signals S0, ORF and OA.

Signal A is again shown as the output of OR circuit 51 which is identical to OR circuits 31 and 35 of FIG. 2, and which in fact could all be combined into one OR circuit. Signal A is ANDED, in AND circuit 52, with signal S0, OCF, 1SA, and C=0 (the output of NOR circuit 15 from FIG. 1). Output signal E from AND circuit 52 is connected to one input of OR circuit 54.

AND circuit 53 has three input signals, S2, 2SA (second successor active from Successor Address Portion Queue 13 in FIG. 1) and C=0. Output H of AND circuit 53 is a second input to OR circuit 54 whose output is signal OE.

Signals S1 and S3 are the inputs to OR circuit 56 whose output is signal PM.

Signal OR from operational unit 18 in FIG. 1 is the set input for flip flop 57, while signal B is the reset input. The output signal from flip flop 57 is signal ORF. Signal ORF is also inverted through inverter 58 to form signal ORF.

Signals S2 and S3 are the inputs to OR circuit 60 whose output is signal 2SS, also inverted through inverter 62 to form signal 2SS.

Signal OC from operational unit 18 in FIG. 1 serves as a set input to flip flop 59 while signal S4 is the reset input. The output of flip flop 59 is signal OCF.

FIG. 4 shows a typical digital operation packet 24 from the operation memory (or operation portion) having a successor address portion 25 with provision for storing at least one successor address, a specification portion 26 for storing at least one operation to be performed, a predecessor state portion 27 for storing the state of the predecessor instructions to be completed before the operation in specification portion 26 of the current instruction can be executed, and restore state portion 28 whose contents are used when the predecessor state portion has been counted to zero to restore the predecessor state portion to its original value. It should be noted that the predecessor state portion could actually be indicative of a state with an update of the state ultimately resulting in a comparison of another predetermined state to cause the instruction to be sent to the operational unit. Likewise, the restore state portion 28 can be a restore state portion with the original state held to later be written into the predecessor state portion 27.

To understand the operation of the processor of this invention, reference should be made to all of the figures, but particularly to FIGS. 5a and 5b which, in flow diagram form, illustrate the total operation. The signals designated A through H in FIG. 5 correspond to the signals of the same designation shown in FIGS. 2 and 3.

The processor is said to be in an idle loop when in state 0 as shown in FIG. 5a. Signal A high results from "no operation request flag" or an "empty operation address queue." This corresponds to the OR circuits 31, 35 and 51 of FIGS. 2 and 3. If the operation address queue is not empty and there is an "operation request flag," then the operation fetch sequence begins as indicated. At this point, it must be assumed that there is a digital operation packet in the operation address queue 17 of FIG. 1 so that signal B high causes it to transfer into the operation address selector 21 which in turn causes the contents of the specification portion (FIG. 4) to be transmitted to operation register 12. Operation register 12 is gated also by signal B which sends the specification into the operational unit 18 for processing. When the processing is completed, the path proceeds back to state 0 and through "no operation request flag." There is an "operation complete flag" at that point and therefore the successor update sequence is begun. Typically, one bit of the successor address indicates whether the successor is active, that is, whether it should be updated. The successor addresses are ordinarily active and are designated as inactive for special purposes such as having two of them in a row to stop the program. In this case, assume that the first successor is active which then provides signal C high which is the output of AND gate 32 in FIG. 2. Then the first successor should be processed. The processing is accomplished by sending the address from successor address select 19 to the operation address select 21. The digital operation packet at that address is then read out of the RAM 11 for updating. The contents of the predecessor state portion 27 are read into the decrementer 14, the contents of which in turn are read into the new count selector 22 along with the restore state portion.

Assume that C.noteq.0. Then signal S1 is high (from flip flop 33 in FIG. 2). The next step is to provide a predecessor memory write gate (signal PM from OR circuit 56 of FIG. 3) which is an input to RAM 11 for writing in the decremented count from decrementer 14 when operation enable gate (OE) signal is low. The OE signal low is applied to new count selector 22 which provides the decremented count to the new count register 16, the contents of which are gated to be written into the RAM 11 in the predecessor state portion 27.

Returning to signal C, if the zero detect resulted in C=0, then the operation enable gate (OE) signal from OR circuit 54 in FIG. 3 goes high, indicating that the operation at the first successor address is ready to be executed. The first successor address is then sent to the operation address queue 17 as a "fired" instruction taking its place in the queue. Also, signal OE gates the contents of the restore count field 28 out of new count selector 22 into new count register 16. The contents are then written as described above in the predecessor count field 27 to restore it to its original value. If the first successor had not been active, then signal D, the output of AND circuit 36 in FIG. 2, would have been high, and the first successor address would have been skipped, taking the operation directly to state 2 (S2).

In FIG. 5b, the process goes from state 2 and provides the second successor select (2SS) signal high which is seen in FIG. 3 as a signal that is present out of OR circuit 60 when either state 2 (S2) or state 3 (S3) is high. If the second successor is active, the process continues to provide signal F high for processing the second successor. As in the case of the first successor, the address of the second successor is gated out of the successor address select 19 and into the operation address select 21 to read out the operation packet from the RAM 11 at the address of the second successor. The contents of the predecessor state portion enter the decrementer 14 and the decremented number enters the new count selector 22. In FIG. 5b, if the count is not zero, the procedure goes on to state 3 with the second successor select (2SS) signal again being high with a predecessor memory write gate (PM) being high out of OR circuit 56. If the operation enable gate is low, the decremented number from decrementer 14 is moved out of the new count selector 22 into the new count register 16 and then by way of signal PM high is written into RAM 11 at the address of the second successor in the predecessor state portion. If the count equals zero, then signal H, from AND gate 53, is high which, through OR circuit 54, provides the operation enable gate (OE) signal high. The operation enable gate enables the entry of the second successor address from successor address select 19 into the operation address queue 17 to take its place as a "fired" instruction for processing. The signal OE also gates out of new count selector 22 the contents of the restore state portion 28 instead of the decremented number from decrementer 14. The restore state portion contents are transferred to new count register 16 and then written into the predecessor state portion 27 of the digital operation packet 24 at the address of the second successor.

If the second successor had not been active, then signal G would have been high out of OR circuit 41 in FIG. 2 and the process would have gone directly to develop state 4 (S4) signal high. The S4 signal is the update complete gate (UC) which unloads and discards the successor addresses in successor address portion queue 13 and also takes the operation back to state zero.

It should be pointed out that the successor address portion queue 13 holds the successor addresses which are companions to the operation held in the operation register. In the case of multiple functional units within the operational unit, or multiple operational units, the queue 13 must be capable of holding the successor address portions of all outstanding operations which have been requested but not completed. The length of the queue 13 must be equal to the largest number of operations that the operational unit or units may ever be processing in parallel plus one entry for the operation held in operation register 12.

It should further be noted that the operation address queue 17 in this preferred embodiment is a first-in first-out type of queue. It may be that instead of a first-in first-out system, a priority system is desired. This might be desirable for a number of reasons. In any event, having the operation addresses stored in one location makes the job of selection on a priority basis extremely simple and such a system is contemplated herein. The operation address list may be connected, for example, to the "operation complete" outputs of a plurality of operational units to provide a first indicia signal so that if an operation requires the use of a particular unit and that unit becomes available, the operation may be performed on the demanding packet even though its address is not up for action. In a similar manner, the successor address portion may be connected to the outputs of a plurality of operational units to provide a second indicia signal to call up selected successor addresses associated with the completed operation.

While this preferred embodiment uses a first-in, first-out memory for the successor address portion and the operation address portion list, it should be understood that such lists can also be formed and handled within the main memory. The operation register 12 may be designed to hold a plurality of specifications, perhaps a block of eight. Such a use is contemplated. Also, although the preferred embodiment illustrates the use of two successor addresses in each operation packet, it is obviously contemplated to use only one, or to use any number more than two.

Even though the preferred embodiment of the invention has been disclosed herein, there may be suggested to those skilled in the art certain minor modifications which do not depart from the spirit and scope of the invention.