Hardware accelerator template and design framework for implementing recurrent neural networks

Hardware accelerator templates and design frameworks for implementing recurrent neural networks (RNNs) and variants thereof are described. A design framework module obtains a flow graph for an RNN algorithm. The flow graph identifies operations to be performed to implement the RNN algorithm and further identifies data dependencies between ones of the operations. The operations include matrix operations and vector operations. The design framework module maps the operations of the flow graph to an accelerator hardware template, yielding an accelerator instance comprising register transfer language code that describes how one or more matrix processing units and one or more vector processing units are to be arranged to perform the RNN algorithm. At least one of the one or more MPUs, as part of implementing the RNN algorithm, is to directly provide or directly receive a value from one of the one or more VPUs.

TECHNICAL FIELD

The disclosure relates generally to electronics, and, more specifically, embodiments relating to hardware accelerator templates and design frameworks for implementing recurrent neural networks and variants thereof.

BACKGROUND

Neural networks, which is an umbrella term including many diverse models and approaches, are a type of artificial intelligence that attempts to imitate the way a human brain works. Neural networks, at their core, work by creating connections between nodes, the computer equivalent of neurons. The organization and weights of the connections determine the output. One key feature of a neural network is that it has an ability to learn. Thus, neural networks are not just complex systems but are adaptive systems that can change their internal structure based on the information that flows through it—typically using weights.

Recurrent Neural Networks (RNNs) are one type of neural network that include recurrent connections (i.e., loops) within the network.FIG. 1is a block diagram illustrating a RNN100and an unrolled recurrent neural network150. The RNN100includes an input value (It)102, a node104(sometimes referred to as a neuron, etc.) that is executed a number of times via the recurrent connection105, and an output value (Ot)106. RNNs, within the node104, typically perform a variety operations; commonly, these are matrix operations and/or vector operations (e.g., a dense matrix*vector, or vector-wise add, multiply, hyperbolic tangent, sigmoid, etc.).

Due to such recurrent connections105, RNNs are especially useful in analyzing sequences of data. While a typical feedforward (or non-recurrent) neural network produces its output solely based on its current input, an RNN100produces its output by considering not only its current input102, but also based on the history of its previous inputs and/or outputs.

RNNs are currently utilized to provide state-of-the-art results in many applications, e.g., in language modeling. For example, the “unrolled” (or expanded) RNN150shows how multiple iterations (or copies of a node104) can use multiple input values152A-152D can be used to generate an output value154. In this case, the input values152A-152D are a sequence of words, and the RNN150can output a predicted next word in the sequence, a probability for a next word in the sequence, etc. Such predictions are particularly useful in various applications such as sentence completion, speech recognition, sentiment analysis, machine translation, etc. In the example illustrated by the unrolled RNN150, the input values152A-152D are a 3-word sequence for a sentence “a week has seven”, which is provided to the RNN150, which analyzes its inputs on a word-by-word basis, and ultimately predicts that the next word for the sentence is “days”. Thus, one of the appeals of RNNs is that they can make use of “context” via previous information, which can be applied it to a present task, such as using previous words in a sentence to assist in determining what a next word might be.

Thus, the goal of neural networks is to solve problems similar to how a human brain would. To attempt to achieve this functionality, most modern neural network implementations typically utilize a few thousand to a few million neural units and millions of connections or more. Accordingly, the training and use of such networks is extremely computationally expensive, requiring substantial requirements in terms of processing, memory, bandwidth, etc.

Thus, as the benefits of neural networks become apparent and the desire to use them increases, systems and techniques for efficiently implementing neural networks are strongly desired.

DETAILED DESCRIPTION

The following description describes hardware accelerator templates and design frameworks for implementing recurrent neural networks (RNNs) and variants thereof. In this description, numerous specific details such as logic implementations, types and interrelationships of system components, etc., may be set forth in order to provide a more thorough understanding of some embodiments. It will be appreciated, however, by one skilled in the art that the invention may be practiced without such specific details. In other instances, control structures, gate level circuits, and/or full software instruction sequences have not been shown in detail in order not to obscure the invention. Those of ordinary skill in the art, with the included descriptions, will be able to implement appropriate functionality without undue experimentation.

Throughout this description, the use of a letter character at the end of a reference numeral (corresponding to an illustrated entity) is not meant to indicate that any particular number of that entity must necessarily exist, but merely that the entity is one of potentially many similar entities. For example, matrix processing units464A-464M include both “A” and “M” letter suffixes, which means that there could be one matrix processing unit, two matrix processing units, sixteen matrix processing units, etc. Moreover, the use of dashed lines (e.g., matrix processing unit464M, vector processing unit470N), as described above, indicates that one or more of the entities could be optional; thus, in some embodiments only one vector processing unit470A is utilized, whereas in other embodiments multiple vector processing units470A-470N are utilized. Additionally, the use of different letter characters as reference suffixes for different entities is not meant to indicate that there must be different numbers of these entities. For example, although the vector processing units470A-470N and the matrix processing units464A-464M include different letter suffixes—i.e., “N” and “M”—there could be the same number (or different numbers) of these in various embodiments. Similarly, the use of the same letter character as a reference suffix for different entities is not meant to indicate that there must be the same numbers of these entities, although there could be in some embodiments.

As indicated above, RNNs have been applied to help solve a variety of problems. A “standard” version of a RNN is provided inFIG. 2, which is a block diagram illustrating exemplary compositions of a standard RNN200, a gated recurrent unit (GRU) variant210, and a long short term memory (LSTM) variant220.

The standard RNN200includes of a fully connected tan h( ) layer with recurrent connections. It accepts as inputs: (1) data at step t, It, and (2) the output of previous step Ot-1. The values W and U are dense matrices containing the neural network weights, whereas Itand Ot-1are represented as dense vectors.

Although standards RNNs200are useful, one weakness of the standard RNN200is its poor ability to learn long-term dependencies. Consider a sentence completion task for the following example input sentences (parts omitted via ellipses): “I grew up in France . . . I speak fluent French.” In the last sentence, recent information (i.e., “I speak fluent”) suggests that the next word would be a name of a language. However, to correctly predict that the language is “French,” a network has to consider information from a much earlier part of the input sentences (“I grew up in France”).

However, the standard RNN200provides fixed weights between the current input (It) and the previous history (Ot-1) in producing the current output (Ot), which tends to “forget” information from a much earlier part of the input sequence, making the standard RNN200ineffective in learning long-term dependencies.

Accordingly, advanced RNN variants, such as Gated Recurrent Unit (GRU)210and Long Short Term Memory (LSTM)220, have been developed to aim to address this long-term dependency issue.

Unlike the standard RNN200, a GRU210or LSTM220have the ability to dynamically adjust the weights on current input and a history to determine how much long-term history to keep and the new information to carry forward.

Equations are also illustrated inFIG. 2along with the node part of the standard RNN200, GRU210, and LSTM220. These equations can thus “define” the particular network, and represent how the output (Ot) is to be determined based upon the inputs. In this example, the standard RNN200has one such equation, whereas GRU210has four equations and LSTM220has six such equations.

For example, the four equations of GRU210are for an update gate, a reset gate, a new memory content, and a final memory content. In addition to each node being dependent upon the output of a previous node, it is also notable that in the case of GRU210and LSTM220, there are data dependencies between some of these equations, and thus, certain equations require the use of the output of other equations within the same node. For example, for LSTM220, the equation for Ntutilizes both ftand it, which are the outputs of other equations. Accordingly, due to these inter-node and intra-node data dependencies, the use of these types of networks can be computationally “expensive” as they are not easily implemented in a parallelizable manner.

Aside from the type of unit (or “node”) used in an RNN (e.g., standard, GRU, LSTM), there are also many other possible RNN architecture variations. For example, the number of layers, the number of hidden units per layer, which activation functions (AF) to use (i.e., tan h, sigmoid, etc.) are some of the parameters that describe an RNN variant.

As indicated above, RNNs are typically compositions of matrix and/or vector operations. Thus, although there are many possible variants of RNNs, at its core an RNN is composed of matrix and vector operations with data dependencies among them. As an example,FIG. 3illustrates the GRU computation as a composition of matrix and vector operations. In this example, the “inputs” include a “regular” input value304of xt(e.g., Itof previous figures) and an output value302from a previous node of ht-1(e.g., Otof previous figures), and each box with an M (e.g., M1, M2, etc.) represents a matrix operation to be performed, where each box with a V (e.g., V1, V2, V3) represents a vector operation. Accordingly,FIG. 3shows a visual representation of a “flow graph” of the sets of operations, the involved operands, and the dependencies between data to perform a GRU computation. For example, the xtand ht-1can be used to determine the value of rt(via rtcomputation310), which then is used in part to determine the value of ˜ht(via ˜htcomputation320), which is used along with the determined value of zt(via ztcomputation340) to determine the value of ht(via htcomputation330).

Although this example is illustrated using visual features, the same information can be determined from the GRU equations in a straightforward manner using a simple algorithm (of a type known to those of ordinary skill in the art) that identifies the types of values used in the GRU equations and the data dependencies therein. Thus, a more mathematical representation of the GRU data flow can be generated using a variety of data structures such as a graph, which is referred to herein as a “flow graph.”

Thus, the RNN variants may dictate the sizes and types of the matrix and vector operations, as well as their data dependencies. For example, matrix and vector sizes can be related to the number of hidden units in the RNN, and the activation function (AF) type (tan h, sigmoid, etc.) can relate to the type of vector operations. Thus, many matrix and vector operations in RNNs make them computationally intensive, so being able to execute RNNs as efficient as possible is of critical importance.

Accordingly, to address the need for highly-efficient executions of RNNs, embodiments disclosed herein provide a design framework that can be based on a customizable and programmable RNN hardware accelerator architecture template to enable automated development of RNN hardware accelerator instances that are specialized to meet user-provided sets of design constraints and goals while being flexible through programmability to execute arbitrary RNN variants. Thus, some embodiments enable customizable and programmable hardware accelerator instances for RNNs that can deliver extreme execution efficiency, while being able to flexibility execute arbitrary RNNs. In some embodiments, the hardware accelerator instances can be deployed using a variety of types of hardware, including but not limited to Field Programmable Gate Arrays (FPGAs) as well as Application-Specific Integrated Circuits (ASICs).

Thus, some embodiments can produce an accelerator instance optimized for a target FPGA chip with a particular number of hardware multiply and on-chip RAM resources, and some embodiments can produce an accelerator instance optimized for an ASIC for a particular market segment, programmable to support all RNN applications in this segment. For example, in embodiments where the accelerator instance comprises RTL code, the RTL code can be used as an input for a standard ASIC developmental tool (e.g., a logic synthesis tool) to generate an ASIC design.

Furthermore, in some embodiments each accelerator instance is programmable. Thus, even though the design can be customized for certain design goals, the accelerator itself can be programmed to support execution of arbitrary RNN variants. Optionally, if programmability is not needed, the framework can be configured to generate more efficient fixed-control units within the accelerator at the cost of programmability.

Thus, embodiments enable the creation of RNN accelerators that can flexibly execute a wide range of RNN variants with optimal execution efficiency for the user-provided design constraints and goals.

FIG. 4is a block diagram illustrating an exemplary design framework400and top-level architecture of a hardware accelerator template450according to some embodiments.

The design framework400is shown as including a template mapping module404, a validation module410, and an automatic-tuning416module. The design framework400can be, for example, a software application that is executed by one or more computing devices. In some embodiments, one or more of these modules are not implemented or used. As one example, in some embodiments the design framework400includes the template mapping module404but not the validation module410or automatic-tuning416module; in other embodiments, the design framework400includes the template mapping module404and the validation module410, but not the automatic-tuning416module.

As illustrated, the design framework400can take hardware (HW) design constraints402as an input. The HW design constraints402can specify what hardware should or should not be included (or utilized) by the resultant accelerator instance406. For example, the HW design constraints402can include constraints such as a number of hardware multiply and adder resources to use, a number of pipeline stages in the multiply and adder units to use, available memory bandwidths, the type and/or amounts of on-chip RAMs, etc.

The design framework400, in some embodiments, utilizes optimization goal inputs408, such as latency, throughput, power use, required layout area, etc., as inputs, which can be used when making design instances for the accelerator instance to meet the goals of the particular user.

The design framework400, in some embodiments, utilizes inputs such as a specification414of the particular RNN architecture targets, such as range of hidden unit sizes, type of activation functions (AFs), etc. In some embodiments, these inputs are not used, but in others they are used and allow the generated accelerator instances to be specialized based on their target RNN applications. Additionally or alternatively, the inputs can include dataset properties415, such as the acceptable data types (e.g., float, double), expected lengths of input sequences, type of compression techniques amenable to the data, etc. This also is used in some embodiments but not in others, but its inclusion can allow the generated accelerator instances to be specialized to their target datasets.

Given these inputs402/408/414/415, the framework400module can perform automatic tuning (via automatic tuning module416) to explore the design space to determine an optimal set of customization parameters to be used in the design.

For example, we turn toFIG. 5, which is a block diagram illustrating a table500of customizable parameters of a hardware accelerator template and a table550of auto-tuning factors according to some embodiments. Regarding the table550of auto-tuning factors, these parameters502can be applied to a customizable hardware template for RNN accelerator architecture, which will be detailed below. As shown, a variety of tuning considerations can be utilized, such as the RNN unit types (e.g., standard RNN, GRU, LTSM), RNN architecture parameters (e.g., number of layers, sizes of hidden layers), dataset properties (e.g., sizes, distribution of values), optimization goals (e.g., latency, throughput), and/or design constraints (e.g., how many multiply units, random access memories (RAMs)). The second column554shows what parameters of the hardware accelerator template may be affected by the tuning considerations552, such as the amount or configuration of various hardware blocks, e.g., matrix processing units (MPUs), vector processing units (VPUs), scratchpads (SPADs), data management units (DMUs), caches, pack/unpack units, etc.

Turning back to theFIG. 4, framework400module can include a template mapping module404that produces a customized accelerator instance (e.g., such as synthesizable register transfer language (RTL) utilizing a hardware description language (HDL) such as Verilog, VHDL, etc.) of the hardware accelerator that best meets the input constraints402and optimization goals408. Alongside the RTL, in some embodiments the framework400module also generates a compiler to program the accelerator, e.g., via providing micro-code executed by control units, as described further herein.

Aside from auto-tuning416and template mapping404, the framework400module in some embodiments also performs validations (via validation module410), which includes comparing the generated accelerator instance (e.g., RTL) against reference functional and cycle-level performance models derived from the provided inputs constraints402/goals408. This validation checks for functional correctness, as well as whether the design meets the expected performance.

As described, the template mapping module404can map the design constraints402, subject to the optimization goals408and/or RNN specs414and/or dataset properties415if they exist, to a hardware accelerator template.

One example of a hardware accelerator template450is shown at the bottom ofFIG. 4that can be used to efficiently implement RNNs and variants thereof. The hardware accelerator template450includes one or more matrix processing units464A-464M (MPUs), which includes one or more floating-point multiply-accumulate units466(FMAs, also sometimes called floating-point multiply-add units) and an MPU control unit468. The hardware accelerator template450also includes one or more vector processing units470A-470N (VPUs), which includes one or more FMAs472and/or one or more activation function blocks (for performing needed activation functions efficiently in hardware) and a VPU control unit474. As shown, the MPUs464A-464M and VPUs470A-470N may be directly connected (as shown by arrows490) to allow the MPUs464A-464M and VPUs470A-470N to pass computed data between the two, thus reducing delay due to data dependencies that would be introduced in other systems.

In some embodiments, the hardware accelerator template450also includes one or more data management units (DMUs)454A-454Z to handle data movements in and out of the accelerator, each of which can include one or more scratchpads (SPADs)456and caches ($)458.

The scratchpads can be used to keep the matrix and vector data on-chip for the MPUs and VPUs to process. The scratchpads can be multi-banked/multi-ported accordingly to deliver the necessary bandwidth to feed the need for the MPUs and VPUs. The cache can optionally be used to take advantage of data locality. For example, in applications that accept word sequences as inputs, certain words can occur more often than others. Thus, it is beneficial to cache the vector representations of these frequent words to avoid accessing them from outside of the accelerator each time they are encountered.

The DMUs also includes a pack/unpack unit462for handling various data formats, e.g., 32-bit double, 16-bit float, N-bit custom, and/or for processing compressed data, such as compressed representations of matrices.

In some embodiments, the MPU, VPU, and/or DMU includes control units (MPU control unit468, VPU control unit474, DMU control unit460) that are based on programmable micro-codes. These units can orchestrate the operations among the MPUs, VPUs, and DMU to facilitate certain composition of matrix and vector operation executions. Thus, these control units can control the flow of data and processing of data within the accelerator to perform the desired RNN.

Accordingly, the hardware accelerator template450can be viewed as a description of components that can be used in a physical hardware accelerator, in which particular component numbers, types, and/or arrangements can be determined by the template mapping module404(e.g., based upon the hardware design constraints402, optimization goals408, RNN specs, and/or dataset properties) to result in a custom, optimized hardware accelerator design that is specific to a particular application.

FIG. 6shows an example of how a 6×4 matrix multiplication (shown as600) can be mapped to two possible customized MPUs that use six floating-point multiply-and-add (FMA) units (as625) and twelve FMA units (as650).

The 6×4 matrix multiplication (shown as600) illustrates how an input vector (VecIn) can be multiplied against a matrix having 6 rows and 4 columns, to result in an output vector (VecOut). As shown, the 6 rows can be split into two grouping: rows 0-2, and rows 3-5.

The first customizable MPU625can implement this multiplication600using 6 FMAs, each of which operates upon a full row of the matrix to generate one value of the result vector (VecOut).

In contrast, the second customizable MPU650can implement the multiplication600using 12 FMAs, where groupings of two FMAs will together generate one value of the output vector by each working on two values from a row, instead of working on four values from a row, to together generate one value of the result vector (VecOut). Thus, this design can execute the 6×4 matrix multiplication faster (than the 6 FMA design625), but at the expense of requiring more hardware resources, layout size, power, etc. Accordingly, based upon the inputs402/408/414/415, the first design625could be selected when a constraint402or goal408causes a desire for fewer hardware blocks to be utilized, whereas the second design650could be selected when a constraint402or goal408causes a desire for optimal performance to be implemented.

As described above, the control units (MPU control unit468, VPU control unit474, DMU control unit460) can be based on programmable micro-codes to orchestrate the operations among the MPUs, VPUs, and DMU to facilitate certain composition of matrix and vector operation executions for the RNN.FIG. 7is a block diagram illustrating an example of how an accelerator instance with 2 VPUs, 1 MPU, and 1 DMU could be programmed to execute the GRU210computation illustrated inFIG. 2.

Each box in the figure is a micro-code command executed by the corresponding DMU702, MPU704, or VPUs706/708that is shown above it. For example, the first box for the DMU702is a “load” command of row 0 from matrix 1.

The lines connecting the boxes show data dependencies. Each micro-code command is executed when its dependencies have been resolved. The micro-codes are produced by a compiler for the accelerator (as described above with regard toFIG. 4), which can take as inputs the RNN architecture specifications414, optimization goals408, and/or dataset properties415.

Accordingly, embodiments provide a design framework for automated—as opposed to manual—development (e.g., tuning, optimization, validation) of hardware accelerators to efficiently implement RNNs.

FIG. 8is a flow diagram illustrating a flow800of operations for generating an accelerator instance to implement a recurrent neural network according to some embodiments.

The operations in this and other flow diagrams will be described with reference to the exemplary embodiments of the other figures. However, it should be understood that the operations of the flow diagrams can be performed by embodiments other than those discussed with reference to the other figures, and the embodiments discussed with reference to these other figures can perform operations different than those discussed with reference to the flow diagrams. In some embodiments, this flow600is performed by the design framework module400ofFIG. 4.

Flow800includes, at block805, obtaining a flow graph for a recurrent neural network (RNN) algorithm. The flow graph identifies a plurality of operations to be performed to implement the RNN algorithm and further identifies data dependencies between ones of the plurality of operations. The plurality of operations includes one or more matrix operations and one or more vector operations.

Optionally, in some embodiments block805includes block810, which includes computing the flow graph based upon a plurality of equations corresponding to the RNN algorithm.

Flow800also includes, at block815, mapping the plurality of operations of the flow graph to an accelerator hardware template to yield the accelerator instance comprising register transfer language code that describes how one or more matrix processing units (MPUs) and one or more vector processing units (VPUs) are to be arranged to perform the RNN algorithm. At least one of the one or more MPUs, as part of implementing the RNN algorithm, is to directly provide or directly receive a value from one of the one or more VPUs.

Optionally, in some embodiments, block815includes block820, where the mapping is based upon hardware design constraints indicating amounts or capabilities of hardware elements that can be utilized in the accelerator instance.

Optionally, in some embodiments, block815includes block825, where the mapping is based upon optimization goals indicating properties of the accelerator instance that should be optimized for.

Optionally, in some embodiments, block815includes block830, where the mapping is based upon one or more dataset properties identifying properties of the input data to be used with the accelerator instance.

Optionally, in some embodiments, block815includes block835, where the mapping further yields a compiler that is executable to program an accelerator, generated based upon the accelerator instance, to execute micro-code to implement the RNN algorithm.

Examples

According to some embodiments, a method in a design framework module implemented by an electronic device for generating an accelerator instance optimized to implement a recurrent neural network (RNN) algorithm includes: obtaining, by the design framework module, a flow graph for the RNN algorithm, the flow graph identifying a plurality of operations to be performed to implement the RNN algorithm and further identifying data dependencies between ones of the plurality of operations, wherein the plurality of operations include one or more matrix operations and one or more vector operations; and mapping, by the design framework module, the plurality of operations of the flow graph to an accelerator hardware template to yield the accelerator instance comprising register transfer language (RTL) code that describes how one or more matrix processing units (MPUs) and one or more vector processing units (VPUs) are to be arranged to perform the RNN algorithm, wherein at least one of the one or more MPUs, as part of implementing the RNN algorithm, is to directly provide or directly receive a value from one of the one or more VPUs.

In some embodiments, the obtaining comprises: computing, by the design framework module, the flow graph based upon a plurality of equations corresponding to the RNN algorithm. In some embodiments, the mapping is based upon hardware design constraints indicating amounts or capabilities of hardware elements that can be utilized in the accelerator instance. In some embodiments, the mapping is based upon optimization goals indicating properties of the accelerator instance that should be optimized for. In some embodiments, the mapping is based upon one or more dataset properties identifying properties of the input data to be used with the accelerator instance. In some embodiments, the mapping further yields a compiler that is executable to program an accelerator, generated based upon the accelerator instance, to execute micro-code to implement the RNN algorithm. In some embodiments, the compiler is to program the accelerator by causing a control unit of the accelerator to execute at least some of the micro-code. In some embodiments, the method further includes validating a performance of and functionalities of the generated accelerator instance against one or more performance and functional models derived from hardware design constraints and optimization goals. In some embodiments, the method further comprises at least one of: programming a Field Programmable Gate Array (FPGA), using the accelerator instance, to cause the FPGA to become operable to implement the RNN algorithm; and providing the RTL code to be used as an input to a logic synthesis tool to yield a circuit design for an Application-Specific Integrated Circuit. In some embodiments, the RNN algorithm is either: a gated recurrent unit (GRU) RNN variant; or a long short term memory (LSTM) RNN variant.

According to some embodiments, a non-transitory machine readable storage medium having instructions which, when executed by one or more processors of a device, cause the device to implement a design framework module to generate an accelerator instance optimized to implement a recurrent neural network (RNN) algorithm by performing operations comprising: obtaining a flow graph for the RNN algorithm, the flow graph identifying a plurality of operations to be performed to implement the RNN algorithm and further identifying data dependencies between ones of the plurality of operations, wherein the plurality of operations include one or more matrix operations and one or more vector operations; and mapping the plurality of operations of the flow graph to an accelerator hardware template to yield the accelerator instance comprising register transfer language (RTL) code that describes how one or more matrix processing units (MPUs) and one or more vector processing units (VPUs) are to be arranged to perform the RNN algorithm, wherein at least one of the one or more MPUs, as part of implementing the RNN algorithm is to directly provide or directly receive a value from one of the one or more VPUs.

In some embodiments, the obtaining comprises: computing the flow graph based upon a plurality of equations corresponding to the RNN algorithm. In some embodiments, the mapping is based upon hardware design constraints indicating amounts or capabilities of hardware elements that can be utilized in the accelerator instance. In some embodiments, the mapping is based upon optimization goals indicating properties of the accelerator instance that should be optimized for. In some embodiments, the mapping is based upon one or more dataset properties identifying properties of the input data to be used with the accelerator instance. In some embodiments, the mapping further yields a compiler that is executable to program an accelerator, generated based upon the accelerator instance, to execute micro-code to implement the RNN algorithm. In some embodiments, the compiler is to program the accelerator by causing a control unit of the accelerator to execute at least some of the micro-code. In some embodiments, the operations further comprise: validating a performance of and functionalities of the generated accelerator instance against one or more performance and functional models derived from hardware design constraints and optimization goals. In some embodiments, the operations further comprise at least one of: programming a Field Programmable Gate Array (FPGA), using the accelerator instance, to cause the FPGA to become operable to implement the RNN algorithm; and providing the RTL code to be used as an input to a logic synthesis tool to yield a circuit design for an Application-Specific Integrated Circuit. In some embodiments, the RNN algorithm is either: a gated recurrent unit (GRU) RNN variant; or a long short term memory (LSTM) RNN variant.

According to some embodiments, a device comprises: one or more processors; and one or more non-transitory machine readable storage media having instructions which, when executed by the one or more processors, cause the device to implement a design framework module that is to generate an accelerator instance optimized to implement a recurrent neural network (RNN) algorithm by performing operations comprising: obtaining a flow graph for the RNN algorithm, the flow graph identifying a plurality of operations to be performed to implement the RNN algorithm and further identifying data dependencies between ones of the plurality of operations, wherein the plurality of operations include one or more matrix operations and one or more vector operations; and mapping the plurality of operations of the flow graph to an accelerator hardware template to yield the accelerator instance comprising register transfer language (RTL) code that describes how one or more matrix processing units (MPUs) and one or more vector processing units (VPUs) are to be arranged to perform the RNN algorithm, wherein at least one of the one or more MPUs, as part of implementing the RNN algorithm is to directly provide or directly receive a value from one of the one or more VPUs.

According to some embodiments, a system comprises: a device comprising one or more processors and one or more non-transitory machine readable storage media having instructions which, when executed by the one or more processors, cause the device to implement a design framework module that is to generate an accelerator instance optimized to implement a recurrent neural network (RNN) algorithm by performing operations comprising: obtaining a flow graph for the RNN algorithm, the flow graph identifying a plurality of operations to be performed to implement the RNN algorithm and further identifying data dependencies between ones of the plurality of operations, wherein the plurality of operations include one or more matrix operations and one or more vector operations; and mapping the plurality of operations of the flow graph to an accelerator hardware template to yield the accelerator instance comprising register transfer language (RTL) code that describes how one or more matrix processing units (MPUs) and one or more vector processing units (VPUs) are to be arranged to perform the RNN algorithm, wherein at least one of the one or more MPUs, as part of implementing the RNN algorithm is to directly provide or directly receive a value from one of the one or more VPUs.

According to some embodiments, a device comprises: a first means for obtaining a flow graph for a recurrent neural network (RNN) algorithm, the flow graph identifying a plurality of operations to be performed to implement the RNN algorithm and further identifying data dependencies between ones of the plurality of operations, wherein the plurality of operations include one or more matrix operations and one or more vector operations; and a second means for mapping the plurality of operations of the flow graph to an accelerator hardware template to yield the accelerator instance comprising register transfer language (RTL) code that describes how one or more matrix processing units (MPUs) and one or more vector processing units (VPUs) are to be arranged to perform the RNN algorithm, wherein at least one of the one or more MPUs, as part of implementing the RNN algorithm is to directly provide or directly receive a value from one of the one or more VPUs.

Embodiments disclosed herein utilize electronic devices. An electronic device stores and transmits (internally and/or with other electronic devices over a network) code (which is composed of software instructions and which is sometimes referred to as computer program code or a computer program) and/or data using machine-readable media (also called computer-readable media), such as machine-readable storage media (e.g., magnetic disks, optical disks, read only memory (ROM), flash memory devices, phase change memory) and machine-readable transmission media (also called a carrier) (e.g., electrical, optical, radio, acoustical or other form of propagated signals—such as carrier waves, infrared signals). Thus, an electronic device (e.g., a computer) includes hardware and software, such as one or more processors coupled to one or more machine-readable storage media to store code for execution on the processor(s) and/or to store data. For instance, an electronic device may include non-volatile memory containing the code since the non-volatile memory can persist code/data even when the electronic device is turned off (when power is removed), and while the electronic device is turned on that part of the code that is to be executed by the processor(s) of that electronic device is typically copied from the slower non-volatile memory into volatile memory (e.g., dynamic random access memory (DRAM), static random access memory (SRAM)) of that electronic device. Typical electronic devices also include a set or one or more physical network interface(s) to establish network connections (to transmit and/or receive code and/or data using propagating signals) with other electronic devices. One or more parts of an embodiment of the invention may be implemented using different combinations of software, firmware, and/or hardware.

Exemplary Accelerator Architectures

Overview

In some implementations, an accelerator is coupled to processor cores or other processing elements to accelerate certain types of operations such as graphics operations, machine-learning operations, pattern analysis operations, and (as described in detail below) sparse matrix multiplication operations, to name a few. The accelerator may be communicatively coupled to the processor/cores over a bus or other interconnect (e.g., a point-to-point interconnect) or may be integrated on the same chip as the processor and communicatively coupled to the cores over an internal processor bus/interconnect. Regardless of the manner in which the accelerator is connected, the processor cores may allocate certain processing tasks to the accelerator (e.g., in the form of sequences of instructions or tops) which includes dedicated circuitry/logic for efficiently processing these tasks.

FIG. 9illustrates an exemplary implementation in which an accelerator900is communicatively coupled to a plurality of cores910-911through a cache coherent interface930. Each of the cores910-911includes a translation lookaside buffer912-913for storing virtual to physical address translations and one or more caches914-915(e.g., L1 cache, L2 cache, etc.) for caching data and instructions. A memory management unit920manages access by the cores910-911to system memory950which may be a dynamic random access memory DRAM. A shared cache926such as an L3 cache may be shared among the processor cores910-911and with the accelerator900via the cache coherent interface930. In one implementation, the cores ATA1010T-1011, MMU920and cache coherent interface930are integrated on a single processor chip.

The illustrated accelerator900includes a data management unit905with a cache907and scheduler AT006for scheduling operations to a plurality of processing elements901-902, N. In the illustrated implementation, each processing element has its own local memory903-904, N. As described in detail below, each local memory903-904, N may be implemented as a stacked DRAM.

In one implementation, the cache coherent interface930provides cache-coherent connectivity between the cores910-911and the accelerator900, in effect treating the accelerator as a peer of the cores910-911. For example, the cache coherent interface930may implement a cache coherency protocol to ensure that data accessed/modified by the accelerator900and stored in the accelerator cache907and/or local memories903-904, N is coherent with the data stored in the core caches910-911, the shared cache926and the system memory950. For example, the cache coherent interface930may participate in the snooping mechanisms used by the cores910-911and MMU920to detect the state of cache lines within the shared cache926and local caches914-915and may act as a proxy, providing snoop updates in response to accesses and attempted modifications to cache lines by the processing elements901-902, N. In addition, when a cache line is modified by the processing elements901-902, N, the cache coherent interface930may update the status of the cache lines if they are stored within the shared cache926or local caches914-915.

In one implementation, the data management unit1005includes memory management circuitry providing the accelerator900access to system memory950and the shared cache926. In addition, the data management unit905may provide updates to the cache coherent interface930and receiving updates from the cache coherent interface930as needed (e.g., to determine state changes to cache lines). In the illustrated implementation, the data management unit905includes a scheduler905for scheduling instructions/operations to be executed by the processing elements901-902, N. To perform its scheduling operations, the scheduler906may evaluate dependences between instructions/operations to ensure that instructions/operations are executed in a coherent order (e.g., to ensure that a first instruction executes before a second instruction which is dependent on results from the first instruction). Instructions/operations which are not inter-dependent may be executed in parallel on the processing elements901-902, N.

Accelerator Architecture for Matrix and Vector Operations

FIG. 10illustrates another view of accelerator900and other components previously described including a data management unit905, a plurality of processing elements901-N, and fast on-chip storage1000(e.g., implemented using stacked local DRAM in one implementation). In one implementation, the accelerator900is a hardware accelerator architecture and the processing elements901-N include circuitry for performing matrix*vector and vector*vector operations, including operations for sparse/dense matrices. In particular, the processing elements901-N may include hardware support for column and row-oriented matrix processing and may include microarchitectural support for a “scale and update” operation such as that used in machine learning (ML) algorithms.

The described implementations perform matrix/vector operations which are optimized by keeping frequently used, randomly accessed, potentially sparse (e.g., gather/scatter) vector data in the fast on-chip storage1000and maintaining large, infrequently used matrix data in off-chip memory (e.g., system memory950), accessed in a streaming fashion whenever possible, and exposing intra/inter matrix block parallelism to scale up.

Implementations of the processing elements901-N process different combinations of sparse matrixes, dense matrices, sparse vectors, and dense vectors. As used herein, a “sparse” matrix or vector is a matrix or vector in which most of the elements are zero. By contrast, a “dense” matrix or vector is a matrix or vector in which most of the elements are non-zero. The “sparsity” of a matrix/vector may be defined based on the number of zero-valued elements divided by the total number of elements (e.g., m×n for an m×n matrix). In one implementation, a matrix/vector is considered “sparse” if its sparsity if above a specified threshold.

An exemplary set of operations performed by the processing elements901-N is illustrated in the table inFIG. 11. In particular the operation types include a first multiply1100using a sparse matrix, a second multiply1101using a dense matrix, a scale and update operation1102mand a dot product operation1103. Columns are provided for a first input operand1110and a second input operand1111(each of which may include sparse or dense matrix/vector); an output format1113(e.g., dense vector or scalar); a matrix data format (e.g., compressed sparse row, compressed sparse column, row-oriented, etc.); and an operation identifier1114.

The runtime-dominating compute patterns found in some current workloads include variations of matrix multiplication against a vector in row-oriented and column-oriented fashion. They work on well-known matrix formats: compressed sparse row (CSR) and compressed sparse column (CSC).FIG. 12adepicts an example of a multiplication between a sparse matrix A against a vector x to produce a vector y.FIG. 12billustrates the CSR representation of matrix A in which each value is stored as a (value, row index) pair. For example, the (3,2) for row0 indicates that a value of 3 is stored in element position 2 for row 0.FIG. 12cillustrates a CSC representation of matrix A which uses a (value, column index) pair.

FIGS. 13a, 13b, and 13cillustrate pseudo code of each compute pattern, which is described below in detail. In particular,FIG. 13aillustrates a row-oriented sparse matrix dense vector multiply (spMdV_csr);FIG. 13billustrates a column-oriented sparse matrix sparse vector multiply (spMspC_csc); andFIG. 13cillustrates a scale and update operation (scale_update).

This is a well-known compute pattern that is important in many application domains such as high-performance computing. Here, for each row of matrix A, a dot product of that row against vector x is performed, and the result is stored in the y vector element pointed to by the row index. This computation is used in a machine-learning (ML) algorithm that performs analysis across a set of samples (i.e., rows of the matrix). It may be used in techniques such as “mini-batch.” There are also cases where ML algorithms perform only a dot product of a sparse vector against a dense vector (i.e., an iteration of the spMdV_csr loop), such as in the stochastic variants of learning algorithms.

A known factor that can affect performance on this computation is the need to randomly access sparse x vector elements in the dot product computation. For a conventional server system, when the x vector is large, this would result in irregular accesses (gather) to memory or last level cache.

To address this, one implementation of a processing element divides matrix A into column blocks and the x vector into multiple subsets (each corresponding to an A matrix column block). The block size can be chosen so that the x vector subset can fit on chip. Hence, random accesses to it can be localized on-chip.

This pattern that multiplies a sparse matrix against a sparse vector is not as well-known as spMdV_csr. However, it is important in some ML algorithms. It is used when an algorithm works on a set of features, which are represented as matrix columns in the dataset (hence, the need for column-oriented matrix accesses).

In this compute pattern, each column of the matrix A is read and multiplied against the corresponding non-zero element of vector x. The result is used to update partial dot products that are kept at the y vector. After all the columns associated with non-zero x vector elements have been processed, the y vector will contain the final dot products.

While accesses to matrix A is regular (i.e., stream in columns of A), the accesses to the y vector to update the partial dot products is irregular. The y element to access depends on the row index of the A vector element being processed. To address this, the matrix A can be divided into row blocks. Consequently, the vector y can be divided into subsets corresponding to these blocks. This way, when processing a matrix row block, it only needs to irregularly access (gather/scatter) its y vector subset. By choosing the block size properly, the y vector subset can be kept on-chip.

C. Scale and Update (scale_update)

This pattern is typically used by ML algorithms to apply scaling factors to each sample in the matrix and reduced them into a set of weights, each corresponding to a feature (i.e., a column in A). Here, the x vector contains the scaling factors. For each row of matrix A (in CSR format), the scaling factors for that row are read from the x vector, and then applied to each element of A in that row. The result is used to update the element of y vector. After all rows have been processed, the y vector contains the reduced weights.

Similar to prior compute patterns, the irregular accesses to the y vector could affect performance when y is large. Dividing matrix A into column blocks and y vector into multiple subsets corresponding to these blocks can help localize the irregular accesses within each y subset.

One implementation includes a hardware accelerator1000that can efficiently perform the compute patterns discussed above. The accelerator1000is a hardware IP block that can be integrated with general purpose processors, similar to those found in existing accelerator-based solutions (e.g., IBM® PowerEN, Oracle® M7). In one implementation, the accelerator900independently accesses memory950through an interconnect shared with the processors to perform the compute patterns. It supports any arbitrarily large matrix datasets that reside in off-chip memory.

FIG. 14illustrates the processing flow for one implementation of the data management unit905and the processing elements901-902. In this implementation, the data management unit905includes a processing element scheduler1401, a read buffer1402, a write buffer1403and a reduction unit1404. Each PE901-902includes an input buffer1405-1406, a multiplier1407-1408, an adder1409-1410, a local RAM1421-1422, a sum register1411-1412, and an output buffer1413-1414.

The accelerator supports the matrix blocking schemes discussed above (i.e., row and column blocking) to support any arbitrarily large matrix data. The accelerator is designed to process a block of matrix data. Each block is further divided into sub-blocks which are processed in parallel by the Pes901-902.

In operation, the data management unit905reads the matrix rows or columns from the memory subsystem into its read buffer1402, which is then dynamically distributed by the PE scheduler1401across PEs901-902for processing. It also writes results to memory from its write buffer1403.

Each PE901-902is responsible for processing a matrix sub-block. A PE contains an on-chip RAM1421-1422to store the vector that needs to be accessed randomly (i.e., a subset of x or y vector, as described above). It also contains a floating point multiply-accumulate (FMA) unit including multiplier1407-1408and adder1409-1410and unpack logic within input buffers1405-1406to extract matrix elements from input data, and a sum register1411-1412to keep the accumulated FMA results.

One implementation of the accelerator achieves extreme efficiencies because (1) it places irregularly accessed (gather/scatter) data in on-chip PE RAMs1421-1422, (2) it utilizes a hardware PE scheduler1401to ensure PEs are well utilized, and (3) unlike with general purpose processors, the accelerator consists of only the hardware resources that are essential for sparse matrix operations. Overall, the accelerator efficiently converts the available memory bandwidth provided to it into performance.

Scaling of performance can be done by employing more PEs in an accelerator block to process multiple matrix subblocks in parallel, and/or employing more accelerator blocks (each has a set of PEs) to process multiple matrix blocks in parallel. A combination of these options is considered below. The number of PEs and/or accelerator blocks should be tuned to match the memory bandwidth.

One implementation of the accelerator900can be programmed through a software library (similar to Intel® Math Kernel Library). Such library prepares the matrix data in memory, sets control registers in the accelerator900with information about the computation (e.g., computation type, memory pointer to matrix data), and starts the accelerator. Then, the accelerator independently accesses matrix data in memory, performs the computation, and writes the results back to memory for the software to consume.

The accelerator handles the different compute patterns by setting its PEs to the proper datapath configuration, as depicted inFIGS. 15a-15b. In particular,FIG. 15ahighlights paths (using dotted lines) for spMspV_csc and scale_update operations andFIG. 15billustrates paths for a spMdV_csr operation. The accelerator operation to perform each compute pattern is detailed below.

For spMspV_csc, the initial y vector subset is loaded in to PE's RAM1421by the DMU905. It then reads x vector elements from memory. For each x element, the DMU905streams the elements of the corresponding matrix column from memory and supplies them to the PE901. Each matrix element contains a value (A.val) and an index (A.idx) which points to the y element to read from PE's RAM1421. The DMU1005also provides the x vector element (x.val) that is multiplied against A.val by the multiply-accumulate (FMA) unit. The result is used to update the y element in the PE's RAM pointed to by A.idx. Note that even though not used by our workloads, the accelerator also supports column-wise multiplication against a dense x vector (spMdV_csc) by processing all matrix columns instead of only a subset (since x is dense).

The scale_update operation is similar to the spMspV_csc, except that the DMU905reads the rows of an A matrix represented in a CSR format instead of a CSC format. For the spMdV_csr, the x vector subset is loaded in to the PE's RAM1421. DMU905streams in matrix row elements (i.e., {A.val,A.idx} pairs) from memory. A.idx is used to read the appropriate x vector element from RAM1421, which is multiplied against A.val by the FMA. Results are accumulated into the sum register1412. The sum register is written to the output buffer each time a PE sees a marker indicating an end of a row, which is supplied by the DMU905. In this way, each PE produces a sum for the row sub-block it is responsible for. To produce the final sum for the row, the sub-block sums produced by all the PEs are added together by the Reduction Unit1404in the DMU (seeFIG. 14). The final sums are written to the output buffer1413-1414, which the DMU1005then writes to memory.

Graph Data Processing

In one implementation, the accelerator architectures described herein are configured to process graph data. Graph analytics relies on graph algorithms to extract knowledge about the relationship among data represented as graphs. The proliferation of graph data (from sources such as social media) has led to strong demand for and wide use of graph analytics. As such, being able to do graph analytics as efficient as possible is of critical importance.

To address this need, one implementation automatically maps a user-defined graph algorithm to a hardware accelerator architecture “template” that is customized to the given input graph algorithm. The accelerator may comprise the architectures described above and may be implemented as a FPGA/ASIC, which can execute with extreme efficiency. In summary, one implementation includes:

(1) a hardware accelerator architecture template that is based on a generalized sparse matrix vector multiply (GSPMV) accelerator. It supports arbitrary graph algorithm because it has been shown that graph algorithm can be formulated as matrix operations.

(2) an automatic approach to map and tune a widely-used “vertex centric” graph programming abstraction to the architecture template.

There are existing sparse matrix multiply hardware accelerators, but they do not support customizability to allow mapping of graph algorithms.

One implementation of the design framework operates as follows.

(1) A user specifies a graph algorithm as “vertex programs” following vertex-centric graph programming abstraction. This abstraction is chosen as an example here due to its popularity. A vertex program does not expose hardware details, so users without hardware expertise (e.g., data scientists) can create it.

(2) Along with the graph algorithm in (1), one implementation of the framework accepts the following inputs:

c. The properties of the target graph data (e.g., type of graph) or the graph data itself. This is optional, and is used to aid in automatic tuning.

(3) Given above inputs, one implementation of the framework performs auto-tuning to determine the set of customizations to apply to the hardware template to optimize for the input graph algorithm, map these parameters onto the architecture template to produce an accelerator instance in synthesizable RTL, and conduct functional and performance validation of the generated RTL against the functional and performance software models derived from the input graph algorithm specification.

In one implementation, the accelerator architecture described above is extended to support execution of vertex programs by (1) making it a customizable hardware template and (2) supporting the functionalities needed by vertex program. Based on this template, a design framework is described to map a user-supplied vertex program to the hardware template to produce a synthesizable RTL (e.g., Verilog) implementation instance optimized for the vertex program. The framework also performs automatic validation and tuning to ensure the produced RTL is correct and optimized. There are multiple use cases for this framework. For example, the produced synthesizable RTL can be deployed in an FPGA platform (e.g., Xeon-FPGA) to efficiently execute the given vertex program. Or, it can be refined further to produce an ASIC implementation.

It has been shown that graphs can be represented as adjacency matrices, and graph processing can be formulated as sparse matrix operations.FIGS. 16a-16bshows an example of representing a graph as an adjacency matrix. Each non-zero in the matrix represents an edge among two nodes in the graph. For example, a 1 in row 0 column 2 represents an edge from node A to C.

One of the most popular models for describing computations on graph data is the vertex programming model. One implementation supports the vertex programming model variant from Graphmat software framework, which formulates vertex programs as generalized sparse matrix vector multiply (GSPMV). As shown inFIG. 16c, a vertex program consists of the types of data associated with edges/vertices in the graph (edata/vdata), messages sent across vertices in the graph (mdata), and temporary data (tdata) (illustrated in the top portion of program code); and stateless user-defined compute functions using pre-defined APIs that read and update the graph data (as illustrated in the bottom portion of program code).

FIG. 16dillustrates exemplary program code for executing a vertex program. Edge data is represented as an adjacency matrix A (as inFIG. 16b), vertex data as vector y, and messages as sparse vector x.FIG. 16eshows the GSPMV formulation, where the multiply( ) and add( ) operations in SPMV is generalized by user-defined PROCESS_MSG( ) and REDUCE( ).

One observation here is that the GSPMV variant needed to execute vertex program performs a column-oriented multiplication of sparse matrix A (i.e., adjacency matrix) against a sparse vector x (i.e., messages) to produce an output vector y (i.e., vertex data). This operation is referred to as col_spMspV (previously described with respect to the above accelerator).

One implementation of the framework is shown inFIG. 17which includes a template mapping component1711, a validation component1712and an automatic tuning component1713. Its inputs are a user-specified vertex program1701, design optimization goals1703(e.g., max performance, min area), and target hardware design constraints1702(e.g., maximum amount of on-chip RAMs, memory interface width). As an optional input to aid automatic-tuning, the framework also accepts graph data properties1704(e.g., type=natural graph) or a sample graph data.

Given these inputs, the template mapping component1711of the framework maps the input vertex program to a hardware accelerator architecture template, and produces an RTL implementation1705of the accelerator instance optimized for executing the vertex program1701. The automatic tuning component1713performs automatic tuning1713to optimize the generated RTL for the given design objectives, while meeting the hardware design constraints. Furthermore, the validation component1712automatically validates the generated RTL against functional and performance models derived from the inputs. Validation test benches1706and tuning reports1707are produced along with the RTL.

Generalized Sparse Matrix Vector Multiply (GSPMV) Hardware Architecture Template

One implementation of an architecture template for GSPMV is shown inFIG. 18, which is based on the accelerator architecture described above (see, e.g.,FIG. 14and associated text). Many of the components illustrated inFIG. 18are customizable (as highlighted with grey lines). In one implementation, the architecture to support execution of vertex programs has been extended as follows.

As illustrated inFIG. 18, customizable logic blocks are provided inside each PE to support PROCESS_MSG( )1910, REDUCE( )1811, APPLY1812, and SEND_MSG( )1813needed by the vertex program. In addition, one implementation provides customizable on-chip storage structures and pack/unpack logic1805to support user-defined graph data (i.e., vdata, edata, mdata, tdata). The data management unit905illustrated inFIG. 18includes a PE scheduler1401(for scheduling PEs as described above), aux buffers1801for storing active column, x data), a read buffer1402, a memory controller1803for controlling access to system memory, and a write buffer1404. In addition, in the implementation shown inFIG. 18old and new vdata and tdata is stored within the local PE memory1421. Various control state machines may be modified to support executing vertex programs, abiding to the functionalities specified by the algorithms inFIGS. 16dand16e.

The operation of each accelerator tile is summarized inFIG. 19. At1901, the y vector (vdata) is loaded to the PE RAM1421. At1902, the x vector and column pointers are loaded to the aux buffer1801. At1903, for each x vector element, the A column is streamed in (edata) and the PEs execute PROC_MSG( )1810and REDUCE( )1811. At1904, the PEs execute APPLY( )1812. At1905, the PEs execute SEND_MSG( )1813, producing messages, and the data management unit905writes them as x vectors in memory. At1906, the data management unit905writes the updated y vectors (vdata) stored in the PE RAMs1421back to memory. The above techniques conform to the vertex program execution algorithm shown inFIGS. 16dand 16e. To scale up performance, the architecture allows increasing the number of PEs in a tile and/or the number of tiles in the design. This way, the architecture can take advantage of multiple levels of parallelisms in the graph (i.e., across subgraphs (across blocks of adjacency matrix) or within each subgraph). The Table inFIG. 20asummarizes the customizable parameters of one implementation of the template. It is also possible to assign asymmetric parameters across tiles for optimization (e.g., one tile with more PEs than another tile).

Automatic Mapping, Validation, and Tuning

Based on the inputs, one implementation of the framework performs automatic tuning to determine the best design parameters to use to customize the hardware architecture template in order to optimize it for the input vertex program and (optionally) graph data. There are many tuning considerations, which are summarized in the table inFIG. 20b. As illustrated, these include locality of data, graph data sizes, graph compute functions, graph data structure, graph data access attributes, graph data types, and graph data patterns.

In this phase, the framework takes the template parameters determined by the tuning phase, and produces an accelerator instance by “filling” in the customizable portions of the template. The user-defined compute functions (e.g.,FIG. 16c) may be mapped from the input specification to the appropriate PE compute blocks using existing High-Level Synthesis (HLS) tools. The storage structures (e.g., RAMs, buffers, cache) and memory interfaces are instantiated using their corresponding design parameters. The pack/unpack logic may automatically be generated from the data type specifications (e.g.,FIG. 16a). Parts of the control finite state machines (FSMs) are also generated based on the provided design parameters (e.g., PE scheduling schemes).

In one implementation, the accelerator architecture instance (synthesizable RTL) produced by the template mapping is then automatically validated. To do this, one implementation of the framework derives a functional model of the vertex program to be used as the “golden” reference. Test benches are generated to compare the execution of this golden reference against simulations of the RTL implementation of the architecture instance. The framework also performs performance validation by comparing RTL simulations against analytical performance model and cycle-accurate software simulator. It reports runtime breakdown and pinpoint the bottlenecks of the design that affect performance.

Accelerator Architecture for Processing Sparse Data

Introduction

Computations on sparse datasets—vectors or matrices most of whose values are zero—are critical to an increasing number of commercially-important applications, but typically achieve only a few percent of peak performance when run on today's CPUs. In the scientific computing arena, sparse-matrix computations have been key kernels of linear solvers for decades. More recently, the explosive growth of machine learning and graph analytics has moved sparse computations into the mainstream. Sparse-matrix computations are central to many machine-learning applications and form the core of many graph algorithms.

Sparse-matrix computations tend to be memory bandwidth-limited rather than compute-limited, making it difficult for CPU changes to improve their performance. They execute few operations per matrix data element and often iterate over an entire matrix before re-using any data, making caches ineffective. In addition, many sparse-matrix algorithms contain significant numbers of data-dependent gathers and scatters, such as the result[row]+=matrix[row][i].value*vector[matrix[row][i].index] operation found in sparse matrix-vector multiplication, which are hard to predict and reduce the effectiveness of prefetchers.

To deliver better sparse-matrix performance than conventional microprocessors, a system must provide significantly higher memory bandwidth than current CPUs and a very energy-efficient computing architecture. Increasing memory bandwidth makes it possible to improve performance, but the high energy/bit cost of DRAM accesses limits the amount of power available to process that bandwidth. Without an energy-efficient compute architecture, a system might find itself in the position of being unable to process the data from a high-bandwidth memory system without exceeding its power budget.

One implementation comprises an accelerator for sparse-matrix computations which uses stacked DRAM to provide the bandwidth that sparse-matrix algorithms require combined with a custom compute architecture to process that bandwidth in an energy-efficient manner.

Many applications create data sets where the vast majority of the values are zero. Finite-element methods model objects as a mesh of points where the state of each point is a function of the state of the points near it in the mesh. Mathematically, this becomes a system of equations that is represented as a matrix where each row describes the state of one point and the values in the row are zero for all of the points that do not directly affect the state of the point the row describes. Graphs can be represented as an adjacency matrix, where each element {i,j} in the matrix gives the weight of the edge between vertices i and j in the graph. Since most vertexes connect to only a small fraction of the other vertices in the graph, the vast majority of the elements in the adjacency matrix are zeroes. In machine learning, models are typically trained using datasets that consist of many samples, each of which contains a set of features (observations of the state of a system or object) and the desired output of the model for that set of features. It is very common for most of the samples to only contain a small subset of the possible features, for example when the features represent different words that might be present in a document, again creating a dataset where most of the values are zero.

Datasets where most of the values are zero are described as “sparse,” and it is very common for sparse datasets to be extremely sparse, having non-zero values in less than 1% of their elements. These datasets are often represented as matrices, using data structures that only specify the values of the non-zero elements in the matrix. While this increases the amount of space required to represent each non-zero element, since it is necessary to specify both the element's location and its value, the overall space (memory) savings can be substantial if the matrix is sparse enough. For example, one of the most straightforward representations of a sparse matrix is the coordinate list (COO) representation, in which each non-zero is specified by a {row index, column index, value} tuple. While this triples the amount of storage required for each non-zero value, if only 1% of the elements in a matrix have non-zero values, the COO representation will take up only 3% of the space that a dense representation (one that represents the value of each element in the matrix) would take.

FIG. 21illustrates one of the most common sparse-matrix formats, the compressed row storage (CRS, sometimes abbreviated CSR) format. In CRS format, the matrix2100is described by three arrays: a values array2101, which contains the values of the non-zero elements, an indices array2102, which specifies the position of each non-zero element within its row of the matrix, and a row starts array2103, which specifies where each row of the matrix starts in the lists of indices and values. Thus, the first non-zero element of the second row of the example matrix can be found at position 2 in the indices and values arrays, and is described by the tuple {0, 7}, indicating that the element occurs at position 0 within the row and has value 7. Other commonly-used sparse-matrix formats include compressed sparse column (CSC), which is the column-major dual to CRS, and ELLPACK, which represents each row of the matrix as a fixed-width list of non-zero values and their indices, padding with explicit zeroes when a row has fewer non-zero elements than the longest row in the matrix.

Computations on sparse matrices have the same structure as their dense-matrix counterparts, but the nature of sparse data tends to make them much more bandwidth-intensive than their dense-matrix counterparts. For example, both the sparse and dense variants of matrix-matrix multiplication find C=A·B by computing Ci,j=Ai,·B,j for all i, j. In a dense matrix-matrix computation, this leads to substantial data re-use, because each element of A participates in N multiply-add operations (assuming N×N matrices), as does each element of B. As long as the matrix-matrix multiplication is blocked for cache locality, this re-use causes the computation to have a low bytes/op ratio and to be compute-limited. However, in the sparse variant, each element of A only participates in as many multiply-add operations as there are non-zero values in the corresponding row of B, while each element of B only participates in as many multiply-adds as there are non-zero elements in the corresponding column of A. As the sparseness of the matrices increases, so does the bytes/op ratio, making the performance of many sparse matrix-matrix computations limited by memory bandwidth in spite of the fact that dense matrix-matrix multiplication is one of the canonical compute-bound computations.

Four operations make up the bulk of the sparse-matrix computations seen in today's applications: sparse matrix-dense vector multiplication (SpMV), sparse matrix-sparse vector multiplication, sparse matrix-sparse matrix multiplication, and relaxation/smoother operations, such as the Gauss-Seidel smoother used in Intel's implementation of the High-Performance Conjugate Gradient benchmark. These operations share two characteristics that make a sparse-matrix accelerator practical. First, they are dominated by vector dot-products, which makes it possible to implement simple hardware that can implement all four important computations. For example, a matrix-vector multiplication is performed by taking the dot-product of each row in the matrix with the vector, while a matrix-matrix multiplication takes the dot-product of each row of one matrix with each column of the other. Second, applications generally perform multiple computations on the same matrix, such as the thousands of multi-plications of the same matrix by different vectors that a support vector machine algorithm performs with training a model. This repeated use of the same matrix makes it practical to transfer matrices to/from an accelerator during program execution and/or to re-format the matrix in a way that simplifies the hardware's task, since the cost of data transfers/transformations can be amortized across many operations on each matrix.

Sparse-matrix computations typically achieve only a few percent of the peak performance of the system they run on. To demonstrate why this occurs,FIG. 22shows the steps2201-2204involved in an implementation of sparse matrix-dense vector multiplication using the CRS data format. First, at2201, the data structure that represents a row of the matrix is read out of memory, which usually involves a set of sequential reads that are easy to predict and prefetch. Second, at2202, the indices of the non-zero elements in the matrix row are used to gather the corresponding elements of the vector, which requires a number of data-dependent, hard-to-predict memory accesses (a gather operation). Moreover, these memory accesses often touch only one or two words in each referenced cache line, resulting in significant wasted bandwidth when the vector does not fit in the cache.

Third, at2203, the processor computes the dot-product of the non-zero elements of the matrix row and the corresponding elements of the vector. Finally, at2204, the result of the dot-product is written into the result vector, which is also accessed sequentially, and the program proceeds to the next row of the matrix. Note that this is a conceptual/algorithmic view of the computation, and the exact sequence of operations the program executes will depend on the processor's ISA and vector width.

This example illustrates a number of important characteristics of sparse-matrix computations. Assuming 32-bit data types and that neither the matrix nor the vector fit in the cache, computing the first element of the output row requires reading 36 bytes from DRAM, but only five compute instructions (three multiplies and two adds), for a bytes/op ratio of 7.2:1.

Memory bandwidth is not the only challenge to high-performance sparse-matrix computations, however. AsFIG. 22shows, the accesses to the vector in SpMV are data-dependent and hard to predict, exposing the latency of vector accesses to the application. If the vector does not fit in the cache, SpMV performance becomes sensitive to DRAM latency as well as bandwidth unless the processor provides enough parallelism to saturate the DRAM bandwidth even when many threads are stalled waiting for data.

Thus, an architecture for sparse-matrix computations must provide several things to be effective. It must deliver high memory bandwidth to meet the bytes/op needs of sparse computations. It must also support high-bandwidth gathers out of large vectors that may not fit in the cache. Finally, while performing enough arithmetic operations/second to keep up with DRAM bandwidth is not a challenge in and of itself, the architecture must perform those operations and all of the memory accesses they require in an energy-efficient manner in order to remain within system power budgets.

Implementations

One implementation comprises an accelerator designed to provide the three features necessary for high sparse-matrix performance: high memory bandwidth, high-bandwidth gathers out of large vectors, and energy-efficient computation. As illustrated inFIG. 23, one implementation of the accelerator includes an accelerator logic die2305and one of more stacks2301-2304of DRAM die. Stacked DRAM, which is described in more detail below, provides high memory bandwidth at low energy/bit. For example, stacked DRAMs are expected to deliver 256-512 GB/sec at 2.5 pJ/bit, while LPDDR4 DIMMs are only expected to deliver 68 GB/sec and will have an energy cost of 12 pJ/bit.

The accelerator logic chip2305at the bottom of the accelerator stack is customized to the needs of sparse-matrix computations, and is able to consume the bandwidth offered by a DRAM stack2301-2304while only expending 2-4 Watts of power, with energy consumption proportional to the bandwidth of the stack. To be conservative, a stack bandwidth of 273 GB/sec is assumed (the expected bandwidth of WIO3 stacks) for the remainder of this application. Designs based on higher-bandwidth stacks would incorporate more parallelism in order to consume the memory bandwidth.

FIG. 24illustrates one implementation of the accelerator logic chip2305, oriented from a top perspective through the stack of DRAM die2301-2304. The stack DRAM channel blocks2405towards the center of the diagram represent the through-silicon vias that connect the logic chip2305to the DRAMs2301-2304, while the memory controller blocks1410contain the logic that generates the control signals for the DRAM channels. While eight DRAM channels2405are shown in the figure, the actual number of channels implemented on an accelerator chip will vary depending on the stacked DRAMs used. Most of the stack DRAM technologies being developed provide either four or eight channels.

The dot-product engines (DPEs)2420are the computing elements of the architecture. In the particular implementation shown inFIG. 24, each set of eight DPEs is associated with a vector cache2415.FIG. 25provides a high-level overview of a DPE which contains two buffers2505-2506, two 64-bit multiply-add ALUs2510, and control logic2500. During computations, the chip control unit2500streams chunks of the data being processed into the buffer memories2505-2506. Once each buffer is full, the DPE's control logic sequences through the buffers, computing the dot-products of the vectors they contain and writing the results out to the DPE's result latch2510, which is connected in a daisy-chain with the result latches of the other DPE's to write the result of a computation back to the stack DRAM2301-2304.

In one implementation, the accelerator logic chip2405operates at approximately 1 GHz and 0.65V to minimize power consumption (although the particular operating frequency and voltage may be modified for different applications). Analysis based on 14 nm design studies shows that 32-64 KB buffers meet this frequency spec at that voltage, although strong ECC may be required to prevent soft errors. The multiply-add unit may be operated at half of the base clock rate in order to meet timing with a 0.65V supply voltage and shallow pipeline. Having two ALUs provides a throughput of one double-precision multiply-add/cycle per DPE.

At 273 GB/second and a clock rate of 1.066 MHz, the DRAM stack2301-2304delivers 256 bytes of data per logic chip clock cycle. Assuming that array indices and values are at least 32-bit quantities, this translates to 32 sparse-matrix elements per cycle (4 bytes of index+4 bytes of value=8 bytes/element), requiring that the chip perform 32 multiply-adds per cycle to keep up. (This is for matrix-vector multiplication and assumes a high hit rate in the vector cache so that 100% of the stack DRAM bandwidth is used to fetch the matrix.) The 64 DPEs shown inFIG. 24provide 2-4× the required compute throughput, allowing the chip to process data at the peak stack DRAM bandwidth even if the ALUs2510are not used 100% of the time.

In one implementation, the vector caches2415cache elements of the vector in a matrix-vector multiplication. This significantly increases the efficiency of the matrix-blocking scheme described below. In one implementation, each vector cache block contains 32-64 KB of cache, for a total capacity of 256-512 KB in an eight-channel architecture.

The chip control unit2401manages the flow of a computation and handles communication with the other stacks in an accelerator and with other sockets in the system. To reduce complexity and power consumption, the dot-product engines never request data from memory. Instead, the chip control unit2401manages the memory system, initiating transfers that push the appropriate blocks of data to each of the DPEs.

In one implementation, the stacks in a multi-stack accelerator communicate with each other via a network of KTI links2430that is implemented using the neighbor connections2431shown in the figure. The chip also provides three additional KTI links that are used to communicate with the other socket(s) in a multi-socket system. In a multi-stack accelerator, only one of the stacks' off-package KTI links2430will be active. KTI transactions that target memory on the other stacks will be routed to the appropriate stack over the on-package KTI network.

Implementing Sparse-Matrix Operations

In this section, we describe the techniques and hardware required to implement sparse matrix-dense vector and sparse matrix-sparse vector multiplication on one implementation of the accelerator. This design is also extended to support matrix-matrix multiplication, relaxation operations, and other important functions to create an accelerator that supports all of the key sparse-matrix operations.

While sparse-sparse and sparse-dense matrix-vector multiplications execute the same basic algorithm (taking the dot product of each row in the matrix and the vector), there are significant differences in how this algorithm is implemented when the vector is sparse as compared to when it is dense, which are summarized in Table 1 below.

In a sparse matrix-dense vector multiplication, the size of the vector is fixed and equal to the number of columns in the matrix. Since many of the matrices found in scientific computations average approximately 10 non-zero elements per row, it is not uncommon for the vector in a sparse matrix-dense vector multiplication to take up 5-10% as much space as the matrix itself. Sparse vectors, on the other hand, are often fairly short, containing similar numbers of non-zero values to the rows of the matrix, which makes them much easier to cache in on-chip memory.

In a sparse matrix-dense vector multiplication the location of each element in the vector is determined by its index, making it feasible to gather the vector elements that correspond to the non-zero values in a region of the matrix and to pre-compute the set of vector elements that need to be gathered for any dense vector that the matrix will be multiplied by. The location of each element in a sparse vector, however is unpredictable and depends on the distribution of non-zero elements in the vector. This makes it necessary to examine the non-zero elements of the sparse vector and of the matrix to determine which non-zeroes in the matrix correspond to non-zero values in the vector.

It is helpful to compare the indices of the non-zero elements in the matrix and the vector because the number of instructions/operations required to compute a sparse matrix-sparse vector dot-product is unpredictable and depends on the structure of the matrix and vector. For example, consider taking the dot-product of a matrix row with a single non-zero element and a vector with many non-zero elements. If the row's non-zero has a lower index than any of the non-zeroes in the vector, the dot-product only requires one index comparison. If the row's non-zero has a higher index than any of the non-zeroes in the vector, computing the dot-product requires comparing the index of the row's non-zero with every index in the vector. This assumes a linear search through the vector, which is common practice. Other searches, such as binary search, would be faster in the worst case, but would add significant overhead in the common case where the non-zeroes in the row and the vector overlap. In contrast, the number of operations required to perform a sparse matrix-dense vector multiplication is fixed and determined by the number of non-zero values in the matrix, making it easy to predict the amount of time required for the computation.

Because of these differences, one implementation of the accelerator uses the same high-level algorithm to implement sparse matrix-dense vector and sparse matrix-sparse vector multiplication, with differences in how the vector is distributed across the dot-product engines and how the dot-product is computed. Because the accelerator is intended for large sparse-matrix computations, it cannot be assumed that either the matrix or the vector will fit in on-chip memory. Instead, one implementation uses the blocking scheme outlined inFIG. 26.

In particular, in this implementation, the accelerator will divide matrices into fixed-size blocks of data2601-2602, sized to fit in the on-chip memory, and will multiply the rows in the block by the vector to generate a chunk of the output vector before proceeding to the next block. This approach poses two challenges. First, the number of non-zeroes in each row of a sparse matrix varies widely between datasets, from as low as one to as high as 46,000 in the datasets studied. This makes it impractical to assign one or even a fixed number of rows to each dot-product engine. Therefore, one implementation assigns fixed-size chunks of matrix data to each dot product engine and handles the case where a chunk contains multiple matrix rows and the case where a single row is split across multiple chunks.

The second challenge is that fetching the entire vector from stack DRAM for each block of the matrix has the potential to waste significant amounts of bandwidth (i.e., fetching vector elements for which there is no corresponding non-zero in the block). This is particularly an issue for sparse matrix-dense vector multiplication, where the vector can be a significant fraction of the size of the sparse matrix. To address this, one implementation constructs a fetch list2611-2612for each block2601-2602in the matrix, which lists the set of vector2610elements that correspond to non-zero values in the block, and only fetch those elements when processing the block. While the fetch lists must also be fetched from stack DRAM, it has been determined that the fetch list for most blocks will be a small fraction of the size of the block. Techniques such as run-length encodings may also be used to reduce the size of the fetch list.

Thus, a matrix-vector multiplication on Accelerator will involve the following sequence of operations:

1. Fetch a block of matrix data from the DRAM stack and distribute it across the dot-product engines;

2. Generate fetch list based on non-zero elements in the matrix data;

3. Fetch each vector element in the fetch list from stack DRAM and distribute it to the dot-product engines;

4. Compute the dot-product of the rows in the block with the vector and write the results out to stack DRAM; and

5. In parallel with the computation, fetch the next block of matrix data and repeat until the entire matrix has been processed.

When an accelerator contains multiple stacks, “partitions” of the matrix may be statically assigned to the different stacks and then the blocking algorithm may be executed in parallel on each partition. This blocking and broadcast scheme has the advantage that all of the memory references originate from a central control unit, which greatly simplifies the design of the on-chip network, since the network does not have to route unpredictable requests and replies between the dot product engines and the memory controllers. It also saves energy by only issuing one memory request for each vector element that a given block needs, as opposed to having individual dot product engines issue memory requests for the vector elements that they require to perform their portion of the computation. Finally, fetching vector elements out of an organized list of indices makes it easy to schedule the memory requests that those fetches require in a way that maximizes page hits in the stacked DRAM and thus bandwidth usage.

Implementing Sparse Matrix-Dense Vector Multiplication

One challenge in implementing sparse matrix-dense vector multiplication on the accelerator implementations described herein is matching the vector elements being streamed from memory to the indices of the matrix elements in each dot-product engine's buffers. In one implementation, 256 bytes (32-64 elements) of the vector arrive at the dot-product engine per cycle, and each vector element could correspond to any of the non-zeroes in the dot-product engine's matrix buffer since fixed-size blocks of matrix data were fetched into each dot-product engine's matrix buffer.

Performing that many comparisons each cycle would be prohibitively expensive in area and power. Instead, one implementation takes advantage of the fact that many sparse-matrix applications repeatedly multiply the same matrix by either the same or different vectors and pre-compute the elements of the fetch list that each dot-product engine will need to process its chunk of the matrix, using the format shown inFIG. 27. In the baseline CRS format, a matrix is described by an array of indices2702that define the position of each non-zero value within its row, an array containing the values of each non-zero2703, and an array2701that indicates where each row starts in the index and values arrays. To that, one implementation adds an array of block descriptors2705that identify which bursts of vector data each dot-product engine needs to capture in order to perform its fraction of the overall computation.

As shown inFIG. 27, each block descriptor consists of eight 16-bit values and a list of burst descriptors. The first 16-bit value tells the hardware how many burst descriptors are in the block descriptor, while the remaining seven identify the start points within the burst descriptor list for all of the stack DRAM data channels except the first. The number of these values will change depending on the number of data channels the stacked DRAM provides. Each burst descriptor contains a 24-bit burst count that tells the hardware which burst of data it needs to pay attention to and a “Words Needed” bit-vector that identifies the words within the burst that contain values the dot-processing engine needs.

The other data structure included in one implementation is an array of matrix buffer indices (MBIs)2704, one MBI per non-zero in the matrix. Each MBI gives the position at which the dense vector element that corresponds to the non-zero will be stored in the relevant dot-product engine's vector value buffer (see, e.g.,FIG. 29). When performing a sparse matrix-dense vector multiplication, the matrix buffer indices, rather than the original matrix indices, are loaded into the dot-product engine's matrix index buffer2704, and serve as the address used to look up the corresponding vector value when computing the dot product.

FIG. 28illustrates how this works for a two-row matrix that fits within the buffers of a single dot-product engine, on a system with only one stacked DRAM data channel and four-word data bursts. The original CRS representation including row start values2801, matrix indices2802and matrix values2803are shown on the left of the figure. Since the two rows have non-zero elements in columns {2, 5, 6} and {2, 4, 5}, elements 2, 4, 5, and 6 of the vector are required to compute the dot-products. The block descriptors reflect this, indicating that word 2 of the first four-word burst (element 2 of the vector) and words 0, 1, and 2 of the second four-word burst (elements 4-6 of the vector) are required. Since element 2 of the vector is the first word of the vector that the dot-product engine needs, it will go in location 0 in the vector value buffer. Element 4 of the vector will go in location 1, and so on.

The matrix buffer index array data2804holds the location within the vector value buffer where the hardware will find the value that corresponds to the non-zero in the matrix. Since the first entry in the matrix indices array has value “2”, the first entry in the matrix buffer indices array gets the value “0”, corresponding to the location where element 2 of the vector will be stored in the vector value buffer. Similarly, wherever a “4” appears in the matrix indices array, a “1” will appear in the matrix buffer indices, each “5” in the matrix indices array will have a corresponding “2” in the matrix buffer indices, and each “6” in the matrix indices array will correspond to a “3” in the matrix buffer indices.

One implementation of the invention performs the pre-computations required to support fast gathers out of dense vectors when a matrix is loaded onto the accelerator, taking advantage of the fact that the total bandwidth of a multi-stack accelerator is much greater than the bandwidth of the KTI links used to transfer data from the CPU to the accelerator. This pre-computed information increases the amount of memory required to hold a matrix by up to 75%, depending on how often multiple copies of the same matrix index occur within the chunk of the matrix mapped onto a dot-product engine. However, because the 16-bit matrix buffer indices array is fetched instead of the matrix indices array when a matrix-vector multiplication is performed, the amount of data fetched out of the stack DRAMs will often be less than in the original CRS representation, particularly for matrices that use 64-bit indices.

FIG. 29illustrates one implementation of the hardware in a dot-product engine that uses this format. To perform a matrix-vector multiplication, the chunks of the matrix that make up a block are copied into the matrix index buffer3003and matrix value buffer3005(copying the matrix buffer indices instead of the original matrix indices), and the relevant block descriptor is copied into the block descriptor buffer3002. Then, the fetch list is used to load the required elements from the dense vector and broadcast them to the dot-product engines. Each dot-product engine counts the number of bursts of vector data that go by on each data channel. When the count on a given data channel matches the value specified in a burst descriptor, the match logic3020captures the specified words and stores them in its vector value buffer3004.

FIG. 30shows the contents of the match logic3020unit that does this capturing. A latch3105captures the value on the data channel's wires when the counter matches the value in the burst descriptor. A shifter3106extracts the required words3102out of the burst3101and routes them to the right location in a line buffer3107whose size matches the rows in the vector value buffer. A load signal is generated when the burst count3101is equal to an internal counter3104. When the line buffer fills up, it is stored in the vector value buffer3004(through mux3108). Assembling the words from multiple bursts into lines in this way reduces the number of writes/cycle that the vector value buffer needs to support, reducing its size.

Once all of the required elements of the vector have been captured in the vector value buffer, the dot-product engine computes the required dot-product(s) using the ALUs3010. The control logic3001steps through the matrix index buffer3003and matrix value buffer3004in sequence, one element per cycle. The output of the matrix index buffer3003is used as the read address for the vector value buffer3004on the next cycle, while the output of the matrix value buffer3004is latched so that it reaches the ALUs3010at the same time as the corresponding value from the vector value buffer3004. For example, using the matrix fromFIG. 28, on the first cycle of the dot-product computation, the hardware would read the matrix buffer index “0” out of the matrix index buffer3003along with the value “13” from the matrix value buffer3005. On the second cycle, the value “0” from the matrix index buffer3003acts as the address for the vector value buffer3004, fetching the value of vector element “2”, which is then multiplied by “13” on cycle 3.

The values in the row starts bit-vector2901tell the hardware when a row of the matrix ends and a new one begins. When the hardware reaches the end of the row, it places the accumulated dot-product for the row in its output latch3011and begins accumulating the dot-product for the next row. The dot-product latches of each dot-product engine are connected in a daisy chain that assembles the output vector for writeback.

Implementing Sparse Matrix-Sparse Vector Multiplication

In sparse matrix-sparse vector multiplication, the vector tends to take up much less memory than in sparse matrix-dense vector multiplication, but, because it is sparse, it is not possible to directly fetch the vector element that corresponds to a given index. Instead, the vector must be searched, making it impractical to route only the elements that each dot-product engine needs to the dot-product engine and making the amount of time required to compute the dot-products of the matrix data assigned to each dot-product engine unpredictable. Because of this, the fetch list for a sparse matrix-sparse vector multiplication merely specifies the index of the lowest and highest non-zero elements in the matrix block and all of the non-zero elements of the vector between those points must be broadcast to the dot-product engines.

FIG. 31shows the details of a dot-product engine design to support sparse matrix-sparse vector multiplication. To process a block of matrix data, the indices (not the matrix buffer indices used in a sparse-dense multiplication) and values of the dot-product engine's chunk of the matrix are written into the matrix index and value buffers, as are the indices and values of the region of the vector required to process the block. The dot-product engine control logic3140then sequences through the index buffers3102-3103, which output blocks of four indices to the 4×4 comparator3120. The 4×4 comparator3120compares each of the indices from the vector3102to each of the indices from the matrix3103, and outputs the buffer addresses of any matches into the matched index queue3130. The outputs of the matched index queue3130drive the read address inputs of the matrix value buffer3105and vector value buffer3104, which output the values corresponding to the matches into the multiply-add ALU3110. This hardware allows the dot-product engine to consume at least four and as many as eight indices per cycle as long as the matched index queue3130has empty space, reducing the amount of time required to process a block of data when index matches are rare.

As with the sparse matrix-dense vector dot-product engine, a bit-vector of row starts3101identifies entries in the matrix buffers3192-3103that start a new row of the matrix. When such an entry is encountered, the control logic3140resets to the beginning of the vector index buffer ATA3202and starts examining vector indices from their lowest value, comparing them to the outputs of the matrix index buffer3103. Similarly, if the end of the vector is reached, the control logic3140advances to the beginning of the next row in the matrix index buffer3103and resets to the beginning of the vector index buffer3102. A “done” output informs the chip control unit when the dot-product engine has finished processing a block of data or a region of the vector and is ready to proceed to the next one. To simplify one implementation of the accelerator, the control logic3140will not proceed to the next block/region until all of the dot-product engines have finished processing.

In many cases, the vector buffers will be large enough to hold all of the sparse vector that is required to process the block. In one implementation, buffer space for 1,024 or 2,048 vector elements is provided, depending on whether 32- or 64-bit values are used.

When the required elements of the vector do not fit in the vector buffers, a multipass approach may be used. The control logic3140will broadcast a full buffer of the vector into each dot-product engine, which will begin iterating through the rows in its matrix buffers. When the dot-product engine reaches the end of the vector buffer before reaching the end of the row, it will set a bit in the current row position bit-vector3111to indicate where it should resume processing the row when the next region of the vector arrives, will save the partial dot-product it has accumulated in the location of the matrix values buffer3105corresponding to the start of the row unless the start of the row has a higher index value than any of the vector indices that have been processed so far, and will advance to the next row. After all of the rows in the matrix buffer have been processed, the dot-product engine will assert its done signal to request the next region of the vector, and will repeat the process until the entire vector has been read.

FIG. 32illustrates an example using specific values. At the start of the computation3201, a four-element chunk of the matrix has been written into the matrix buffers3103,3105, and a four-element region of the vector has been written into the vector buffers3102,3104. The row starts3101and current row position bit-vectors3111both have the value “1010,” indicating that the dot-product engine's chunk of the matrix contains two rows, one of which starts at the first element in the matrix buffer, and one of which starts at the third.

When the first region is processed, the first row in the chunk sees an index match at index 3, computes the product of the corresponding elements of the matrix and vector buffers (4×1=4) and writes that value into the location of the matrix value buffer3105that corresponds to the start of the row. The second row sees one index match at index 1, computes the product of the corresponding elements of the vector and matrix, and writes the result (6) into the matrix value buffer3105at the position corresponding to its start. The state of the current row position bit-vector changes to “0101,” indicating that the first element of each row has been processed and the computation should resume with the second elements. The dot-product engine then asserts its done line to signal that it is ready for another region of the vector.

When the dot-product engine processes the second region of the vector, it sees that row 1 has an index match at index 4, computes the product of the corresponding values of the matrix and vector (5×2=10), adds that value to the partial dot-product that was saved after the first vector region was processed, and outputs the result (14). The second row finds a match at index 7, and outputs the result 38, as shown in the figure. Saving the partial dot-products and state of the computation in this way avoids redundant work processing elements of the matrix that cannot possibly match indices in later regions of the vector (because the vector is sorted with indices in ascending order), without requiring significant amounts of extra storage for partial products.

Unified Dot-Product Engine Design

FIG. 33shows how the sparse-dense and sparse-sparse dot-product engines described above are combined to yield a dot-product engine that can handle both types of computations. Given the similarity between the two designs, the only required changes are to instantiate both the sparse-dense dot-product engine's match logic3311and the sparse-sparse dot-product engine's comparator3320and matched index queue3330, along with a set of multiplexors3350that determine which modules drive the read address and write data inputs of the buffers3104-3105and a multiplexor3351that selects whether the output of the matrix value buffer or the latched output of the matrix value buffer is sent to the multiply-add ALUs3110. In one implementation, these multiplexors are controlled by a configuration bit in the control unit3140that is set at the beginning of a matrix-vector multiplication and remain in the same configuration throughout the operation.

Instruction Sets

Exemplary Register Architecture

FIG. 34is a block diagram of a register architecture3400according to one embodiment of the invention. In the embodiment illustrated, there are 32 vector registers3410that are 512 bits wide; these registers are referenced as zmm0 through zmm31. The lower order 256 bits of the lower 16 zmm registers are overlaid on registers ymm0-16. The lower order 128 bits of the lower 16 zmm registers (the lower order 128 bits of the ymm registers) are overlaid on registers xmm0-15.

Write mask registers3415—in the embodiment illustrated, there are 8 write mask registers (k0 through k7), each 64 bits in size. In an alternate embodiment, the write mask registers3415are 16 bits in size. As previously described, in one embodiment of the invention, the vector mask register k0 cannot be used as a write mask; when the encoding that would normally indicate k0 is used for a write mask, it selects a hardwired write mask of 0xFFFF, effectively disabling write masking for that instruction.

Exemplary Core Architectures

In-Order and Out-Of-Order Core Block Diagram

InFIG. 35A, a processor pipeline3500includes a fetch stage3502, a length decode stage3504, a decode stage3506, an allocation stage3508, a renaming stage3510, a scheduling (also known as a dispatch or issue) stage3512, a register read/memory read stage3514, an execute stage3516, a write back/memory write stage3518, an exception handling stage3522, and a commit stage3524.

FIG. 35Bshows processor core3590including a front end unit3530coupled to an execution engine unit3550, and both are coupled to a memory unit3570. The core3590may be a reduced instruction set computing (RISC) core, a complex instruction set computing (CISC) core, a very long instruction word (VLIW) core, or a hybrid or alternative core type. As yet another option, the core3590may be a special-purpose core, such as, for example, a network or communication core, compression engine, coprocessor core, general purpose computing graphics processing unit (GPGPU) core, graphics core, or the like.

The front end unit3530includes a branch prediction unit3532coupled to an instruction cache unit3534, which is coupled to an instruction translation lookaside buffer (TLB)3536, which is coupled to an instruction fetch unit3538, which is coupled to a decode unit3540. The decode unit3540(or decoder) may decode instructions, and generate as an output one or more micro-operations, micro-code entry points, microinstructions, other instructions, or other control signals, which are decoded from, or which otherwise reflect, or are derived from, the original instructions. The decode unit3540may be implemented using various different mechanisms. Examples of suitable mechanisms include, but are not limited to, look-up tables, hardware implementations, programmable logic arrays (PLAs), microcode read only memories (ROMs), etc. In one embodiment, the core3590includes a microcode ROM or other medium that stores microcode for certain macroinstructions (e.g., in decode unit3540or otherwise within the front end unit3530). The decode unit3540is coupled to a rename/allocator unit3552in the execution engine unit3550.

The execution engine unit3550includes the rename/allocator unit3552coupled to a retirement unit3554and a set of one or more scheduler unit(s)3556. The scheduler unit(s)3556represents any number of different schedulers, including reservations stations, central instruction window, etc. The scheduler unit(s)3556is coupled to the physical register file(s) unit(s)3558. Each of the physical register file(s) units3558represents one or more physical register files, different ones of which store one or more different data types, such as scalar integer, scalar floating point, packed integer, packed floating point, vector integer, vector floating point, status (e.g., an instruction pointer that is the address of the next instruction to be executed), etc. In one embodiment, the physical register file(s) unit3558comprises a vector registers unit, a write mask registers unit, and a scalar registers unit. These register units may provide architectural vector registers, vector mask registers, and general purpose registers. The physical register file(s) unit(s)3558is overlapped by the retirement unit3554to illustrate various ways in which register renaming and out-of-order execution may be implemented (e.g., using a reorder buffer(s) and a retirement register file(s); using a future file(s), a history buffer(s), and a retirement register file(s); using a register maps and a pool of registers; etc.). The retirement unit3554and the physical register file(s) unit(s)3558are coupled to the execution cluster(s)3560. The execution cluster(s)3560includes a set of one or more execution units3562and a set of one or more memory access units3564. The execution units3562may perform various operations (e.g., shifts, addition, subtraction, multiplication) and on various types of data (e.g., scalar floating point, packed integer, packed floating point, vector integer, vector floating point). While some embodiments may include a number of execution units dedicated to specific functions or sets of functions, other embodiments may include only one execution unit or multiple execution units that all perform all functions. The scheduler unit(s)3556, physical register file(s) unit(s)3558, and execution cluster(s)3560are shown as being possibly plural because certain embodiments create separate pipelines for certain types of data/operations (e.g., a scalar integer pipeline, a scalar floating point/packed integer/packed floating point/vector integer/vector floating point pipeline, and/or a memory access pipeline that each have their own scheduler unit, physical register file(s) unit, and/or execution cluster—and in the case of a separate memory access pipeline, certain embodiments are implemented in which only the execution cluster of this pipeline has the memory access unit(s)3564). It should also be understood that where separate pipelines are used, one or more of these pipelines may be out-of-order issue/execution and the rest in-order.

The set of memory access units3564is coupled to the memory unit3570, which includes a data TLB unit3572coupled to a data cache unit3574coupled to a level 2 (L2) cache unit3576. In one exemplary embodiment, the memory access units3564may include a load unit, a store address unit, and a store data unit, each of which is coupled to the data TLB unit3572in the memory unit3570. The instruction cache unit3534is further coupled to a level 2 (L2) cache unit3576in the memory unit3570. The L2 cache unit3576is coupled to one or more other levels of cache and eventually to a main memory.

By way of example, the exemplary register renaming, out-of-order issue/execution core architecture may implement the pipeline3500as follows: 1) the instruction fetch3538performs the fetch and length decoding stages3502and3504; 2) the decode unit3540performs the decode stage3506; 3) the rename/allocator unit3552performs the allocation stage3508and renaming stage3510; 4) the scheduler unit(s)3556performs the schedule stage3512; 5) the physical register file(s) unit(s)3558and the memory unit3570perform the register read/memory read stage3514; the execution cluster3560perform the execute stage3516; 6) the memory unit3570and the physical register file(s) unit(s)3558perform the write back/memory write stage3518; 7) various units may be involved in the exception handling stage3522; and 8) the retirement unit3554and the physical register file(s) unit(s)3558perform the commit stage3524.

Specific Exemplary In-Order Core Architecture

FIG. 36Ais a block diagram of a single processor core, along with its connection to the on-die interconnect network3602and with its local subset of the Level 2 (L2) cache3604, according to embodiments of the invention. In one embodiment, an instruction decoder3600supports the x86 instruction set with a packed data instruction set extension. An L1 cache3606allows low-latency accesses to cache memory into the scalar and vector units. While in one embodiment (to simplify the design), a scalar unit3608and a vector unit3610use separate register sets (respectively, scalar registers3612and vector registers3614) and data transferred between them is written to memory and then read back in from a level 1 (L1) cache3606, alternative embodiments of the invention may use a different approach (e.g., use a single register set or include a communication path that allow data to be transferred between the two register files without being written and read back).

FIG. 36Bis an expanded view of part of the processor core inFIG. 36Aaccording to embodiments of the invention.FIG. 36Bincludes an L1 data cache3606A part of the L1 cache3604, as well as more detail regarding the vector unit3610and the vector registers3614. Specifically, the vector unit3610is a 16-wide vector processing unit (VPU) (see the 16-wide ALU3628), which executes one or more of integer, single-precision float, and double-precision float instructions. The VPU supports swizzling the register inputs with swizzle unit3620, numeric conversion with numeric convert units3622A-B, and replication with replication unit3624on the memory input. Write mask registers3626allow predicating resulting vector writes.

FIG. 37is a block diagram of a processor3700that may have more than one core, may have an integrated memory controller, and may have integrated graphics according to embodiments of the invention. The solid lined boxes inFIG. 37illustrate a processor3700with a single core3702A, a system agent3710, a set of one or more bus controller units3716, while the optional addition of the dashed lined boxes illustrates an alternative processor3700with multiple cores3702A-N, a set of one or more integrated memory controller unit(s)3714in the system agent unit3710, and special purpose logic3708.

The memory hierarchy includes one or more levels of cache within the cores, a set or one or more shared cache units3706, and external memory (not shown) coupled to the set of integrated memory controller units3714. The set of shared cache units3706may include one or more mid-level caches, such as level 2 (L2), level 3 (L3), level 4 (L4), or other levels of cache, a last level cache (LLC), and/or combinations thereof. While in one embodiment a ring based interconnect unit3712interconnects the special purpose logic3708(e.g., integrated graphics logic), the set of shared cache units3706, and the system agent unit3710/integrated memory controller unit(s)3714, alternative embodiments may use any number of well-known techniques for interconnecting such units. In one embodiment, coherency is maintained between one or more cache units3706and cores3702-A-N.

In some embodiments, one or more of the cores3702A-N are capable of multithreading. The system agent3710includes those components coordinating and operating cores3702A-N. The system agent unit3710may include for example a power control unit (PCU) and a display unit. The PCU may be or include logic and components needed for regulating the power state of the cores3702A-N and the integrated graphics logic3708. The display unit is for driving one or more externally connected displays.

Exemplary Computer Architectures

Referring now toFIG. 38, shown is a block diagram of a system3800in accordance with one embodiment of the present invention. The system3800may include one or more processors3810,3815, which are coupled to a controller hub3820. In one embodiment, the controller hub3820includes a graphics memory controller hub (GMCH)3890and an Input/Output Hub (IOH)3850(which may be on separate chips); the GMCH3890includes memory and graphics controllers to which are coupled memory3840and a coprocessor3845; the IOH3850couples input/output (I/O) devices3860to the GMCH3890. Alternatively, one or both of the memory and graphics controllers are integrated within the processor (as described herein), the memory3840and the coprocessor3845are coupled directly to the processor3810, and the controller hub3820in a single chip with the IOH3850.

The optional nature of additional processors3815is denoted inFIG. 38with broken lines. Each processor3810,3815may include one or more of the processing cores described herein and may be some version of the processor3700.

The memory3840may be, for example, dynamic random access memory (DRAM), phase change memory (PCM), or a combination of the two. For at least one embodiment, the controller hub3820communicates with the processor(s)3810,3815via a multi-drop bus, such as a frontside bus (FSB), point-to-point interface such as QuickPath Interconnect (QPI), or similar connection3895.

In one embodiment, the coprocessor3845is a special-purpose processor, such as, for example, a high-throughput MIC processor, a network or communication processor, compression engine, graphics processor, GPGPU, embedded processor, or the like. In one embodiment, controller hub3820may include an integrated graphics accelerator.

There can be a variety of differences between the physical resources3810,3815in terms of a spectrum of metrics of merit including architectural, microarchitectural, thermal, power consumption characteristics, and the like.

In one embodiment, the processor3810executes instructions that control data processing operations of a general type. Embedded within the instructions may be coprocessor instructions. The processor3810recognizes these coprocessor instructions as being of a type that should be executed by the attached coprocessor3845. Accordingly, the processor3810issues these coprocessor instructions (or control signals representing coprocessor instructions) on a coprocessor bus or other interconnect, to coprocessor3845. Coprocessor(s)3845accept and execute the received coprocessor instructions.

Referring now toFIG. 39, shown is a block diagram of a first more specific exemplary system3900in accordance with an embodiment of the present invention. As shown inFIG. 39, multiprocessor system3900is a point-to-point interconnect system, and includes a first processor3970and a second processor3980coupled via a point-to-point interconnect3950. Each of processors3970and3980may be some version of the processor3700. In one embodiment of the invention, processors3970and3980are respectively processors3810and3815, while coprocessor3938is coprocessor3845. In another embodiment, processors3970and3980are respectively processor3810coprocessor3845.

Processors3970and3980are shown including integrated memory controller (IMC) units3972and3982, respectively. Processor3970also includes as part of its bus controller units point-to-point (P-P) interfaces3976and3978; similarly, second processor3980includes P-P interfaces3986and3988. Processors3970,3980may exchange information via a point-to-point (P-P) interface3950using P-P interface circuits3978,3988. As shown inFIG. 39, IMCs3972and3982couple the processors to respective memories, namely a memory3932and a memory3934, which may be portions of main memory locally attached to the respective processors.

Processors3970,3980may each exchange information with a chipset3990via individual P-P interfaces3952,3954using point to point interface circuits3976,3994,3986,3998. Chipset3990may optionally exchange information with the coprocessor3938via a high-performance interface3992. In one embodiment, the coprocessor3938is a special-purpose processor, such as, for example, a high-throughput MIC processor, a network or communication processor, compression engine, graphics processor, GPGPU, embedded processor, or the like.

Chipset3990may be coupled to a first bus3916via an interface3996. In one embodiment, first bus3916may be a Peripheral Component Interconnect (PCI) bus, or a bus such as a PCI Express bus or another third generation I/O interconnect bus, although the scope of the present invention is not so limited.

As shown inFIG. 39, various I/O devices3914may be coupled to first bus3916, along with a bus bridge3918which couples first bus3916to a second bus3920. In one embodiment, one or more additional processor(s)3915, such as coprocessors, high-throughput MIC processors, GPGPU's, accelerators (such as, e.g., graphics accelerators or digital signal processing (DSP) units), field programmable gate arrays, or any other processor, are coupled to first bus3916. In one embodiment, second bus3920may be a low pin count (LPC) bus. Various devices may be coupled to a second bus3920including, for example, a keyboard and/or mouse3922, communication devices3927and a storage unit3928such as a disk drive or other mass storage device which may include instructions/code and data3930, in one embodiment. Further, an audio I/O3924may be coupled to the second bus3920. Note that other architectures are possible. For example, instead of the point-to-point architecture ofFIG. 39, a system may implement a multi-drop bus or other such architecture.

Referring now toFIG. 40, shown is a block diagram of a second more specific exemplary system4000in accordance with an embodiment of the present invention. Like elements inFIGS. 39 and 40bear like reference numerals, and certain aspects ofFIG. 39have been omitted fromFIG. 40in order to avoid obscuring other aspects ofFIG. 40.

FIG. 40illustrates that the processors3970,3980may include integrated memory and I/O control logic (“CL”)3972and3982, respectively. Thus, the CL3972,3982include integrated memory controller units and include I/O control logic.FIG. 40illustrates that not only are the memories3932,3934coupled to the CL3972,3982, but also that I/O devices4014are also coupled to the control logic3972,3982. Legacy I/O devices4015are coupled to the chipset3990.

Referring now toFIG. 41, shown is a block diagram of a SoC4100in accordance with an embodiment of the present invention. Similar elements inFIG. 37bear like reference numerals. Also, dashed lined boxes are optional features on more advanced SoCs. InFIG. 41, an interconnect unit(s)4102is coupled to: an application processor4110which includes a set of one or more cores3702A-N, which include cache units3704A-N, and shared cache unit(s)3706; a system agent unit3710; a bus controller unit(s)3716; an integrated memory controller unit(s)3714; a set or one or more coprocessors4120which may include integrated graphics logic, an image processor, an audio processor, and a video processor; an static random access memory (SRAM) unit4130; a direct memory access (DMA) unit4132; and a display unit4140for coupling to one or more external displays. In one embodiment, the coprocessor(s)4120include a special-purpose processor, such as, for example, a network or communication processor, compression engine, GPGPU, a high-throughput MIC processor, embedded processor, or the like.

FIG. 42is a block diagram contrasting the use of a software instruction converter to convert binary instructions in a source instruction set to binary instructions in a target instruction set according to embodiments of the invention. In the illustrated embodiment, the instruction converter is a software instruction converter, although alternatively the instruction converter may be implemented in software, firmware, hardware, or various combinations thereof.FIG. 42shows a program in a high level language4202may be compiled using an x86 compiler4204to generate x86 binary code4206that may be natively executed by a processor with at least one x86 instruction set core4216. The processor with at least one x86 instruction set core4216represents any processor that can perform substantially the same functions as an Intel processor with at least one x86 instruction set core by compatibly executing or otherwise processing (1) a substantial portion of the instruction set of the Intel x86 instruction set core or (2) object code versions of applications or other software targeted to run on an Intel processor with at least one x86 instruction set core, in order to achieve substantially the same result as an Intel processor with at least one x86 instruction set core. The x86 compiler4204represents a compiler that is operable to generate x86 binary code4206(e.g., object code) that can, with or without additional linkage processing, be executed on the processor with at least one x86 instruction set core4216. Similarly,FIG. 42shows the program in the high level language4202may be compiled using an alternative instruction set compiler4208to generate alternative instruction set binary code4210that may be natively executed by a processor without at least one x86 instruction set core4214(e.g., a processor with cores that execute the MIPS instruction set of MIPS Technologies of Sunnyvale, Calif. and/or that execute the ARM instruction set of ARM Holdings of Sunnyvale, Calif.). The instruction converter4212is used to convert the x86 binary code4206into code that may be natively executed by the processor without an x86 instruction set core4214. This converted code is not likely to be the same as the alternative instruction set binary code4210because an instruction converter capable of this is difficult to make; however, the converted code will accomplish the general operation and be made up of instructions from the alternative instruction set. Thus, the instruction converter4212represents software, firmware, hardware, or a combination thereof that, through emulation, simulation or any other process, allows a processor or other electronic device that does not have an x86 instruction set processor or core to execute the x86 binary code4206.

Though the flow diagrams in the figures show a particular order of operations performed by certain embodiments, it should be understood that such order is exemplary. Thus, alternative embodiments may perform the operations in a different order, combine certain operations, overlap certain operations, etc.