Node-based representation of multi-threaded computing environment tasks, and node-based data race evaluation
A method for detecting race conditions in a concurrent processing environment is provided. The method comprises implementing a data structure configured for storing data related to at least one task executed in a concurrent processing computing environment, each task represented by a node in the data structure; and assigning to a node in the data structure at least one of a task number, a wait number, and a wait list; wherein the task number uniquely identifies the respective task, wherein the wait number is calculated based on a segment number of the respective task's parent node, and wherein the wait list comprises at least an ancestor's wait number. The method may further comprise monitoring a plurality of memory locations to determine if a first task accesses a first memory location, wherein said first memory location was previously accessed by a second task.
1. A computer-implemented method comprising:
processing a task in a multi-threaded computing environment, wherein the task includes multiple segments of code;
representing the task as a node of a data structure;
adding child nodes to the data structure to represent child tasks spawned by corresponding parent tasks;
associating each added child node with a wait number based on a segment number of a corresponding parent node;
associating each added child node with a corresponding wait list that includes a wait number of each of one or more lineal parent nodes of the added child node, wherein a lineal parent node corresponds to a task from which, or through which, a child task is spawned;
identifying first and second tasks that access a memory location; and
evaluating one or more of the following to determine whether the accesses to the memory location by the first and second tasks correspond to a data race to the memory location;
wait numbers associated with first and second nodes corresponding to the first and second tasks, and
wait lists associated with lineal parent nodes of the first and second nodes.
2. The method of claim 1 , wherein the evaluating includes:
determining that a race condition does not exist based at least in part on a determination that the wait numbers associated with the first and second nodes differ from one another.
3. The method of claim 1 , wherein the evaluating includes:
determining that a race condition does not exist when,
execution of at least one of the first and second tasks is complete, the first and second tasks are spawned from a same parent task, and
the wait numbers associated with the first and second nodes differ from one another.
4. The method of claim 1 , wherein the evaluating includes:
determining that a race condition does not exist based at least in part on a determination that the wait lists of the lineal parent nodes of the first and second nodes differ from one another.
5. The method of claim 1 , wherein the evaluating includes:
determining that a race condition does not exist when,
the first and second tasks are not spawned by a same parent task,
neither of the first and second nodes is a lineal parent node of the other of the first and second nodes, and
the wait lists associated with the lineal parent nodes of the first and second nodes differ from one another,
wherein the lineal parent nodes of the first and second nodes are child nodes of a same parent node.
6. The method of claim 1 , wherein maintaining of the data structure includes:
removing a node from the data structure when execution of a corresponding task is complete.
7. The method of claim 1 , wherein maintaining of the data structure includes:
identifying child nodes of a parent node for which execution of corresponding tasks are complete; and
combining the identified child nodes into a single child node when wait lists associated with the identified child nodes are identical to one another.
8. The method of claim 1 , wherein maintaining of the data structure includes:
identifying a node for which a corresponding task maintains exclusive access to the memory location until processing of the corresponding task and associated child tasks is complete; and
combining the identified node and corresponding child nodes into a single node.
9. A non-transitory computer readable medium encoded with a computer program, including instructions to cause a multi-threaded processor system to:
process a task in a multi-threaded computing environment, wherein the task includes multiple segments of code;
represent the task as a node of a data structure;
add child nodes to the data structure to represent child tasks spawned by corresponding parent tasks;
associate each added child node with a wait number based on a segment number of a corresponding parent node;
associate each added child node with a corresponding wait list that includes a wait number of each of one or more lineal parent nodes of the added child node, wherein a lineal parent node corresponds to a task from which, or through which, a child task is spawned;
identify first and second tasks that access a memory location; and
evaluate one or more of the following to determine whether the accesses to the memory location by the first and second tasks correspond to a data race to the memory location:
wait numbers associated with first and second nodes corresponding to the first and second tasks, and
wait lists associated with lineal parent nodes of the first and second nodes.
10. The computer readable medium of claim 9 , wherein the instructions include instructions to cause the multi-threaded processor system to:
determine that a race condition does not exist based at least in part on a determination that the wait numbers associated with the first and second nodes differ from one another.
11. The computer readable medium of claim 9 , wherein the instructions include instructions to cause the multi-threaded processor system to:
determine that a race condition does not exist when,
execution of at least one of the first and second tasks is complete,
the first and second tasks are spawned from a same parent task, and
the wait numbers associated with the first and second nodes differ from one another.
12. The computer readable medium of claim 9 , wherein the instructions include instructions to cause the multi-threaded processor system to:
determine that a race condition does not exist based at least in part on a determination that the wait lists of the lineal parent nodes of the first and second nodes differ from one another.
13. The computer readable medium of claim 9 , wherein the instructions include instructions to cause the multi-threaded processor system to:
determine that a race condition does not exist when,
the first and second tasks are not spawned by a same parent task,
neither of the first and second nodes is a lineal parent node of the other of the first and second nodes, and
the wait lists associated with the lineal parent nodes of the first and second nodes differ from one another,
wherein the lineal parent nodes of the first and second nodes are child nodes of a same parent node.
14. The computer readable medium of claim 9 , wherein the instructions include instructions to cause the multi-threaded processor system to:
remove a node from the data structure when execution of a corresponding task is complete.
15. The computer readable medium of claim 9 , wherein the instructions include instructions to cause the multi-threaded processor system to:
identify child nodes of a parent node for which execution of corresponding tasks are complete; and
combine the identified child nodes into a single child node when wait lists associated with the identified child nodes are identical to one another.
16. The computer readable medium of claim 9 , wherein the instructions include instructions to cause the multi-threaded processor system to:
identify a node for which a corresponding task maintains exclusive access to the memory location until processing of the corresponding task and associated child tasks is complete; and
combine the identified node and corresponding child nodes into a single node.
17. A system, comprising:
a multi-threaded processor system including memory;
a non-transitory computer readable medium encoded with a computer program, including instructions to cause the multi-threaded processor system to:
process a task in a multi-threaded computing environment, wherein the task includes multiple segments of code;
represent the task as a node of a data structure;
add child nodes to the data structure to represent child tasks spawned by corresponding parent tasks;
associate each added child node with a wait number based on a segment number of a corresponding parent node;
associate each added child node with a corresponding wait list that includes a wait number of each of one or more lineal parent nodes of the added child node, wherein a lineal parent node corresponds to a task from which, or through which, a child task is spawned;
identify first and second tasks that access a memory location; and
evaluate one or more of the following to determine whether the accesses to the memory location by the first and second tasks correspond to a data race to the memory location:
wait numbers associated with first and second nodes corresponding to the first and second tasks, and
wait lists associated with lineal parent nodes of the first and second nodes.
18. The system of claim 17 , wherein the instructions include instructions to cause the multi-threaded processor system to determine that a race condition does not exist when, execution of at least one of the first and second tasks is complete,
the first and second tasks are spawned from a same parent task, and
the wait numbers associated with the first and second nodes differ from one another.
19. The system of claim 17 , wherein the instructions include instructions to cause the multi-threaded processor system to determine that a race condition does not exist when,
the first and second tasks are not spawned by a same parent task,
neither of the first and second nodes is a lineal parent node of the other of the first and second nodes, and
the wait lists associated with the lineal parent nodes of the first and second nodes differ from one another,
wherein the lineal parent nodes of the first and second nodes are child nodes of a same parent node.
20. The system of claim 17 , wherein the instructions include instructions to cause the multi-threaded processor system to:
identify child nodes of a parent node for which execution of corresponding tasks are complete;
combine the identified child nodes into a single child node when wait lists associated with the identified child nodes are identical to one another;
identify a node for which a corresponding task maintains exclusive access to the memory location until processing of the corresponding task and associated child tasks is complete;
combine the identified node and corresponding child nodes into a single node; and
remove a node from the data structure when execution of a corresponding task is complete.