Termination detection for shared-memory parallel programs
View Patent ↗A “garbage collector” employed to reclaim memory dynamically allocated to data objects employs multiple execution threads to perform a parallel-execution operation and its garbage-collection cycle. A thread executes tasks that it selects from lists whose entries represent tasks dynamically identified during other tasks' performance. When a thread fails to find a task in one of these lists, it sets to an inactivity-indicating value a field associated with it in a global status word. It also determines whether any field associated with any of the other threads indicates activity. If not, the thread concludes that the parallel-execution operation has been completed. Otherwise, it returns to searching for further tasks to perform.
1. A computer system that employs a plurality of threads of execution to perform a parallel-execution operation in which the threads identify tasks dynamically and in which the computer system comprises:
A) a mechanism that associates a separate status-word field with each of the threads; and
B) a mechanism that operates the threads in a manner that each thread:
i) executes a task-finding routine to find tasks previously identified dynamically and performs tasks thereby found, with its associated status-word field containing a value indicating it is active, until the task-finding routine finds no more tasks;
ii) when the task-finding routine executed in step (i) finds no more tasks, sets the contents of its associated status-word field to a value indicating it is inactive;
iii) after completing step (ii) and while the status-word field associated with any other thread contains a value indicating that the other thread is active, continues to search for a task using the task-finding routine, and, if it finds one, sets its associated status-word field contents to a value indicating that it is active before attempting to execute a found task; and
iv) during step (iii) when none of the status-word fields associated with other threads contains a value indicating that an associated thread is active and no task has been found, terminates its performance of the parallel-execution operation.
2. A computer system as defined in claim 1 wherein the parallel-execution operation is a garbage-collection operation.
3. A computer system as defined in claim 1 wherein:
A) each thread has associated with it a respective work queue in which it places task identifiers of tasks that thread identifies dynamically;
B) the task-finding routine executed by that thread includes performing an initial search for a task identifiers in the work queue associated with that thread and, if that work queue contains no task identifiers that thread can claim thereafter performing a further search for a task identifier in at least one other task-storage location.
4. A computer system as defined in claim 3 wherein the parallel-execution operation is a garbage-collection operation.
5. A computer system as defined in claim 3 wherein the at least one other task-storage location includes at least one work queue associated with a thread other than the executing thread.
6. A computer system as defined in claim 5 wherein:
A) there is a size limit associated with each work queue;
B) when a given thread dynamically identifies a given task that would cause the number of task entries in the work queue associated with the given thread to exceed the size limit if a task identifier that identifies it were placed in that work queue, the given thread instead places that task identifier in an overflow list instead of in that work queue; and
C) the at least one other task-storage location includes at least one such over flow list.
7. A computer system as defined in claim 5 wherein the task-finding routine includes selecting in a random manner the at least one work queue associated with a thread other than the executing thread.
8. A computer system as defined in claim 5 wherein the further search includes repeatedly searching a work queue associated with a thread other than the executing thread until the executing thread thereby finds a task or has performed a number of repetitions equal to a repetition limit greater than one.
9. A computer system as defined in claim 8 wherein the task-finding routine includes selecting in a random manner the at least one work queue associated with a thread other than the executing thread.
10. A computer system as defined in claim 3 wherein:
A) there is a size limit associated with each work queue;
B) when a given thread dynamically identifies a given task that would cause the number of task entries in the work queue associated with the given thread to exceed the size limit if a task identifier that identifies it were placed in that work queue, the given thread instead places that task identifier in an overflow list instead of in that work queue; and
C) the at least one other task-storage location includes at least one such over flow list.
11. A computer system as defined in claim 1 wherein the contents of all of the status-word fields fit in a memory location accessible in a single machine instruction.
12. A computer system as defined in claim 11 wherein the parallel-execution operation is a garbage-collection operation.
13. A computer system as defined in claim 11 wherein each status-word field is a single-bit field.
14. A computer system as defined in claim 13 wherein each single-bit field contains a logic one to indicate that the associated thread is active and contains a logic zero to indicate that the associated thread is inactive.
15. For employing a plurality of threads of execution to perform a parallel-execution operation in which the threads identify tasks dynamically, a computer-implemented method comprising:
A) associating a separate status-word field with each of the threads; and
B) operating the threads in a manner that each thread:
i) executes a task-finding routine to find tasks previously identified dynamically and performs tasks thereby found, with its associated status-word field containing a value indicating it is active, until the task-finding routine finds no more tasks;
ii) when the task-finding routine executed in step (i) finds no more tasks, sets the contents of its associated status-word field to a value indicating it is inactive;
iii) after completing step (ii) and while the status-word field associated with any other thread contains a value indicating that the other thread is active, continues to search for a task using the task-finding routine, and, if it finds one, sets its associated status-word field contents to a value indicating that it is active before attempting to execute a found task; and
iv) during step (iii) when none of the status-word fields associated with other threads contains a value indicating that an associated thread is active and no task has been found, terminates its performance of the parallel-execution operation.
16. A method as defined in claim 15 wherein the parallel-execution operation is a garbage-collection operation.
17. A method as defined in claim 15 wherein:
A) each thread has associated with it a respective work queue in which it places task identifiers of tasks that thread identifies dynamically;
B) the task-finding routine executed by that thread includes performing an initial search for a task identifiers in the work queue associated with that thread and, if that work queue contains no task identifiers that thread can claim, thereafter performing a further search for a task identifier in at least one other task-storage location.
18. A method as defined in claim 17 wherein the parallel-execution operation is a garbage-collection operation.
19. A method as defined in claim 17 wherein the at least one other task-storage location includes at least one work queue associated with a thread other than the executing thread.
20. A method as defined in claim 19 wherein:
A) there is a size limit associated with each work queue;
B) when a given thread dynamically identifies a given task that would cause the number of task entries in the work queue associated with the given thread to exceed the size limit if a task identifier that identifies it were placed in that work queue, the given thread instead places that task identifier in an overflow list instead of in that work queue; and
C) the at least one other task-storage location includes at least one such over-flow list.
21. A method as defined in claim 19 wherein the task-finding routine includes selecting in a random manner the at least one work queue associated with a thread other than the executing thread.
22. A method as defined in claim 19 wherein the further search includes repeatedly searching a work queue associated with a thread other than the executing thread until the executing thread thereby finds a task or has performed a number of repetitions equal to a repetition limit greater than one.
23. A method as defined in claim 22 wherein the task-finding routine includes selecting in a random manner the at least one work queue associated with a thread other than the executing thread.
24. A method as defined in claim 17 wherein:
A) there is a size limit associated with each work queue;
B) when a given thread dynamically identifies a given task that would cause the number of task entries in the work queue associated with the given thread to exceed the size limit if a task identifier that identifies it were placed in that work queue, the given thread instead places that task identifier in an overflow list instead of in that work queue; and
C) the at least one other task-storage location includes at least one such over-flow list.
25. A method as defined in claim 15 wherein the contents of all of the status-word fields fit in a memory location accessible in a single machine instruction.
26. A method as defined in claim 25 wherein the parallel-execution operation is a garbage-collection operation.
27. A method as defined in claim 25 wherein each status-word field is a single-bit field.
28. A method as defined in claim 27 wherein each single-bit field contains a logic one to indicate that the associated thread is active and contains a logic zero to indicate that the associated thread is inactive.
29. A storage medium containing instructions readable by a computer system to configure the computer system to employ a plurality of threads of execution to perform a parallel-execution operation in which the threads identify tasks dynamically and in which the computer system comprises:
A) a mechanism that associates a separate status-word field with each of the threads; and
B) a mechanism that operates the threads in a manner that each thread:
i) executes a task-finding routine to find tasks previously identified dynamically and performs tasks thereby found, with its associated status-word field containing a value indicating it is active, until the task-finding routine finds no more tasks;
ii) when the task-finding routine executed in step (i) finds no more tasks, sets the contents of its associated status-word field to a value indicating it is inactive;
iii) after completing step (ii) and while the status-word field associated with any other thread contains a value indicating that the other thread is active, continues to search for a task using the task finding routine, and, if it finds one, sets its associated status-word field contents to a value indicating that it is active before attempting to execute a found task; and
iv) if none of the status-word fields associated with other threads contains a value indicating that an associated thread is active, terminates its performance of the parallel-execution operation.
30. A storage medium as defined in claim 29 wherein the parallel-execution operation is a garbage-collection operation.
31. A storage medium as defined in claim 29 wherein:
A) each thread has associated with it a respective work queue in which it places task identifiers of tasks that thread identifies dynamically;
B) the task-finding routine executed by that thread includes performing an initial search for a task identifiers in the work queue associated with that thread and, if that work queue contains no task identifiers that thread can claim, thereafter performing a further search for a task identifier in at least one other task-storage location.
32. A storage medium as defined in claim 31 wherein the parallel-execution execution operation is a garbage-collection operation.
33. A storage medium as defined in claim 31 wherein the at least one other task-storage location includes at least one work queue associated with a thread other than the executing thread.
34. A storage medium as defined in claim 33 wherein:
A) there is a size limit associated with each work queue;
B) when a given thread dynamically identifies a given task that would cause the number of task entries in the work queue associated with the given thread to exceed the size limit if a task identifier that identifies it were placed in that work queue, the given thread instead places that task identifier in an overflow list instead of in that work queue; and
C) the at least one other task-storage location includes at least one such over flow list.
35. A storage medium as defined in claim 33 wherein the task-finding routine includes selecting in a random manner the at least one work queue associated with a thread other than the executing thread.
36. A storage medium as defined in claim 33 wherein the further search includes repeatedly searching a work queue associated with a thread other than the executing thread until the executing thread thereby finds a task or has performed a number of repetitions equal to a repetition limit greater than one.
37. A storage medium as defined in claim 36 wherein the task-finding routine includes selecting in a random manner the at least one work queue associated with a thread other than the executing thread.
38. A storage medium as defined in claim 31 wherein:
A) there is a size limit associated with each work queue;
B) when a given thread dynamically identifies a given task that would cause the number of task entries in the work queue associated with the given thread to exceed the size limit if a task identifier that identifies it were placed in that work queue, the given thread instead places that task identifier in an overflow list instead of in that work queue; and
C) the at least one other task-storage location includes at least one such over flow list.
39. A storage medium as defined in claim 29 wherein the contents of all of the status-word fields fit in a memory location accessible in a single machine instruction.
40. A storage medium as defined in claim 39 wherein the parallel-execution operation is a garbage-collection operation.
41. A storage medium as defined in claim 39 wherein each status-word field is a single-bit field.
42. A storage medium as defined in claim 41 wherein each single-bit field contains a logic one to indicate that the associated thread is active and contains a logic zero to indicate that the associated thread is inactive.
43. A computer system that employs a plurality of threads of execution to perform a parallel-execution operation in which the threads identify tasks dynamically, the computer system including:
A) means for associating a separate status-word field with each of the threads; and
B) means for operating the threads in a manner that each thread:
i) executes a task-finding routine to find tasks previously identified dynamically and performs tasks thereby found, with its associated status-word field containing a value indicating it is active, until the task-finding routine finds no more tasks;
ii) when the task-finding routine executed in step (i) finds no more tasks, sets the contents of its associated status-word field to a value indicating it is inactive
iii) after completing step (ii) and while the status-word field associated with any other thread contains a value indicating that the other thread is active, continues to search for a task using the task-finding routine, and, if it finds one, sets the status-word field contents to the activity-indicating a value indicating that it is active before attempting to execute a found task; and
iv) during step (iii) when none of the status-word fields associated with other threads contains a value indicating that an associated thread is active and no task has been found, termiates its performance of the parallel-execution operation.