Method and apparatus for implementing atomicity of memory operations in dynamic multi-streaming processors
View Patent ↗A multi-streaming processor has a plurality of streams for streaming one or more instruction threads, a set of functional resources for processing instructions from streams, and a lock mechanism for locking selected memory locations shared by streams of the processor, the hardware-lock mechanism operating to set a lock when an atomic memory sequence is started and to clear a lock when an atomic memory sequence is completed. In preferred embodiments the lock mechanism comprises one or more storage locations associated with each stream of the processor, each storage location enabled to store a memory address a lock bit, and a stall bit. Methods for practicing the invention using the apparatus are also taught.
1. A multi-streaming processor, comprising:
a plurality of streams for streaming one or more instruction threads; and
a lock mechanism for locking selected memory locations shared by the plurality of streams,
wherein for each of the selected memory locations the lock mechanism is configured to store:
a lock indication which indicates whether a corresponding memory location is locked; and
one or more stall indications, each of which identify a stream of the plurality of streams that is stalled waiting for a locked memory location to become unlocked.
2. The multi-streaming processor of claim 1 , wherein for a given locked memory location the lock mechanism is further configured to:
detect an instruction which causes any corresponding streams that are stalled to become un-stalled prior to the given locked memory location becoming unlocked.
3. The multi-streaming processor of claim 2 , wherein said instruction is executing within a particular stream, and wherein the instruction further indicates a period of time the particular stream will wait before resuming execution.
4. The multi-streaming processor of claim 3 , wherein the instruction is included in an instruction sequence configured to support an atomic read-modify-write operation.
5. The multi-streaming processor of claim 1 , wherein the lock mechanism is configured to:
set a lock for a given memory location when an atomic memory sequence is started; and
clear the lock when an atomic memory sequence is completed.
6. The multi-streaming processor of claim 1 , wherein said selected memory locations are memory locations of a cache shared by the plurality of streams.
7. The multi-streaming processor of claim 6 , wherein each memory location comprises a cache line, and wherein each of said cache lines is configured to store one of said lock indications and one or more of said stall indications.
8. The multi-streaming processor of claim 7 , wherein the lock indication comprises a lock bit, and each of the one or more stall indications comprise a stream number.
9. A method for implementing atomic memory sequences in a multi-streaming processor, comprising:
detecting an atomic access by a first stream of a plurality of streams to a selected memory location of a plurality of memory locations, wherein said plurality of memory locations are shared by the plurality of streams;
storing a lock indication associated with the selected memory location, in response to the detected access;
detecting a subsequent access by a second stream to the selected memory location while the memory location is locked; and
storing a stall indication associated with the selected memory location which indicates the second stream is stalled,
wherein each of said memory locations is configured to store a lock indication and one or more stall indications.
10. The method of claim 9 , wherein for a given locked memory location the method further comprises:
detecting a particular instruction; and
un-stalling any corresponding streams which are stalled prior to the given locked memory location becoming unlocked, in response to the particular instruction.
11. The method of claim 10 , wherein said particular instruction is executing within a particular stream, and wherein the instruction further indicates a period of time the particular stream will wait before resuming execution.
12. The method of claim 11 , wherein the instruction is included in an instruction sequence configured to support an atomic read-modify-write operation.
13. The method of claim 9 , further comprising:
setting a lock for a given memory location when an atomic memory sequence is started; and
clearing the lock when an atomic memory sequence is completed.
14. The method of claim 9 , wherein said selected memory locations are memory locations of a cache shared by the plurality of streams.
15. The method of claim 14 , wherein each memory location comprises a cache line, and wherein the method comprises storing for each of said cache lines one of said lock indications and one or more of said stall indications.
16. The method of claim 15 , wherein the lock indication comprises a lock bit, and each of the one or more stall indications comprise a stream number.