Patent Description:
Modern computing hardware is energy constrained. Reducing the energy needed to perform computations is often essential in improving performance.

For example, many of the computations performed by convolutional neural networks during inference are due to 2D convolutions. 2D convolutions entail numerous multiply-accumulate operations where most of the work is due to the multiplication of an activation and a weight. Many of these multiplications are ineffectual.

The training or running or other use of neural networks often includes the performance of a vast number of computations. Performing less computations typically results in efficiencies such as time and energy efficiencies. <NPL>, discusses that, during inference with Convolutional Neural Networks (CNNs), more than 2x to 8x ineffectual work can be exposed if instead of targeting those weights and activations that are zero, different combinations of value stream properties are targeted. A practical application with Bit-Tactical (TCL) is demonstrated, a hardware accelerator which exploits weight sparsity, per layer precision variability and dynamic fine-grain precision reduction for activations, and optionally the naturally occurring sparse effectual bit content of activations to improve performance and energy efficiency. <NPL>, discusses the following: Deep Neural Networks expose a high degree of parallelism, making them amenable to highly data parallel architectures. However, data-parallel architectures often accept inefficiency in individual computations for the sake of overall efficiency. It is shown that on average, activation values of convolutional layers during inference in modern Deep Convolutional Neural Networks (CNNs) contain <NUM>% zero bits. Processing these zero bits entails ineffectual computations that could be skipped. Pragmatic (PRA) is proposed, a massively data-parallel architecture that uses serial-parallel shift-and-add multiplication while skipping the zero bits of the serial input. <NPL>, relates to Low Complexity Multiply-Accumulate Units for Convolutional Neural Networks with Weight-Sharing.

It is the object of the present invention to provide an improved neural network accelerator tile and a method of operating same. This object is solved by the subject matter of the independent claims which define the present invention.

Other aspects and features according to the present application will become apparent to those ordinarily skilled in the art upon review of the following description of embodiments of the invention in conjunction with the accompanying figures.

The principles of the invention may better be understood with reference to the accompanying figures provided by way of illustration of an exemplary embodiment, or embodiments, incorporating principles and aspects of the present invention, and in which:.

Like reference numerals indicated like or corresponding elements in the drawings.

The description that follows, and the embodiments described therein, are provided by way of illustration of an example, or examples, of particular embodiments of the principles of the present invention. These examples are provided for the purposes of explanation, and not of limitation, of those principles and of the invention. In the description, like parts are marked throughout the specification and the drawings with the same respective reference numerals. The drawings are not necessarily to scale and in some instances proportions may have been exaggerated in order to more clearly depict certain features of the invention.

This description relates to accelerators for decomposing multiplications down to the bit level to reduce the amount of work performed, such as the amount of work performed during inference for image classification models. Such reductions can improve execution time and improve energy efficiency.

This description further relates to accelerators which can improve the execution time and energy efficiency of Deep Neural Network (DNN) inferences. Although, in some embodiments some of the work reduction potential is given up yielding a low cost, simple, and energy efficient design.

As much modern computing hardware is energy-constrained, developing techniques to reduce the amount of energy needed to perform a computation is often essential for improving performance. For example, the bulk of the work performed by most convolutional neural networks during inference is due to 2D convolutions. These convolutions involve a great many multiply-accumulate operations, for which most work is due to the multiplication of an activation A and a weight W. Reducing the number of ineffectual operations may greatly improve energy efficiency.

A variety of computational arrangements have been suggested to decompose an A × W multiplication into a collection of simpler operations. For example, if A and W are 16b fixed-point numbers, A × W can be approached as <NUM>1b × 1b multiplications or <NUM>16b × 1b multiplications.

<FIG> includes six bar graphs, one graph for each of six models used in testing a set of eight example computational arrangements. Each bar graph compares the potential reduction in work for the eight compared computational arrangements.

The leftmost bar <NUM> in each bar graph represents a first computational arrangement which avoids multiplications where the activation is zero, and is representative of the first generation of value-based accelerators which were motivated by the relatively large fraction of zero activations that occur in convolutional neural networks (see for example<NPL>).

The second bar from the left <NUM> in each graph represents a second computational arrangement which skips those multiplications where either the activation or the weight are zero, and is representative of accelerators that target sparse models where a significant fraction of synaptic connections have been pruned (see for example<NPL>).

The third and fourth bars from the left <NUM> and <NUM> represent third and fourth computational arrangements, respectively, which target precision. The third computational arrangement, represented by bar <NUM>, targets the precision of the activations (see for example<NPL> and<NPL>), and the fourth computational arrangement, represented by bar <NUM>, targets the precision of activations and weights (see for example<NPL>).

Further potential for work reduction exists if multiplication is decomposed at the bit level. For example, assuming these multiplications operate on 16b fixed-point values, the multiplication is given by equation (<NUM>) below: <MAT>.

In equation (<NUM>) above, Ai and Wi are bits of A and W respectively. When decomposed down to the individual <NUM> single bit multiplications, only those multiplications where Ai and Wi are non-zero are effectual.

The fifth and sixth bars from the left <NUM> and <NUM> represent fifth and sixth computational arrangements, respectively, which decompose multiplications into single bit multiplications. The fifth computational arrangement, represented by bar <NUM>, skips single bit multiplications where the activation bit is zero (see for example <NPL>). The sixth arrangement, represented by bar <NUM>, skips single bit multiplications where either the activation or the weight bit is zero.

However, in some arrangements rather than representing A and W as bit vectors, they can instead be Booth-encoded as signed powers of two, or higher radix terms. The seventh and eighth bars from the left <NUM> and <NUM> represent seventh and eighth computational arrangements, respectively, in which values are Booth-encoded as signed powers of two or as higher radix terms instead of being represented as bit vectors. The seventh arrangement, represented by bar <NUM>, Booth-encodes the activation values, while the eighth arrangement, represented by bar <NUM>, Booth-encodes both activation and weight values. The multiplication of activations by weights is then given by equation (<NUM>) below: <MAT>.

In equation (<NUM>) above, Ati and Wtj are of the form ±<NUM>x. As with the positional representation, it is only those products where both Ati and Wtj are non-zero that are effectual. Accordingly, <FIG> shows the potential reduction in work where ineffectual terms for a Booth-encoded activation are skipped with <NUM> (see for example <NPL>), and shows the potential reduction in work where ineffectual terms for a Booth-encoded activation and Booth-encoded weight are skipped with <NUM>.

As indicated by <FIG>, a hardware accelerator which computes only effective terms, such as effective terms of Booth-encoded activations and weights, has the potential to greatly reduce computational work. In many embodiments, configurations which target Booth-encoded computations can also be used to compute bit vector representations as well.

Computational arrangements may be used in the implementation of neural networks, such as convolutional neural networks ('CNN'). CNNs usually consist of several convolutional layers followed by a few fully connected layers, and in image processing most of the operation time is spent on processing convolutional layers in which a 3D convolution operation is applied to the input activations producing output activations. An example of a convolutional layer is shown in <FIG>, which shows a c × x × y input activation block <NUM> and a set of N c × h × k filters <NUM>. The layer dot products each of these N filters (denoted f<NUM>, f<NUM>,. , fN-<NUM>) <NUM> by a c × h × k subarray of input activation (or 'window'), such as window <NUM>, to generate a single oh × ok output activation <NUM>. Convolving N filters and an activation window results in N oh × ok outputs which will be passed to the input of the next layer. The convolution of activation windows and filters takes place in a sliding window fashion with a constant stride S. Fully connected layers can be implemented as convolutional layers in which filters and input activations have the same dimensions (x = h and y = k).

Data parallel engines, such as using 16b fixed-point activations and weights, have been suggested for use in implementing neural networks (see for example the DaDianNao accelerator disclosed in <NPL>). In an example of such an engine, which will be referred to as a BASE engine, <NUM> inner product units (IP) may be provided, each accepting <NUM> input activations and <NUM> weights as inputs. Where <NUM> IPs are used, the <NUM> input activations may be broadcast to all <NUM> IPs and each IP may receive its own <NUM> weights; every cycle each IP multiplies <NUM> input activations by their <NUM> corresponding weights and reduces them into a single partial output activation using a <NUM>32b input adder tree. The partial results may be accumulated over multiple cycles to generate the final output activation. An activation memory may provide the activations and a weight memory may provide the weights.

Variations of data parallel engines may be used to implement the computational arrangements discussed above, such as the examples shown in <FIG>.

<FIG> is a simplified schematic diagram of a bit-parallel engine <NUM>, shown multiplying two 4b activation and weight pairs, generating a single 4b output activation per cycle. 4b and other bit sizes are used in various parts of this description as examples, and other sizes may be used in other embodiments. The throughput of engine <NUM> is two 4b × 4b products per cycle.

<FIG> is a simplified schematic diagram of a bit-serial engine <NUM> (see for example <NPL>). To match the bit-parallel engine <NUM> throughput, engine <NUM> processes <NUM> input activations and <NUM> weights every cycle producing <NUM>1b × 1b products. As both activations and weights are processed bit-serially, engine <NUM> results in <NUM> output activations in Pa × Pw cycles, where Pa and Pw are the activation and weight precisions, respectively. As a result, engine <NUM> outperforms engine <NUM> by <MAT>. As depicted in <FIG>, since both activations and weights can be represented in three bits, the speedup of engine <NUM> over engine <NUM> of <FIG> is <NUM>×. Yet, engine <NUM> still processes some ineffectual terms; for example, in the first cycle <NUM> of the <NUM>1b × 1b products are zero and thus ineffectual.

<FIG> is a simplified schematic diagram of an engine <NUM> in which both the activations and weights are represented as vectors of essential powers of two (or 'one-offsets'). For example, A<NUM> = (<NUM>) is represented as a vector of its one-offsets A<NUM> = (<NUM>,<NUM>). Every cycle each processing element ('PE') accepts a 4b one-offset of an input activation and a 4b one-offset of a weight and adds them up to produce the power of the corresponding product term in the output activation. Since engine <NUM> processes activation and weights term-serially, it takes ta × tw cycles for each PE to produce the product terms of an output activation, where ta and tw are the number of one-offsets in the corresponding input activation and weight. The engine processes the next set of activation and weight one-offsets after T cycles, where T is the maximum ta × tw among all the PEs. In the example of <FIG>, the maximum T is <NUM> corresponding to the pair of A<NUM> = (<NUM>,<NUM>) and W<NUM><NUM> = (<NUM>,<NUM>,<NUM>) from PE(<NUM>,<NUM>). Thus, the engine <NUM> can start processing the next set of activations and weights after <NUM> cycles, achieving <NUM>× speedup over the bit-parallel engine <NUM> of <FIG>.

Some embodiments of the present invention are designed to minimize the required computation for producing the products of input activations and weights by processing only the essential bits of both the input activations and weights. In some embodiments, input activations and weights are converted on-the-fly into a representation which contains only the essential bits, and processes one pair of essential bits each cycle: one activation bit and one weight bit.

In some embodiments, a hardware accelerator may be provided for processing only essential bits, whether those essential bits are processed in the form of one-offsets, regular positional representations, non-fixed-point representations, or other representations of the essential bits.

In embodiments in which the essential bits are processed in the form of one-offsets, an accelerator may represent each activation or weight as a list of its one-offsets (on,. Each one-offset is represented as a (sign, magnitude) pair. For example, an activation A = -<NUM>(<NUM>) = <NUM>(<NUM>) with a Booth-encoding of <NUM>(<NUM>) would be represented as (-,<NUM>) and a A = <NUM>(<NUM>) = <NUM>(<NUM>) will be presented as ((+,<NUM>), (-,<NUM>)). The sign can be encoded using a single bit, with, for example, <NUM> representing "+" and <NUM> representing "-".

In some embodiments, a weight W = (Wterms) and an input activation A = (Aterms) are each represented as a (sign, magnitude) pair, (si,ti) and (s'i,t'i) respectively, and the product is calculated as set out in equation (<NUM>) below: <MAT>.

Implementing equation (<NUM>), instead of processing the full A × W product in a single cycle, an accelerator processes each product of a single t' term of the input activation A and of a single t term of the weight W individually. Since these terms are powers of two, their product will also be a power of two. As such, embodiments implementing equation (<NUM>) can first add the corresponding exponents t' + t. If a single product is processed per cycle, the <NUM>t' + t final value can be calculated via a decoder. Where more than one term pair is processed per cycle, embodiments can use one decoder per term pair to calculate the individual <NUM>t' + t products and then employ an efficient adder tree to accumulate all, as described further below with reference to an exemplary embodiment.

<FIG> is a schematic diagram of exemplary processing element (PE) <NUM> of an embodiment, such as may be used in an engine or computational arrangement implementing a neural network. PE <NUM> implements six steps, each step implemented using a processing sub-element. In some embodiments, various sub-elements of a processing element, such as the sub-elements of PE <NUM> described below, may be merged or split with various hardware and software implementations. Processing element <NUM> is set up to multiply <NUM> weights, W<NUM>,. , W<NUM>, by <NUM> input activations, A<NUM>,.

A first sub-element is an exponent sub-element <NUM>, which accepts <NUM>4b weight one-offsets, t<NUM>,. , t<NUM>and their <NUM> corresponding sign bits s<NUM>,. , s<NUM>, along with <NUM><NUM>-bit activation one-offsets, t'<NUM>,. , t'<NUM>and their signs s'<NUM>,. , s'<NUM>, and calculates <NUM> one-offset pair products. Since all one-offsets are powers of two, their products will also be powers of two. Accordingly, to multiply <NUM> activations by their corresponding weights PE <NUM> adds their one-offsets to generate the <NUM>-bit exponents <MAT> and uses <NUM> XOR gates to determine the signs of the products.

A second sub-element is a one-hot encoder <NUM>. For the ith pair of activation and weight, wherein i is ∈ {<NUM>,. , <NUM>}, one-hot encoder <NUM> calculates <MAT> via a 5b-to-32b decoder which converts the <NUM>-bit exponent result ( <MAT>) into its corresponding one-hot format, being a <NUM>-bit number with one '<NUM>' bit and <NUM> '<NUM>' bits. The single '<NUM>' bit in the jth position of a decoder output corresponds to a value of either +<NUM>j or -<NUM>j depending on the sign of the corresponding product, being Eisign as shown in <FIG>.

A third sub-element is a histogrammer <NUM>, which generates the equivalent of a histogram of the decoder output values. Histogrammer <NUM> accumulates the <NUM>32b numbers from one-hot encoder <NUM> into <NUM> buckets, N<NUM>,. , N<NUM> corresponding to the values of <NUM>°,. , <NUM><NUM>, as there are <NUM> powers of two. The signs of these numbers, being Eisign as taken from one-hot encoder <NUM>, are also taken into account. Following this, each bucket contains the count of the number of inputs that had the corresponding value. Since each bucket has <NUM> signed inputs, the resulting count would be in the range of -<NUM> to <NUM> and thus is represented by <NUM> bits in <NUM>'s complement.

Fourth and fifth sub-elements are aligner <NUM> and reducer <NUM>, respectively. Aligner <NUM> shifts the counts according to their weight, converting all to <NUM> + <NUM> = <NUM> b and then reducer uses a <NUM>-input adder tree to reduce the <NUM>6b counts into the final output, as indicated in <FIG>.

Following reduction, a sixth sub-element is an accumulation sub-element <NUM>. Accumulation sub-element <NUM> accepts a partial sum from reducer <NUM>. Accumulation sub-element <NUM> then accumulates the newly received partial sum with any partial sum held in an accumulator. This way the complete A × W product can be calculated over multiple cycles, one effectual pair of one-offsets per cycle.

In some embodiments, sub-element designs may be better able to take advantage of the structure of information being processed. For example, <FIG> is a schematic diagram of a concatenator, aligner and reducer sub-element <NUM>. In some embodiments, both aligner <NUM> and reducer <NUM> of PE <NUM> are replaced by concatenator, aligner and reducer sub-element <NUM>, which comprises concatenator <NUM>, aligner <NUM>, and reducer <NUM>.

Replacing aligner <NUM> and reducer <NUM> of PE <NUM> with concatenator, aligner and reducer sub-element <NUM> has the effect of adding a new concatenator to PE <NUM>, the new concatenator being sub-element <NUM>. The addition of a new concatenator also allows changes to be made to the aligner and reducer, such as to make these sub-elements smaller and more efficient; reflective changes to aligner <NUM> to implement aligner sub-element <NUM>, and reflective changes to reducer <NUM> to implement reducer sub-element <NUM>.

Instead of shifting and adding the <NUM>6b counts, concatenator, aligner and reducer sub-element <NUM> seeks to reduce costs and energy by exploiting the relative weighting of each count by grouping and concatenating them as shown in <FIG>. For example, rather than adding N<NUM> and N<NUM> they are simply concatenated as they are guaranteed to have no overlapping bits that are '<NUM>'. The concatenated values are then added via a <NUM>-input adder tree to produce a 38b partial sum to be output to accumulation sub-element <NUM>.

Concatenator, aligner and reducer sub-element <NUM> implements a more energy and area efficient adder tree than possible using aligner <NUM> and reducer <NUM>, and takes advantage of the fact that the outputs of histogrammer <NUM> contain groups of numbers that have no overlapping bits that are '<NUM>'.

As an example, consider adding the <NUM>th 6b input ( <MAT>)with the <NUM>th 6b input ( <MAT>). Using the adder of aligner <NUM> and reducer <NUM> the <NUM>th input N<NUM> must be shifted by <NUM> bits, which amounts to adding <NUM> zeros as the <NUM> least significant bits of the result. In this case, there will be no bit position in which both N<NUM> shifted by <NUM> and N<NUM> will have a bit that is <NUM>. Accordingly, adding (N<NUM> << <NUM>) and N<NUM> is equivalent to concatenating either N<NUM> and N<NUM> or (N<NUM>-<NUM>) and N<NUM> based on the sign bit of N<NUM>, as depicted schematically in <FIG> as concatenate unit <NUM> and numerically in computation (<NUM>) below: <MAT>.

Accordingly, this process is applied recursively, by grouping those Ni where (i MOD <NUM>) is equal. That is, the ith input would be concatenated with (i + <NUM>)th, (i + <NUM>)th, and so on. Example concatenating unit <NUM> of <FIG> implements recursive concatenation as a stack for those Ni inputs where (i MOD <NUM>) = <NUM>, although other implementations are possible in other embodiments. For the <NUM>-product unit described above, the process yields the six grouped counts of depiction (<NUM>) below: <MAT>.

The final partial sum is then given by equation (<NUM>) below: <MAT>.

A hardware accelerator tile <NUM> is depicted in <FIG>. Tile <NUM> is a 2D array of PEs, such as PE <NUM> of <FIG>, processing <NUM> windows of input activations and K = <NUM> filters every cycle. PEs along the same column share the same input activations and PEs along the same row receive the same weights. Every cycle PE(i,j) receives the next one-offset from each input activation from the jth window and multiplies it by a one-offset of the corresponding weight from the ith filter. Tile <NUM> starts processing the next set of activations and weights when all the PEs are finished with processing the terms of the current set of <NUM> activations and their corresponding weights.

As tiles such as tile <NUM> process both activations and weights term-serially, to match the BASE configuration it must process more filters or windows concurrently. In the worst case each activation and weight possess <NUM> terms, thus tiles such as tile <NUM> should process <NUM> × <NUM> = <NUM> filters in parallel to match the peak compute bandwidth of BASE. However, as indicated in <FIG>, with <NUM>× more filters, the performance of some example implementations using tiles such as tile <NUM> is more than two orders of magnitude improved over the BASE performance. Further, an embodiment can use a modified Booth encoding and reduce the worst case of terms to <NUM> per weight or activation.

<FIG> are schematic drawings of several hardware accelerator configurations, the performance of which is compared in <FIG>. As indicated in <FIG>, a BASE configuration <NUM> can process <NUM> filters with <NUM> weights per filter using around <NUM>,<NUM> wires. As indicated in <FIG>, using tiles such as tile <NUM>, configuration <NUM> can process <NUM> filters using <NUM> wires, configuration <NUM> can process <NUM> filters using <NUM> wires, configuration <NUM> can process <NUM> filters using <NUM> wires, and configuration <NUM> can process <NUM> filters using around <NUM>,<NUM> wires. In each configuration of <FIG> the number of activation wires is set to <NUM>. In other embodiments, other configurations could be employed, such as fixing the number of filters and weight wires and increasing the number of activation windows and wires.

<FIG> compares the performance of configurations <NUM> to <NUM> illustrated in <FIG>. The bar graph of <FIG> shows the relative performance improvement of configurations <NUM> to <NUM> over configuration <NUM> as a set of four bar graphs for each of six models, the six models identified below each set of bars. The relative improvement of configuration <NUM> is shown as the leftmost bar of each set, the relative improvement of configuration <NUM> is shown as the second bar from the left of each set, the relative improvement of configuration <NUM> is shown as the third bar from the left of each set, and the relative improvement of configuration <NUM> is shown as rightmost bar of each set.

Simulations of embodiments of the present invention indicate that such embodiments deliver improvements in execution time, energy efficiency, and area efficiency. A custom cycle-accurate simulator was used to model execution time of tested embodiments. Post layout simulations of the designs were used to test energy and area results. Synopsys Design Compiler (see for example Synopsys, "Design Compiler. " http://www. com/Tools/Implementation/RTLSynthesis/DesignCompiler/Pages,) was used to synthesize the designs with TSMC <NUM> library. Layouts were produced with Cadence Innovus (see for example Cadence, "Encounter rtl compiler. " https://www. com/content/cadencewww/global/en_US/home/training/all-courses/<NUM>. html) using synthesis results. Intel PSG ModelSim was used to generate data-driven activity factors to report the power numbers. The clock frequency of all designs was set to <NUM>. The ABin and About SRAM buffers were modeled with CACTI (see for example<NPL>) and the activation memory and weight memory were modeled as eDRAM with Destiny (see for example <NPL>).

<FIG> indicates the performance of configurations <NUM> to <NUM> relative to BASE configuration <NUM> for convolutional layers with the <NUM>% relative TOP-<NUM> accuracy precision profiles of Table <NUM>, compared using the indicated network architectures (see for example<NPL>).

In some embodiments, further rewards result from the use of embodiment of the present invention with certain models, such as models designed to have a reduced precision, models which use alternative numeric representations that reduce the number of bits that are ` <NUM>', or models with increased weight or activation sparsity. However, embodiments of the present invention target both dense and sparse networks and improve performance by processing only essential terms.

As indicated in <FIG>, on average, configuration <NUM> outperforms configuration <NUM> by more than <NUM>× while for AlexNet-Sparse, a sparse network, it achieves a speedup of <NUM>× over configuration <NUM>. As indicated in <FIG>, configurations <NUM> to <NUM> deliver speedups of up to <NUM>×, <NUM>×, and <NUM>× over configuration <NUM>, respectively.

The energy efficiency of configurations <NUM> to <NUM> relative to configuration <NUM> are shown in Table <NUM>, below. As configurations using tiles such as tile <NUM> require less on-chip memory and communicate fewer bits per weight and activation, the overall energy efficiency is generally higher.

Post layout measurements were used to measure the area of configurations <NUM> to <NUM>. Configuration <NUM> requires <NUM>× the area of configuration <NUM> while achieve an average speedup of <NUM>×. The area overhead for <NUM> is <NUM>×, the area overhead for <NUM> is <NUM>×, and the area overhead for <NUM> is <NUM>×, while execution time improvements over configuration <NUM> are <NUM>×, <NUM>×, and <NUM>× on average, respectively. As such, tiles such as tile <NUM> provide better performance vs. area scaling than configuration <NUM>.

The number of activation and weight pairs processed by a tile or accelerator can be varied. Some processor elements process <NUM> activation and weight pairs per cycle, all contributing to the same output activation. Some processor elements process other than <NUM> pairs per cycle. Some accelerator embodiments combine multiple tiles or processor elements of the same or different configurations. <FIG> is a schematic diagram of a tile <NUM> containing <NUM> processor elements <NUM> organized in an <NUM> by <NUM> grid. Input scratchpads, i.e., small local memory, provide activation and weight inputs, an activation pad <NUM> providing activation inputs and a weight pad <NUM> providing weight inputs. In some layers the activation pad <NUM> provides weight inputs and the weight pad <NUM> provides activation inputs. A third scratchpad, storage pad <NUM>, is used to store partial or complete output neurons.

A bus <NUM> is provided for each row of processing elements <NUM> to connect them to the storage pad <NUM>. Partial sums are read out of the processor element grid and accumulated in accumulator <NUM> and then written to the storage pad <NUM> one column of the processing elements at a time. There is enough time to drain the processing element grid via the common bus <NUM>. Since processing of even a single group of activation and weight pair inputs is typically performed over multiple cycles and typically multiple activation and weight pair groups can be processed before the partial sums need to be read out, this provides enough time for each column of processing elements to access the common bus <NUM> sequentially to drain its output while the other columns of processing elements are still processing their corresponding activations and weights.

Tile <NUM> includes encoders <NUM> between the input scratchpads and the processing element grid, one encoder corresponding to each input scratchpad. Encoders <NUM> convert values into a series of terms. An optional composer column <NUM> provides support for the spatial composition of 16b arithmetic while maintaining 8b processing elements. Tile <NUM> allows for the reuse of activations and weights in space and time and minimizes the number of connections or wires needed to supply tile <NUM> with activations and weights from the rest of a memory hierarchy.

For example, tile <NUM> can proceed with <NUM> windows of activations and <NUM> filters per cycle. In this case, the weight pad <NUM> provides <NUM> weights per filter and the activation pad <NUM> provides the corresponding <NUM> activations per window. Processing elements <NUM> along the same column share the same input activations, while processing elements <NUM> along the same row share the same input weights. Encoders <NUM> convert input values into terms at a rate of one term per cycle as each PE can process a single term of activation and a single term of weight every cycle. Each cycle, the processing element in row 'i' and column 'j' multiples the input activation from the jth window by the weight from the ith filter. Once all activation terms have been multiplied with the current weight term, the next weight term is produced. The processing element cycles through all the corresponding activation terms again to multiply them with the new weight term. The product is complete once all weight and activation terms have been processed. If there are <NUM> activation terms and <NUM> weight terms, at least <NUM> cycles will be needed. In total, tile <NUM> processes <NUM> windows, <NUM> activations per window, and <NUM> filters; <NUM> by <NUM> by <NUM> activation and weight pairs concurrently.

In practice, the number of terms will vary across weight and activation values, and as a result some processing elements will need more cycles than others to process their product. Tile <NUM> implicitly treats all concurrently processed activation and weight pairs as a group and synchronizes processing across different groups; tile <NUM> starts processing the next group when all the processing elements are finished processing all the terms of the current group. However, this gives up some speedup potential.

In some embodiments, computation is allowed to proceed in <NUM> independent groups. For example, the first synchronization group will contain A<NUM>, A<NUM><NUM>, A<NUM>,. , A<NUM> and weights W<NUM>, W<NUM>,. , W<NUM>, the second group will contain A<NUM>, A<NUM>, A<NUM>,. , A<NUM> and weights W<NUM>, W<NUM>,. , W<NUM>, and so on for the remaining <NUM> groups. This example is referred to as comb synchronization, since the groups physically form a comb-like pattern over the grid. A set of buffers at the inputs of the booth-encoders <NUM> can be used to allow the groups to slide ahead of one another.

Some neural networks required 16b data widths or precisions only for some layers. Some neural networks require 16b data widths or precisions only for the activations, and few values require more than 8b. In some embodiments, a tile supports the worst-case data width required across all layers and all values. However, in some embodiments, tiles support data type composition in space or time or both space and time.

For example, a tile design can allow for 16b calculations over 8b processing elements for activations and optionally for weights. Although other bit widths can also be used. Tile designs can be useful for neural networks which require more than 8b for only some of their layers.

A spatial composition tile is shown in <FIG>. Tile <NUM> uses multiple yet unmodified 8b processing elements. The spatial composition tile requires extra processing elements whenever it processes a layer that has 16b values. Tile <NUM> is a <NUM> by <NUM> grid of 8b processing elements <NUM> to extened to support the following weight and activation combinations: 8b and 8b, 16b and 8b, and 16b and 16b. The normalized peak compute throughput is respectively: <NUM>, ½, and ¼. To support 16b and 8b computation the activation terms are split into those corresponding to their lower and upper bytes which are processed respectively by two adjacent processing element ("PE") columns.

In the example indicated in <FIG>, PE(<NUM>,<NUM>) and PE(<NUM>,<NUM>) process the lower bytes ofA<NUM> and A<NUM> and PE(<NUM>,<NUM>) and PE(<NUM>,<NUM>) process the upper bytes. Rows <NUM> and <NUM> respectively process filters <NUM> and <NUM> as before. Processing proceeds until the accumulation sub-element <NUM> have accumulated the sums of the upper and lower bytes for the data block. At the end, the partial sum registers are drained one column at a time. A composer column <NUM> is added at the grid's output. When the partial sums of column <NUM> are read out, they are captured in the respective temporary registers ("tmp") <NUM>. Next cycle, the partial sums of column <NUM> appear on the output bus. The per row adders of the composer <NUM> add the two halves and produce the final partial sum. While the example shows a <NUM> by <NUM> grid, the concept applies without modification to larger processing element grids. A single composer column is sufficient as the grid uses a common bus per row to output the partial sums one column at a time. While not shown, the composer can reuse the accumulate column adders instead of introducing a new set. In general, supporting 16b activations would require two adjacent per row processor elements.

Tile <NUM> also supports 16b weights by splitting them along two rows. This requires four processing elements each assigned to one of the four combinations of lower and upper bytes. In <FIG>, PE(<NUM>,<NUM>), PE(<NUM>,<NUM>), PE(<NUM>,<NUM>) and PE(<NUM>,<NUM>) will respectively calculate (AL, WL), (AH, WL),(AL, WH), and (AH, WD). The second level adder in the composer column takes care of combining the results from the rows by zero-padding row <NUM> appropriately.

A temporal composition tile may also be used. A temporal composition tile would employ temporal composition processing elements. An embodiment of a temporal composition processing element is shown in <FIG>. Processing element <NUM> supports both 8b and 16b operation, albeit at a lower area cost than a native 16b processing element. The temporal composition tile requires extra cycles whenever it has to process 16b values.

Processing element <NUM> allows for the splitting of the terms of activations and weights into those belonging to the upper and the lower bytes and the processing of them separately in time. The output from the front-stage adder is appropriately padded with zeros and then added to the extended precision partial sum. There are three cases based on the source of the activation and weight terms being processed: both belong to lower bytes (L/L), both belong to upper bytes (H/H), or one belongs to an upper byte and the other to a lower one (H/L or L/H). The multiplexer <NUM> selects the appropriately padded value. The multiplexer's select signal can be shared among all processing elements in a tile. Processing 8b values incurs no overhead. Processing 16b activations and 8b weights (or vice versa) requires an extra cycle, whereas processing 16b weights and activations requires <NUM> extra cycles. However, this time overhead has to be paid only when there is a value that really needs 16b with the tile having processing element <NUM>.

A temporal composition tile does not reserve resources for whole layers, and since values that require more than 8b may be few it can be expected to achieve higher throughout per processing element than a spatial composition tile. However, a temporal composition tile requires larger processing elements and more sophisticated control at the booth encoders. In an embodiment, an 8b processing element capable of temporal extension to 16b is <NUM>% smaller compared to a native 16b processing element. In some embodiments, combinations of spatial and temporal designs may be used, such as spatial composition for weights and temporal composition for activations.

In some networks and for some layers (especially the first layer), the data type needed as determined by profiling sometimes exceeds 8b slightly. For example, 9b or 10b are found to be needed. In some embodiments, executing these layers or networks is possible with an unmodified 8b processing element and with a minor modification to the Booth-Encoder. For example, in the case of processing a value which needs the 9th bit, that is where that bit is <NUM>. Since an 8b processing element only supports calculations with up to +<NUM><NUM> the Booth-Encoder can effectively synthesize +<NUM><NUM> by sending +<NUM><NUM> twice. Importantly, this will be needed only for the values where the 9th bit needs to be <NUM>; all negative values in 9b. As an added benefit, this flexibility makes quantization easier for certain networks.

Embodiments presented above exploit inter-value bit-level parallelism. However, some embodiments can exploit intra-value bit-level parallelism and to do so differently than bit-parallel hardware. This is possible, since the processing element produces the correct result even if the terms of a value are processed spatially instead of temporally. For example, if two input lanes are assigned per weight and Booth-encoder is modified so that it outputs up to two terms per cycle. This also enables an accelerator to exploit bit-level parallelism within values, which may be useful to reduce synchronization overheads. Exploiting bit-level parallelism within values may also be useful to improve utilization for layers where there isn't enough reuse of weights or activations or both activations and weights to fill in all columns or rows or both rows and columns, respectively. This is the case, for example, for fully connected layers where there is no reuse of weights. This optimization helps with energy efficiency as fully connected layers are typically memory bound. It is also useful for depth-separable convolutional layers. Exploiting bit-level parallelism within values may also be useful when there are not enough filters to fill in all rows. This is different than the intra-value bit-level parallelism exploited by conventional bit-parallel units: they process all bits regardless of value whereas embodiments of the present accelerator would process only the effectual ones.

The performance of an 8b accelerator with spatial composable processing elements and the performance of an accelerator with native 16b processing elements have been compared. The 8b spatial composable processing elements supported 8b and 16b weights and activations, and the 8b accelerator was scaled up to use the same compute area as the 16b accelerator. Testing was conducted using the GoogleNet-S and Resnet50-S models. The 8b spatial composable processing accelerator used multiple processing elements as needed only for those layers that required more than 8b precision. The 8b spatial composable processing accelerator was faster than the native 16b accelerator: <NUM> times faster for GoogleNet-S and <NUM> times faster for Resnet50-S.

In other embodiments, other configurations could be used, such as an increased number of weight wires. In some embodiments, performance improves sublinearly, such as due to inter-filter imbalance aggravated by scaling up only by increasing the number of filters. In some embodiments, the number of simultaneously processed activations may be increased instead or in addition to increasing the number of weights. Combining configuration designs with minimal buffering configurations (see for example<NPL>) may also reduce cross-activation imbalances. In other embodiments, the activation and weight memories may be distributed along the tiles or shared among all or groups of them.

Embodiments of the present invention are compatible with compression approaches (see for example <NPL>), and can be expected to perform well with practical off-chip memory configurations and interfaces.

Claim 1:
A neural network accelerator tile, comprising:
an activation memory interface for interfacing with an activation memory to receive a set of activation representations;
a weight memory interface for interfacing with a weight memory to receive a set of weight representations, each weight representation corresponding to an activation representation of the set of activation representations; and
a processing element (<NUM>) configured to combine the set of weight representations with the set of activation representations by combining each weight representation with its corresponding activation representation to produce a set of partial results, wherein the processing element (<NUM>) comprises:
a one-hot encoder sub-element (<NUM>) configured to encode the set of partial results to produce a set of one-hot representations;
a histogrammer sub-element (<NUM>) configured to accumulate the set of one-hot representations into a set of histogram bucket counts;
an aligner sub-element (<NUM>) configured to align the counts of the set of histogram bucket counts according to their size; and
a reducer sub-element (<NUM>) configured to reduce the aligned counts of the set of histogram bucket counts to produce a partial sum.