Execution of data-parallel programs on coarse-grained reconfigurable architecture hardware

Abstract

A GPGPU-compatible architecture combines a coarse-grain reconfigurable fabric (CGRF) with a dynamic dataflow execution model to accelerate execution throughput of massively thread-parallel code. The CGRF distributes computation across a fabric of functional units. The compute operations are statically mapped to functional units, and an interconnect is configured to transfer values between functional units.

1 . A method of computing, comprising the steps of:
 providing an arrangement of processing units having interconnects therebetween;   statically mapping compute operations to respective processing units;   configuring the interconnects to transfer values between functional units based on connectivity requirements of the compute operations; and   associating instructions for execution of the compute operations with respective control tokens and thread identifiers, the instructions belonging to a plurality of threads and including a first instruction and a second instruction, wherein the thread identifier of the first instruction identifies a first thread and the thread identifier of the second instruction identifies a second thread;   pipelining the instructions through the arrangement responsively to the control tokens to the mapped processing units;   dynamically rescheduling an order of execution of the first instruction with respect to the second instruction in one of the mapped processing units; and   performing the compute operations responsively to the first instruction and the second instruction in the processing units in the rescheduled order of execution.   
     
     
         2 . The method according to  claim 1 , wherein rescheduling is performed when the first instruction is unable to be executed by the one mapped processing unit. 
     
     
         3 . The method according to  claim 1 , further comprising the steps of:
 representing the instructions as input tokens; and   performing variants of the compute operations in one of the processing units responsively to the input tokens to generate result tokens; and   transmitting the result tokens to another of the processing units.   
     
     
         4 . The method according to  claim 3 , wherein rescheduling is performed when the input tokens of the first instruction are not available to the one mapped processing unit. 
     
     
         5 . The method according to  claim 1 , wherein the arrangement comprises a plurality of cores, wherein pipelining is performed to respective cores, the method further comprising issuing control signals to processing units of the cores to cause the cores to process instances of the compute operations concurrently. 
     
     
         6 . The method according to  claim 1 , further comprising grouping the threads into epochs, wherein the step of rescheduling comprises deferring execution in the one mapped processing unit of a newly arrived instruction belonging to a thread of one of the epochs until execution of previously arrived instructions belonging to threads of others of the epochs has completed. 
     
     
         7 . The method according to  claim 1 , further comprising the steps of:
 performing first compute operations of the first thread in a set of functional units;   upon completion of first compute operations by members of the set of functional units transmitting respective enabling tokens from the members to enable a second compute operation in another functional unit; and   permitting the second compute operation of the first thread to be performed only after all the enabling tokens have been received by the other functional unit.   
     
     
         8 . The method according to  claim 7 , wherein the enabling tokens are control tokens. 
     
     
         9 . The method according to  claim 7 , wherein the enabling tokens are data tokens. 
     
     
         10 . The method according to  claim 1 , further comprising the steps of:
 performing first and second compute operations in one of the threads with first and second functional units, respectively;   transmitting a first enabling token from the first functional unit and a second enabling token from the second functional unit to a third functional unit; and   performing a third compute operation in the one thread only after receipt therein of the first enabling token and the second enabling token in the third functional unit.   
     
     
         11 . The method according to  claim 10 , wherein the first enabling token and the second enabling token are control tokens. 
     
     
         12 . The method according to  claim 10 , wherein the first enabling token and the second enabling token are data tokens. 
     
     
         13 . The method according to  claim 10 , further comprising:
 representing the one thread as a control data flow graph having a join node; and   configuring the third functional unit to effectuate the join node by executing a join operation in the one thread upon receipt of the first enabling token and the second enabling token.   
     
     
         14 . The method according to  claim 13 , wherein the control data flow graph has a split node, further comprising:
 configuring a fourth functional unit to effectuate the split node by executing a split operation in the one thread upon receipt of a result token of the third compute operation, wherein the split operation comprises transmitting respective commit tokens to fifth and sixth functional units; and   concurrently performing new compute operations of the one thread in the fifth and sixth functional units upon receipt of the commit tokens therein.   
     
     
         15 . The method according to  claim 1 , further comprising the steps of:
 representing one of the threads as a control data flow graph;   making a determination that in the control data flow graph one path therethrough is longer than another path;   responsively to the determination, introducing a delay node in the other path; and   delaying compute operations of the one thread that occur in the other path.   
     
     
         16 . The method according to  claim 15 , wherein introducing a delay node comprises:
 introducing delay slots into the control data flow graph by a compiler; and   equalizing a delay of different paths through the control data flow graph by adjusting numbers of the delay slots in the different paths.   
     
     
         17 . The method according to  claim 1 , further comprising the steps of:
 representing one of the threads as a control data flow graph;   providing a label node that collects the control tokens of diverging paths in the one thread;   using the label node to select one of the diverging paths for execution; and   transmitting poisoned control tokens to disable compute operations in the processing units that are represented by others of the diverging paths.   
     
     
         18 . A computing apparatus, comprising:
 at least one core of interconnected processing units configured to execute a plurality of threads, the core comprising compute units for executing computer instructions, load/store units, control units for executing control instructions, and special compute units for executing non-pipelined computing operations;   a switch in each of the processing units for configurably establishing connections to other processing units for transferring values from between the processing units across the connections; and   respective private memories in the processing units, the private memories comprising configuration registers that store token routing information, operands and opcodes, and further comprising reservation buffers for holding thread identifiers that are associated with in-flight data moving through the core, wherein the processing units are responsive to input tokens and control tokens, and are operative to transmit result tokens for use as the input tokens of other processing units via the connections, the processing units being operative to store state information and data pertaining to an incompletely executed compute operation while processing a new compute operation.   
     
     
         19 . The apparatus according to  claim 18 , wherein the load/store units are disposed on a periphery of the core. 
     
     
         20 . The apparatus according to  claim 18 , wherein the core comprises an internal grid of alternating columns of the compute units, and the control units. 
     
     
         21 . The apparatus according to  claim 18 , wherein the core comprises an internal grid comprising a checkerboard arrangement of the compute units, and the control units. 
     
     
         22 . The apparatus according to  claim 18 , wherein the control units comprise a first-in-first-out memory buffer for holding tokens of thread instructions to cause a delay in execution thereof by others of the processing units. 
     
     
         23 . The apparatus according to  claim 18 , wherein the switch is a crossbar switch. 
     
     
         24 . The apparatus according to  claim 18 , wherein the switch is operative to connect the processing unit thereof to selected ones of eight nearest neighboring processing units. 
     
     
         25 . The apparatus according to  claim 18 , wherein the switch is operative to connect the processing unit thereof to selected first processing units and to selected second processing units. 
     
     
         26 . The apparatus according to  claim 25 , wherein the selected first processing units are 8 nearest neighbors of the processing unit. 
     
     
         27 . The apparatus according to  claim 18 , wherein the reservation buffers of the load/store units are programmed to hold input tokens of incomplete compute operations while other compute operations are in progress therein. 
     
     
         28 . The apparatus according to  claim 18 , wherein the load/store units comprise epoch logic circuitry operative to recognize a grouping of the threads into epochs, and to cause the load/store units to defer execution of a newly arrived instruction belonging to a thread of one of the epochs until execution of previously arrived instructions belonging to threads of others of the epochs has completed. 
     
     
         29 . A computer program product, including a non-transitory computer-readable storage medium in which computer program instructions are stored, which instructions, when executed by a computer connected to an arrangement of processing units having interconnects therebetween cause the computer to perform the steps of;
 statically mapping compute operations to respective processing units;   configuring the interconnects according to requirements of the compute operations; and   associating process instructions that belong to a plurality of threads with respective control tokens and thread identifiers, the instructions including a first instruction and a second instruction, wherein the thread identifier of the first instruction identifies a first thread and the thread identifier of the second instruction identifies a second thread;   pipelining the process instructions through the arrangement responsively to the control tokens to the mapped processing units;   dynamically rescheduling an order of execution of the first instruction with respect to the second instruction in one of the mapped processing units; and   performing the compute operations responsively to the first instruction and the second instruction in the processing units in the rescheduled order of execution.   
     
     
         30 . The computer program product according to  claim 29 , wherein rescheduling is performed when the first instruction is unable to be executed by the one mapped processing unit. 
     
     
         31 . The computer program product according to  claim 29 , wherein the instructions further cause the computer to perform the steps of:
 representing the process instructions as input tokens; and   performing variants of the compute operations in one of the processing units responsively to the input tokens to generate result tokens; and   transmitting the result tokens to another of the processing units.   
     
     
         32 . The computer program product according to  claim 31 , wherein rescheduling is performed when the input tokens of the first instruction are not available to the one mapped processing unit. 
     
     
         33 . The computer program product according to  claim 29 , wherein the arrangement comprises a plurality of cores, wherein pipelining is performed to respective cores, the method further comprising issuing control signals to processing units of the cores to cause the cores to process instances of the compute operations concurrently. 
     
     
         34 . The computer program product according to  claim 29 , further comprising grouping the threads into epochs, wherein the step of rescheduling comprises deferring execution in the one mapped processing unit of a newly arrived instruction belonging to a thread of one of the epochs until execution of previously arrived instructions belonging to threads of others of the epochs has completed. 
     
     
         35 . The computer program product according to  claim 29 , further comprising the steps of:
 performing first compute operations of the first thread in a set of functional units;   upon completion of first compute operations by members of the set of functional units transmitting respective enable tokens from the members to another functional unit; and   permitting a second compute operation of the first thread to be performed only after all the enable tokens have been received by the other functional unit.   
     
     
         36 . The computer program product according to  claim 29 , further comprising the steps of:
 representing one of the threads as a control data flow graph;   making a determination that in the control data flow graph one path therethrough is longer than another path;   responsively to the determination, introducing a delay node in the other path; and   delaying compute operations of the one thread that occur in the other path.   
     
     
         37 . The computer program product according to  claim 29 , wherein the instructions further cause the computer to perform the steps of:
 representing one of the threads as a control data flow graph;   providing a label node that collects the control tokens of diverging paths in the one thread;   using the label node to select one of the diverging paths for execution; and   transmitting poisoned control tokens to disable compute operations in the processing units that are represented by others of the diverging paths.   
     
     
         38 . The computer program product according to  claim 37 , wherein the processing units that are represented by others of the diverging paths are load-store units.