SYSTEM AND METHOD FOR HARDWARE ACCELERATION OF A SOFTWARE TRANSACTIONAL MEMORY

• US 20110099335A1
• Filed: 10/26/2010
• Published: 04/28/2011
• Est. Priority Date: 12/09/2005
• Status: Active Grant

• Current Assignee: University of Rochester
• Original Assignee: University of Rochester
• Inventors: Scott, Michael L., Marathe, Virendra, Shriraman, Arrvindh, Spear, Michael F., Dwarkadas, Sandhya
• Granted Patent: US 8,180,971 B2
• Time in Patent Office: Days
• US Class Current: 711/141
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking

Abstract

In a transactional memory technique, hardware serves simply to optimize the performance of transactions that are controlled fundamentally by software. The hardware support reduces the overhead of common TM tasks—conflict detection, validation, and data isolation—for common-case bounded transactions. Software control preserves policy flexibility and supports transactions unbounded in space and in time. The hardware includes 1) an alert-on-update mechanism for fast software-controlled conflict detection; and 2) programmable data isolation, allowing potentially conflicting readers and writers to proceed concurrently under software control.

Claims

1. A method for responding to an eviction or non-local writing (i.e., writing by another thread) of certain line(s) in a local cache of a cache-coherent shared-memory computer, the method comprising:

(a) registering an alert handler for each thread that is interested in the eviction or non-local writing of said certain line(s) in the local cache;

(b) receiving indications from certain thread(s) of the line(s) for which the eviction or non-local writing is of interest, and marking said line(s) in the local cache; and

(c) upon the eviction or non-local writing of a marked line, effecting in each interested thread an immediate subroutine call to the alert handler of the thread, without changing a state of the local cache.

2. The method of claim 1, wherein if the number of lines in which a thread indicates interest exceeds the marking capacity of the cache, the thread is caused to call its alert handler with an indication that said capacity has been exceeded.

3. The method of claim 1, further comprising response to local writes and, optionally, reads, to wit:

(d) receiving indications from certain thread(s) of the line(s) for which local writes and, optionally, reads are of interest, and marking said line(s) in the local cache; and

(e) upon a local write or, optionally, read of a marked line, effecting in each interested thread an immediate subroutine call to the alert handler of that thread, without changing the state of the local cache.

4. The method of claim 1, further comprising a software transactional memory process in which

(f) each thread indicates interest in metadata associated with all data it is reading transactionally;

(g) each thread writes the metadata associated with all data it is modifying transactionally, thereby inducing a call to the alert handler of each transactionally reading thread; and

(h) the alert handler aborts the current transaction of its thread.

5. The method of claim 4, wherein:

(i) if the number of lines in which a thread indicates interest exceeds the marking capacity of the cache, the thread is caused to call its alert handler with an indication that said capacity has been exceeded;

(j) each thread maintains an estimate of the amount of metadata in which it can indicate interest without exceeding the marking capacity of the cache;

(k) in lieu of indicating interest in metadata beyond said estimate, each thread incrementally validates previously read data whenever inconsistency in said data might otherwise lead to incorrect behavior; and

(l) if a thread is caused to execute its alert handler with an indication that the marking capacity of the cache has been exceeded, it reduces its estimate before retrying its transaction.

6. A method for choosing whether to commit speculative writes in a cache-coherent shared-memory computer in which such writes have been indicated, and their lines so marked in a local cache, the method comprising:

(a) distinguishing, in a cache coherence protocol, between ordinary and speculative requests for exclusive access to a line;

(b) retaining, in the local cache, lines that have been speculatively written, despite speculative remote requests for exclusive access to those lines; and

(c) providing an atomic conditional-validate operation which attempts to update a location that has not been speculatively written, which, if successful, makes all speculatively written lines in the local cache appear to have been non-speculatively written, and which, if unsuccessful, makes all speculatively written or threatened lines in the local cache appear to be invalid.

7. The method of claim 6, wherein each thread registers an alert handler, and if the number of lines that have been speculatively written exceeds the marking capacity of the cache, the thread is caused to call its handler with an indication that said capacity has been exceeded.

8. The method of claim 6, for a system in which speculative reads have also been indicated, and their lines so marked in a local cache, the method further comprising:

(d) sending, in response to remote coherence protocol requests for a shared copy of a line that has been speculatively written locally, an indication that the line is threatened;

(e) similarly treating as threatened any line that has been speculatively read locally, and for which a speculative remote request for exclusive access is received;

(f) retaining threatened, speculatively read lines in the local cache, but marking said threatened, speculatively read lines as threatened; and

(g) augmenting the conditional-validate operation such that regardless of outcome, threatened lines in the local cache appear to be invalid, and speculatively read but non-threatened lines in the local cache appear to have been non-speculatively read.

9. The method of claim 8, wherein each thread registers an alert handler, and if the number of lines that have been speculatively written exceeds the marking capacity of the cache, the thread is caused to call its handler with an indication that said capacity has been exceeded.

10. The method of claim 8, wherein:

(h) one bit in the tag of a cache line indicates that the line has been speculatively accessed (read or written) since the most recent invalidate or conditional-validate operation;

(i) one bit indicates that the most recent write to the line was speculative;

(j) one bit indicates, for any line that has not been accessed since the last time at which the bit in (h) was set and an invalidate or conditional-validate operation occurred, whether said operation was a successful conditional-validate;

(k) additional bits indicate the state of the line according to the underlying coherence protocol;

(l) at the time of an invalidate or conditional-validate operation, the cache controller uses the bit in (h) to determine whether to modify the bit in (j);

(m) a line is interpreted as being invalid if the bit in (h) is unset and either the line appears to be invalid according to the bits in (k), or else the line appears to have been written according to the bits in (k), but the bit in (i) is set and the bit in (j) is unset;

(n) a line is interpreted as having been non-speculatively written if it appears to have been written according to the bits in (k), the bit in (h) is unset, and either the bit in (i) is unset or the bit in (j) is set;

(o) on any access to a line, the cache controller unsets the bit in (j); and

(p) on any access other than a speculative write to a line for which the bit in (h) is unset, the cache controller unsets the bit in (i).

11. The method of claim 6, further comprising:

(a′

) registering an alert handler for each thread that is interested in the eviction or non-local writing of certain line(s) in the local cache;

(b′

) receiving indications from certain thread(s) of the line(s) for which the eviction or non-local writing is of interest, and marking said line(s) in the local cache;

(c′

) upon the eviction or non-local writing of a marked line, effecting in each interested thread an immediate subroutine call to the alert handler of the thread, without changing the state of the local cache; and

a software transactional memory process in which;

(q) threads use speculative writes to modify data transactionally, eliminating the need to modify private copies of those data;

(r) each thread indicates interest in metadata associated with its current transaction and with all data it is reading transactionally;

(s) each thread writes the metadata of all data it will modify transactionally, thereby inducing an immediate call to the alert handler of each thread that is reading the data transactionally;

(t) each thread writes the metadata of any transaction it needs to abort, thereby inducing an immediate call to the alert handler of the thread executing said transaction;

(u) the alert handler aborts the current transaction of its thread; and

(v) software ensures that (i) a transaction commits if and only if it ends with a successful conditional-validate instruction;

(ii) if concurrent transactions write the same datum, at most one of them commits; and

(iii) if a concurrent reader and writer of the same datum both commit, the reader does so first.

12. The method of claim 11, for a system in which speculative reads have also been indicated, and their lines so marked in a local cache, said method further comprising:

(d) sending, in response to remote coherence protocol requests for a shared copy of a line that has been speculatively written locally, an indication that the line is threatened;

(e) similarly treating as threatened any line that has been speculatively read locally, and for which a speculative remote request for exclusive access is received;

(f) retaining threatened, speculatively read lines in the local cache, but marking the threatened, speculatively read lines as threatened; and

(g) augmenting the conditional-validate operation such that regardless of outcome, threatened lines in the local cache appear to be invalid, and speculatively read but non-threatened lines in the local cache appear to have been non-speculatively read; and

wherein threads further use speculative reads to inspect transactional data, eliminating the need to re-load lines in the wake of speculative remote requests for exclusive access to those lines.

13. The method of claim 11, wherein:

(w) each thread registers an alert handler, and if the number of lines that have been speculatively written exceeds the marking capacity of the cache, the thread is caused to call its handler with an indication that said capacity has been exceeded;

(x) in response to an indication that the marking capacity of the cache has been exceeded, the alert handler aborts the current transaction and retries in an overflow mode;

(y) a thread that is executing a transaction in overflow mode modifies the metadata of all data it reads, to make itself visible to writers; and

(z) a thread explicitly aborts all visible readers of data it modifies.

14. The method of claim 11, wherein software may choose to delay the action in (s) until just before a thread attempts to commit its transaction, thereby permitting a writer to proceed speculatively in parallel with readers, or with another writer;

in this case the writer transaction indicates interest in the metadata of all data it is speculatively writing.

15. A system for managing a computer memory which is accessible to a plurality of threads responding to an eviction or non-local writing (i.e., writing by another thread) of certain line(s) in a local cache of a cache-coherent shared-memory computer, the system comprising:

a plurality of caches in communication with the computer memory; and

a processor or processors for;

(a) registering an alert handler for each thread that is interested in the eviction or non-local writing of said certain line(s) in the local cache;

(b) receiving indications from each of certain thread(s) of the line(s) for which the eviction or non-local writing is of interest, and marking said line(s) in the local cache; and

(c) upon the eviction or non-local writing of a marked line, effecting in each interested thread an immediate subroutine call to the alert handler of the thread, without changing a state of the local cache.

16. The system of claim 15, wherein if the number of lines in which a thread indicates interest exceeds the marking capacity of the cache, the thread is caused to call its alert handler with an indication that said capacity has been exceeded.

17. The system of claim 15, wherein the processor or processors further perform a response to local writes and, optionally, reads, to wit:

(d) receiving indications from certain thread(s) of the line(s) for which local writes and, optionally, reads are of interest, and marking said line(s) in the local cache; and

(e) upon a local write or, optionally, read of a marked line, effecting in each interested thread an immediate subroutine call to the alert handler of that thread, without changing the state of the local cache.

18. The system of claim 15, wherein the processor or processors further implement a software transactional memory system in which

(f) each thread indicates interest in metadata associated with all data it is reading transactionally;

(g) each thread writes the metadata associated with all data it is modifying transactionally, thereby inducing a call to the alert handler of each transactionally reading thread; and

(h) the alert handler aborts the current transaction of its thread.

19. The system of claim 18, wherein:

(i) if the number of lines in which a thread indicates interest exceeds the marking capacity of the cache, the thread is caused to call its alert handler with an indication that said capacity has been exceeded;

(j) each thread maintains an estimate of the amount of metadata in which it can indicate interest without exceeding the marking capacity of the cache;

(k) in lieu of indicating interest in metadata beyond said estimate, each thread incrementally validates previously read data whenever inconsistency in said data might otherwise lead to incorrect behavior; and

(l) if a thread is caused to execute its alert handler with an indication that the marking capacity of the cache has been exceeded, it reduces its estimate before retrying its transaction.

20. A system for choosing whether to commit speculative writes in a cache-coherent shared-memory computer in which such writes have been indicated, and their lines so marked in a local cache, the system comprising:

a plurality of caches in communication with the computer memory; and

a processor or processors for;

(a) distinguishing, in a cache coherence protocol, between ordinary and speculative requests for exclusive access to a line;

(b) retaining, in the local cache, lines that have been speculatively written, despite speculative remote requests for exclusive access to those lines; and

(c) providing an atomic conditional-validate operation which attempts to update a location that has not been speculatively written, which, if successful, makes all speculatively written lines in the local cache appear to have been non-speculatively written, and which, if unsuccessful, makes all speculatively written or threatened lines in the local cache appear to be invalid.

21. The system of claim 20, wherein each thread registers an alert handler, and if the number of lines that have been speculatively written exceeds the marking capacity of the cache, the thread is caused to call its handler with an indication that said capacity has been exceeded.

22. The system of claim 20, in which speculative reads have also been indicated, and their lines so marked in a local cache, wherein the processor or processors further perform:

(d) sending, in response to remote coherence protocol requests for a shared copy of a line that has been speculatively written locally, an indication that the line is threatened;

(e) similarly treating as threatened any line that has been speculatively read locally, and for which a speculative remote request for exclusive access is received;

(f) retaining threatened, speculatively read lines in the local cache, but marking said threatened, speculatively read lines as threatened; and

(g) augmenting the conditional-validate operation such that regardless of outcome, threatened lines in the local cache appear to be invalid, and speculatively read but non-threatened lines in the local cache appear to have been non-speculatively read.

23. The system of claim 22, wherein each thread registers an alert handler, and if the number of lines that have been speculatively written exceeds the marking capacity of the cache, the thread is caused to call its handler with an indication that said capacity has been exceeded.

24. The system of claim 22, wherein:

(h) one bit in the tag of a cache line indicates that the line has been speculatively accessed (read or written) since the most recent invalidate or conditional-validate operation;

(i) one bit indicates that the most recent write to the line was speculative;

(j) one bit indicates, for any line that has not been accessed since the last time at which the bit in (h) was set and an invalidate or conditional-validate operation occurred, whether said operation was a successful conditional-validate;

(k) additional bits indicate the state of the line according to the underlying coherence protocol;

(l) at the time of an invalidate or conditional-validate operation, the cache controller uses the bit in (h) to determine whether to modify the bit in (j);

(m) a line is interpreted as being invalid if the bit in (h) is unset and either the line appears to be invalid according to the bits in (k), or else the line appears to have been written according to the bits in (k), but the bit in (i) is set and the bit in (j) is unset;

(n) a line is interpreted as having been non-speculatively written if it appears to have been written according to the bits in (k), the bit in (h) is unset, and either the bit in (i) is unset or the bit in (j) is set;

(o) on any access to a line, the cache controller unsets the bit in (j); and

(p) on any access other than a speculative write to a line for which the bit in (h) is unset, the cache controller unsets the bit in (i).

25. The system of claim 20, wherein the processor or processors further perform:

(a′

) registering an alert handler for each thread that is interested in the eviction or non-local writing of certain line(s) in the local cache;

(b′

) receiving indications from each of certain thread(s) of the line(s) for which the eviction or non-local writing is of interest, and marking said line(s) in the local cache;

(c′

) upon the eviction or non-local writing of a marked line, effecting in each interested thread an immediate subroutine call to the alert handler of the thread, without changing the state of the local cache; and

wherein the processor or processors further implement a software transactional memory system in which;

(q) threads use speculative writes to modify data transactionally, eliminating the need to modify private copies of those data;

(r) each thread indicates interest in metadata associated with its current transaction and with all data it is reading transactionally;

(s) each thread writes the metadata of all data it will modify transactionally, thereby inducing an immediate call to the alert handler of each thread that is reading the data transactionally;

(t) each thread writes the metadata of any transaction it needs to abort, thereby inducing an immediate call to the alert handler of the thread executing said transaction;

(u) the alert handler aborts the current transaction of its thread; and

(v) software ensures that (i) a transaction commits if and only if it ends with a successful conditional-validate instruction;

(ii) if concurrent transactions write the same datum, at most one of them commits; and

(iii) if a concurrent reader and writer of the same datum both commit, the reader does so first.

26. The system of claim 25, wherein speculative reads have also been indicated, and their lines so marked in a local cache, and wherein the processor or processors further implement:

(d) sending, in response to remote coherence protocol requests for a shared copy of a line that has been speculatively written locally, an indication that the line is threatened;

(e) similarly treating as threatened any line that has been speculatively read locally, and for which a speculative remote request for exclusive access is received;

(f) retaining threatened, speculatively read lines in the local cache, but marking the threatened, speculatively read lines as threatened; and

(g) augmenting the conditional-validate operation such that regardless of outcome, threatened lines in the local cache appear to be invalid, and speculatively read but non-threatened lines in the local cache appear to have been non-speculatively read; and

wherein threads further use speculative reads to inspect transactional data, eliminating the need to re-load lines in the wake of speculative remote requests for exclusive access to those lines.

27. The system of claim 25, wherein:

(w) each thread registers an alert handler, and if the number of lines that have been speculatively written exceeds the marking capacity of the cache, the thread is caused to call its handler with an indication that said capacity has been exceeded

(x) in response to an indication that the marking capacity of the cache has been exceeded, the alert handler aborts the current transaction and retries in an overflow mode;

(y) a thread that is executing a transaction in overflow mode modifies the metadata of all data it reads, to make itself visible to writers; and

(z) a thread explicitly aborts all visible readers of data it modifies.

28. The system of claim 25, wherein software may choose to delay the action in (s) until just before a thread attempts to commit its transaction, thereby permitting a writer to proceed speculatively in parallel with readers, or with another writer;

in this case the writer transaction indicates interest in the metadata of all data it is speculatively writing.

29. An article of manufacture for responding to an eviction or non-local writing (i.e., writing by another thread) of certain line(s) in a local cache of a cache-coherent shared-memory computer, the article of manufacture comprising:

a computer-readable storage medium; and

code, stored on the computer-readable storage medium, for controlling a processor or processors for;

(a) registering an alert handler for each thread that is interested in the eviction or non-local writing of said certain line(s) in the local cache;

(b) receiving indications from each of certain thread(s) of the line(s) for which the eviction or non-local writing is of interest, and marking said line(s) in the local cache; and

(c) upon the eviction or non-local writing of a marked line, effecting in each interested thread an immediate subroutine call to the alert handler of the thread, without changing a state of the local cache.

30. The article of manufacture of claim 29, wherein if the number of lines in which a thread indicates interest exceeds the marking capacity of the cache, the thread is caused to call its alert handler with an indication that said capacity has been exceeded.

31. The article of manufacture of claim 29, wherein the code comprises code for response to local writes and, optionally, reads, to wit:

(d) receiving indications from certain thread(s) of the line(s) for which local writes and, optionally, reads are of interest, and marking said line(s) in the local cache; and

(e) upon a local write or, optionally, read of a marked line, effecting in each interested thread an immediate subroutine call to the alert handler of that thread, without changing the state of the local cache.

32. The article of manufacture of claim 29, wherein the code comprises code for implementing a software transactional memory system in which

(f) each thread indicates interest in metadata associated with all data it is reading transactionally;

(g) each thread writes the metadata associated with all data it is modifying transactionally, thereby inducing a call to the alert handler of each transactionally reading thread; and

(h) the alert handler aborts the current transaction of its thread.

33. The article of manufacture of claim 32, wherein:

(i) if the number of lines in which a thread indicates interest exceeds the marking capacity of the cache, the thread is caused to call its alert handler with an indication that said capacity has been exceeded;

(j) each thread maintains an estimate of the amount of metadata in which it can indicate interest without exceeding the marking capacity of the cache;

(k) in lieu of indicating interest in metadata beyond said estimate, each thread incrementally validates previously read data whenever inconsistency in said data might otherwise lead to incorrect behavior; and

(l) if a thread is caused to execute its alert handler with an indication that the marking capacity of the cache has been exceeded, it reduces its estimate before retrying its transaction.

34. An article of manufacture for choosing whether to commit speculative writes in a cache-coherent shared-memory computer in which such writes have been indicated, and their lines so marked in a local cache, the article of manufacture comprising:

a computer-readable storage medium; and

code, stored on the computer-readable storage medium, for controlling a processor or processors for;

(a) distinguishing, in a cache coherence protocol, between ordinary and speculative requests for exclusive access to a line;

(b) retaining, in the local cache, lines that have been speculatively written, despite speculative remote requests for exclusive access to those lines; and

(c) providing an atomic conditional-validate operation which attempts to update a location that has not been speculatively written, which, if successful, makes all speculatively written lines in the local cache appear to have been non-speculatively written, and which, if unsuccessful, makes all speculatively written or threatened lines in the local cache appear to be invalid.

35. The article of manufacture of claim 34, wherein each thread registers an alert handler, and if the number of lines that have been speculatively written exceeds the marking capacity of the cache, the thread is caused to call its handler with an indication that said capacity has been exceeded.

36. The article of manufacture of claim 34, for a system in which speculative reads have also been indicated, and their lines so marked in a local cache, wherein the code comprises code for:

(d) sending, in response to remote coherence protocol requests for a shared copy of a line that has been speculatively written locally, an indication that the line is threatened;

(e) similarly treating as threatened any line that has been speculatively read locally, and for which a speculative remote request for exclusive access is received;

(f) retaining threatened, speculatively read lines in the local cache, but marking said threatened, speculatively read lines as threatened; and

(g) augmenting the conditional-validate operation such that regardless of outcome, threatened lines in the local cache appear to be invalid, and speculatively read but non-threatened lines in the local cache appear to have been non-speculatively read.

37. The article of manufacture of claim 36, wherein each thread registers an alert handler, and if the number of lines that have been speculatively written exceeds the marking capacity of the cache, the thread is caused to call its handler with an indication that said capacity has been exceeded.

38. The article of manufacture of claim 36, wherein:

(h) one bit in the tag of a cache line indicates that the line has been speculatively accessed (read or written) since the most recent invalidate or conditional-validate operation;

(i) one bit indicates that the most recent write to the line was speculative;

(j) one bit indicates, for any line that has not been accessed since the last time at which the bit in (h) was set and an invalidate or conditional-validate operation occurred, whether said operation was a successful conditional-validate;

(k) additional bits indicate the state of the line according to the underlying coherence protocol;

(l) at the time of an invalidate or conditional-validate operation, the cache controller uses the bit in (h) to determine whether to modify the bit in (j);

(m) a line is interpreted as being invalid if the bit in (h) is unset and either the line appears to be invalid according to the bits in (k), or else the line appears to have been written according to the bits in (k), but the bit in (i) is set and the bit in (j) is unset;

(n) a line is interpreted as having been non-speculatively written if it appears to have been written according to the bits in (k), the bit in (h) is unset, and either the bit in (i) is unset or the bit in (j) is set;

(o) on any access to a line, the cache controller unsets the bit in (j); and

(p) on any access other than a speculative write to a line for which the bit in (h) is unset, the cache controller unsets the bit in (i).

39. The article of manufacture of claim 34, wherein the code comprises code for:

(a′

) registering an alert handler for each thread that is interested in the eviction or non-local writing of certain line(s) in the local cache;

(b′

) receiving indications from certain thread(s) of the line(s) for which the eviction or non-local writing is of interest, and marking said line(s) in the local cache;

(c′

) upon the eviction or non-local writing of a marked line, effecting in each interested thread an immediate subroutine call to the alert handler of the thread, without changing the state of the local cache; and

a software transactional memory process in which;

(q) threads use speculative writes to modify data transactionally, eliminating the need to modify private copies of those data;

(r) each thread indicates interest in metadata associated with its current transaction and with all data it is reading transactionally;

(s) each thread writes the metadata of all data it will modify transactionally, thereby inducing an immediate call to the alert handler of each thread that is reading the data transactionally;

(t) each thread writes the metadata of any transaction it needs to abort, thereby inducing an immediate call to the alert handler of the thread executing said transaction;

(u) the alert handler aborts the current transaction of its thread; and

(v) software ensures that (i) a transaction commits if and only if it ends with a successful conditional-validate instruction;

(ii) if concurrent transactions write the same datum, at most one of them commits; and

(iii) if a concurrent reader and writer of the same datum both commit, the reader does so first.

40. The article of manufacture of claim 39, for a system in which speculative reads have also been indicated, and their lines so marked in a local cache, wherein the code comprises code for:

(d) sending, in response to remote coherence protocol requests for a shared copy of a line that has been speculatively written locally, an indication that the line is threatened;

(e) similarly treating as threatened any line that has been speculatively read locally, and for which a speculative remote request for exclusive access is received;

(f) retaining threatened, speculatively read lines in the local cache, but marking the threatened, speculatively read lines as threatened; and

(g) augmenting the conditional-validate operation such that regardless of outcome, threatened lines in the local cache appear to be invalid, and speculatively read but non-threatened lines in the local cache appear to have been non-speculatively read; and

wherein threads further use speculative reads to inspect transactional data, eliminating the need to re-load lines in the wake of speculative remote requests for exclusive access to those lines.

41. The article of manufacture of claim 39, wherein:

(w) each thread registers an alert handler, and if the number of lines that have been speculatively written exceeds the marking capacity of the cache, the thread is caused to call its handler with an indication that said capacity has been exceeded

(x) in response to an indication that the marking capacity of the cache has been exceeded, the alert handler aborts the current transaction and retries in an overflow mode;

(y) a thread that is executing a transaction in overflow mode modifies the metadata of all data it reads, to make itself visible to writers; and

(z) a thread explicitly aborts all visible readers of data it modifies.

42. The article of manufacture of claim 39, wherein software may choose to delay the action in (s) until just before a thread attempts to commit its transaction, thereby permitting a writer to proceed speculatively in parallel with readers, or with another writer;

in this case the writer transaction indicates interest in the metadata of all data it is speculatively writing.