Dynamic circular work-stealing deque
View Patent ↗A deque of a local process in a memory work-stealing implementation may use one or more data structures to perform work. If the local process attempts to add a new value to its deque's circular array when the data structure is full (i.e., an overflow condition occurs), the contents of the data structure are copied to a larger allocated circular array (e.g., a circular array of greater size than the original circular array). The entries in the original, smaller-sized circular array are copied to positions in the now-active, larger-sized circular array, and the system is configured to work with the newly activated circular array. By this technique, the local process is thus provided with space to add the new value.
1. A method of executing threads comprising:
obtaining a first circular array local to a first process, wherein the first circular array is associated with a first minimum bottom value and stores a plurality of thread references;
invoking a first push operation to add a first thread reference to the first circular array, wherein the first push operation triggers an overflow condition associated with the first circular array;
allocating a second circular array exceeding a size of the first circular array, wherein the second circular array is associated with a shrink operation and a second minimum bottom value;
copying the plurality of thread references from the first circular array to the second circular array;
adding the first thread reference to the second circular array;
invoking a first pop operation to remove a second thread reference from the second circular array;
invoking the shrink operation after invoking the first pop operation to activate the first circular array, wherein invoking the shrink operation comprises copying a third thread reference with an index value exceeding the second minimum bottom value from the second circular array to the first circular array; and
executing a thread referenced by the second thread reference.
2. The method of claim 1 , wherein invoking the shrink operation further comprises:
switching an array pointer from referencing the second circular array to referencing the first circular array.
3. The method of claim 1 , wherein a copy of a fourth thread reference stored in the second circular array having an index value less than the second minimum bottom value is stored in the first circular array prior to copying the third thread reference.
4. The method of claim 1 , further comprising:
invoking a second push operation associated with the first circular array after invoking the shrink operation, wherein the second push operation triggers the overflow condition;
copying a fourth thread reference with an index value exceeding the first minimum bottom value from the first circular array to the second circular array; and
activating the second circular array.
5. The method of claim 4 , wherein a copy of a fifth thread reference stored in the first circular array having an index value less than the first minimum bottom value is stored in the second circular array prior to copying the fourth thread reference.
6. The method of claim 1 , wherein the first circular array, the second circular array, and the array pointer are associated with a deque local to the first process.
7. The method of claim 1 , wherein the first circular array and the second circular array are associated with a shared plurality of buffers.
8. The method of claim 1 , further comprising:
invoking a second pop operation on a top of at least one circular array selected from a group consisting of the first circular array and the second circular array, wherein the second pop operation is invoked by a second process.
9. The method of claim 1 , wherein the first push operation is performed on a bottom of the first circular array.
10. The method of claim 1 , wherein the first pop operation is performed on a bottom of the second circular array.
11. An apparatus for executing threads comprising:
means for obtaining a first circular array local to a first process, wherein the first circular array stores a plurality of thread references and wherein the first circular array is associated with a first minimum bottom value;
means for invoking a first push operation to add a first thread reference to the first circular array, wherein the first push operation triggers an overflow condition associated with the first circular array;
means for allocating a second circular array exceeding a size of the first circular array, wherein the second circular array is associated with a shrink operation and a second minimum bottom value;
means for copying the plurality of thread references from the first circular array to the second circular array;
means for adding the first thread reference to the second circular array;
means for invoking a first pop operation to remove a second thread reference from the second circular array;
means for invoking the shrink operation after invoking the first pop operation to activate the first circular array, wherein invoking the shrink operation comprises copying a third thread reference with an index value exceeding the second minimum bottom value from the second circular array to the first circular array; and
means for executing a thread referenced by the second thread reference.
12. The apparatus of claim 11 , wherein a copy of a fourth thread reference stored in the second circular array having an index value less than the second minimum bottom value is stored in the first circular array prior to copying the third thread reference.
13. The apparatus of claim 11 , further comprising:
means for invoking a second push operation associated with the first circular array after activating the first circular array, wherein the second push operation triggers the overflow condition;
means for copying a fourth thread reference with an index value exceeding the first minimum bottom value from the first circular array to the second circular array; and
means for activating the second circular array.
14. The method of claim 13 , wherein a copy of a fifth thread reference stored in the first circular array having an index value less than the first minimum bottom value is stored in the second circular array prior to copying the fourth thread reference.