Method and apparatus for aligning the operation of a plurality of processors5673423Abstract A method and apparatus are disclosed for aligning a plurality of multi-processors. The apparatus preferably comprises an alignment unit associated with each processor and a logic network for combining the output of the alignment unit and for broadcasting information to these units. Alignment is achieved by inserting in the instruction stream from each processor that is to be aligned a request for alignment, by testing for prior completion of any instructions that must be completed and by causing all processors to wait until they have all made the request for alignment and completed necessary prior instructions. The alignment unit associated with each processor monitors the instruction stream to detect a request for alignment. The logic network illustratively is an array of AND gates that tests each alignment unit to determine if it has detected a request for alignment. When all the units have made such a request, the logic network informs the alignment units; and the alignment units inform the processors. Claims What is claimed: Description BACKGROUND OF THE INVENTION
TABLE I
______________________________________
INPUTS OUTPUTS
State INST GRANT State+1
ALIGN ASSERT
______________________________________
IDLE TEST LOW ERROR X X
IDLE TEST HIGH ERROR X X
IDLE REQ LOW PEND LOW LOW
IDLE REQ HIGH ERROR X X
IDLE OTHER LOW IDLE LOW LOW
IDLE OTHER HIGH ERROR X X
PEND TEST LOW PEND LOW HIGH
PEND TEST HIGH BLOCK HIGH HIGH
PEND REQ LOW ERROR X X
PEND REQ HIGH ERROR X X
PEND OTHER LOW PEND LOW HIGH
PEND OTHER HIGH GOT HIGH HIGH
GOT TEST LOW IDLE HIGH LOW
GOT TEST HIGH BLOCK HIGH LOW
GOT REQ LOW ERROR X X
GOT REQ HIGH ERROR X X
GOT OTHER LOW SAVE HIGH LOW
GOT OTHER HIGH GOT HIGH LOW
SAVE TEST LOW IDLE HIGH LOW
SAVE TEST HIGH ERROR X X
SAVE REQ LOW ERROR X X
SAVE REQ HIGH ERROR X X
SAVE OTHER LOW SAVE HIGH LOW
SAVE OTHER HIGH ERROR X X
BLOCK TEST LOW ERROR X X
BLOCK TEST HIGH ERROR X X
BLOCK REQ LOW PEND LOW LOW
BLOCK REQ HIGH QUEUE LOW LOW
BLOCK OTHER LOW IDLE LOW LOW
BLOCK OTHER HIGH BLOCK LOW LOW
QUEUE TEST LOW PEND LOW LOW
QUEUE TEST HIGH QUEUE LOW LOW
QUEUE REQ LOW ERROR X X
QUEUE REQ HIGH ERROR X X
QUEUE OTHER LOW PEND LOW LOW
QUEUE OTHER HIGH QUEUE LOW LOW
______________________________________
Each alignment unit receives from the processor to which it is connected the instruction stream INST being executed by the processor. In accordance with the input/output table of Table I as described more fully below, each alignment unit provides to its processor a signal ALIGN indicating whether or not alignment has been achieved. In addition, each alignment unit also provides an output signal ASSERT to an input of the logic cell to which it is connected and it receives from that logic cell a READY signal which is applied to flip-flop 21 and then to combinatorial logic 26. AND gate 33 of logic cell 30 receives ASSERT signals on input lines 31, 32 and produces an output ASSERT signal on output line 34 (optionally, via flip-flop 36). In the specific embodiment of the invention shown in FIG. 3, a logic high signal is not asserted on an output line 34 until logic high signals are asserted on both input signal lines 31, 32 to AND gate 33. The output ASSERT signals from two cells are applied as the two inputs to a logic cell 30 in the next higher level of the binary tree. The uppermost cell in the AND tree has an output line 34 which is input to an AND gate 60 along with a signal from interconnection network 10 which indicates that the interconnection network is empty. The network is empty whenever there are no messages being routed through the network. A test for this condition is conventional in some interconnection networks and the provision of a signal indicating that the network is empty is within the ordinary skill of the art. In the preferred embodiment shown in FIG. 1, a test for an empty network is made to ensure that message traffic on the interconnection network is completed. Upon coincidence of a logic high empty signal and a logic high signal on the assert output 34 of the uppermost cell, a ready signal is applied by AND gate 60 to an input ready line 37 to the uppermost cell of the binary tree. This signal is provided to two output ready lines 38, 39 (optionally, via flip-flop 35) which are connected respectively to the input ready lines of two cells in the next lower level of the binary tree. At the lowest level of the binary tree, the READY signal is provided by each cell to two alignment units 20 so that the READY signal is broadcast to the entire array of alignment units 20. In general, the operation of alignment units 20 and logic cells 30 is such that a logic high signal is output on the ASSERT line from an alignment unit when that unit detects a REQUEST for alignment signal in the instruction stream received at the alignment unit. If and only if each alignment unit detects a REQUEST for alignment signal, output line 34 from the uppermost logic cell 30 in the binary tree will be logic high. If message traffic on processor interconnection network 10 is completed at some point after all the processors issue a REQUEST for alignment, then the empty signal will become logic high as well and the output of AND gate 60 will become logic high. As a result, a logic high READY signal will be broadcast down through logic cells 30 to all the alignment units where the logic high READY signal is recognized as a GRANT signal. The GRANT signal is processed by each alignment unit so as to output to the processor a single logic high ALIGN instruction for each TEST instruction in the instruction stream from the processor. If the GRANT signal is received before the TEST signal in the instruction stream, each alignment unit simply stores the GRANT signal and waits. If the TEST signal is received first, the alignment unit likewise just waits. Upon receipt of both TEST and GRANT signals, the alignment unit issues a logic high ALIGN signal to the processor, and the processor is then enabled to perform the operation for which alignment was required. Further details of the operation of the alignment unit are best explained in conjunction with Table I and the state diagram of FIG. 4, which depict the operation of alignment unit 20 and its combinatorial logic 26 and flip-flops 22-24. As shown in FIG. 4, the alignment unit can be in any one of six states: IDLE, PENDING, BLOCKING, QUEUE, GOT and SAVE. The state of the alignment unit is stored in binary encoded form in flip-flops 22, 23, 24 and is provided as an input to combinatorial logic 26 along with the instruction stream INST from the processor and the GRANT signal from flip-flop 21. The instruction stream is the sequence of instructions that is provided to the processor and, in accordance with the invention includes three types of instructions: REQUEST for alignment, TEST, and all OTHER instructions which are represented in FIG. 4 by the symbols R, T and 0 respectively. The logic high GRANT signal is represented in FIG. 4 by G and the logic low GRANT signal by G. The different combinations of inputs to combinatorial logic 26 are set forth in the three left-hand columns of Table I. The outputs produced by combinatorial logic 26 in response to these inputs are set forth in the three right-hand columns of Table I. As indicated, one output specifies the next state of the alignment unit and the other two specify the logic level of the ALIGN and ASSERT lines. In cases where some combination of inputs is not possible, the next state has been indicated to be an ERROR and the ALIGN and ASSERT levels have been left undefined. The apparatus of FIG. 1 is initialized so that the alignment units are in the IDLE state. Ordinarily, each alignment unit is in the IDLE state and remains so upon receipt of any instruction in the instruction stream from the processor except for a REQUEST instruction. This is indicated by the loop labelled O G. While in the IDLE state both the ALIGN and ASSERT outputs are logic low. The alignment unit changes to the PENDING state upon receipt of a REQUEST signal as detailed below; and in the PENDING state causes the ASSERT output to be logic high. If and when the ASSERT outputs of all the alignment units become logic high and the interconnection network is empty, the GRANT signal will become logic high and causing the GRANT signal to be logic high each alignment unit will producing output signals as specified in Table I. The alignment unit will ultimately return to the IDLE state if a TEST instruction and a logic low GRANT signal are received. As indicated, if a REQUEST signal is detected in the instruction stream and if a logic high GRANT signal has not been received from the logic cells, the alignment unit changes from the IDLE state to the PENDING state as indicated by the line R G in FIG. 4 and the third line of Table I. Once in the PENDING state, the alignment unit will stay there unless a logic high. GRANT signal is received. While in the PENDING state, combinatorial logic 26 will issue a logic high ASSERT signal for any of the possible combination of input signals. The ASSERT signals are applied to the inputs to logic cells 30; and if all the ASSERT signals are logic high and if the connection network is empty a logic high READY will be broadcast to all the alignment units indicating that all the processors have completed the instruction (such as a communication instruction) they were required to complete and accordingly are aligned. This logic high READY signal is the logic high GRANT signal of Table I. If a logic high GRANT signal is received along with an OTHER instruction, the unit changes to the GOT state as indicated by the line OG in FIG. 4 and the twelfth line of Table I and issues a logic high ALIGN signal while continuing to issue a logic high ASSERT signal. If any OTHER instruction continues to be received and the GRANT signal continues to be logic high, the combinatorial logic remains in the GOT state, but drops the ASSERT signal to logic low which causes the GRANT signal to become logic low. If the GRANT signal is logic low while an OTHER instruction is received, the alignment unit switches to the SAVE state where it remains until a TEST instruction is received and then returns to the IDLE state. If, however, a TEST instruction is received while the unit is in the GOT state, the unit changes to the BLOCKING state if the GRANT signal is logic high or to the IDLE state if the GRANT signal is logic low and causes the ASSERT signal to become logic low. The BLOCKING state prevents other alignment operations from being performed. Upon receipt of any OTHER instruction at the alignment unit while it is in the BLOCKING state and the GRANT signal is low, the unit returns to the IDLE state as indicated by the line O G between the BLOCKING and IDLE states. If, however, another REQUEST instruction is received, the alignment unit returns to the PENDING state if the GRANT signal is logic low or to the QUEUE state if the GRANT signal is logic high. The unit will remain in QUEUE as long as the GRANT signal is high and will return to PENDING when the GRANT signal goes low. Alternatively, while in the PENDING state, if the alignment unit receives the TEST instruction while the GRANT signal is logic high, it will change to the BLOCKING state. Further operations in the BLOCKING state will be the same as described above. An alternative embodiment of the invention is disclosed in FIG. 5. As shown therein, the apparatus comprises an array of processors 110, an array of alignment units 130, an array of combinatorial logic cells 130 and an interconnection network 140. The processors 110, alignment units 120 and combinatorial logic cells 130 may be the same as processors 10, alignment units 20 and logic cells 30 of FIG. 1 and processors 110 may be controlled by a control unit that is not shown. Interconnection network 140, however, is different from that of network 40 in that it is implemented in the form of separate routers 142 and connection paths 144 between each pair of processors. In such a case, it is possible to test for the absence of message traffic in the interconnection network by testing on a processor by processor basis. Thus as shown in FIG. 5, the router for each processor produces an output signal which is a logic high when there is no message traffic on the connection paths to or from the processor with which it is associated. This signal is applied as one input to an AND gate 146 which has as a second input the output of the alignment unit 130 associated with that processor. As a result, a high logic signal is provided by AND gate 146 to an input to logic cell 130 when there is no message traffic from the portion of the interconnection network associated with that processor and a logic high ASSERT signal has been generated by the alignment unit. As will be apparent, this changes the location of the test for no message traffic from the uppermost cell in the binary tree of logic cells 30 of FIG. 1 to the lowermost cells in the binary tree of logic cells 130 of FIG. 5. In other respects the operation of the alignment units and logic cells is the same as described for FIGS. 1-4. The invention may be practiced in numerous environments. For example, if the processors are Intel 80386 microprocessors, the invention may be practiced using the IN and OUT instructions of the 80386 instruction set to provide instructions to an alignment unit and receive an ALIGN signal from such unit.
______________________________________
1. MOV AL, 5 load an address, 5, of the
processor to which data is
to be sent
2. OUT sending device, AL
sand data via sending
device
3. ADD AL, CL compute data of message
4. OUT sending device, AL
send data via sending
device
5. MOV AL, 1 load into AL a 1-bit
representing a request for
alignment
6. OUT align unit, AL
mend the 1-bit in register
AL to the alignment unit
20
.
.
20. IN AL, align unit
load the ALIGN signal from
the alignment unit into
register AL
21. TEST AL, 1 test if the signal in
register AL is a 1-bit
22. INE 20 if not, return to
instruction at line 20
23. IN AL, receiving device
if it is a 1-bit, proceed
with program
illustratively by loading
signals from receiving
device into register AL
______________________________________
In the practice of the invention, the request for alignment is made by each processor wherever it is necessary for inter-processor communications to have been completed before the processor can continue with its program. In the illustrative code set forth above, the request for alignment is made at line 6. The requests for alignment are processed by the alignment units 20 associated with each processor and are forwarded to logic cells 30 as logic high ASSERT signals. These requests are ANDed together by logic cells 30 and when all processors have made such a request a logic high signal is applied to AND gate 60. If the interconnection network is empty, a logic high READY signal is broadcast by AND gate 60 to all the alignment units 20 via logic cells 30. In the illustrative code set forth above, the logic level of the READY or GRANT signal is monitored by the instructions at lines 20, 21, and 22, which respectively read this signal level, test if it is a 1-bit or logic high, and recycle if the 1-bit has not been received. These instructions provide the function of the TEST instruction and the ALIGN signal of Table I. The processors are all aligned at the time the READY signal goes logic high which occurs at some point between the request for alignment at line 6 and the time each processor initiates a successful test for a 1-bit in the AL register as at lines 20-23. It is not necessary, however, that each processor make such a test at the same time; and it is not necessary that the first such test be made after the READY signal goes logic high. If the logic high READY signal is received before the program reaches lines 20-21, the alignment unit will save that information until those lines are reached; and if the READY signal is still logic low when the program reaches line 20, the program will simply loop through the instructions at lines 20-22 until the READY signal goes logic high. As will be apparent to those skilled in the art, numerous modifications may be made in the practice of the invention. For example, while the invention has been described in terms of apparatus (AND gate 60) which tests for completion of communication on an interconnection network, it may be desirable to make other tests in place of or in addition to such a test of the communication network. Thus, if the computer systems includes mathematics co-processors or the software includes various subroutines whose outputs might alter data to be communicated from one processor to another, it will be desirable to test such equipment or operations to make sure they have completed their tasks before issuing the READY signal to the processors. Such a test can readily be made by using a global OR network to test the state of an activity flag associated with each hardware or software element whose operation must be completed before the program can proceed.
|
Same subclass Same class Consider this |
||||||||||