Patent Description:
The subject matter discussed in this section should not be assumed to be prior art merely as a result of its mention in this section. Similarly, a problem mentioned in this section or associated with the subject matter provided as background should not be assumed to have been previously recognized in the prior art. The subject matter in this section merely represents different approaches, which in and of themselves can also correspond to implementations of the claimed technology.

Reconfigurable processors, including field programmable gate arrays (FPGAs), can be configured to implement a variety of functions more efficiently or faster than might be achieved using a general purpose processor executing a computer program. So-called coarse-grain reconfigurable architectures (CGRAs) are being developed in which the configurable units in the array are more complex than used in typical, more fine-grained FPGAs, and may enable faster or more efficient execution of various classes of functions. For example, CGRAs have been proposed that can enable implementation of energy-efficient accelerators for machine learning and artificial intelligence workloads. See, <NPL>.

CGRAs are an extremely attractive platform when performance, power, or energy efficiency are paramount. A CGRA is a composition of coarse-grained reconfigurable compute and memory elements that are interconnected together in a certain topology using a reconfigurable interconnect fabric. It is referred to as coarse-grained reconfigurable because the reconfigurable components in the architecture operate at a coarser granularity such as instructions, words, and vectors of words, as opposed to fine-grained, bit-level granularity commonly found in architectures such as FPGAs. The programmable data and control paths in CGRAs make them a natural fit to exploit nested parallelism in applications, by connecting the reconfigurable compute and memory components into customized, deeply nested, and hierarchical pipelines.

Modern applications often have several levels of nested loop levels, and contain parallelism at multiple levels of nesting. For such deeply-nested loops, traditional loop pipelining methods, which focus only on bodies of the innermost loops, often exploits insufficient parallelism and results poor hardware utilization, resulting in poor performance, power, or energy efficiency.

Efficient compiler technology enables programmers to describe applications in a high-level language, while most of the optimizations happen automatically. Compilers have been proposed that can automatically translate high-level language to a hierarchy of pipelines and state machines on FPGAs.

Achieving the promised performance, power, and energy efficiency critically hinges on the compiler technology. A CGRA compiler is much more complex than a regular compiler because it has to (i) perform code analysis to extract task, data, and pipelined parallelism at multiple levels of nesting, (ii) partition and schedule operations in both space and time on the reconfigurable elements, (iii) place the operations onto the reconfigurable elements, and (iv) route the data and control dependencies between the reconfigurable elements.

Therefore, an opportunity arises to efficiently map nested loops onto the reconfigurable elements of CGRAs. Improved parallelization and hardware utilization may result.

In the drawings, like reference characters generally refer to like parts throughout the different views. Also, the drawings are not necessarily to scale, with an emphasis instead generally being placed upon illustrating the principles of the technology disclosed. In the following description, various implementations of the technology disclosed are described with reference to the following drawings, in which:.

The following discussion is presented to enable any person skilled in the art to make and use the technology disclosed, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed implementations will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other implementations and applications without departing from the scope of the technology disclosed. Thus, the technology disclosed is not intended to be limited to the implementations shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.

<FIG> is a system diagram illustrating a system including a compiler <NUM>, a host <NUM>, a memory <NUM>, and a reconfigurable data processor <NUM>. As shown in the example of <FIG>, the reconfigurable data processor <NUM> includes an array <NUM> of configurable units and a configuration load/unload controller <NUM>. The phrase "configuration load/unload controller", as used herein, refers to a combination of a configuration load controller and a configuration unload controller. The configuration load controller and the configuration unload controller may be implemented using separate logic and data path resources, or may be implemented using shared logic and data path resources as suits a particular embodiment. In some embodiments, a system may include only a configuration load controller of the types described herein. In some embodiments, a system may include only a configuration unload controller of the types described herein.

Configuration of the array <NUM> of configurable units involves compilation of a configuration description by the compiler <NUM> to produce a configuration file <NUM>, referred to sometimes as a bitstream or bit file, and distributing the configuration file <NUM> to the configurable units on the array <NUM>. In one embodiment, the compiler <NUM> provides translations from application programs to bit file.

The processor <NUM> includes an external I/O interface <NUM> connected to the host <NUM>, and external I/O interface <NUM> connected to the memory <NUM>. The I/O interfaces <NUM>, <NUM> connect via a bus system <NUM> to the array <NUM> of configurable units and to the configuration load/unload controller <NUM>. The bus system <NUM> may have a bus width of carrying one chunk of data, which can be for this example <NUM> bits (references to <NUM> bits throughout can be considered as an example chunk size more generally). In general, a chunk of the configuration file can have a number N of bits of data, and the bus system can be configured to transfer N bits of data in one bus cycle, where N is any practical bus width. A sub-file distributed in the distribution sequence can comprise one chunk, or other amounts of data as suits a particular embodiment. Procedures are described herein using sub-files consisting of one chunk of data each. Of course, the technology can be configured to distribute sub-files of different sizes, including sub-files that may comprise two chunks distributed in two bus cycles for example.

To configure configurable units in the array <NUM> of configurable units with a configuration file, the host <NUM> can send the configuration file to the memory <NUM> via the interface <NUM>, the bus system <NUM>, and the interface <NUM> in the reconfigurable data processor <NUM>. The host <NUM> connects to the interface <NUM> via the bus system <NUM>. The memory <NUM> connects to the interface <NUM> via the bus system <NUM>. The configuration file can be loaded in many ways, as suits a particular architecture, including in data paths outside the configurable processor <NUM>. The configuration file can be retrieved from the memory <NUM> via the memory interface <NUM>. Chunks of the configuration file can then be sent in a distribution sequence as described herein to configurable units in the array <NUM> of configurable units in the reconfigurable data processor <NUM>.

An external clock generator <NUM> or other clock signal sources can provide a clock signal <NUM> or clock signals to elements in the reconfigurable data processor <NUM>, including the array <NUM> of configurable units, and the bus system <NUM>, and the external data I/O interfaces.

<FIG> is a block diagram <NUM> of one implementation of transforming a high-level program for mapping onto the reconfigurable data processor <NUM>. Mapping of an application onto the reconfigurable data processor <NUM> involves mapping of arithmetic and logical operations to reconfigurable units of the reconfigurable data processor <NUM>. The design is specified at a high level of abstraction using machine learning frameworks like PyTorch, ONNX, and Tensorflow, or high-level languages such as C, C++, Java, Python, or Spatial. See, <NPL>. The proposed technique is used to automatically generate the configuration bits structure that implements the behavior described at the high-level of abstraction.

High-level program <NUM> is an application program or source code written in programming languages such as (but not restricted to) C, C++, Java, Python, or Spatial. For example, the high-level program <NUM> can implement convolutional neural network (CNN) processing with several layers of varying sizes and data type such that each layer comprises several nested loops with different properties. For example, the high-level program <NUM> can involve memory operations to access the inputs and weights and floating point operations to perform matrix multiplications. As another example, the high-level program <NUM> can include nested loops with high iteration count and loop bodies that load and multiply the input values from a preceding layer with the weights of a succeeding layer to produce the output of the succeeding layer. The high-level program <NUM> has loop-level parallelism of the outermost loop body that can be exploited using coarse-grained pipelining. It has instruction-level parallelism of the innermost loop body that can be similarly exploited using loop unrolling, SIMD vectorization, and pipelining.

Regarding loops, loops directly nested in a loop body are termed the child loops of the outer parent loop. A loop is called an innermost loop if it does not have any children, i.e., there are not any nested loops within its body. A loop is an outermost loop if it does not have a parent, i.e., it is not nested within another loop's body. An imperfectly nested loop has a body with a mix of non-looping statements (e.g., primitive arithmetic, logical, and relational operations) and one or more child loops. Parallelism in the imperfectly nested loops can be exploited at any or all loop levels, and in the operations that comprise loop bodies. Parallelism can occur in multiple forms such as fine-grained and coarse-grained pipeline parallelism, data parallelism, and task parallelism.

At action <NUM>, a dataflow graph generator <NUM> generates a dataflow graph <NUM> of the high-level program <NUM>. The compilation transforms the input behavioral description into an intermediate representation. This first step may include various code optimizations such as false data dependency elimination, dead-code elimination, and constant folding. The intermediate representation produced by the compilation exhibits the data and control dependencies between the operations.

Nodes in the dataflow graph <NUM> represent control structures, data operations, and memory allocations, while edges represent data and effect dependencies. Each loop in the program is represented as a "controller" in the intermediate representation. The dataflow graph <NUM> supports branches, loops, function calls, and other variations of control dependencies. Once the dataflow graph <NUM> is built, additional analyses or optimizations can be performed focusing on loop transformations including loop unrolling, loop pipelining, loop fission/fusion, and loop tiling.

At action <NUM>, a partitioner <NUM>, partitions the dataflow graph <NUM> into memory allocations <NUM> and execution fragments <NUM>. Regarding execution fragments <NUM>, they represent operations on the data. An execution fragment can comprise portions of a program representing an amount of work. An execution fragment can comprise computations encompassed by a set of loops, a set of graph nodes, or some other unit of work that requires synchronization. An execution fragment can comprise a fixed or variable amount of work, as needed by the program. Similarly, different ones of the execution fragments <NUM> can contain different amounts of computation. Execution fragments <NUM> can represent parallel patterns or portions of parallel patterns. Also, the execution fragments <NUM> are executable asynchronously.

In one embodiment, the partitioner <NUM> comprises a memory allocator <NUM> that generates the memory allocations <NUM> and an execution fragment generator <NUM> that generates the execution fragments <NUM>. In one embodiment, the partitioning of the dataflow graph <NUM> into the execution fragments <NUM> further includes treating calculations within at least one innermost loop of a nested loop of the dataflow graph <NUM> as a separate execution fragment. In another embodiment, the partitioning of the dataflow graph <NUM> into the execution fragments <NUM> further includes treating calculations of an outer loop around the innermost loop of the dataflow graph <NUM> as a separate execution fragment. In the case of imperfectly nested loops, operations within a loop body up to the beginning of a nested loop within that loop body are grouped together as a separate execution fragment.

Regarding memory allocations <NUM>, they represent the creation of logical memory spaces in on-chip and/or off-chip memories for data required to implement the dataflow graph <NUM>. Memory allocations <NUM> define the type and the number of hardware resources (functional units, storage, or connectivity components). Main memory, abbreviated as DRAM, is an example of off-chip memory for which the memory allocations <NUM> are made. Scratchpad memory, or SRAM, is an example of on-chip memory for which the memory allocations <NUM> are made. Other memory types for which the memory allocations <NUM> can be made for various commonly occurring access patterns and layouts found in applications. Examples of such memory types include read-only lookup-tables (LUTs), fixed size queues (FIFOs), and register files.

At action <NUM>, a designator <NUM>, designates the memory allocations <NUM> to virtual memory units <NUM> and designates the execution fragments <NUM> to virtual compute units <NUM>.

At action <NUM>, an execution fragment partitioner <NUM>, partitions the execution fragments <NUM> into memory fragments <NUM> and compute fragments <NUM>. Each memory fragment includes address calculation leading up to a memory access. The compute fragment comprises all other operations in the parent execution fragment. In one embodiment, each execution fragment is broken up into a plurality of memory fragments and exactly one compute fragment. The compiler <NUM> performs the partitioning using reverse dataflow analysis such that inputs to an address used in a memory access are recursively flagged until the compiler <NUM> reaches either constant values or (bound) loop/pattern iterators. A single execution fragment may produce one or more memory fragments, depending on how many memory accesses exist in the original loop body. In cases where the same memory addressing logic is shared across multiple memory accesses, address calculation may be duplicated to create multiple memory fragments from the same execution fragment.

The memory fragments <NUM> of the execution fragments <NUM> are configured to index into data structures. At least one of the memory fragments <NUM> indexes into a data structure in the logical memory spaces of one of the memory allocations <NUM>. Each compute and memory fragment preserves information about all loops whose loop bodies directly contain the operations in the corresponding execution fragment. In one embodiment, this corresponds to replicating the calculation of the loop iterators of each loop into each compute and memory fragment. This replication allows each fragment to preserve the same iterative behavior as the original program while also allowing distributed calculation of loop iterators.

At action <NUM>, an assigner <NUM>, assigns the memory fragments <NUM> to the virtual memory units <NUM> and assigns the compute fragments <NUM> to the virtual compute units <NUM>. The virtual memory units <NUM> implement the corresponding memory fragments <NUM>. The virtual compute units <NUM> implement the corresponding compute fragments <NUM>.

Each memory fragment is mapped operation-wise to the virtual memory unit corresponding to the memory being accessed. Each operation is lowered to its corresponding configuration intermediate representation (IR) for that virtual memory unit. Each compute fragment is mapped operation-wise to a newly allocated virtual compute unit. Each operation is lowered to its corresponding configuration intermediate representation (IR) for that virtual compute unit.

At action <NUM>, an allocator <NUM>, allocates the virtual memory units <NUM> to physical memory units <NUM> and allocates the virtual compute units <NUM> to physical compute units <NUM>.

At action <NUM>, a placer and router <NUM>, places the physical memory units <NUM> and the physical compute units <NUM> onto positions in the array <NUM> of configurable units and routes data and control networks between the placed positions. In one embodiment, this further includes allocating physical resources such as counters and registers within each physical memory and compute unit.

At action <NUM>, a bit file generator <NUM>, accesses placement and routing information <NUM> produced by the placer and router <NUM> and generates the bit file <NUM> with configuration data for the placed positions and the routed data and control networks. In one embodiment, this includes assigning coordinates and communication resources of the physical memory and compute units by placing and routing units onto the array <NUM> of configurable units while maximizing bandwidth and minimizing latency.

At action <NUM>, the configuration load/unload controller <NUM> loads the bit file <NUM> onto an instance of the array <NUM> of configurable units and causes the array <NUM> of configurable units to implement the dataflow graph <NUM>.

<FIG> is a block diagram <NUM> of one implementation of allocating the virtual memory units <NUM> to multiple physical memory units <NUM>, <NUM> and allocating the virtual compute units <NUM> to multiple physical compute units <NUM>, <NUM>. This is done at action <NUM> in <FIG> by the allocator <NUM>. In one embodiment, the allocation satisfies hardware constraints of the multiple physical memory units <NUM>, <NUM> and the multiple physical compute units <NUM>, <NUM>.

In one embodiment, the allocating depends, at least in part, on a number of inputs accepted by a particular physical compute unit. In one embodiment, as a first step, in each virtual memory and compute unit, operations are removed until the virtual memory and compute unit is physically realizable. In one embodiment, as a second step, the removed operations are grouped into a separate, new virtual memory and compute unit. In one embodiment, these two steps are repeated until all virtual memory and compute units are physically realizable. In one embodiment, the compiler <NUM> then adds data and control communication channels to the IR between the virtual memory and compute units based on dependencies in the original virtual memory and compute unit.

In the context of this application, "physically realizable" is modeled using analysis with target architecture parameters. In one embodiment, the parameters include a capacity of on-chip SRAM available in a physical memory unit, a number of arithmetic logic unit (ALU) stages, a number of registers per stage, capabilities of each ALU stage, connections available between ALUs and the registers, and connections available between the registers. In one embodiment, the order in which the operations are removed can vary and is based on heuristics whose objective function is to minimize the final number of physically realizable units. In other embodiments, heuristics may be applied with a different objective function to minimize the total execution time, which could increase the number of physically realizable units.

At action <NUM>, the placer and router <NUM>, places the multiple physical memory units <NUM>, <NUM> and the multiple physical compute units <NUM>, <NUM> onto positions in the array <NUM> of configurable units and routes data and control networks between the placed positions.

At action <NUM>, the bit file generator <NUM>, accesses the placement and routing information <NUM> produced by the placer and router <NUM> and generates the bit file <NUM> with configuration data for the placed positions and the routed data and control networks.

<FIG> is a block diagram <NUM> of one implementation of fusing the multiple physical memory units <NUM>, <NUM>, <NUM> into a single physical memory unit <NUM> and fusing the multiple physical compute units <NUM>, <NUM>, <NUM> into a single physical compute unit <NUM>. This is done at action <NUM> in <FIG> by fuser <NUM> based on fusion logic <NUM>. The goal of fusion is to reduce resource wastage by better packing operations into physical memory and compute units. In one embodiment, termed as "fusion in space," two or more physical memory or compute units with underutilized resources can be combined into a single memory or compute unit with a higher resource utilization for efficiency, as long as the resulting resource utilization is still physically realizable. In another embodiment, termed as "fusion in time," two or more physical memory or compute units can be combined by scheduling them to execute sequentially as separate execution contexts within a single, new physical memory or compute unit. In still other embodiments, a combination of fusion rules in both in space and time may be employed if such a combination of optimizations is deemed profitable by the compilation flow. The fusion rules may be determined using heuristics, search algorithms, or other algorithmic optimization techniques.

in one embodiment, the fusing depends, at least in part, on a capacity of on-chip SRAM available in a physical memory unit, and a number of ALU stages within the single physical compute unit. In one embodiment, the fusion in space includes executing multiple operations on the single physical compute unit <NUM> that would otherwise execute on separate physical compute units <NUM>, <NUM>, <NUM> at different clock cycles. In one embodiment, the fusion in time includes sequentially executing the multiple operations on the single physical compute unit <NUM> as separate execution contexts. In one embodiment, a plurality of operations from the dataflow graph <NUM> grouped onto a particular physical compute unit are mapped onto resources within the particular physical compute unit. In other embodiments, heuristics are used that look for the tradeoff between the number of required physical memory and compute units and the achieved performance.

At action <NUM>, the placer and router <NUM>, places the single physical memory unit <NUM> and the single physical compute unit <NUM> onto positions in the array <NUM> of configurable units and routes data and control networks between the placed positions.

In some embodiments, the compiler flow logic discussed with reference to <FIG>, <FIG>, and <FIG> is implemented by the compiler <NUM>.

<FIG> shows an example of the high-level program <NUM> in PyTorch. This example implements a residual neural network (ResNet) block, which is a commonly used type of Convolutional Neural Network (CNN) popularly used for automatic image classification. The ResNet architecture contains several layers of convolution operations, where each layer performs several convolution operations on the output of the preceding layer and the weight filters of the current layer. The ResNet architecture also contains skip connections that connect outputs of some layers to the inputs of layers that are much further in the network, "skipping" two or three layers in between. ResNet models also contain nonlinear functions such as ReLU and batch normalization in between. Batch normalization is a method for accelerating deep network training by making data standardization an integral part of the network architecture.

<FIG> depicts one example of the dataflow graph <NUM> of the ResNet block <NUM>. This example performs convolution <NUM> on input <NUM> and produces output <NUM>. Batch normalization <NUM> is performed on output <NUM> to produce output <NUM>. The batch normalized output <NUM> is then linearized between zero and the maximum positive values by the ReLU activation <NUM> to produce the ReLU activated output <NUM>. Average pooling <NUM> is performed on ReLU activated output <NUM> to produce the average pooled output <NUM>. The average pooled output <NUM> is then fed as input to a linear layer <NUM> (e.g. a fully-connected network) to produce a final output <NUM> of the ResNet block <NUM>. The linear layer <NUM> has <NUM> neurons (weights).

Dimensionality of the input <NUM> is <NUM> x <NUM> x <NUM> x <NUM>, where <NUM> is the batch size, <NUM> is the number of input channels (e.g. RGB image channels), <NUM> is the input width (e.g. number of pixel columns in an image), and <NUM> is the input height (e.g. number of pixel widths in an image). Dimensionality of the convolution <NUM> is <NUM> x <NUM> x <NUM> x <NUM>, where <NUM> is the number of convolution filters, <NUM> is the number of kernels in each convolution filter, <NUM> is the kernel width (e.g. number of weight columns in a kernel), and <NUM> is the kernel height (e.g. number of weight rows in a kernel). Dimensionality of the output <NUM> is <NUM> x <NUM> x <NUM> x <NUM>, where <NUM> is the batch channel, <NUM> is the number of output channels, <NUM> is the output width (e.g. number of feature columns in a feature map), and <NUM> is the output height (e.g. number of feature rows in a feature map). Dimensionality of the final output <NUM> is <NUM> x <NUM>, where <NUM> is the batch channel and <NUM> is the number of output channels.

<FIG>, <FIG>, <FIG> show example implementations of a subset of the ResNet architecture as the high-level program <NUM>, which is represented internally as the dataflow graph <NUM>. In one embodiment, the high-level program could be written in the Spatial high-level language.

<FIG>, <FIG>, and <FIG> illustrate one example of partitioning the dataflow graph <NUM> into memory allocations <NUM> and execution fragments <NUM>. In <FIG>, <FIG>, and <FIG>, italicized code identifies the memory allocations <NUM> and bold code identifies the execution fragments <NUM>. The first memory allocation <NUM> allocates memory spaces in on-chip SRAM for the input <NUM>. The second memory allocation <NUM> allocates memory spaces in the on-chip SRAM for the convolution <NUM>. The third memory allocation <NUM> allocates memory spaces in the on-chip SRAM for the output <NUM>.

The first execution fragment <NUM> implements the convolution <NUM> between the input <NUM> and convolution weights of the convolution <NUM>. The second execution fragment <NUM> implements accumulation of the output <NUM>.

The fourth memory allocation <NUM> allocates memory spaces in the on-chip SRAM for the output <NUM> of the batch normalization <NUM>. The fifth memory allocation <NUM> allocates memory spaces in the on-chip SRAM for the scaling value of the batch normalization <NUM>. The sixth memory allocation <NUM> allocates memory spaces in the on-chip SRAM for the bias value of the batch normalization <NUM>.

The third execution fragment <NUM> implements mean calculation <NUM> of the batch normalization <NUM>. The fourth execution fragment <NUM> implements mean normalization <NUM> of the batch normalization <NUM>.

In <FIG>, the fifth execution fragment <NUM> implements variance calculation <NUM> of the batch normalization <NUM>. The sixth execution fragment <NUM> implements variance normalization <NUM> of the batch normalization <NUM>. The seventh execution fragment <NUM> implements calculation of the output <NUM> of the batch normalization <NUM>.

The seventh memory allocation <NUM> allocates memory spaces in the on-chip SRAM for the output <NUM> of the ReLU activation <NUM>. The eighth execution fragment <NUM> implements calculation of the output <NUM> of the ReLU activation <NUM>.

The eighth memory allocation <NUM> allocates memory spaces in the on-chip SRAM for the output <NUM> of the average pooling <NUM>. The ninth execution fragment <NUM> implements calculation of the output <NUM> of the average pooling <NUM>. The tenth execution fragment <NUM> implements accumulation of the output <NUM> of the average pooling <NUM>.

In <FIG>, the ninth memory allocation <NUM> allocates memory spaces in the on-chip SRAM for the neurons (weights) of the linear layer <NUM>. The tenth memory allocation <NUM> allocates memory spaces in the on-chip SRAM for the final output <NUM>. The eleventh execution fragment <NUM> implements calculation of the final output <NUM>.

<FIG> shows an example of one implementation of designating the memory allocations <NUM> to the virtual memory units <NUM> and designating the execution fragments to the virtual compute units <NUM>. In <FIG>, the ten memory allocations <NUM> in <FIG>, <FIG>, and <FIG> are respectively designated a corresponding virtual memory unit (VMU). Also in <FIG>, the eleven execution fragments in <FIG>, <FIG>, and <FIG> are respectively designated a corresponding virtual compute unit (VCU).

<FIG> show one implementation of partitioning the execution fragments <NUM> into memory fragments <NUM> and compute fragments <NUM>. <FIG> shows that the first execution fragment <NUM>, which implements the convolution <NUM> between the input <NUM> and convolution weights of the convolution <NUM>, is partitioned into a first memory fragment <NUM>, a second memory fragment <NUM>, and a compute fragment <NUM>. <FIG> also shows the respective addresses computed by the first and second memory fragments <NUM>, <NUM> (MF1a, MF1b) for memory access.

<FIG> depicts one implementation of respectively assigning the memory fragments <NUM>, <NUM> to the virtual memory units <NUM>, <NUM> (VMU <NUM>, VMU <NUM>) and assigning the compute fragment <NUM> to the virtual compute unit <NUM> (VCU <NUM>). The address calculation <NUM>, <NUM> (MF1a, MF1b) are respectively allocated to the virtual memory units <NUM>, <NUM> (VMU <NUM>, VMU <NUM>) with the allocations <NUM>, <NUM> (A1, A2).

<FIG> illustrates one implementation of mapping the virtual memory units <NUM>, <NUM> (VMU <NUM>, VMU <NUM>) to one or more physical memory units <NUM>, <NUM>, <NUM>, <NUM>, <NUM> (PMU 1_0, PMU 1_1, PMU 2_0, PMU 2_1, PMU 2_2) and mapping the virtual compute unit <NUM> (VCU <NUM>) to one or more physical compute units <NUM>, <NUM> (PCU 1_0, PCU 1_1).

The virtual memory unit <NUM> (VMU <NUM>) is mapped to the physical memory unit <NUM> (PMU 1_0) and the physical memory unit <NUM> (PMU 1_1). The original address designation <NUM> (A1) of the virtual memory unit <NUM> (VMU <NUM>) is expressed as duplicated address designations <NUM>, <NUM> (A1_0, A1_1) of the physical memory units <NUM>, <NUM> (PMU 1_0, PMU 1_1), respectively.

The virtual memory unit <NUM> (VMU <NUM>) is mapped to the physical memory unit <NUM> (PMU 2_0), the physical memory unit <NUM> (PMU 2_1), and the physical memory unit <NUM> (PMU 2_1). The original address designation <NUM> (A2) of the virtual memory unit <NUM> (VMU <NUM>) is expressed as duplicated address designations <NUM>, <NUM>, <NUM> (A2_0, A2_1, A2_2) of the physical memory units <NUM>, <NUM>, <NUM> (PMU 2_0, PMU 2_1, PMU 2_2), respectively.

The virtual compute unit <NUM> (VCU <NUM>) is mapped to the physical compute unit <NUM> (PCU 1_0) and the physical compute unit <NUM> (PCU 1_1).

<FIG> depict one example of mapping execution fragment <NUM> to a virtual compute unit (VCU <NUM>) that has four inputs. Execution fragment <NUM> is partitioned into a first memory fragment <NUM>, a second memory fragment <NUM>, a third memory fragment <NUM>, a fourth memory fragment <NUM>, and a compute fragment <NUM>.

In <FIG>, since the virtual compute unit (VCU <NUM>) has four inputs, it is able to process all the four memory fragments <NUM>, <NUM>, <NUM>, <NUM> to compute the compute fragment <NUM> for the execution fragment <NUM>.

When a single physical compute unit is not enough to execute an execution fragment mapped to a virtual compute and/or memory unit, then splitting can be used to map the virtual compute and/or memory unit to multiple physical compute and/or memory units. The multiple physical compute and/or memory units then together execute the execution fragment.

Turning to <FIG>, consider that a single physical compute unit has only three inputs. However though, the virtual compute unit (VCU <NUM>) has four inputs. To account for this, two physical compute units (PCU 7_0 and PCU 7_1) are used to compute the compute fragment <NUM> for the execution fragment <NUM>. This is achieved by mapping the virtual compute unit (VCU <NUM>) to the two physical compute units (PCU 7_0 and PCU 7_1).

<FIG> is one example of fusing physical compute units and physical memory units. In <FIG>, physical compute units and physical memory units implementing various memory fragments and compute fragments are connected. The connections follow data and control dependencies required by the dataflow graph <NUM>.

<FIG> illustrates one example of fusion in space by executing multiple operations on the single physical compute unit that would otherwise execute on separate physical compute units at different clock cycles. In <FIG>, PCU 3_0 and PCU 4_0 are combined into a single PCU 3_0_4_0. Also, PCU 5_0 and PCU 6_0 are combined into a single PCU 5_0_6_0.

<FIG> shows one example of fusion in time by sequentially executing the multiple operations on the single physical compute unit as separate execution contexts. In <FIG>, PCU 3_0, PCU 4_0, PCU 5_0, and PCU 6_0 are combined into a single PCU 3_0_4_0_5_0_6_0. This means the single PCU 3_0_4_0_5_0_6_0 executes the fused compute fragments <NUM>, <NUM> (CF <NUM>/<NUM>) for one segment of time, then changes contexts and executes the fused compute fragments <NUM>, <NUM> (CF <NUM>/<NUM>). The value after CF <NUM>/<NUM> is passed back to the unit (since it is an intermediate value used as an input to CF <NUM>/<NUM>). The implementation of this self-loop depends on the hardware embodiment, but can be implemented as an internal register or memory in the PCU or using the external network by feeding the PCU's output back into itself. In another embodiment, the data fed back to the PCU can be stored in a separate memory unit such as a PMU or a set of PMUs.

<FIG> is a simplified diagram <NUM> of a tile and an array level network usable in the reconfigurable data processor of <FIG>. <FIG> illustrates an example switch unit connecting elements in the array level network. In this example, the array of configurable units <NUM> includes a plurality of types of configurable units. The types of configurable units in this example, include Pattern Compute Units (PCU), Pattern Memory Units (PMU), switch units (S), and Address Generation and Coalescing Units (each including two address generators AG and a shared CU). For an example of the functions of these types of configurable units, see,<NPL>, which is incorporated by reference as if fully set forth herein.

Each of these configurable units contains a configuration store comprising a set of registers or flip-flops that represent either the setup or the sequence to run a program, and can include the number of nested loops, the limits of each loop iterator, the instructions to be executed for each stage, the source of the operands, and the network parameters for the input and output interfaces.

Additionally, each of these configurable units contains a configuration store comprising a set of registers or flip-flops that store status usable to track progress in nested loops or otherwise. The configuration file <NUM> contains a bitstream representing the initial configuration, or starting state, of each of the components that execute the program. This bitstream is referred to as a bit file. Program load is the process of setting up the configuration stores in the array <NUM> of configurable units based on the contents of the bit file to allow all the components to execute a program (i.e., a machine). Program Load may also require the load of all PMU memories.

The array level network includes links interconnecting configurable units in the array. The links in the array level network include one or more and, in this case three, kinds of physical buses: a chunk-level vector bus (e.g. <NUM> bits of data), a word-level scalar bus (e.g. <NUM> bits of data), and a multiple bit-level control bus. For instance, interconnect <NUM> between switch units <NUM> and <NUM> includes a vector bus interconnect with vector bus width of <NUM> bits, a scalar bus interconnect with a scalar bus width of <NUM> bits, and a control bus interconnect.

The three kinds of physical buses differ in the granularity of data being transferred. In one embodiment, the vector bus can carry a chunk that includes <NUM>-Bytes (=<NUM> bits) of data as its payload. The scalar bus can have a <NUM>-bit payload, and carry scalar operands or control information. The control bus can carry control handshakes such as tokens and other signals. The vector and scalar buses can be packet switched, including headers that indicate a destination of each packet and other information such as sequence numbers that can be used to reassemble a file when the packets are received out of order. Each packet header can contain a destination identifier that identifies the geographical coordinates of the destination switch unit (e.g. the row and column in the array), and an interface identifier that identifies the interface on the destination switch (e.g. North, South, East, West, etc.) used to reach the destination unit. The control network can be circuit switched based on timing circuits in the device, for example. The configuration load/unload controller can generate a header for each chunk of configuration data of <NUM> bits. The header is transmitted on a header bus to each configurable unit in the array <NUM> of configurable units.

In one example, a chunk of data of <NUM> bits is transmitted on the vector bus that provides the chunk as vector inputs to a configurable unit. The vector bus can include <NUM> payload lines, and a set of header lines. The header can include a sequence ID for each chunk, which can includes:.

A bit to indicates if the chunk is scratchpad memory or configuration store data.

For a load operation, the configuration load controller can send the number N of chunks to a configurable unit in order from N-<NUM> to <NUM>. For this example, the <NUM> chunks are sent out in most significant bit first order of Chunk <NUM>-> Chunk <NUM>->Chunk <NUM>->Chunk <NUM>->Chunk <NUM>-> Chunk <NUM>. (Note that this most significant bit first order results in Chunk <NUM> being distributed in round <NUM> of the distribution sequence from the array configuration load controller. ) For an unload operation, the configuration unload controller can write out the unload data of order to the memory. For both load and unload operations, the shifting in the configuration serial chains in a configuration data store in a configurable unit is from LSB (least-significant-bit) to MSB (most-significant-bit), or MSB out first.

<FIG> illustrates an example switch unit connecting elements in the array level network. As shown in the example of <FIG>, a switch unit can have <NUM> interfaces. The North, South, East and West interfaces of a switch unit are used for connections between switch units. The Northeast, Southeast, Northwest and Southwest interfaces of a switch unit are each used to make connections to PCU or PMU instances. A set of <NUM> switch units in each tile quadrant have connections to an Address Generation and Coalescing Unit (AGCU) that include multiple address generation (AG) units and a coalescing unit (CU) connected to the multiple address generation units. The coalescing unit (CU) arbitrates between the AGs and processes memory requests. Each of the <NUM> interfaces of a switch unit can include a vector interface, a scalar interface, and a control interface to communicate with the vector network, the scalar network, and the control network.

During execution of a machine after configuration, data can be sent via one or more unit switches and one or more links between the unit switches to the configurable units using the vector bus and vector interface(s) of the one or more switch units on the array level network.

In embodiments described herein, a configuration file or bit file <NUM>, before configuration of the tile, can be sent from the configuration load controller using the same vector bus, via one or more unit switches and one or more links between the unit switches to the configurable unit using the vector bus and vector interface(s) of the one or more switch units on the array level network. For instance, a chunk of configuration data in a unit file particular to a configurable unit PMU <NUM> can be sent from the configuration load/unload controller <NUM> to the PMU <NUM>, via a link <NUM> between the configuration load/unload controller <NUM> and the West (W) vector interface of the switch unit <NUM>, the switch unit <NUM>, and a link <NUM> between the Southeast (SE) vector interface of the switch unit <NUM> and the PMU <NUM>.

In this example, one of the AGCUs is configured to be a master AGCU, which includes a configuration load/unload controller (e.g. <NUM>). The master AGCU implements a register through which the host (<NUM>, <FIG>) can send commands via the bus system to the master AGCU. The master AGCU controls operations on an array of configurable units in a tile and implements a program control state machine to track the state of the tile based on the commands it receives from the host through writes to the register. For every state transition, the master AGCU issues commands to all components on the tile over a daisy chained command bus (<FIG>). The commands include a program reset command to reset configurable units in an array of configurable units in a tile, and a program load command to load a configuration file to the configurable units.

The configuration load controller in the master AGCU is responsible for reading the configuration file from the memory and sending the configuration data to every configurable unit of the tile. The master AGCU can read the configuration file from the memory at preferably the maximum throughput of the top level network. The data read from memory are transmitted by the master AGCU over the vector interface on the array level network to the corresponding configurable unit according to a distribution sequence described herein.

In one embodiment, in a way that can reduce the wiring requirements within a configurable unit, configuration and status registers holding unit files to be loaded in a configuration load process, or unloaded in a configuration unload process in a component are connected in a serial chain and can be loaded through a process of shifting bits through the serial chain. In some embodiments, there may be more than one serial chain arranged in parallel or in series. When a configurable unit receives the for example <NUM> bits of configuration data from the master AGCU in one bus cycle, the configurable unit shifts this data through its serial chain at the rate of <NUM> bit per cycle, where shifter cycles can run at the same rate as the bus cycle. It will take <NUM> shifter cycles for a configurable unit to load <NUM> configuration bits with the <NUM> bits of data received over the vector interface. The <NUM> bits of configuration data are referred to as a chunk. A configurable unit can require multiple chunks of data to load all its configuration bits.

The configurable units interface with the memory through multiple memory interfaces (<NUM>, <FIG>). Each of the memory interfaces can be accessed using several AGCUs. Each AGCU contains a reconfigurable datapath to generate requests for the off-chip memory. Each AGCU contains FIFOs (first-in-first-out buffers for organizing data) to buffer outgoing commands, data, and incoming responses from the off-chip memory.

The address generators AGs in the AGCUs can generate memory commands that are either dense or sparse. Dense requests can be used to bulk transfer contiguous off-chip memory regions, and can be used to read or write chunks of data from/to configurable units in the array of configurable units. Dense requests can be converted to multiple off-chip memory burst requests by the coalescing unit (CU) in the AGCUs. Sparse requests can enqueue a stream of addresses into the coalescing unit. The coalescing unit can use a coalescing cache to maintain metadata on issued off-chip memory requests to combine sparse addresses that belong to the same off-chip memory request to minimize the number of issued off-chip memory requests.

<FIG> is a block diagram illustrating an example configurable unit <NUM>, such as a Pattern Compute Unit (PCU). In the context of this application, a PCU corresponds to a physical compute unit. Configurable units in the array of configurable units include configuration data stores <NUM> (e.g. serial chains) to store unit files comprising a plurality of chunks (or sub-files of other sizes) of configuration data particular to the corresponding configurable units. Configurable units in the array of configurable units each include unit configuration load logic <NUM> connected to the configuration data store <NUM> via line <NUM>, to execute a unit configuration load process. The unit configuration load process includes, receiving via the bus system (e.g. the vector inputs), chunks of a unit file particular to the configurable unit, and loading the received chunks into the configuration data store <NUM> of the configurable unit.

The configuration data stores in configurable units in the plurality of configurable units in this example comprise serial chains of latches, where the latches store bits that control configuration of the resources in the configurable unit. A serial chain in a configuration data store can include a shift register chain for configuration data and a second shift register chain for state information and counter values connected in series.

A configurable unit can interface with the scalar, vector, and control buses using three corresponding sets of inputs and outputs (IO): scalar inputs/outputs, vector inputs/outputs, and control inputs/outputs. Scalar IOs can be used to communicate single words of data (e.g. <NUM> bits). Vector IOs can be used to communicate chunks of data (e.g. <NUM> bits), in cases such as receiving configuration data in a unit configuration load process, and transmitting and receiving data during operation after configuration across a long pipeline between multiple PCUs. Control IOs can be used to communicate control signals such as the start or end of execution of a configurable unit. Control inputs are received by control block <NUM>, and control outputs are provided by the control block <NUM>.

Each vector input is buffered using a vector FIFO in a vector FIFO block <NUM> which can include one or more vector FIFOs. Each scalar input is buffered using a scalar FIFO <NUM>. Using input FIFOs decouples timing between data producers and consumers, and simplifies inter-configurable-unit control logic by making it robust to input delay mismatches.

Input configuration data <NUM> can be provided to a vector FIFO as vector inputs, and then be transferred to the configuration data store <NUM>. Output configuration data <NUM> can be unloaded from the configuration data store <NUM> using the vector outputs.

The CGRA uses a daisy chained completion bus to indicate when a load/unload command has been completed. The master AGCU transmits the program load and unload commands to configurable units in the array of configurable units over a daisy-chained command bus. As shown in the example of <FIG>, a daisy chained completion bus <NUM> and a daisy chained command bus <NUM> are connected to daisy chain logic <NUM>, which communicates with the unit configuration load logic <NUM>. The daisy chain logic <NUM> can include load complete status logic, as described below. The daisy chained completion bus is further described below. Other topologies for the command and completion buses are clearly possible but not described here.

A configurable unit includes multiple reconfigurable datapaths in block <NUM>. A datapath in a configurable unit can be organized as a multi-stage (Stage <NUM>. Stage N), reconfigurable SIMD (Single Instruction, Multiple Data) pipeline. The chunks of data pushed into the configuration serial chain in a configurable unit include configuration data for each stage of each datapath in the configurable unit. The configuration serial chain in the configuration data store <NUM> is connected to the multiple datapaths in block <NUM> via lines <NUM>.

In the context of this application, a pattern memory unit (PMU) corresponds to a physical memory unit. A PMU can contain scratchpad memory coupled with a reconfigurable datapath intended for address calculation, along with the bus interfaces used in the PCU. PMUs can be used to distribute on-chip memory throughout the array of reconfigurable units. In one embodiment, address calculation within the memory in the PMUs is performed on the PMU datapath, while the core computation is performed within the PCU. Each PMU contains a programmer-managed scratchpad memory coupled with a reconfigurable datapath intended primarily for address calculation, and other compute operations as required by the program. PMUs are used to distribute on-chip memory throughout the array <NUM>. The array architecture makes a distinction between the operations involved in memory addresses calculation and the core computation underlying applications. Address calculation is performed on the PMU datapath, while the core computation is performed within the PCU. Several observations have motivated this design choice: (i) address calculation involves simple scalar math, which requires simpler ALUs than the ALUs in PCUs; (ii) Using multiple lanes for address computation is often unnecessary for most on-chip access patterns; and (iii) Performing address calculation within the PCU requires routing the addresses from the PCU to the PMU, which occupies PCU stages and output links, and can lead to PCU under-utilization.

PCUs and PMUs (collectively "units") communicate with three kinds of interconnect: word-level scalar, multiple-word-level vector, and bit-level control interconnects. The array <NUM> of configurable units interfaces with DRAM through multiple DDR channels. Each channel has an associated address management unit that arbitrates between multiple address streams, and consists of buffers to support multiple outstanding memory requests and address coalescing to minimize DRAM accesses. Local address calculation is done in PMUs, DRAM address computation happens in the DRAM address management units, and the remaining data computation happens in PCUs. The scratchpads are built with multiple SRAM banks matching the number of PCU lanes. Address decoding logic around the scratchpad can be configured to operate in several banking modes to support various access patterns. Strided banking mode supports linear access patterns often found on dense data structures. FIFO mode supports streaming accesses. Line buffer mode captures access patterns resembling a sliding window. Duplication mode, where the contents are duplicated across all memory banks, provides multiple read address channels to support parallelized on-chip gather operations.

The PCU is designed to execute innermost parallel patterns in an application. The PCU datapath is organized as a multi-stage, reconfigurable SIMD pipeline. This design enables each PCU to achieve high compute density, and exploit both loop-level parallelism across lanes and pipeline parallelism across stages. Each stage of each SIMD lane is composed of a functional unit (FU) and associated pipeline registers (PR). FUs perform <NUM> bit word-level arithmetic and binary operations, including support for floating point and integer operations. As the FUs in a single pipeline stage operate in SIMD, each stage requires only a single configuration register. Results from each FU are written to its associated register. PRs in each lane are chained together across pipeline stages to allow live values propagate between stages within the same lane. Cross-lane communication between FUs is captured using two types of intra-PCU networks: a reduction tree network that allows reducing values from multiple lanes into a single scalar, and a shift network which allows using PRs as sliding windows across stages to exploit reuse in stencil applications. Both networks use dedicated registers within PRs to minimize hardware overhead.

PCUs interface with the global interconnect using three kinds of inputs and outputs (IO); scalar, vector, and control. Scalar IO is used to communicate single words of data, such as the results of Folds. Each vector IO allows communicating one word per lane in the PCU, and is used in cases such as reading and writing to scratchpads in PMUs and transmitting intermediate data across a long pipeline between multiple PCUs. Each vector and scalar input is buffered using a small FIFO. Using input FIFOs decouples data producers and consumers, and simplifies inter-PCU control logic by making it robust to input delay mismatches. Control IO is used to communicate control signals such as the start or end of execution of a PCU, or to indicate backpressure.

A reconfigurable chain of counters generates pattern iteration indices and control signals to coordinate execution. PCU execution begins when the control block enables one of the counters. Based on the application's control and data dependencies, the control block can be configured to combine multiple control signals from both local FIFOs and global control inputs to trigger PCU execution. The control block is implemented using reconfigurable combinational logic and programmable up-down counters for state machines.

Just as banking is important to feed multiple SIMD units to sustain compute throughput, N-buffering, or generalized double buffering, is just as important to support coarse-grained pipelines. As an example, the skip connections in ResNet, and the buffers that hold the outputs of each layer can be implemented using N-buffering. The PMU scratchpad can be configured to operate as an N-buffer with any of the banking modes described. N-buffers are implemented by partitioning the address space in each SRAM bank into N disjoint regions. Using write and read state information, an appropriate offset is added to each bank's local address to access the correct data.

A programmable counter chain and control block triggers PMU execution similar to the PCU. Each PMU typically contains write address calculation logic from the producer pattern, and read address calculation logic from the consumer pattern. Based on the state of the local FIFOs and external control inputs, the control block can be configured to trigger the write address computation, read address computation, or both, by enabling the appropriate counters.

Claim 1:
A computer-implemented method of transforming a high-level program (<NUM>) for mapping onto a reconfigurable data processor (<NUM>) with an array of configurable units (<NUM>), the method including:
partitioning a dataflow graph (<NUM>) of the high-level program (<NUM>) into memory allocations (<NUM>) and execution fragments (<NUM>), wherein the memory allocations (<NUM>) represent creation of logical memory spaces in on-processor and/or off-processor memories for data required to implement the dataflow graph (<NUM>), and the execution fragments (<NUM>) require operations on the data including loading the data from allocated memory and computing with the data;
designating the memory allocations (<NUM>) to virtual memory units (<NUM>) and designating the execution fragments (<NUM>) to virtual compute units (<NUM>);
partitioning the execution fragments (<NUM>) into memory fragments (<NUM>) and compute fragments (<NUM>), wherein each memory fragment of the memory fragments (<NUM>) includes an address calculation operation leading up to a memory access operation, and wherein each compute fragment of the compute fragments (<NUM>) comprises all other operations of a respective execution fragment of the execution fragments (<NUM>);
assigning the memory fragments (<NUM>) to the virtual memory units (<NUM>) and assigning the compute fragments (<NUM>) to the virtual compute units (<NUM>);
allocating the virtual memory units (<NUM>) to physical memory units (<NUM>) and allocating the virtual compute units (<NUM>) to physical compute units (<NUM>);
placing (<NUM>) the physical memory units (<NUM>) and the physical compute units (<NUM>) onto positions in the array of configurable units (<NUM>) and routing data and control networks between the placed positions; and
generating a bit file (<NUM>) with configuration data for the placed positions and the routed data and control networks, wherein the bit file (<NUM>), when loaded onto an instance of the array of configurable units (<NUM>), causes the array of configurable units (<NUM>) to implement the dataflow graph (<NUM>).