# US 2021/0243080 A1 · Efficient Loop Execution for a Multi-Threaded, Self-Scheduling Reconfigurable Computing Fabric

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0243080 A1
- Document ID: US20210243080A1
- Status: Published application
- Kind: A1
- Application number: 17/200,841
- Filed: 2021-03-14
- Published: 2021-08-05
- Earliest claimed: 2018-03-31
- Assignees: Micron Technology, Inc.
- Applicants: Micron Technology, Inc.
- Inventors: Tony M. Brewer
- Web page: https://patentgrep.com/patent/US20210243080A1

## CPC

- G06F 9/546: {Message passing systems or structures, e.g. queues}
- G06F 9/30036: {Instructions to perform operations on packed data, e.g. vector, tile or matrix operations}
- G06F 9/30038: {using a mask}
- G06F 9/3009: {Thread control instructions}
- G06F 9/3013: {according to data content, e.g. floating-point registers, address registers}
- G06F 9/3856: {Reordering of instructions, e.g. using queues or age tags}
- G06F 9/3871: {Asynchronous instruction pipeline, e.g. using handshake signals between stages}
- G06F 9/45558: {Hypervisor-specific management and integration aspects}
- G06F 9/467: {Transactional memory (G06F9/528 takes precedence)}
- G06F 9/52: Program synchronisation; Mutual exclusion, e.g. by means of semaphores
- G06F 15/17325: {Synchronisation; Hardware support therefor (intertask synchronisation G06F9/52)}
- G06F 15/7825: {Globally asynchronous, locally synchronous, e.g. network on chip}
- G06F 15/7867: {with reconfigurable architecture}
- H04L 41/0816: the condition being an adaptation, e.g. in response to network events
- H04L 45/02: Topology update or discovery
- H04L 47/625: for service slots or service orders
- H04L 49/3063: {Pipelined operation}
- G06F 2009/45595: {Network integration; Enabling network access in virtual machine instances}
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

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.

## Claims

### Claim 1

A configurable circuit, comprising:
a configurable computation circuit;
an asynchronous network input queue coupled to an asynchronous packet network;
an asynchronous network output queue coupled to the asynchronous packet network; and
a control circuit coupled to the configurable computation circuit, the control circuit comprising:
a plurality of control registers storing a completion table having a plurality of thread identifiers and a loop count of an active number of loop threads, the plurality of control registers further storing a thread identifier pool having a predetermined number of thread identifiers of the plurality of thread identifiers; and
a thread control circuit, wherein 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, the thread control circuit decrements the loop count and, when the loop count reaches zero, generates an asynchronous packet network completion message for transmission on the asynchronous packet network from the asynchronous network output queue.

### Claim 2 (depends on 1)

The configurable circuit of claim 1, wherein the configurable circuit further comprises:
a plurality of synchronous network inputs coupled to a synchronous network and to the configurable computation circuit; and.
a plurality of synchronous network outputs coupled to the synchronous network and to the configurable computation circuit.

### Claim 3 (depends on 2)

The configurable circuit of claim 2, wherein a plurality of the configurable circuits are arranged in an array, one or more configurable circuits of the plurality of configurable circuits of the array are coupled in series in a first predetermined sequence through the synchronous network to form a first synchronous domain; and wherein one or more configurable circuits of the plurality of configurable circuits of the array are coupled in series in a second predetermined sequence through the synchronous network to form a second synchronous domain.

### Claim 4 (depends on 3)

The configurable circuit of claim 3, wherein the first synchronous domain is adapted to generate a continuation message to the second synchronous domain transmitted through the asynchronous packet network.

### Claim 5 (depends on 3)

The configurable circuit of claim 3, wherein the second synchronous domain is adapted to generate a completion message to the first synchronous domain transmitted through the asynchronous packet network.

### Claim 6 (depends on 2)

The configurable circuit of claim 2, wherein the configurable circuit further comprises:
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 circuit comprising:
a first instruction memory storing a first plurality of data path configuration instructions to configure a data path of the configurable computation circuit; and
a second instruction memory storing a second plurality of data path configuration instructions or instruction indices for selection of a master synchronous network input of the plurality of synchronous network inputs for receipt of a current data path configuration instruction or instruction index from an adjacent configurable circuit.

### Claim 7 (depends on 6)

The configurable circuit of claim 6, wherein the second plurality of data path configuration instructions or instruction indices further comprises data path configuration instructions or instruction indices for selection of the current data path configuration instruction of the first plurality of data path configuration instructions from the first instruction memory for the configurable computation circuit.

### Claim 8 (depends on 6)

The configurable circuit of claim 6, wherein the second plurality of data path configuration instructions or instruction indices further comprises data path configuration instructions or instruction indices for selection of a next data path configuration instruction or instruction index for output to the master synchronous network input of a next configurable computation circuit.

### Claim 9 (depends on 1)

The configurable circuit of claim 1, wherein the plurality of control registers further store, in the completion table, a corresponding data completion count for each thread identifier, for one or more current execution threads, of the plurality of thread identifiers.

### Claim 10 (depends on 9)

The configurable circuit of claim 9, wherein the plurality of control registers further store, in the completion table, for each thread identifier for the one or more current execution threads, of the plurality of thread identifiers, an identification of a last iteration or another thread identifier identifying a next execution thread for execution following execution of the current execution thread.

### Claim 11 (depends on 10)

The configurable circuit of claim 10, wherein the thread control circuit queues a selected execution thread for execution when, for a thread identifier of the plurality of thread identifiers for the selected execution thread, the corresponding data completion count indicates completion of any data dependencies and the selected thread identifier is identified for the next execution thread.

### Claim 12 (depends on 10)

The configurable circuit of claim 10, wherein the data completion count indicates a predetermined number of completion messages to be received, per selected thread of a plurality of threads, prior to execution of the selected thread.

### Claim 13 (depends on 1)

The configurable circuit of claim 1, 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.

### Claim 14 (depends on 1)

The configurable circuit of claim 1, wherein the thread control circuit further comprises:
a run queue storing one or more thread identifiers for one or more threads which are ready to execute;
a continuation queue storing one or more thread identifiers for threads having completion counts allowing execution or storing threads without an assigned thread identifier; and
a reenter queue storing one or more thread identifiers for threads having 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.

### Claim 15

A configurable circuit, comprising:
a configurable computation circuit;
a plurality of synchronous network inputs coupled to a synchronous network and to the configurable computation circuit;
a plurality of synchronous network outputs coupled to the synchronous network and to the configurable computation circuit;
an asynchronous network input queue coupled to an asynchronous packet network;
an asynchronous network output queue coupled to the asynchronous packet network;
a configuration memory 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 storing a first plurality of data path configuration instructions to configure an internal data path of the configurable computation circuit; and
a second instruction memory storing a second plurality of data path configuration instructions or instruction indices for selection of a master synchronous network input of the plurality of synchronous network inputs for receipt of a current data path configuration instruction or instruction index from an adjacent configurable circuit; and
a control circuit coupled to the configurable computation circuit, the control circuit comprising:
a plurality of control registers storing a completion table having a plurality of thread identifiers and a loop count of an active number of loop threads, the plurality of control registers further storing a thread identifier pool having a predetermined number of thread identifiers of the plurality of thread identifiers; and
a thread control circuit, wherein 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, the thread control circuit decrements the loop count and, when the loop count reaches zero, generates an asynchronous packet network completion message for transmission on the asynchronous packet network from the asynchronous network output queue.

### Claim 16 (depends on 15)

The configurable circuit of claim 15, wherein the plurality of control registers further store, in the completion table, a corresponding data completion count for each thread identifier, for one or more current execution threads, of the plurality of thread identifiers.

### Claim 17 (depends on 16)

The configurable circuit of claim 16, wherein the plurality of control registers further store, in the completion table, for each thread identifier for the one or more current execution threads, of the plurality of thread identifiers, an identification of a last iteration or another thread identifier identifying a next execution thread for execution following execution of the current execution thread; and wherein the thread control circuit self-schedules and queues a selected execution thread for execution when, for a thread identifier of the plurality of thread identifiers for the selected execution thread, the corresponding data completion count indicates completion of any data dependencies and the selected thread identifier is identified for the next execution thread.

### Claim 18 (depends on 16)

The configurable circuit of claim 16, wherein the plurality of control registers further store, in the completion table, an iteration count and an identification of a first iteration.

### Claim 19 (depends on 15)

The configurable circuit of claim 15, wherein the second plurality of data path configuration instructions or instruction indices further comprises data path configuration instructions or instruction indices for selection of the 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 next data path configuration instruction or instruction index for output to the master synchronous network input of a next configurable computation circuit.

### Claim 20

A system comprising:
an interconnection network;
a processor coupled to the interconnection network;
a synchronous network;
an asynchronous packet network; and
a plurality of configurable circuits arranged in an array, each configurable circuit comprising:
a configurable computation circuit;
a plurality of synchronous network inputs coupled to the synchronous network and to the configurable computation circuit;
a plurality of synchronous network outputs coupled to the synchronous network and to the configurable computation circuit;
an asynchronous network input queue coupled to the asynchronous packet network;
an asynchronous network output queue coupled to the asynchronous packet network;
a control circuit coupled to the configurable computation circuit, the control circuit comprising:
a plurality of control registers storing a completion table having a plurality of thread identifiers, a corresponding data completion count for each thread identifier, for one or more current execution threads, of the plurality of thread identifiers, and a loop count of an active number of loop threads, the plurality of control registers further storing a thread identifier pool having a predetermined number of thread identifiers of the plurality of thread identifiers, and the plurality of control registers further storing, for each thread identifier for the one or more current execution threads, an identification of a last iteration or another thread identifier identifying a next execution thread for execution following execution of the current execution thread; and
a thread control circuit to self-schedule and queue a selected execution thread for execution when, for a thread identifier of the plurality of thread identifiers for the selected execution thread, the corresponding data completion count indicates completion of any data dependencies and the selected thread identifier is identified for the next execution thread, and wherein 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, the thread control circuit decrements the loop count and, when the loop count reaches zero, generates an asynchronous packet network completion message for transmission on the asynchronous packet network from the asynchronous network output queue.