Loop execution control for a multi-threaded, self-scheduling reconfigurable computing fabric using a reenter queue
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, a corresponding data completion count; and
a thread control circuit configured to self-schedule and queue a plurality of computation threads for execution upon a predetermined cadence, the thread control circuit comprising:
a first queue configured to store one or more thread identifiers for one or more computation threads of the plurality of computation threads which are ready to execute;
a second queue configured to store one or more computation threads of the plurality of computation threads having corresponding data completion counts allowing execution without an assigned thread identifier or configured to store one or more acquired thread identifiers for computation threads of the plurality of computation threads having completion counts allowing execution; and
a third queue configured to store one or more thread identifiers for computation threads of the plurality of computation threads having corresponding data completion counts allowing execution to provide for continuing execution of the computation threads in the third queue by moving the one or more thread identifiers or computation threads in the third queue into the first queue ahead of any thread identifiers for computation threads in the second queue.
2. The configurable circuit of claim 1 , wherein the plurality of control registers are further configured to store a thread identifier pool having a predetermined number of the plurality of thread identifiers, and the completion table further stores a loop count of an active number of loop threads.
3. The configurable circuit of claim 2 , wherein the third queue provides for continuing execution of the computation threads of the third queue when no thread identifier is available in the thread identifier pool for assignment to the one or more computation threads in the second queue.
4. The configurable circuit of claim 2 , wherein the thread control circuit is further configured, in response to receipt of an asynchronous packet network message returning a thread identifier of the plurality of thread identifiers to the thread identifier pool, to decrement the loop count and, when the loop count reaches zero, to transmit an asynchronous packet network completion message.
5. The configurable circuit of claim 1 , wherein upon completion of execution of a computation thread from the third queue, the thread identifier for the completed computation thread is available for assignment to a computation thread of the second queue.
6. The configurable circuit of claim 1 , wherein any computation thread in the third queue is executed prior to execution of any computation thread in the second queue which has an acquired thread identifier.
7. The configurable circuit of claim 1 , wherein the thread control circuit further comprises:
a fourth queue, wherein any computation thread having a thread identifier in the fourth queue is executed prior to execution of any computation thread having a thread identifier in the second queue or in the third queue.
8. The configurable circuit of claim 1 , wherein the plurality of control registers are further configured to store, in the completion table, an iteration count, an identification of a first iteration, an identification of a last iteration, and for each thread identifier for a current computation thread, further configured to store a thread identifier identifying a next computation thread or the identification of the last iteration.
9. The configurable circuit of claim 8 , wherein the thread control circuit is further configured to queue a selected computation thread for execution when, for the thread identifier for the selected computation thread, the corresponding data completion count indicates completion of any data dependencies and the thread identifier for the selected computation thread is identified as the next computation thread or the first iteration.
10. The configurable circuit of claim 1 , wherein the thread control circuit is further configured to queue a computation thread for execution when, for its thread identifier, the corresponding data completion count indicates completion of any data dependencies.
11. The configurable circuit of claim 1 , wherein the corresponding data completion count indicates a predetermined number of completion messages to be received, for a selected computation thread of a plurality of computation threads, prior to execution of the selected computation thread.
12. The configurable circuit of claim 1 , wherein the second queue is configured to allocate an available thread identifier, of the plurality of thread identifiers, to a selected computation thread of the plurality of computation threads in the second queue.
13. 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 and directly coupled to the plurality of synchronous network inputs of adjacent configurable circuits to form a synchronous network.
14. The configurable circuit of claim 13 , 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 data path 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 configurable circuit, and for selection of a next data path configuration instruction or instruction index for a next configurable computation circuit for output to the master synchronous network input of a next configurable circuit.
15. The configurable circuit of claim 14 , further comprising:
a conditional logic circuit coupled to the configurable computation circuit, wherein depending upon an output from the configurable computation circuit, the conditional logic circuit is configured to modify the next data path configuration instruction or next data path configuration instruction index provided to the master synchronous input of the next configurable computation circuit.
16. 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, wherein the plurality of control registers are configured to store a completion table having a plurality of thread identifiers for a plurality of computation threads and, for each thread identifier of the plurality of thread identifiers, further having a corresponding data completion count; and
a thread control circuit configured to self-schedule and queue a selected computation thread for execution when, for the thread identifier for the selected computation thread, the corresponding data completion count indicates completion of any data dependencies and the thread identifier for the selected computation thread is identified as a first or next computation thread for execution, wherein the thread control circuit further comprises:
a first queue configured to store one or more thread identifiers for one or more computation threads of the plurality of computation threads which are ready to execute;
a second queue configured to store one or more computation threads of the plurality of computation threads having corresponding data completion counts allowing execution without an assigned thread identifier and configured to store one or more thread identifiers for computation threads of the plurality of computation threads having completion counts allowing execution; and
a third queue configured to store one or more thread identifiers for computation threads of the plurality of computation threads having completion counts allowing execution to provide for continuing execution of the computation threads in the third queue by moving the one or more thread identifiers for the computation threads in the third queue into the first queue ahead of any one or more thread identifiers for computation threads in the second queue.
17. The configurable circuit of claim 16 , further comprising:
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 and directly coupled to the plurality of synchronous network inputs of adjacent configurable circuits to form a synchronous network;
and 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 data path 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 an adjacent 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.
18. The configurable circuit of claim 16 , wherein upon completion of execution of a computation thread from the third queue, the thread identifier for the completed computation thread is available for assignment to another computation thread.
19. The configurable circuit of claim 16 , wherein the thread control circuit further comprises a fourth queue, wherein any computation thread having a thread identifier in the fourth queue is executed prior to execution of any computation thread having a thread identifier in the second queue or in the third queue.
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 circuit coupled to the configurable computation circuit, to the plurality of synchronous network inputs, and to the plurality of synchronous network outputs, 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 of data path 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 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 or instruction index;
and
a control circuit coupled to the configurable computation circuit, the control circuit comprising:
a plurality of control registers, wherein the plurality of control registers are 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
a thread control circuit configured to self-schedule and queue for execution a selected computation thread, of a plurality of computation threads, when the corresponding data completion count for the thread identifier for the selected computation thread indicates completion of any data dependencies, the thread control circuit further comprising:
a first queue configured to store one or more thread identifiers for one or more computation threads which are ready to execute;
a second queue configured to store computation threads having corresponding data completion counts allowing execution without an assigned thread identifier and configured to store one or more thread identifiers for computation threads of the plurality of computation threads having completion counts allowing execution; and
a third queue configured to store one or more thread identifiers for computation threads having completion counts allowing execution to provide for continuing execution of the computation threads of the third queue by moving the thread identifiers for computation threads in the third queue into the first queue ahead of any thread identifiers for computation threads in the second queue.