Loop thread order execution control of a multi-threaded, self-scheduling reconfigurable computing fabric
Representative apparatus, method, and system embodiments are disclosed for configurable computing. A representative system includes an interconnection network; a processor; and a plurality of configurable circuit clusters. Each configurable circuit cluster includes a plurality of configurable circuits arranged in an array; a synchronous network coupled to each configurable circuit of the array; and an asynchronous packet network coupled to each configurable circuit of the array. A representative configurable circuit includes a configurable computation circuit and a configuration memory having a first, instruction memory storing a plurality of data path configuration instructions to configure a data path of the configurable computation circuit; and a second, instruction and instruction index memory storing a plurality of spoke instructions and data path configuration instruction indices for selection of a master synchronous input, a current data path configuration instruction, and a next data path configuration instruction for a next configurable computation circuit.
1. A configurable circuit, comprising:
a configurable computation circuit;
a configuration memory circuit coupled to the configurable computation circuit; and
a control circuit coupled to the configurable computation circuit, the control circuit comprising:
a plurality of control registers configured to store a completion table having a plurality of thread identifiers, and for each thread identifier of the plurality of thread identifiers, having a corresponding data completion count and further having a next thread identifier identifying a next thread for execution or having an identification of a last iteration; and
a thread control circuit configured to self-schedule and queue a selected thread for execution when, for the thread identifier for the selected thread, the corresponding data completion count indicates completion of any data dependencies and the thread identifier for the selected thread is identified as the next thread for execution.
2. The configurable circuit of claim 1 , wherein the plurality of control registers are further configured to store, in the completion table, a loop count of an active number of loop threads.
3. The configurable circuit of claim 1 , wherein the plurality of control registers are further configured to store, in the completion table, an iteration count and an identification of a first iteration, and wherein the thread control circuit is further configured to self-schedule and queue a selected thread for execution when, for the thread identifier for the selected thread, the corresponding data completion count indicates completion of any data dependencies and the thread identifier for the selected thread is identified as the first iteration for execution.
4. The configurable circuit of claim 1 , wherein the configurable circuit further comprises:
a plurality of synchronous network inputs coupled to the configurable computation circuit; and
a plurality of synchronous network outputs coupled to the configurable computation circuit.
5. The configurable circuit of claim 4 , wherein the configuration memory circuit comprises:
a first instruction memory configured to store a first plurality of data path configuration instructions to configure a data path of the configurable computation circuit; and
a second instruction memory configured to store a second plurality of configuration instructions or instruction indices for selection of a current data path configuration instruction of the first plurality of data path configuration instructions from the first instruction memory, for selection of a master synchronous network input of the plurality of synchronous network inputs for receipt of the current data path configuration instruction or instruction index from another, different configurable circuit, and for selection of a next data path configuration instruction or instruction index for output to the master synchronous network input of a next configurable circuit.
6. The configurable circuit of claim 5 , wherein the configurable circuit further comprises:
a conditional logic circuit coupled to the configurable computation circuit, the conditional logic circuit configured to modify the next data path configuration instruction or instruction index, depending upon an output from the configurable computation circuit, to form and output a modified next data path configuration instruction or instruction index to the master synchronous input of the next configurable circuit.
7. The configurable circuit of claim 5 , wherein the plurality of synchronous network outputs are directly coupled through a synchronous network to the plurality of synchronous network inputs of adjacent configurable circuits of an array of a plurality of configurable circuits, wherein a first plurality of configurable circuits of the array of the plurality of configurable circuits are coupled in series in a first predetermined sequence through the synchronous network to form a first synchronous domain; and wherein a second plurality of configurable circuits of the array of the plurality of configurable circuits are coupled in series in a second predetermined sequence through the synchronous network to form a second synchronous domain.
8. The configurable circuit of claim 7 , wherein the first synchronous domain is configured to generate a continuation message to the second synchronous domain transmitted through an asynchronous packet network and wherein the second synchronous domain is configured to generate a completion message to the first synchronous domain transmitted through the asynchronous packet network.
9. The configurable circuit of claim 8 , wherein the corresponding data completion count indicates a corresponding predetermined number of completion messages to be received, for each selected thread of the plurality of threads, prior to execution of the selected thread.
10. The configurable circuit of claim 8 , wherein the plurality of control registers are further configured to store, in the completion table, a loop count of an active number of loop threads, and wherein in response to receipt of an asynchronous fabric message returning a thread identifier to a thread identifier pool, the control circuit is further configured to decrement the loop count and, when the loop count reaches zero, to transmit the completion message.
11. The configurable circuit of claim 1 , wherein the thread control circuit is further configured to self-schedule and queue a plurality of different threads for execution upon a predetermined cadence when, for the thread identifier of each selected thread of the plurality of different threads, of the plurality of thread identifiers, the corresponding data completion count has decremented to zero to indicate the completion of any data dependencies.
12. The configurable circuit of claim 1 , wherein the thread control circuit further comprises:
a run queue configured to store one or more thread identifiers for one or more threads which are ready to execute;
a continuation queue configured to store one or more thread identifiers for threads having corresponding data completion counts allowing execution or configured to store threads without an assigned thread identifier; and
a reenter queue configured to store one or more thread identifiers for threads having corresponding data completion counts allowing execution to provide for continuing execution of the threads in the reenter queue upon a predetermined cadence by moving the threads in the reenter queue into the run queue ahead of any threads in the continuation queue.
13. A plurality of configurable circuits arranged in an array, each configurable circuit, of the plurality of configurable circuits, comprising:
a configurable computation circuit;
a configuration memory circuit coupled to the configurable computation circuit; and
a control circuit coupled to the configurable computation circuit, the control circuit comprising:
a plurality of control registers configured to store a completion table having an iteration count, having an identification of a first iteration, having an identification of a last iteration, having a plurality of thread identifiers and, for each thread identifier of the plurality of thread identifiers, having a corresponding data completion count and further having a next thread identifier identifying a next thread for execution or the identification of the last iteration; and
a thread control circuit configured to self-schedule and queue a selected thread for execution when, for the thread identifier for the selected thread, the corresponding data completion count indicates completion of any data dependencies and the thread identifier for the selected thread is identified as the first iteration or identified as the next thread for execution.
14. The configurable circuit of claim 13 , wherein the configurable circuit further comprises:
a plurality of synchronous network inputs coupled to the configurable computation circuit; and
a plurality of synchronous network outputs coupled to the configurable computation circuit.
15. The configurable circuit of claim 14 , wherein the configuration memory circuit comprises:
a first instruction memory configured to store a first plurality of data path configuration instructions to configure a data path of the configurable computation circuit; and
a second instruction memory configured to store a second plurality of configuration instructions or instruction indices for selection of a current data path configuration instruction of the first plurality of data path configuration instructions from the first instruction memory, for selection of a master synchronous network input of the plurality of synchronous network inputs for receipt of the current data path configuration instruction or instruction index from another, different configurable circuit, and for selection of a next data path configuration instruction or instruction index for output to the master synchronous network input of a next configurable circuit.
16. The configurable circuit of claim 15 , wherein the configurable circuit further comprises:
a conditional logic circuit coupled to the configurable computation circuit, the conditional logic circuit configured to modify the next data path configuration instruction or instruction index, depending upon an output from the configurable computation circuit, to form and output a modified next data path configuration instruction or instruction index to the master synchronous input of the next configurable circuit.
17. The configurable circuit of claim 14 , wherein the plurality of synchronous network outputs are directly coupled through a synchronous network to the plurality of synchronous network inputs of adjacent configurable circuits of an array of a plurality of configurable circuits; wherein a first plurality of configurable circuits of the array of the plurality of configurable circuits are coupled in series in a first predetermined sequence through the synchronous network to form a first synchronous domain; wherein a second plurality of configurable circuits of the array of the plurality of configurable circuits are coupled in series in a second predetermined sequence through the synchronous network to form a second synchronous domain; wherein the first synchronous domain is configured to generate a continuation message to the second synchronous domain transmitted through an asynchronous packet network and wherein the second synchronous domain is configured to generate a completion message to the first synchronous domain transmitted through the asynchronous packet network.
18. The configurable circuit of claim 17 , wherein the corresponding data completion count indicates a corresponding predetermined number of completion messages to be received, for each selected thread of the plurality of threads, prior to execution of the selected thread; and wherein the plurality of control registers are further configured to store, in the completion table, a loop count of an active number of loop threads, and wherein in response to receipt of an asynchronous fabric message returning a thread identifier to a thread identifier pool, the control circuit is further configured to decrement the loop count and, when the loop count reaches zero, to transmit the completion message.
19. The configurable circuit of claim 13 , wherein the plurality of control registers further store, in the completion table, a plurality of types of thread identifiers, with each type of thread identifier indicating a loop level for loop and nested loop execution.
20. A configurable circuit, comprising:
a configurable computation circuit;
a plurality of synchronous network inputs coupled to the configurable computation circuit;
a plurality of synchronous network outputs coupled to the configurable computation circuit; and
a configuration memory coupled to the configurable computation circuit, the configuration memory comprising:
a first instruction memory configured to store a first plurality of data path configuration instructions to configure a data path of the configurable computation circuit; and
a second instruction memory configured to store a second plurality data path configuration instructions or instruction indices for selection of a current data path configuration instruction from the first instruction memory for the configurable computation circuit and for selection of a master synchronous network input of the plurality of synchronous network inputs for receipt of the current data path configuration instruction; and
a control circuit coupled to the configurable computation circuit, the control circuit comprising:
a plurality of control registers configured to store a completion table having a plurality of thread identifiers, having an identification of a first iteration, having an identification of a last iteration, and for each thread identifier of the plurality of thread identifiers, having a corresponding data completion count and further having a next thread identifier identifying a next thread for execution or having the identification of the last iteration; and
a thread control circuit configured to self-schedule and queue a selected thread for execution when, for the thread identifier for the selected thread, the corresponding data completion count indicates completion of any data dependencies and the thread identifier for the selected thread is identified as the first iteration or identified as the next thread for execution.