GPU support for garbage collection

1. A processing node comprising:

a general-purpose central processing unit (CPU);

a special processing unit (SPU); and

a memory;

wherein the CPU is configured to:

store an indication corresponding to a portion of the memory, in response to detecting a data object stored in the portion has been modified; and

send a notification to the SPU responsive to detecting a garbage collection start condition is satisfied, the notification including the stored indication and base address of a region of the memory corresponding to the portion;

wherein in response to receiving the notification from the CPU, the SPU is configured to compute a plurality of root addresses, each root address corresponding to a stored indication, and send the computed root addresses to the CPU to be used by a garbage collection algorithm to identify reachable data objects in one or more predetermined collectable regions, wherein the one or more predetermined collectable regions are youngest regions of the plurality of regions.

2. The processing node as recited in claim 1 ,

wherein the CPU is further configured to:

divide the memory into a plurality of regions, each region comprising a plurality of sub-regions, said portion corresponding to one of said sub-regions.

3. The processing node as recited in claim 1 , wherein the CPU is further configured to store an indication corresponding to a sub-region of the plurality of sub-regions responsive to detecting a data object stored in the sub-region comprises a pointer value that points to one of the one or more predetermined collectable regions.

4. The processing node as recited in claim 1 , wherein the SPU is further configured to:

read in parallel two or more stored indications to locate two or more corresponding sub-regions; and

compute in parallel, for each of the two or more located sub-regions, one root address based on a corresponding base address.

5. The processing node as recited in claim 4 , wherein the SPU comprises a single instruction multiple data (SIMD) parallel architecture.

6. The processing node as recited in claim 4 , wherein the SPU computes said plurality of root addresses without a pause that halts execution of the CPU.

7. A method for garbage collection, the method comprising:

a general-purpose central processing unit (CPU) storing an indication corresponding to a portion of a memory, in response to detecting a data object stored in the portion has been modified;

sending a notification from the CPU to a special processing unit (SPU) responsive to detecting a garbage collection start condition is satisfied, the notification including the stored indication and base address of a region of the memory corresponding to the portion; and

the SPU computing a plurality of root addresses, each root address corresponding to a stored indication, and the SPU sending the computed root addresses to the CPU to be used by a garbage collection algorithm to identify reachable data objects in one or more predetermined collectable regions, wherein the one or more predetermined collectable regions are youngest regions of the plurality of regions.

8. The method as recited in claim 7 , further comprising:

the CPU dividing the memory into a plurality of regions, each region comprising a plurality of sub-regions, said portion corresponding to one of said sub-regions.

9. The method as recited in claim 8 , further comprising storing an indication corresponding to a sub-region of the plurality of sub-regions responsive to detecting a data object stored in the sub-region comprises a pointer value that points to one of the one or more predetermined collectable regions.

10. The method as recited in claim 7 , further comprising:

reading in parallel two or more stored indications to locate two or more corresponding sub-regions; and

computing in parallel, for each of the two or more located sub-regions, one root address based on a corresponding base address.

11. The method as recited in claim 7 , wherein the garbage collection start condition comprises a condition wherein a youngest sub-region has less free space than a predetermined threshold.

12. A computing system comprising:

a first processing node comprising a general purpose central processing unit (CPU);

a memory coupled to the first processing node; and

a second processing node comprising a special processing unit (SPU);

wherein the CPU is configured to:

store an indication corresponding to a portion of the memory, in response to detecting a data object stored in the portion has been modified; and

send a notification to the SPU responsive to detecting a garbage collection start condition is satisfied, the notification including the stored indication and base address of a region of the memory corresponding to the portion;

wherein in response to receiving the notification from the CPU, the SPU is configured to compute a plurality of root addresses, each root address corresponding to a stored indication, and send the computed root addresses to the CPU to be used by a garbage collection algorithm to identify reachable data objects in one or more predetermined collectable regions, wherein the one or more predetermined collectable regions are youngest regions of the plurality of regions.

13. The computing system as recited in claim 12 , wherein the CPU is further configured to:

divide the memory into a plurality of regions, each region comprising a plurality of sub-regions, said portion corresponding to one of said sub-regions.

14. The computing system as recited in claim 13 , wherein the CPU is further configured to store an indication corresponding to a sub-region of the plurality of sub-regions responsive to detecting a data object stored in the sub-region comprises a pointer value that points to one of the one or more predetermined collectable regions.