Method and apparatus for arbitration and serialization in a multiprocessor system
First Claim
1. A distributed multiprocessor system comprising:
- a plurality of distributed central processing units (CPUs) for processing data in response to instructions, wherein each given CPU in said plurality of distributed CPUs comprises;
means, responsive to a predetermined instruction in said given CPU, for generating a REQUEST TO SERIALIZE OTHER CPUs signal (REQUEST);
means, connected to the REQUEST generating means in said given CPU, for transmitting a REQUEST generated by said REQUEST generating means in said given CPU to all of said plurality of distributed CPUs;
means, coupled to said REQUEST transmitting means in said plurality of distributed CPUs and having a plurality of outputs, for simultaneously supplying at said outputs all REQUESTs simultaneously generated by CPUs in said plurality of distributed CPUs, includinga plurality of inputs for receiving REQUESTS from all CPUs in said system; and
a delay circuit means for providing in series with each of said plurality of inputs a predetermined delay having a magnitude which is inversely proportional to an amount of time it takes to transmit a REQUEST from a sending CPU to one of said plurality of inputs; and
means, connected to receive REQUESTs from said plurality of outputs and responsive to simultaneously received REQUESTs, for awarding priority to one REQUEST from a single CPU of said simultaneously received REQUESTs for processing by said given CPU.
0 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for providing arbitration between and serialization of plural processors in a multiprocessor system comprising, in each processor, a delay network, a priority circuit, a REQUEST generator, an ORDER generator, a serialization program, an ACK generator and an ACK receiver. In operation, the delay network insures that simultaneously generated REQUESTS received from plural processors are received by the priority circuit at the same time. A processor awarded priority issues an ORDER to the other processors and thereafter drops its REQUEST to allow an award of priority to another processor. An ACK is received by the ORDER issuing processor from each processor when it executes the ORDER. The ORDER issuing processor then completes the task which gave rise to the ORDER. To conserve processing time, priority awards may be made before previously issued ORDERS are completed. Alternatively, REQUEST issuing processors can simply hold their REQUEST and thereby prevent interruption of instructions or groups of instructions.
44 Citations
9 Claims
-
1. A distributed multiprocessor system comprising:
-
a plurality of distributed central processing units (CPUs) for processing data in response to instructions, wherein each given CPU in said plurality of distributed CPUs comprises; means, responsive to a predetermined instruction in said given CPU, for generating a REQUEST TO SERIALIZE OTHER CPUs signal (REQUEST); means, connected to the REQUEST generating means in said given CPU, for transmitting a REQUEST generated by said REQUEST generating means in said given CPU to all of said plurality of distributed CPUs; means, coupled to said REQUEST transmitting means in said plurality of distributed CPUs and having a plurality of outputs, for simultaneously supplying at said outputs all REQUESTs simultaneously generated by CPUs in said plurality of distributed CPUs, including a plurality of inputs for receiving REQUESTS from all CPUs in said system; and a delay circuit means for providing in series with each of said plurality of inputs a predetermined delay having a magnitude which is inversely proportional to an amount of time it takes to transmit a REQUEST from a sending CPU to one of said plurality of inputs; and means, connected to receive REQUESTs from said plurality of outputs and responsive to simultaneously received REQUESTs, for awarding priority to one REQUEST from a single CPU of said simultaneously received REQUESTs for processing by said given CPU. - View Dependent Claims (2, 3, 9)
-
-
4. A distributed multiprocessor system comprising:
-
a plurality of distributed central processing units (CPUs) for processing data in response to instructions, wherein each given CPU in said plurality of distributed CPUs comprises; means, responsive to a predetermined instruction in said given CPU, for generating a REQUEST TO SERIALIZE OTHER CPUs signal (REQUEST); means, connected to the REQUEST generating means in said given CPU, for transmitting a REQUEST generated by said REQUEST generating means in said given CPU to all of said plurality of distributed CPUs; means, coupled to said REQUEST transmitting means in said plurality of distributed CPUs and having a plurality of outputs, for simultaneously supplying at said outputs all REQUESTs simultaneously generated by CPUs in said plurality of distributed CPUs; and means, connected to receive REQUESTS from said plurality of outputs and responsive to simultaneously received REQUESTs, for awarding priority to one REQUEST from a single CPU of said simultaneously received REQUESTs for processing by said given CPU;
wherein said REQUEST generating means comprises means, responsive to an instruction requiring the execution of a predetermined operation without interruption and without serializing other CPU'"'"'s in the system, for holding said REQUEST once priority is granted to said CPU to prevent other CPU'"'"'s in the system from being granted priority until after completion of the execution of said predetermined operation.
-
-
5. A method of arbitration between requests for serialization of a plurality of distributed central processing units (CPUs) in a multiprocessor system in which each of said plurality of CPUs comprises a priority circuit having a plurality of inputs, and a means for generating a REQUEST TO SERIALIZE OTHER CPUs control signal (REQUEST) in response to an instruction comprising steps of:
-
transmitting a REQUEST from one or more of said plurality of CPUs to said priority circuit in each of said plurality of CPUs in such a manner that all REQUESTs simultaneously generated by said plurality of CPUs are simultaneously received by said priority circuits in all of said plurality of CPUs; and
awarding priority to a determined one REQUEST of the simultaneously received REQUESTs in the priority circuit in all of said plurality of CPUs;
wherein said transmitting step further comprises a step of;providing in series with each of said plurality of inputs of said priority circuits a predetermined delay between the means for generating in one of the plurality of CPUs and a corresponding one of said plurality of inputs, the predetermined delay having a magnitude which is inversely proportional to an amount of time it takes to transmit a REQUEST from a sensing one of said plurality of CPUs to a corresponding one of said plurality of inputs.
-
-
6. A method of arbitration between and serialization of a plurality of central processing units (CPUs) in a multiprocessor system in which each of said plurality of CPUs comprises a priority circuit having a plurality of inputs, and a means for a generating a REQUEST TO SERIALIZE OTHER CPUs control signal (REQUEST) comprising steps of:
-
transmitting a REQUEST from one or more of said plurality of CPUs to said priority circuit in each of said plurality of CPUs in such a manner that all REQUESTs simultaneously generated by said plurality of CPUs are simultaneously received by said priority circuits in all of said plurality of CPUs; and
awarding priority to a determined one of the plurality of CPUs which generated one REQUEST of the simultaneously received REQUESTs in the priority circuit in all of said plurality of CPUs;generating, in an ORDER generating means located in the determined one of the plurality of CPUs, a SERIALIZE YOURSELF control signal (ORDER); performing a local serialization operation in the determined one CPU which generates said ORDER; transmitting said ORDER from said ORDER generating means to a remainder of said plurality of CPU'"'"'s; executing, in response to said ORDER in each of the remainder of said plurality of CPU'"'"'s receiving said ORDER, a serialization operation; generating, in an ACK generating means located in each of the remainder of said plurality of CPU'"'"'s executing said serialization operation, a SERIALIZATION COMPLETED control signal (ACK) when said execution of said serialization operation is completed; transmitting said ACK from each of said ACK generating means to said determined one CPU; dropping said REQUEST in response to said ORDER in said determined one CPU; and completing the instruction in said determined one CFU and thereafter dropping said ORDER in response to receipt of said ACK from said other CPU'"'"'s and upon the completion of said local serialization operation in said determined one CPU. - View Dependent Claims (8)
-
-
7. A method of arbitration between requests for serialization of a plurality of distributed central processing units (CPUs) in a multiprocessor system in which each of said plurality of CPUs comprises a priority circuit having a plurality of inputs, and a means for generating a REQUEST TO SERIALIZE OTHER CPUs control signal (REQUEST) in response to an instruction comprising steps of:
-
transmitting a REQUEST from one or more of said plurality of CPUs to said priority circuit in each of said plurality of CPUs in such a manner that all REQUESTs simultaneously generated by said plurality of CPUs are simultaneously received by said priority circuits in all of said plurality of CPUs; and
awarding priority to a determined one REQUEST of the simultaneously received REQUESTS in the priority circuit in all of said plurality of CPUs, wherein said transmitting step further comprises steps of;providing a plurality of delay circuits; and coupling a predetermined number of said delay circuits in series between each of said plurality of inputs of said priority circuits and a corresponding one of said plurality of CPUs, said predetermined number being inversely proportional to an amount of time it takes to transmit a REQUEST to said one of said plurality of inputs from a corresponding one of said plurality of CPUs.
-
Specification