Memory-to-memory copy and compare/exchange instructions to support non-blocking synchronization schemes

• US 20020078307A1
• Filed: 12/15/2000
• Published: 06/20/2002
• Est. Priority Date: 12/15/2000
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Zahir, Achmed Rumi
• Granted Patent: US 6,502,170 B2
• Time in Patent Office: Days
• US Class Current: 711/145
• CPC Class Codes: G06F 12/0831 using a bus scheme, e.g. with bus monitoring or watching means
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A coherency technique for multiprocessor systems in which threads perform atomic read or atomic write transactions pursuant to memory-to-memory copy instructions or memory-to-memory compare-and-exchange instructions. Although the source reads and target writes are each atomic, the instruction is not required to be atomic from the read through the write operation. Accordingly, once a first thread reads source data pursuant to a read, for example, it may allow other threads to access that data prior to completing its own target write. The data may include a version stamp. After the first thread operates on the data, software may read in the version stamp a second time. If the two version stamps agree, the results of the thread'"'"'s operation may be considered valid for lookup operations. For a compare and exchange operation, a thread may read data from a source location. Subsequently, the thread may read atomically a current copy of a version stamp from a target address, compare it to a version of the same version stamp obtained earlier, and, if the two version stamps agree, write the source data to the target address.

Claims

1. A method of implementing an atomic memory-to-memory copy of data, comprising:

atomically reading data to a thread from a source location, and

atomically writing the data from a thread to a target location,

wherein cache coherent operations may occur between the reading and the writing.

2. The method of claim 1, wherein the reading and writing respectively transfer a quantity of data larger than an internal register of the thread.

3. The method of claim 1, wherein the reading and writing respectively transfer a quantity of data up to a cache line of a computer system in which the thread is located.

4. The method of claim 1, wherein the reading is directed to a predetermined address in a system memory, a first portion of the address representing a cache line from which the data is to be read and a second portion of the address representing a location within the cache line where a version stamp is located.

5. The method of claim 4, wherein, in a system having aligned cache lines of L bytes in length, the second address portion is log₂(L) in length.

6. The method of claim 4, wherein a length of the version stamp is defined by an instruction used by software to invoke the method.

7. A method of implementing an atomic memory-to-memory copy of data, comprising:

atomically reading data from a source location to a thread, and atomically;

acquiring exclusive ownership of a target location, and

writing the data to the target location,

wherein the atomic reading operation and the atomic acquisition-and-writing operation may be interrupted by cache coherent operations.

8. The method of claim 7, wherein the reading and writing respectively transfer a quantity of data larger than an internal register of the thread.

9. The method of claim 7, wherein the reading and writing respectively transfer a quantity of data up to a cache line of a computer system in which the thread is located.

10. The method of claim 7, wherein the reading is directed to a predetermined address in a system memory, a first portion of the address representing a cache line from which the data is to be read and a second portion of the address representing a location within the cache line where a version stamp is located.

11. The method of claim 10, wherein a length of the version stamp is defined by an instruction used by software to invoke the method.

12. The method of claim 10, wherein, in a system having aligned cache lines of L bytes in length, the second portion is log₂(L) in length.

14. The method of claim 13, wherein the reading and writing respectively transfer a quantity of data larger than an internal register of the thread.

15. The method of claim 13, wherein the reading and writing respectively transfer a quantity of data up to a cache line of a computer system in which the thread is located.

16. The method of claim 13, wherein the reading is directed to a predetermined address in a system memory, a first portion of the address representing a cache line from which the data is to be read and a second portion of the address representing a location within the cache line where a version stamp is located.

17. The method of claim 16, wherein a length of the version stamp is defined by an instruction used by software to invoke the method.

18. The method of claim 13, wherein, in a system having aligned cache lines of L bytes in length, the second portion is log₂(L) in length.

19. The method of claim 13, wherein data at the source location includes a third version stamp.

20. The method of claim 13, further comprising returning the first version stamp to a software level of the thread.

21. The method of claim 13, further comprising, if the first and the second version stamps agree, returning a flag indicating that the version stamps agree.

22. The method of claim 13, further comprising, if the first and the second version stamps do not agree, returning a flag indicating that the version stamps do not agree.

13. A method of implementing an atomic memory-to-memory compare and exchange operation, comprising:

atomically data from a source location to a thread; and

atomically;

reading a first version stamp from a target location,

comparing the first version stamp with a second version stamp stored by the thread, and

if the first and the second version stamps agree, writing the M bytes of source data to the target location.