Apparatus for aligning the operation of a plurality of processors

• US 5,222,237 A
• Filed: 05/29/1990
• Issued: 06/22/1993
• Est. Priority Date: 02/02/1988
• Status: Expired due to Term

• Current Assignee: TM Patents LP
• Original Assignee: Thinking Machines Corporation (Oracle Corporation)
• Inventors: Hillis, W. Daniel
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US07/530,484
• Time in Patent Office: 1,120 Days
• Field of Search: 364/200, 364/900, 371/47, 371/19, 371/36, 371/47.1, 395/200, 395/650, 395/375, 395/800
• US Class Current: 712/204
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

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

1. A system comprising:

A. a plurality of processors each for processing a separate instruction stream, each instruction stream comprising a sequence of instructions of a plurality of diverse instruction types including an alignment request type and an alignment test type, each processor while processing an instruction of said alignment request type generating an alignment request indication, each processor while processing an instruction of said alignment test type generating an alignment test indication and monitoring for receipt of an alignment indication, each processor being inhibited from processing instructions after processing an instruction of the alignment test type until after it receives an alignment indication; and

B. an alignment network for generating an alignment indication for a processor in response to receipt therefrom of an alignment test indication following generation of alignment request indications by all of said processors, said alignment network comprising;

i. a plurality of alignment state control circuits each connected to a processor, each alignment state control circuit generating an alignment request signal in response to an alignment request indication from its connected processor and the alignment indication in response to receipt of a ready indication, each said alignment state control circuit comprising;

a. a request receiving circuit for receiving alignment request indications and alignment test indications from a processor;

b. a ready indication latch circuit connected to a coincidence circuit for latching said ready indication, the ready indication latch circuit having a ready state determined by the latched ready indication; and

c. a state circuit for controlling the generation of said alignment request signal in response to the receipt of said alignment request indication and for controlling the generation of said alignment indication in response to the receipt of said alignment test indication by said request receiving circuit and the ready indication latch circuit having the ready state; and

ii. a coincidence circuit connected to all of said alignment state control circuits for generating the ready indication coupled to all of said ready indication latch circuits in response to generation of alignment request signals by all of said state circuits.

2. A system comprising:

A. a plurality of processors each for processing a separate instruction stream, each instruction stream comprising a sequence of instructions of a plurality of diverse instruction types including an alignment request type and an alignment test type, each processor while processing an instruction of said alignment request type generating an alignment request indication, each processor while processing an instruction of said alignment test type generating an alignment test indication and monitoring for receipt of an alignment indication, each processor being inhibited from processing instructions after processing an instruction of the alignment test type until after it receives an alignment indication;

B. an interconnection network connected to all of said processors for facilitating transfer of information there-among, said interconnection network further generating an empty signal if it is empty;

C. an alignment network for generating an alignment indication for a processor in response to receipt therefrom of an alignment test indication following generation of alignment request indications by all of said processors, said alignment network comprising;

i. a plurality of alignment state control circuits each connected to a processor, each alignment state control circuit generating an alignment request signal in response to an alignment request indication from its connected processor and the alignment indication in response to receipt of an alignment test indication from its connected processor and a ready indication; and

ii. a coincidence circuit connected to all of said alignment state control circuits for generating the ready indication coupled to all of said alignment state control circuits in response to generation of alignment request signals by all of said alignment state control circuits and said empty signal from said interconnection network.

3. In a computer comprising a plurality of processors each of which executes its own sequence of instructions defining an instruction stream, each instruction stream including instructions of a plurality of types including an alignment request type, an alignment test type and at least one other instruction type, and each instruction stream including at least one instruction of the alignment request type situated int he instruction stream to be executed at one point in time, at least one instruction of the alignment test type situated in the instruction steam to be executed at a later point in time than the instruction of the alignment request type, and at least some instruction streams having at least one instruction of another instruction type situated in the instruction stream to be executed at a point in time between execution of the instruction of the alignment request type and the instruction of the alignment test type, an alignment control arrangement comprising:

A. a plurality of testing means each associated with a processor responsive to the processing by the processor of an instruction from the processor'"'"'s respective instruction stream for testing the instruction to determine whether it is an instruction of the alignment request type or an instruction of an alignment test type, the testing means comprising;

i. means for storing an identification of a current state of an alignment process, and

ii. combinatorial logic responsive to a first signal, a signal representative of the executing instruction stream from said processor, and a signal representative of said current state, said combinatorial logic generating a signal identifying a next state of the alignment process, a signal requesting an alignment, and a signal indicating if alignment has been achieved;

B. determining means for determining that all the testing means have detected an instruction of the alignment request type and for using such determination to control generation of said first signal; and

C. a plurality of inhibiting means each associated with a processor for preventing the associated processor from executing an instruction beyond an instruction of said alignment test type until said first signal is generated by said determining means.

4. In a computer comprising a plurality of processors each of which executes its own sequence of instructions defining an instruction stream, each instruction stream including instructions of a plurality of types including an alignment request type, an alignment test type and at least one other instruction type, and each instruction stream including at least one instruction of the alignment request type situated in the instruction stream to be executed at one point in time, at least one instruction of the alignment test type situated in the instruction stream to be executed at a later point in time than the instruction of the alignment request type, and at least some instruction streams having at least one instruction of another instruction type situated in the instruction stream to be executed at a point in time between execution of the instruction of the alignment request type and the instruction of the alignment test type, an alignment control arrangement comprising:

A. a plurality of testing means each associated with a processor responsive to the processing by the processor of an instruction from the processor'"'"'s respective instruction stream for testing the instruction to determine whether it is an instruction of the alignment request type or an instruction of an alignment test type;

B. determining means for determining that all the testing means have detected an instruction of the alignment request type and for using such determination to control generation of a first signal, said determining means comprising an array of AND gates for detecting a request for alignment from each processor, and means for testing for the absence of message traffic in a communications means between said processors and for using said test for the absence of message traffic to control the generation of said first signal; and

C. a plurality of inhibiting means each associated with a processor for preventing the associated processor from executing an instruction beyond an instruction of said alignment test type until said first signal is generated by said determining means.

5. A system comprising a plurality of processors interconnected by an interconnection network and an alignment network;

A. each processor (10,20) processing a separate instruction stream, each processor being responsive to its instruction stream for generating messages for transfer over said interconnection network and for receiving messages from said interconnection network, each processor further being responsive to processing of its instruction stream to generate an alignment request signal for transmission over said alignment network in response to the processing, and each processor receiving a consolidated alignment signal from said alignment network and using it to control timing of processing of instructions from its instruction stream;

B. said interconnection network (40) being connected to at least some of said processors for transferring messages among said processors;

C. said alignment network (30) receiving the alignment request signal from all of said processors, the alignment network generating in response thereto said consolidated alignment signal representing a selected logical function of the alignment request signals provided by all of said processors, said alignment network comprising a plurality of logic cells (30) connected in a tree structure defining a root logic cell and a plurality of leaf logic cells, said leaf logic cells being connected to said processors, each logic cell including a coincidence circuit (33) that receives intermediate consolidated alignment signals from each of its children and generates an intermediate consolidated alignment signal in response thereto, the intermediate consolidated alignment signal generated by said root logic cell corresponding to the consolidated alignment signal that is provided to said processors.

6. A system as defined in claim 5 in which each logic cell further includes a latch circuit (36) for latching the output signal from said coincidence circuit in response to a clock signal, the latch circuit generating a latched output signal that comprises the intermediate consolidated alignment signal generated by the logic cell.

7. A system as defined in claim 5 in which each logic cell further includes a consolidated alignment distribution circuit (35,37,38,39) that receives the consolidated alignment signal from its parent logic cell and distributes it to both of its children, each leaf logic cell distributing the consolidated alignment signals it receives from its parent to the processors connected thereto.

8. A system as defined in claim 7 in which said consolidated alignment distribution circuit includes a latch (35) that latches the consolidated alignment signal received from its parent logic cell in response to a clock signal and that transmits the consolidated alignment signal to its children to thereby propagate the consolidated alignment signal form the root logic cell to the logic cells and thereby to the processors.

9. A system comprising:

A. a plurality of processors each for processing a separate instruction stream, each instruction stream comprising a sequence of instructions of a plurality of diverse instruction types including an alignment request type and an alignment test type, each processor while processing an instruction of said alignment request type generating an alignment request indication, each processor while processing an instruction of said alignment test type generating an alignment test indication and monitoring for receipt of an alignment indication, each processor being inhibited from processing instructions after processing an instruction of the alignment test type until after it receives an alignment indication; and

B. an alignment network for generating an alignment indication for a processor in response to receipt therefrom of an alignment test indication following generation of alignment request indications by all of said processors, said alignment network comprising;

i. a plurality of alignment state control circuits each connected to a processor, each alignment state control circuit generating (a) an alignment request signal in response to receipt of the alignment request indication from its connected processor and (b) the alignment indication in response to receipt of a ready indication; and

ii. a coincidence circuit connected to all of said alignment state control circuits for generating the ready indication coupled to all of said alignment state control circuits in response to generation of alignment request signals by all of said alignment state control circuits, said coincidence circuit comprising a plurality of logic cells connected in a tree structure defining a root logic cell and a plurality of leaf logic cells, each logic cell including a coincidence circuit that generates an output signal that is coupled to a parent in response to reception of input signals from a plurality of children, each leaf logic cell having as input signals alignment request signals from a predetermined number of alignment state control circuits and generating as an output signal an assert signal, the logic cells propagating the assert signals to the root cell, the root cell including a ready indication generating circuit for generating the ready indication in response to its receipt of assert signals from its children for coupling to all of said alignment state control circuits.

10. A system as defined in claim 9 in which each logic cell further includes a latch circuit for latching the output signal in response to a clock signal, the latch circuit generating a latched output signal that comprises the assert signal that is propagated toward the root cell.

11. A system as defined in claim 9 in which each logic cell further includes a ready indication distribution circuit including a latch that latches the ready indication from its parent logic cell in response to a clock signal and that transmits the latched ready indication to its children to thereby propagate the ready indication from the root logic cell to the leaf logic cells, the leaf logic cells transmitting the ready indications latched thereby to the alignment state control circuits connected thereto.

12. A system as defined in claim 9 further including an interconnection network connected to all of said processors for facilitating transfer of information there-among, said interconnection network further generating an empty signal if it is empty, said coincidence circuit further using said empty signal in generation of said ready indication.

13. A system comprising:

A. a plurality of processors each for processing a separate instruction stream, each instruction stream comprising a sequence of instructions of a plurality of diverse instruction types including an alignment request type, an alignment test type and at least one other instruction type, and each instruction stream including at least one instruction of the alignment request type situated in the instruction stream to be executed at one point in time, at least one instruction of the alignment test type situated in the instruction stream to be executed at a later point in time than the instruction of the alignment request type, and at least some instruction streams having at least one instruction of another instruction type situated in the instruction stream to be executed at a point in time between execution of the instruction of the alignment request type and the instruction of the alignment test type, each processor while processing an instruction of said alignment request type generating an alignment request indication, each processor while processing an instruction of said alignment test type generating an alignment test indication and monitoring for receipt of an alignment indication, each processor being inhibited from processing instructions after said instruction of the alignment test type until after it receives an alignment indication; and

B. an alignment network for generating an alignment indication for a processor in response to receipt therefrom of an alignment test indication following generation of alignment request indications by all of said processors, said alignment network comprising;

i. a plurality of alignment state control circuits each connected to a processor, each alignment state control circuit generating an alignment request signal in response to an alignment request indication from its connected processor; and

ii. a coincidence circuit connected to all of said alignment state control circuits for generating a ready indication coupled to all of said alignment state control circuits in response to generation of alignment request signals by all of said alignment state control circuits.

14. A system as defined in claim 13 in which each said alignment state control circuit further generates an alignment indication in response to the coincidence of an alignment test indication and a ready indication.

15. A system as defined in claim 14 further including an interconnection network connected to all of said processors for facilitating transfer of information there-among, said interconnection network further generating an empty signal if it is empty, said coincidence circuit further using said empty signal in generation of said alignment indication.

16. A system as defined in claim 14 in which each said alignment state control circuit comprises:

a. a request receiving circuit for receiving alignment request indications and alignment test indications from a processor;

b. a ready indication latch circuit connected to said coincidence circuit for latching said ready indication, the ready indication latch circuit having a ready state determined by the latched ready indication; and

c. a state circuit for controlling the generation of said alignment request signal and said ready indication in response to the receipt of said alignment request indication and alignment test indication by said request receiving circuit and the ready state.

17. A system as defined in claim 13 in which said coincidence circuit comprises a plurality of logic cells connected in a tree structure defining a root logic cell and a plurality of leaf logic cells, each logic cell including a coincidence circuit that generates an output signal that is coupled to its parent in response to reception of input signals from a plurality of children, each leaf cell having as input signals alignment request signals from a predetermined number of alignment state control circuits and generating as an output signal an assert signal, the logic cells propagating the assert signals to the root cell, the root cell including a ready indication generating circuit for generating the ready indication for coupling to all of said alignment state control circuits.

18. A system as defined in claim 17 in which each logic cell further includes a latch circuit for latching the output signal from said coincidence circuit in response to a clock signal, the latch circuit generating a latched output signal that comprises the assert signal that is propagated toward the root cell.

19. A system as defined in claim 17 in which each logic cell further includes a ready indication distribution circuit including a latch that latches the ready indication from its parent logic cell in response to a clock signal and that transmits the latched ready indication to its children to thereby propagate the ready indication form the root logic cell to the leaf logic cells, the leaf logic cells transmitting the ready indications latched thereby to the alignment state control circuits connected thereto.

20. A system as defined in claim 17 further including an interconnection network connected to all of said processors for facilitating transfer of information there-among, said interconnection network further generating an empty signal if it is empty, said ready indication generating circuit further using said empty signal in generation of said ready indication.