# US 11,030,146 B2 · Execution engine for executing single assignment programs with affine dependencies

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

- Number: US 11,030,146 B2
- Document ID: US11030146B2
- Status: Granted
- Kind: B2
- Application number: 16/372,069
- Filed: 2019-04-01
- Published: 2019-07-25
- Granted: 2021-06-08
- Earliest claimed: 2008-05-27
- Assignees: Stillwater Supercomputing, Inc.
- Applicants: Stillwater Supercomputing, Inc.
- Inventors: Erwinus Theodorus Leonardus Omtzigt
- Web page: https://patentgrep.com/patent/US11030146B2

## CPC

- G06F 15/825: {Dataflow computers}
- G06F 15/17381: {Two dimensional, e.g. mesh, torus}
- G06F 15/8023: {Two dimensional arrays, e.g. mesh, torus}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The execution engine is a new organization for a digital data processing apparatus, suitable for highly parallel execution of structured fine-grain parallel computations. The execution engine includes a memory for storing data and a domain flow program, a controller for requesting the domain flow program from the memory, and further for translating the program into programming information, a processor fabric for processing the domain flow programming information and a crossbar for sending tokens and the programming information to the processor fabric.

## Claims

### Claim 1

A computing device comprising:
a memory for storing data and a domain flow program;
a crossbar for sending data tokens and the domain flow programming information to a processor fabric, wherein the processor fabric comprises one or more processing elements that match data tokens in a domain flow program; and
one or more data streamers for sending data streams to the crossbar.

### Claim 2 (depends on 1)

The device of claim 1 wherein the one or more data streamers have page awareness so that caching is used to accumulate page coherent data for efficient writeback to DRAM or for efficient input stream generation from DRAM to fabric streams.

### Claim 3 (depends on 1)

The device of claim 1 wherein a data structure descriptor is used by the one or more data streamers to derive data streams to and from the memory.

### Claim 4 (depends on 3)

The device of claim 3 wherein for sparse matrices, index structures that use hierarchical blocks to enable n-bit indices are used to minimize memory bandwidth and maximize performance for a DRAM.

### Claim 5 (depends on 4)

The device of claim 4 wherein the n-bit indices comprise 8-bit indices.

### Claim 6 (depends on 1)

The device of claim 1 further comprising a controller configured for requesting the domain flow program including presenting a read request to a memory controller which translates the read request to a memory request and returns the data to the controller.

### Claim 7 (depends on 1)

The device of claim 1 wherein the crossbar is further configured for routing data streams to rows or columns in the processor fabric.

### Claim 8 (depends on 7)

The device of claim 7 wherein the processor fabric is further configured for producing output data streams.

### Claim 9 (depends on 8)

The device of claim 8 wherein the output data streams are written to the memory by traversing through the crossbar to the one or more data streamers that associate memory addresses to the data streams according to a data structure descriptor definition and whereupon the data streams are presented to a memory controller which writes the data streams into the memory.

### Claim 10 (depends on 9)

The device of claim 9 wherein the one or more data streamers are further configured for sending notifier events to the memory controller once the one or more data streamers identify completion of a computational task.

### Claim 11

A method comprising:
executing instructions on matching data tokens belonging to a same single assignment equation specified in a domain flow program; and
configuring a processor fabric comprising one or more processing elements to execute a single assignment program defined by a coupled set of affine recurrences equations based on programming information.

### Claim 12 (depends on 11)

The method of claim 11 further comprising utilizing data streamers that have page awareness so that caching is used to accumulate page coherent data for efficient writeback to DRAM or for efficient input stream generation from DRAM to fabric streams.

### Claim 13 (depends on 12)

The method of claim 12 wherein a data structure descriptor is used by the data streamers to derive data streams to and from a memory.

### Claim 14 (depends on 12)

The method of claim 12 wherein a data path between a sensor, a network or a device to the data streamers is optimized.

### Claim 15 (depends on 12)

The method of claim 12 wherein the data streamers utilize a multidimensional data stream, wherein the multidimensional data stream has more than two dimensions.

### Claim 16 (depends on 11)

The method of claim 11 wherein for sparse matrices, index structures are used to minimize memory bandwidth and maximize performance for a DRAM.

### Claim 17 (depends on 11)

The method of claim 11 further comprising pushing a write command from the processor fabric to a memory controller.

### Claim 18

A processor fabric for processing domain flow programming information comprising:
a first set of processing elements; and
a second set of processing elements which communicate with the first set of processing elements, wherein the first set of processing elements and/or the second set of processing elements match data tokens belonging to a same single assignment equation specified in a domain flow program, wherein the processor fabric is further configured for execution of fine-grain parallel algorithms.

### Claim 19 (depends on 18)

The processor fabric of claim 18 wherein the first set of processing elements and/or the second set of processing elements process an instruction set architecture configured for a specific class of algorithms.

### Claim 20 (depends on 19)

The processor fabric of claim 19 wherein the specific class of algorithms comprise hashing algorithms.

### Claim 21 (depends on 19)

The processor fabric of claim 19 wherein the specific class of algorithms comprise optimizations for interpolations and resampling.

### Claim 22 (depends on 18)

The processor fabric of claim 18 wherein the first set of processing elements and/or the second set of processing elements are further configured for receiving multidimensional data streams and producing output data streams.

### Claim 23 (depends on 22)

The processor fabric of claim 22 wherein the output data streams are written to a memory by traversing through a crossbar to data streamers that associate memory addresses to data streams according to a data structure descriptor definition and whereupon the data streams are presented to a memory controller which writes the data streams into the memory.

### Claim 24 (depends on 23)

The processor fabric of claim 23 wherein the data streamers are further configured for sending notifier events to the controller once the streamers identify completion of a computational task.

### Claim 25 (depends on 18)

The processor fabric of claim 18 wherein the first set of processing elements and/or the second set of processing elements recognize a spatial tag of a computational event and take action under control of the domain flow program.

### Claim 26 (depends on 25)

The processor fabric of claim 25 wherein the action taken includes comparing a signature of an incoming data token with signatures of instruction tokens that accumulate in the first set of processing elements and/or the second set of processing elements, and extracting the data token from an internal network if there is a match.

### Claim 27 (depends on 18)

The processor fabric of claim 18 wherein the domain flow program evolves as multi-dimensional data streams match up with the first set of processing elements and/or the second set of processing elements and produce new multi-dimensional data streams.

### Claim 28 (depends on 18)

The processor fabric of claim 18 wherein the first set of processing elements and/or the second set of processing elements each include a content addressable memory, an instruction scheduling/dispatch queue, one or more functional units, and a router configured to generate affine routing vectors.

### Claim 29 (depends on 18)

The processor fabric of claim 18 wherein the processor fabric manages and maintains global operators.

### Claim 30 (depends on 18)

The processor fabric of claim 18 wherein the processor fabric implements testing and reconfiguring to identify and isolate a faulty processing element of the first set of processing elements and/or the second set of processing elements or a faulty storage element.

### Claim 31 (depends on 18)

The processor fabric of claim 18 wherein the processor fabric is implemented on a chip with one or more additional processor fabrics which are able to communicate data streams to each other.

### Claim 32 (depends on 18)

The processor fabric of claim 18 wherein the first set of processing elements and/or the second set of processing elements each comprise a Single Instruction Multiple Data (SIMD) unit configured to process a plurality of operations per instruction.

### Claim 33 (depends on 11)

The method of claim 11 wherein the operations include integer, genomic strings, floating point, non-integer or non-floating point.

### Claim 34 (depends on 18)

The processor fabric of claim 18 wherein the operations include integer, genomic strings, non-integer or non-floating point.