Determining a conflict in accessing shared resources using a reduced number of cycles
View Patent ↗Illustrated is a system and method for identifying a potential conflict, using a conflict determination engine, between a first transaction and a second transaction stored in a conflict hash map, the potential conflict based upon a potential accessing of a shared resource common to both the first transaction and the second transaction. The system and method further includes determining an actual conflict, using the conflict determination engine to access the combination of the conflict hash map and the read set hash map, between the first transaction and the second transaction, where a time stamp value of only selected shared locations has changed relative to a previous time stamp value, the time stamp value stored in the read set hash map and accessed using the first transaction.
1. A computer implemented method comprising:
identifying a potential conflict, using a conflict determination engine, between a first transaction and a second transaction both stored in a read set hash map and a conflict hash map, the potential conflict based upon a potential accessing of a shared resource common to both the first transaction and the second transaction; and
determining an actual conflict, using the conflict determination engine to access the combination of the conflict hash map and the read set hash map, between the first transaction and the second transaction, where a time stamp value of only selected shared locations has changed relative to a previous time stamp value, the time stamp value stored in the read set hash map and accessed using the first transaction.
2. The computer implemented method of claim 1 , wherein the conflict hash map is instantiated at runtime from a static conflict graph, the static conflict graph including the first transaction and the second transaction as nodes in the static conflict graph, and the potential conflict as an edge in the static conflict graph.
3. The computer implemented method of claim 2 , further comprising mapping, using a mapping engine, a counter value to corresponding shared locations, the counter value having been obtained from the static conflict graph.
4. The computer implemented method of claim 1 , wherein the first and second transactions include at least one of a variable, a thread, or a function.
5. The computer implemented method of claim 1 , wherein the shared resource includes memory.
6. The computer implemented method of claim 1 , further comprising identifying the potential conflict, using the conflict determination engine, through a change in a counter value relative to a previous counter value, the counter used to access an address of a potentially conflicting shared resource as stored in the conflict hash map, this address used to query the read set hash map and validate only entries found in the read set hash map.
7. The computer implemented method of claim 1 , further comprising aborting, using a Software Transactional Memory (STM) module, the first transaction based upon the actual conflict.
8. A computer system comprising:
a conflict determination engine to identify a potential conflict between a first transaction and a second transaction both stored in a read set hash map and a conflict hash map, the potential conflict based upon a potential accessing of a shared resource common to both the first transaction and the second transaction; and
the conflict determination engine to access the conflict hash map and the read set hash map determine an actual conflict between the first transaction and the second transaction, where a time stamp value of only selected shared locations has changed relative to a previous time stamp value, the time stamp value stored in the read set hash map and accessed using the first transaction.
9. The computer system of claim 8 , wherein the conflict hash map is instantiated at runtime from a static conflict graph, the static conflict graph including the first transaction and the second transaction as nodes in the static conflict graph, and the potential conflict as an edge in the static conflict graph.
10. The computer system of claim 8 , further comprising a mapping engine to map a counter value to corresponding shared locations, the counter value having been obtained from the static conflict graph.
11. The computer system of claim 8 , wherein the first transaction and the second transaction include at least one of a variable, a thread, or a function.
12. The computer system of claim 8 , wherein the system resource includes memory.
13. The computer system of claim 8 , wherein the conflict determination engine is used to identify the potential conflict through a change in a counter value relative to a previous counter value, the counter used to access an address of a potentially conflicting shared resource as stored in the conflict hash map, this address used to query the read set hash map and validate only entries found in the read set hash map.
14. The computer system of claim 8 , further comprising a Software Transactional Memory (STM) module to abort the first transaction based upon the actual conflict.
15. A computer system comprising:
at least one processor;
a memory in communication with the at least one processor, the memory including logic encoded in one or more tangible media for execution and when executed operable to:
identify a potential conflict between a first transaction and a second transaction both stored in a read set hash map and a conflict hash map, the potential conflict based upon a potential accessing of a shared resource common to both the first transaction and the second transaction; and
determine an actual conflict, through the access of the conflict hash map and the read set hash, between the first transaction and the second transaction, where a time stamp value of only selected shared locations has changed relative to a previous time stamp value, the time stamp value stored in the read set hash map and accessed using the first transaction.
16. The computer system of claim 15 , wherein the conflict hash map is instantiated at runtime from a static conflict graph, the static conflict graph including the first transaction and the second transaction as nodes in the static conflict graph, and the potential conflict as an edge in the static conflict graph.
17. The computer system of claim 16 , further comprising the memory in communication with the at least one processor, the memory including logic encoded in one or more tangible media for execution and when executed operable to map a counter value to corresponding shared locations, the counter value having been obtained from the static conflict graph.
18. The computer system of claim 15 , wherein the first transaction and the second transaction include at least one of a variable, a thread, or a function.
19. The computer system of claim 15 , wherein the system resource includes memory.
20. The computer system of claim 15 , further comprising the memory in communication with the at least one processor, the memory including logic encoded in one or more tangible media for execution and when executed operable to identify the potential conflict through a change in a counter value relative to a previous counter value, the counter used to access an address of a potentially conflicting shared resource as stored in the conflict hash map, this address used to query the read set hash map and validate only entries found in the read set hash map.