Methods of maintaining cache coherence and processor synchronization in a multiprocessor system using send and receive instructions

Claim 2

In a system having a plurality of processors, each processor controlling a respective one of a plurality of cache memories connected via a shared bus to a common memory system, a method for synchronizing execution of one of said processors functioning as a sending processor and execution of a plurality of said processors functioning as receiving processors, the method comprising the steps of: a) said sending processor executing a SEND instruction specifying a send address, the step of said sending processor executing a SEND instruction comprising the steps of: i) awaiting acknowledgement from any of said receiving processors via assertion of a MATCH SIGNAL over said shared bus, and ii) thereupon transmitting over said shared bus a cache line corresponding to said send address from the cache memory controlled by said sending processor; and b) each receiving processor executing a RECEIVE instruction specifying a receive address, the step of each receiving processor executing a RECEIVE instruction comprising the steps of: i) awaiting transmission of said send address by said sending processor over said shared bus, ii) thereupon receiving said send address and comparing said send address with said receive address, iii) asserting the MATCH SIGNAL over said shared bus when said send address and said receive address are equal, and iv) thereupon awaiting transmission of the cache line over said shared bus and receiving the cache line into the cache memory controlled by any of the receiving processors which have asserted the MATCH SIGNAL; whereby execution of said sending processor and said receiving processors is synchronized.

Claim 3

The method as claimed in claim 1, wherein the step (b) of each receiving processor executing a RECEIVE instruction further comprises the step of: each receiving processor asserting a RECEIVE SIGNAL over said shared bus upon executing said RECEIVE instruction to indicate to said sending processor a readiness to receive data over said shared bus.

Claim 4

The method as claimed in claim 1, wherein the step (a) of said sending processor executing a SEND instruction further comprises the steps of: obtaining exclusive write access to said shared bus, and thereafter, transmitting said send address onto said shared bus while simultaneously asserting a SEND SIGNAL over said shared bus to indicate to said receiving processors that said send address has been transmitted onto said shared bus.

Claim 5

The method as claimed in claim 1, wherein the step (a)(i) of said sending processor awaiting acknowledgement from any of said receiving processors via assertion of a MATCH SIGNAL over said shared bus comprises the steps of: 1) determining whether any of said receiving processors has asserted the MATCH SIGNAL over said shard bus, 2) if the MATCH SIGNAL has not been asserted by any of said receiving processors, stalling indefinitely until a RECEIVE SIGNAL has been asserted by any of said receiving processors over said shared bus and thereupon retransmitting said send address over said shared bus, and 3) repeating steps (a)(i)(1) and (a)(i)(2) until the MATCH SIGNAL has been detected.

Claim 6

The method as claimed in claim 1, wherein the step (b)(i) of each receiving processor awaiting transmission of said send address by said sending processor over said shared bus comprises the steps of: 1) stalling indefinitely until said sending processor has asserted a SEND SIGNAL over said shared bus, and 2) thereupon receiving said send address transmitted by said sending processor; and further wherein the step (a)(i) of said sending processor awaiting acknowledgement from any of said receiving processors via assertion of a MATCH SIGNAL over said shared bus comprises the steps of: 1) determining whether any of said receiving processors has asserted the MATCH SIGNAL over said shared bus, 2) if the MATCH SIGNAL has not been asserted by any of said receiving processors, stalling indefinitely until a RECEIVE SIGNAL has been asserted by any of said receiving processors over said shared bus and thereupon asserting the SEND SIGNAL and transmitting said send address over said shared bus, and 3) repeating steps (a)(i)(1) and (a)(i)(2) until the MATCH SIGNAL has been detected.

Claim 7

The method as claimed in claim 5, further comprising the step of: interrupting further execution of the RECEIVE instruction by at least one of said receiving processors due to an external event and thereafter resuming execution of the RECEIVE instruction by said at least one interrupted receiving processor; and interrupting further execution of the SEND instruction by the sending processor due to an external event and thereafter resuming execution of the SEND instruction by said sending processor.

Claim 8

In a system having a plurality of worker processors and a control processor, each processor having a unique memory address and controlling a respective one of a plurality of cache memories connected via a shared bus, a method of executing a program loop having a plurality of iterations by said plurality of worker processors and said control processor, the method comprising the steps of: each worker processor executing a RECEIVE instruction causing each worker processor to stall indefinitely until said control processor executes a respective SEND instruction for each worker processor; said control processor executing a respective SEND instruction for each worker processor to initiate each worker processor to perform a respective one of the iterations of said program loop, the step of executing a respective SEND instruction comprising the steps of: i) specifying the unique memory address for a respective one of said worker processors, and ii) transferring over said shared bus an index of the iteration to be performed by said one worker processor; each worker processor receiving the iteration index transferred via execution of its respective SEND instruction and storing the iteration index at its unique memory address; each worker processor executing the iteration corresponding to its received iteration index in parallel with and asynchronous to execution by the other worker processors; each worker processor indicating to said control processor completion of its iteration by executing a SEND instruction comprising the steps of: i) specifying the unique memory address of said control processor, and ii) transferring over said shared bus a unique datum; said control processor repeatedly executing a RECEIVE instruction specifying the unique memory address of said control processor to receive the unique datum from each worker processor and to store the unique datum at the unique memory address of said control processor, whereby said control processor receives said unique datum from each worker processor in any order; said control processor initiating each worker processor which has completed its iteration to perform an unexecuted iteration of said program loop by executing a respective SEND instruction comprising the steps of: i) specifying the unique memory address for a respective one of said worker processors which has completed its iteration, and ii) transferring over said shared bus an index of the unexecuted iteration to be performed by said one worker processor which has completed its iteration; and said control processor ceasing to initiate performance of iterations by said worker processors when all iterations of said program loop have been distributed to said worker processors.

Claim 9

In a system having a plurality of worker processors and a control processor, each processor having a unique memory address and controlling a respective one of a plurality of cache memories connected via a shared bus, a method of executing a program loop having a plurality of iterations by said plurality of worker processors and said control processor, the method comprising the steps of: each worker processor executing a RECEIVE instruction causing each worker processor to stall indefinitely until said control processor executes a respective SEND instruction for each worker processor; said control processor executing a respective SEND instruction for each worker processor to initiate each worker processor to perform a respective one of the iterations of said program loop, the step of executing a respective SEND instruction comprising the steps of: i) specifying the unique memory address for a respective one of said worker processors, and ii) transferring over said shared bus an index of the iteration to be performed by said one worker processor; each worker processor receiving the iteration index transferred via execution of its respective SEND instruction and storing the iteration index at its unique memory address; each worker processor executing the iteration corresponding to its received iteration index in parallel with and asynchronous to execution by the other worker processors; each worker processor indicating to said control processor completion of its iteration by executing a SEND instruction comprising the steps of: i) specifying the unique memory address of said control processor, and ii) transferring over said shared bus a unique datum; said control processor repeatedly executing a RECEIVE instruction specifying the unique memory address of said control processor to receive the unique datum from each worker processor and to store the unique datum at the unique memory address of said control processor, whereby said control processor receives said unique datum from each worker processor in any order; said control processor initiating each worker processor which has completed its iteration to perform an unexecuted iteration of said program loop by executing a respective SEND instruction comprising the steps of: i) specifying the unique memory address for a respective one of said worker processors which has completed its iteration, and ii) transferring over said shared bus an index of the unexecuted iteration to be performed by said one worker processor which has completed its iteration; and said control processor ceasing to initiate performance of iterations by said worker processors when all iterations of said program loop have been distributed to said worker processors.

Claim 10

The method as claimed in claim 7, wherein execution of an iteration by a first one of said worker processors is dependent on shared datum modified during execution of an iteration by a second one of said worker processors, the method further comprising the steps of: said first worker processor executing a RECEIVE instruction specifying a memory address of said shared datum, the step of said first worker processor executing a RECEIVE instruction comprising the steps: i) awaiting execution by said second worker processor of a SEND instruction specifying the memory address, and ii) thereupon receiving the shared datum from said shared bus; said second worker processor executing a SEND instruction specifying the memory address, the step of said second worker processor executing a SEND instruction comprising the steps: i) awaiting execution by said first worker processor of a RECEIVE instruction specifying the memory address, and ii) thereupon transmitting said shared datum over said shared bus; and said first and second worker processors each continuing execution independently after execution of said RECEIVE and SEND instructions, respectively.

Claim 11

The method as claimed in claim 7, further comprising the steps of: interrupting further execution of the RECEIVE instruction or the SEND instruction by at least one of said processors due to an external event and thereafter resuming execution of the RECEIVE instruction or the SEND instruction by said at least one interrupted processor.