Apparatus for aligning the operation of a plurality of processors
First Claim
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.
5 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
Specification