Work Stealing in Heterogeneous Computing Systems

Abstract

A work stealer apparatus includes a determination module. The determination module is to determine to steal work from a first hardware computation unit of a first type for a second hardware computation unit of a second type that is different than the first type. The work is to be queued in a first work queue, which is to correspond to the first hardware computation unit, and which is to be stored in a shared memory that is to be shared by the first and second hardware computation units. A synchronized work stealer module is to steal the work through a synchronized memory access to the first work queue. The synchronized memory access is to be synchronized relative to memory accesses to the first work queue from the first hardware computation unit.

1 - 25 . (canceled) 
     
     
         26 . A work stealer apparatus comprising:
 a determination module to determine to steal work from a first hardware computation unit of a first type for a second hardware computation unit of a second type that is to be different than the first type, wherein the work is to be queued in a first work queue, which is to correspond to the first hardware computation unit, and which is to be stored in a shared memory that is to be shared by the first and second hardware computation units; and   a synchronized work stealer module to steal the work through a synchronized memory access to the first work queue, the synchronized memory access to be synchronized relative to memory accesses to the first work queue from the first hardware computation unit.   
     
     
         27 . The apparatus of  claim 26 , wherein the synchronized work stealer module is to add the work to a second work queue, which is to correspond to the second hardware computation unit, and which is to be stored in the shared memory, and wherein the second type is more special-purpose than the first type. 
     
     
         28 . The apparatus of  claim 26 , wherein the synchronized work stealer module is to steal the work through the synchronized memory access that is to include an atomic operation to be performed on the first work queue. 
     
     
         29 . The apparatus of  claim 28 , wherein the atomic operation comprises one of a read-modify-write operation, a compare-and-swap operation, a compare-and-exchange operation, a test-and-set operation, a compare-and-set operation, and a load-link/store-conditional operation. 
     
     
         30 . The apparatus of  claim 28 , wherein the atomic operation comprises an Open Computing Language (OpenCL) atomic operation. 
     
     
         31 . The apparatus of  claim 28 , wherein the synchronized work stealer module is to steal the work through a CUDA synchronized memory access. 
     
     
         32 . The apparatus of  claim 26 , further comprising a second determination module to determine to steal a second work from the second hardware computation unit for the first hardware computation unit, wherein the second work is to be queued in a second work queue, which is to correspond to the second hardware computation unit, and which is to be stored in the shared memory. 
     
     
         33 . The apparatus of  claim 32 , further comprising a second synchronized work stealer module to steal the second work through a second synchronized memory access to the second work queue from the first hardware computation unit, the second synchronized memory access to be synchronized relative to memory accesses to the second work queue from the second hardware computation unit. 
     
     
         34 . The apparatus of  claim 26 , wherein the determination module is to determine to steal the work when a second work queue, which is to correspond to the second hardware computation unit, and which is to be stored the shared memory, is to be one of empty and filled below a threshold level. 
     
     
         35 . The apparatus of  claim 26 , wherein the first hardware computation unit is to comprise one selected from a general-purpose processor and a central processing unit (CPU), and wherein the second hardware computation unit is to comprise one selected from a graphics processor, a hardware accelerator device, a cryptographic processor, a communications processor, a network processor, a special-purpose processor, a special-purpose core, a highly-parallel special-purpose hardware, a digital signal processor (DSP), and a field programmable gate array (FPGA). 
     
     
         36 . The apparatus of  claim 35 , wherein the first hardware computation unit is to comprise the CPU, and wherein the second hardware computation unit is to comprise the graphics processor which is selected from a graphics processing unit (GPU) and an integrated graphics core. 
     
     
         37 . A method in a heterogeneous computing system comprising:
 determining to steal work from a first hardware computation unit of a first type for a second hardware computation unit of a second, different type that is more special-purpose than the first type, wherein the work is queued in a first work queue which corresponds to the first hardware computation unit and which is stored a shared memory that is shared by the first and second hardware computation units; and   stealing the work including performing a synchronized memory access to the first work queue stored in the shared memory that is synchronized relative to memory accesses to the first work queue from the first hardware computation unit;   
     
     
         38 . The method of  claim 37 , further comprising adding the work to a second work queue, which corresponds to the second hardware computation unit, and which is also stored in the shared memory. 
     
     
         39 . The method of  claim 37 , wherein performing the synchronized memory access comprises performing an atomic operation. 
     
     
         40 . The method of  claim 39 , wherein performing the atomic operation comprises performing an atomic operation selected from a read-modify-write operation, a compare-and-swap operation, a compare-and-exchange operation, a test-and-set operation, a compare-and-set operation, and a load-link/store-conditional operation. 
     
     
         41 . The method of  claim 39 , wherein performing the atomic operation comprises performing an Open Computing Language (OpenCL) atomic operation. 
     
     
         42 . The method of  claim 37 , further comprising determining to steal a second work and stealing the second work from the second hardware computation unit for the first hardware computation unit, wherein the second work is queued in a second work queue which corresponds to the second hardware computation unit and which is stored in the shared memory. 
     
     
         43 . The method of  claim 38 , wherein determining comprises determining to steal the work in response to determining that a second work queue which corresponds to the second hardware computation unit and which is stored the shared memory is one of empty and filled below a threshold level. 
     
     
         44 . The method of  claim 38 , wherein the first hardware computation unit is one selected from a general-purpose processor, a central processing unit (CPU), and a system on chip having multiple general-purpose cores, and wherein the second hardware computation unit is one selected from a graphics processor, a hardware accelerator device, a cryptographic processor, a communications processor, a network processor, a special-purpose processor, a special-purpose core, a special-purpose core on a system on chip, a highly-parallel special-purpose hardware, a digital signal processor (DSP), and a field programmable gate array (FPGA). 
     
     
         45 . The method of  claim 44 , wherein the first hardware computation unit comprises the CPU, and wherein the second hardware computation unit comprises the graphics processor which is selected from a graphics processing unit (GPU) and an integrated graphics core. 
     
     
         46 . A heterogeneous computer system comprising:
 an interconnect;   a first hardware computation unit of a first type coupled with the interconnect;   a second hardware computation unit of a second, different type coupled with the interconnect, the second type to be more special-purpose than the first type;   a dynamic random access memory (DRAM) coupled with the interconnect, the DRAM to include a shared memory that is to be shared by the first and second hardware computation units, the shared memory to include a first work queue to queue work for the first hardware computation unit and a second work queue to queue work for the second hardware computation unit; and   a work stealer apparatus to determine to steal and steal work from the first queue and add it to the second queue through a synchronized memory access to the first work queue, the synchronized memory access to be synchronized relative to memory accesses to the first work queue from the first hardware computation unit.   
     
     
         47 . The system of  claim 46 , wherein the work stealer apparatus is to steal the work through the synchronized memory access that is to include an atomic operation on the first work queue. 
     
     
         48 . The system of  claim 46 , further comprising a second work stealer apparatus to determine to steal and steal a second work from the second work queue and add it to the first work queue through a second synchronized memory access to the second work queue, the second synchronized memory access to be synchronized relative to memory accesses to the second work queue from the second hardware computation unit. 
     
     
         49 . One or more computer-readable storage medium storing instructions that, if executed by a machine, will cause the machine to perform operations including:
 determine to steal work from a first hardware computation unit of a first type for a second hardware computation unit of a second, different type that is to be more special-purpose than the first type, wherein the work is to be queued in a first work queue which is to corresponds to the first hardware computation unit and which is to be stored a shared memory that is to be shared by the first and second hardware computation units; and   steal the work through a synchronized memory access that is to be performed to the first work queue, the synchronized memory access to be synchronized relative to memory accesses to the first work queue from the first hardware computation unit.   
     
     
         50 . The computer-readable storage medium of  claim 49 , wherein the machine-readable storage medium further provides instructions that, if executed by the machine, will cause the machine to performing operations including:
 add the work to a second work queue, which is to correspond to the second hardware computation unit, and which is to be stored in the shared memory.