TWI886942B - Application specific integrated circuit for computing a convolutional neural network - Google Patents

Abstract

An Application Specific Integrated Circuit (ASIC) for computing a convolutional neural network (CNN) has a first input bus receiving an ordered stream of values from an array, each position in the array having one or more channels, and a plurality of kernel processing tiles receiving inputs through configurable multiplexors. The kernel processing tiles and buses are arranged and connected in a manner that the ASIC operates as a pipelined system delivering an output stream in synchronization with the input stream.

Description

Special application integrated circuit for computing convolutional neural networks

Related Applications: This application is a continuation-in-part of co-pending application 17/742,245 filed on May 11, 2022, which was a continuation-in-part of application 17/570,757 filed on January 7, 2022 and published on June 7, 2022 as US 11,354,571, which was a continuation-in-part of application 17/373,497 filed on July 12, 2021 and published on February 22, 2022 as US 11256981, which was a continuation-in-part of application 17/373,497 filed on April 15, 2021 and published on August 24, 2021 as US 17/231,711, which is a continuation-in-part of co-pending application 17/071,875 filed on October 15, 2020. All disclosures of the parent application are incorporated herein by reference at least in part.

Field of Invention: This invention belongs to the technical field of computer operations involving matrix input and output, and more specifically, it relates to circuits designed for large-scale multiplication in matrix operations.

Background of the invention: The use of computers for matrix operations is well known in the art, with particular examples being image processing and the development and use of neural networks. Neural networks are an important component of artificial intelligence and, therefore, are a very popular subject for intellectual property development at the time of filing this patent application. Generally speaking, in such computer operations, a large number of input values are processed in a regular pattern, which in most cases is a matrix. The processing of the input values may involve biasing and applying weights by which individual input values may be multiplied.

The inventors of this case believe that the complex and computationally intensive operation in the art of neural networks in which an input value is multiplied by each of a plurality of weight values is open to innovative steps to provide significant advantages in the art. The inventors of this case also believe that advantages will be obtained in modifying the order of the mathematical processes to be applied.

The inventor of this case believes that he has determined that a general change in the order and manner of mathematical processes to be performed in such applications may well produce a very significant reduction in the time and cost of such operations.

Summary of the Invention: In an embodiment of the present invention, an application specific integrated circuit (ASIC) for computing a convolutional neural network (CNN) is provided, comprising: a first input bus that receives an ordered stream of values from an array, each position in the array having one or more data channels; a first set of core processing blocks that are ordered throughout, having a fixed number of parallel input connections and a fixed number of parallel output connections, each core processing block of the first ordered set being coupled to the input bus via one of a first set of configurable multiplexers; , the core processing blocks being adapted to compute a convolution of a common core size and passing the computed value to a first output bus and to an adjacent downstream core processing block of the first ordered group, the first output bus being connected back as an input to each configurable multiplexer in the first set of configurable multiplexers; a second set of core processing blocks being ordered throughout, having the fixed number of parallel input connections and the fixed number of parallel output connections, each core processing block of the second ordered group being coupled to the first through one of the second set of configurable multiplexers output bus, the core processing blocks of the second ordered group are adapted to calculate a convolution of the common core size and pass the calculated value to a second output bus and to an adjacent downstream core processing block of the second ordered group, the second output bus being connected back as an input to each configurable multiplexer in the second set of configurable multiplexers; and a third set of core processing blocks ordered from beginning to end, which have the fixed number of parallel input connections and the fixed number of parallel output connections, each core processing block of the third ordered group is connected to the third set of configurable multiplexers through a third set of configurable multiplexers. One of the configuration multiplexers is coupled to the second output bus, the core processing blocks of the third ordered group are adapted to compute a convolution of the common core size and pass the computational value to a third output bus and to an adjacent downstream core processing block of the third ordered group, the third output bus is connected back as an input to each configurable multiplexer in the third group of configurable multiplexers, the third output bus is also connected to a primary output circuit through a single primary output multiplexer, the primary output circuit is adapted to perform primary output processing and provide final output.

In one embodiment, the ASIC further includes: an additional configurable multiplexer coupled to the first output bus that provides selected values to the first core processing block in the second ordered group; and an additional configurable multiplexer coupled to the second output bus that provides selected values to the first core processing block in the third ordered group. In addition, in one embodiment, the ASIC further includes one or more auxiliary function blocks that provide functions other than the functions of the core processing blocks. In one embodiment, the one or more auxiliary function blocks receive inputs from dual multiplexers connected to the input bus and the first output bus and provide outputs to the first output bus. And in one embodiment, the one or more auxiliary functional blocks receive input from a dual multiplexer connected to the first output bus and the second output bus and provide output to the second output bus.

In one embodiment of the present invention, the one or more auxiliary function blocks receive inputs from a dual multiplexer connected to the second output bus and the third output bus and provide outputs to the third output bus. In addition, in one embodiment, the ASIC further includes an external functional circuit system that selects inputs from the first output bus through a configurable multiplexer and provides outputs to the first output bus. In addition, in one embodiment, the ASIC further includes an external functional circuit system that selects inputs from the second output bus through a configurable multiplexer and provides outputs to the second output bus. In one embodiment, the ASIC further includes an external functional circuit system that selects inputs from the third output bus and provides outputs to the third output bus through a configurable multiplexer. And in one embodiment, the common core size is a 3×3 core.

In one embodiment, the fixed number of parallel input connections is 16, and the fixed number of parallel output connections is 16. Further, in one embodiment, the ordered stream of values is provided by one of a direct camera output of RGB values, a DMA interface suitable for access from a CPU bus, or a video stream decompression circuit, thereby generating three parallel channels of red, green, and blue (RGB) values for an image. Further, in one embodiment, the ASIC further includes combining the operation of two or more core processing blocks of a 3x3 core that processes 16 parallel input and output connections to configure a 3x3 core with more than 16 inputs or more than 16 outputs or more than 16 inputs and outputs. In one embodiment, the ASIC is adapted by additional circuitry to compute a product having a core greater than 3x3 by combining operations of a plurality of the 3x3 core processing blocks. And in one embodiment, the ASIC is adapted to compute a 5x5 product, a 7x7 product, or a 9x9 product.

In one embodiment, the core processing blocks present each input channel value to a large number of multipliers which operate on the full set of possible multiples of the input and provide those multiples along with the individual channel values from an auxiliary set of parallel connections to a single convolution unit, the resulting outputs from each convolution unit being grouped in a set of 16 parallel output connections and made available to other core processing blocks on the output bus. In one embodiment, the core processing block input values are processed by local two-input fixed multipliers. In addition, in one embodiment, each of the auxiliary function blocks receives parallel input connections from two independent buses through a dual multiplexer and outputs one of a MaxPool function, an average function, a sampling function, and an expansion function selected by an output multiplexer. In one embodiment, the auxiliary function block sums the values from the parallel input connections through individual channels and multiplexes the summed value to a lookup table, which is suitable for providing any activation function that can be represented in a table, including a RELU, a sigmoid, or a hyperbolic tangent activation function. In one embodiment, the input channels received from independent parallel input connections are inputs to a first dedicated multiplexer, which concatenates the parallel input connections to effectively reroute the data channels to specific parallel output connections and provides the concatenated output to the output multiplexer as a candidate for selection as an output of the auxiliary function block. And in one embodiment, the input channels received from independent parallel input connections are inputs to a second dedicated multiplexer, which concatenates two parallel input connections into one parallel output connection by alternating samples from each connection and provides the result to the output multiplexer as a candidate for selection as an output of the auxiliary function block.

101,101a: Source multiplicand/source channel

101b,101c,101d: source channel

102a, 102b, 102c, 102d: dedicated large number of multipliers

103a,103b,103c,103d,203a,203b,203c,203d: Operational unit

104,204:Processing

201a,201b,201c,201d,1008,1010,1011,1012,1106,1303,1402,4312,4403,4404,4407,4409,4412,4803,4905,4907,4912,4913:Multiplexer

302a,302b,302c,302d: Bit Item/Unused Item/Item

302e,401:Item

303a,303b,303c,303d,303e,303f: Product/Unused Product

304: multiples

402a,402b,402c,402d,402e,402f,605a,605b,605c,605d,605e,605f: product

501a,501b: pipeline register/reserved items

502: Yes

503:Retained

504,601: triplet

505: Four bytes

506a,506b,506c,506d,506e,506f: product/multiple

507: Best Logic Circuit

603: seven bytes

604: octet

701: Input channel group

702: Control signal/control circuit system

703: Public circuit system

704a,704b,704c: Subfunction operation circuit

705: Output channel group/output stream sink

801a,801b,801c,4603: a large number of multipliers

802: Source channel product

803: Control circuit system/public control and synchronization circuit system/control

804:rowSrc counter

805:colSrc counter

806:rowDst counter

807:colDst counter

808: First row signal (ROWFST)

809: Last row signal (ROWLST)

810: First line signal (COLFST)

811: Last row signal (COLLST)

812: Post-processing enabling signal (POSTEN)

813: Output enable signal (DSTEN)

814: Source control signal

815: Output channel control and counter

901:Synthesizer/Synthesizer Circuit/Cell

902a,902b,902c,903a,903b,903c,904,905a,905b,905c,906,907a,907b,907c:Synthesizer/Synthesizer Circuit

908a,908b,908c,908d,908e,908f: Delay level/delay/delay line within a row

909,910a,910b: Delay level/delay/truncated output delay line/final truncated result delay line/truncated delay line/final result delay line

911: Termination step/termination function/termination/final processing

1001: Source input group of stream value

1002: The synthesizer is connected to the left side

1003: The synthesizer row immediately above

1004,1005,1006,1007,2709:Circuit system

1009,3201,3304:Synthesizer

1101,1102: Column

1103,1111:row/path

1104,1105,3301,3401,3402,3501: register

1107,2403: First-in, first-out (FIFO) circuit

1109,1110:Parallel access to register/delayed result

1112,1113: Parallel paths

1114: value

1201: Auxiliary output

1202,1304,2405,2409,2504,2602,2605,2703,2704,3302,3305,4202,4203,4204 ,4205,4208,4209,4304,4305,4306,4308,4309,4311,4705,4706,4902,5003:FIFO

1301: Partial results

1401: Delay line after truncation result

1403: Terminate circuit system

1404: Final form of output stream

1701,1801,2711,5001:Input channel

1702,1802: The first 7x7 convolution node

1703,1704,1705,1803,1804,1805: Subsequent convolution nodes

1706,1806: Connect nodes

1707: MaxPool node

1708: Global average node

1709: Output channel

1807: The first MaxPool node

1808,1809,1810,1811: Nodes

1812: Second 2x2 MaxPool node

1813: Final output

2101: A set of four inputs

2102: Current group of four inputs

2103,2104,2105: Core columns

2106,2107,2108: Circuit/core copy

2109: Output stream

2201,2202,2203,2301,2302,2303,2501,2901,2902,2903: Input group

2204,2205,2206,2207: Core circuit

2208,2908:4-up output array stream

2304,2305,2306,2307: Core processing circuit

2308: Insert ("valid") volume output/circuit

2309,2310,2311,2312,2712,2803,2804,2805,2806,2807,2808:Circuit

2313: Exact ("same") convolution output

2401:4-up data stream

2402,2404,2408,2503: Comparator

2406:Output group

2407:2-up data stream

2410: Single output channel

2502,2802,3005:Current input group

2506,2507,2508,2509: Comparator block

2510,2706,2713,3003,3007,4708,4813,4915,5004,5415: Output

2601:4-up streaming

2603:2-up streaming

2604:3-up streaming

2606:5-up streaming

2701,2702: Source

2705: Interlaced circuits

2707,3001,5101,5401:Input

2708:Weight

2710: Single 1-up group of output channels

2801: Register/previous input set

2809: Output array stream

2904,2905,2906,2907:Summing circuit

3002: Routing circuit system

3004:Previous input group

3006: Repackaging circuit system

3100:System

3101,3105,3106,3107,3108:IC

3102: Input port

3103: Output port

3104: Functional circuit

3202: column buffer FIFO

3203: Flat buffer FIFO

3204: Final processing circuit

3303:Bus

3403,3502,3503,3504,3505,3506:Synthesizer set

3601: Input array stream

3602: Aperture function IC circuit

3603,4003,4102:Context management circuit

3604: Final output stream

3701: First stream

3702: Second stream

3703: Storage and forwarding multiplexer/interleaving circuit system

3704:Context circuit

3705,4103: final output

3801: First unscaled substream

3802,3803,3804,3901,3902: substream

4001: Cascaded multi-scale sampler

4002: Time-interleaved sequence/interleaved sample stream/multi-scale sample stream

4004: Interleaved multi-scale array stream

4101: Interlaced input stream

4201:2:1 Sampler

4206,4210,4307: Cut multiplexer

：1取樣器 4207:

: 1 Sampler

4301:U:1 Sampler

4302:V:1 Sampler

4303:W:1 Sampler

4310:1: T-amplifier sampler

4401:Main input

4402: Input bus

4405,4501,4502: core processing block

4406: Output bus

4408: Auxiliary function block

4410: External functional circuit system

4411: 16 parallel input connections

4413: Main output circuit system

4503: First core processing block

4504: Second core processing block

4505,4506,4507,4508: Block

4601: Parallel input connection set

4602: Auxiliary connection set

4604: Volume unit

4605:Parallel output connection

4701: Input product

4702: Auxiliary input

4703:Internal bus

4704: Weighted sum cell

4707,4806,4810,4811,4904: Adder

4801: The number of input channels presented

4802: Configuration register/configurable index

4804: Configuration register/configurable scale

4805: Variable shift register/scaler

4807:Configured offset value

4808: Delayed value/delayed connection

4809: Forwarded part and/or forwarded value

4812: Final adder

4901: Main parallel input connection set

4903: Auxiliary input

4906: Public Lookup Table

4908: MaxPool functional block

4909: Average functional block

4910: Sampling function block

4911: Expanded functional area

4914,5102:Configurable multiplexer

5002: Small functional circuit system

5103:External output

5402,5404,5406,5408,5410,5413: Volume

5403: Sampling

5405,5407,5412:MaxPool

5409:Expansion

5411: Serial connection

5414:Average

q ₀ : First parallel channel group/first output/value/output position/output group

q ₁ : Parallel channel group/value/output group

q ₂ ,q ₃ : parallel channel group/value

p ₀ ,p ₁ ,p ₂ ,p ₃ : input channel

w _0,0 -w _2,2 ,W _0,2,2 : weight

W _2,2,2 : Final weight

R ₀ -R ₁₆ : Column

Figure 1 shows an embodiment in which a large number of multipliers applied to each common source are fixed and directly connected to the processing circuit.

FIG2 illustrates an embodiment in which a large number of multipliers applied to each common source are dynamic and routed to processing circuits via multiplexers.

FIG3 illustrates a simple implementation in which shift terms corresponding to bits set in each of the plurality of multipliers are summed to form a product.

Figure 4 illustrates an enhanced embodiment in which addition and subtraction of shift terms from one another are mixed to form an equivalent solution with lower complexity.

FIG5A illustrates an example of a pipeline implementation that maximizes clock frequency by constructing subcomponents from only paired operations.

FIG5B illustrates an embodiment in which the multiples are formed directly from a set of fixed cases without reference to standard arithmetic operations.

Figure 6 shows an example pipeline implementation that maximizes circuit density by building subassemblies from up to four operations.

FIG. 7 is a diagram showing the structure and connectivity of receiving an input stream, preprocessing the input stream, and feeding the result through a unique digital device to generate an output stream in an embodiment of the present invention.

Figure 8A is a diagram showing the structure and connectivity for generating source channel products.

FIG8B is a diagram showing additional details of the control device and functions in an embodiment of the present invention.

FIG. 9A is a partial diagram of a general situation of pipeline operation in an embodiment of the present invention.

FIG. 9B is another partial diagram of a general situation of pipeline operation in an embodiment of the present invention.

FIG. 9C is another partial diagram of a general situation of pipeline operation in an embodiment of the present invention.

FIG. 10A is a diagram showing the internal structure of synthesizers 905a, 905b, and 905c of FIG. 9A and FIG. 9B in an embodiment of the present invention.

FIG. 10B is a diagram showing the internal structure of synthesizers 902a, 902b, and 902c of FIG. 9A and FIG. 9B in an embodiment of the present invention.

FIG. 10C is a diagram showing the internal structure of the synthesizer 904 of FIG. 9A in an embodiment of the present invention.

FIG. 10D is a diagram showing the internal structure of the synthesizer 901 of FIG. 9A in an embodiment of the present invention.

FIG. 10E is a diagram showing the internal structure of synthesizers 903a, 903b, and 903c of FIG. 9B and FIG. 9C in an embodiment of the present invention.

FIG. 10F is a diagram showing the internal structure of synthesizers 907a, 907b, and 907c of FIG. 9A and FIG. 9B in an embodiment of the present invention.

FIG. 10G is a diagram showing the internal structure of the synthesizer 906 of FIG. 9A in an embodiment of the present invention.

FIG. 11 is a diagram describing the internal structure and function of the delay stages 908a, 908b, 908c, 908d, 908e, and 908f of FIG. 9C in an embodiment of the present invention.

FIG. 12 is a diagram showing the operation of the delay stage 909 of FIG. 9C in an embodiment of the present invention.

FIG. 13 is a diagram illustrating the operation of delay stages 910a and 910b of FIG. 9C in an embodiment of the present invention.

FIG. 14 is a diagram showing the operation of the end step 911 in FIG. 9C .

FIG. 15 is a diagram showing a specific case of pipeline operation in an embodiment of the present invention implementing a 5x5 product node.

FIG. 16 shows an IC for a 4×4 aperture function in an embodiment of the present invention.

FIG. 17A illustrates an IC having a circuit system that implements a portion of a deep neural network that streams input channels individually.

FIG17B shows an IC having a circuit system that implements another portion of a deep neural network.

FIG. 18A illustrates an IC having a circuit system that implements a portion of a deep neural network that streams four input channels simultaneously.

FIG18B shows a circuit system that implements another portion of the deep neural network of FIG18A.

FIG19 is a table showing the array stream sizes of the DNNs of FIG17A and FIG17B.

FIG. 20 is a table showing the array stream sizes of the DNNs of FIG. 18A and FIG. 18B .

Figure 21 shows the circuit system of an IC that implements a 3x3 convolution node that streams four input channels simultaneously.

Figure 22 shows the required configuration of the circuit used to generate the output for the 4-up input channel of the "same" version of the 3x3 convolution.

Figure 23 shows the required configuration of the circuit for outputting two variations of the 1-row by 7-row product of four input channels for simultaneous streaming.

Figure 24A shows the configuration of a 2x2 MaxPool node on a 4-up data stream.

Figure 24B shows the configuration of the 2x2 MaxPool nodes of Figure 24A on a 2-up data stream.

Figure 25 shows a hypothetical example where it is not possible to reduce N.

Figure 26A shows the FIFO circuit used to repack a 4-up stream into a 2-up stream.

Figure 26B shows the repackaging of a 3-up stream into a 5-up stream.

Figure 27A shows an implementation of concatenating nodes so that the output includes all channels from all sources.

Figure 27B shows the implementation of a 4-up dense node.

Figure 27C shows the implementation of the 4-up global average node.

Figure 28 shows a 4-up implementation of a 3x3 local average node.

Figure 29 shows another 4-up implementation of a 3x3 local averaging node.

Figure 30A shows the implementation of a 4-up subgroup node.

Figure 30B shows a typical implementation of a 4-up pruning node.

Figure 31 shows a system of interconnected ICs implementing a neural network.

Figure 32 depicts the arrangement of the synthesizer on an integrated circuit, which is configured to implement a 3x3x3 convolution as a 3D aperture function over twenty-seven individual data samples.

Figure 33 illustrates an IC in which data from multiple planes can be buffered and presented simultaneously so that weights for multiple planes can be applied by a single synthesizer.

Figure 34 illustrates a typical 3x3x3 convolution implementation applied to a 4-up input stream.

Figure 35 shows a fully flipped implementation of the IC for 4-up data streaming.

FIG. 36 illustrates the application of an aperture function IC circuit to an input array stream 3601 of ordered samples in an embodiment of the present invention.

FIG. 37 illustrates an example of receiving two independent input array streams in an embodiment of the present invention.

FIG. 38 illustrates a sequence of full data rows and reduced data rows for a series of four 2:1 data reductions in an embodiment of the present invention.

：1之無理縮放的完全列及經縮小列之序列。 FIG. 39 shows an embodiment of the present invention.

: A sequence of irrationally scaled complete and reduced columns of 1.

FIG. 40 illustrates the application of full-scale data and downscaled data to an aperture function in an embodiment of the present invention.

Figure 41 shows the processing of interleaved streams by subsequent CNN nodes in an embodiment of the present invention.

FIG. 42A illustrates the sampling and slicing logic required to generate an interleaved stream in an embodiment of the present invention.

FIG. 42B shows another example of the sampling and slicing logic required to generate an interleaved stream in an embodiment of the present invention.

FIG. 43A illustrates the sub-sampling and slicing logic required to generate an interleaved stream from various scaled-down streams in an embodiment of the present invention.

FIG. 43B illustrates the generation of an interleaved multi-scale sample stream in another embodiment.

FIG. 43C illustrates the generation of an interleaved multi-scale sample stream in yet another embodiment.

Figure 44 is a diagram of an ASIC in an embodiment of the present invention.

FIG. 45 illustrates a configuration of a block for providing more inputs and outputs in an embodiment of the present invention.

Figure 46 shows the internal structure of the core processing block in an embodiment of the present invention.

Figure 47 shows the internal structure of the convolution unit in an embodiment of the present invention.

Figure 48 depicts a single summing cell of a core processing block in an embodiment of the present invention.

Figure 49 depicts the internal structure of the auxiliary functional block in an embodiment of the present invention.

FIG. 50 depicts the elements required to implement any of the small block functions included in the auxiliary block in an embodiment of the present invention.

FIG. 51 illustrates the configuration of the connection to the external circuit system in an embodiment of the present invention.

FIG. 52 illustrates the configuration of four 3x3 core processing blocks for computing 5x5 products in an embodiment of the present invention.

FIG. 53 depicts the configuration of nine 3x3 core processing blocks configured to implement a 9x9 core in an embodiment of the present invention.

FIG. 54 illustrates an abstract example of a fully functional convolutional neural network in an embodiment of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS: A wide variety of image and data algorithms make extensive use of the matrix form of linear algebra to prove statements and compute results. In this application, "algorithm" means a process or set of rules followed, especially by a computer, in a computation or other problem-solving operation. In this application, an algorithm is not generally interpreted as software. The algorithms described in this application may be, and are often preferably, implemented in hardware.

Matrix operations are defined as orthogonal sets of one or more dimensions, and are usually conceived to have the same number of elements in each iteration of each given dimension. By way of example, an M by N matrix is often depicted by an array of values, such as:

Conceptually, a matrix can have any number of dimensions, and can be depicted as a set of tables showing the values of each dimension.

Subsets of matrices of the form M by 1 or 1 by N are called vectors, which have their own specific properties and defined operations and are widely used in 2D and 3D graphics simulations.

Degenerate subsets of matrices of the form 1 by 1 are called scalars, and form numbers that are quite familiar to those skilled in the art.

Certain operations, such as multiplication, are well-defined when the values of the matrices are constants and the matrices have compatible dimensions. A 3x4 matrix A can be multiplied by a 4x5 matrix B to form a 3x5 matrix C, which can be written generally as: A × B = C

However, the operation B × A is not well defined because the internal dimensions do not match (5 ≠ 3) and k will not have a single range that is compatible with the indices of B and A.

A matrix or other matrix whose elements are vectors is called a tensor (from which TensorFlow gets its name). A familiar form of a tensor is an RGB image. One form of an RGB image is an HDMI frame, which is a 1080 by 1920 matrix of RGB values, where each pixel is a 3 by 1 vector of color components. Pixels are considered true vectors because linear operations on the red component do not affect the green or blue, and vice versa.

HDMI frames are not usually considered to be 5D matrices because the manipulation of pixel positions in an image is unrelated to the manipulation of color. Clipping an image by discarding uninteresting parts of the image is efficient and quite meaningful, but there is no corresponding operation to clip color components. Likewise, there can be many operations on color that have well-understood effects that would be meaningless if applied to elements of a containing array. Therefore, HDMI frames are clearly 2,3 tensors rather than 5D arrays.

There are many image processing algorithms that are known to be expressible as matrix operations. Matrix operations are a concise way to represent repeated operations, and the rules of matrix mathematics help prove certain statements.

Matrix-based algorithms on general-purpose computer processors are often implemented using looping mechanisms, and both computer languages and hardware CPUs may have features that make such loops efficient. However, the mathematical nature of the matrix definition does not require that operations be performed by any particular method or plan in order to compute correct results.

The modern hybrid of image processing and cognition is the convolutional neural network (CNN). Although training such networks has been extremely challenging for many years, actually executing a trained network is relatively simple.

In a CNN, each convolution output element is operated on by passing an independent kernel over the input tensor to produce components of the output tensor. Typically, when a neural network is used to process images, the first layer of the network operates on an input array of RGB pixels of the image and produces an output array of associated size containing an arbitrary vector of output components that are structurally unrelated to the RGB vectors of the input components. The output vector components are often described as features or activations, and represent the strength of the response (degree of recognition) of each kernel. Subsequent layers in a CNN use the output from previous layers as their input, so only the first layer operates on pixel values; all remaining layers operate on features to produce more features. The output features of the convolution are unrelated and different from each other feature, just as color components are different from each other.

The common form of a CNN layer is a 3x3 convolution. In the operation, a 3x3 kernel of constant weights is applied element-wise to each specific position of the input tensor (i.e., image); that is, each of the weights is multiplied by the pixel component at the same relative position in the image, and the products are summed to produce a single component of the output at that position. The bias constant (which can be zero) provides an initial value to facilitate solving the model to achieve the optimal weight value.

If there are three input components, as there are in RGB images, there are three different sets of 3x3 weights to be applied to each component value (color in the case of the first layer), but there is only a single initial bias. Each convolution of the 3x3x3 weights plus the bias forms a single output component value corresponding to the location at the center of a 3x3 pixel patch. Each output channel has its own 27 weight values applied in turn until all output components for a given patch (a subset of input components at the same location as the output location and corresponding to the relative location of the core weights) have been calculated. Convolutions typically have 64 to 256 output components, each of which has a unique set of specific 27 weights plus the bias.

In this example, each core multiplies its 27 weights with the same block of 9 pixels of the 3 RGB components. For relatively small groups of 64 output components, each individual input component is multiplied by 64 arbitrary and unrelated weights. After the output components of each block are calculated, the neighboring blocks are loaded from the image and the core's full set of weights is applied again. This process continues until the right edge of the image is reached, and the blocks go down one row and start again from the left edge.

After processing the first layer, the next convolution layer processes the output of the first layer as input to the second layer. Therefore, the 3x3 convolution now has 3x3x64 weights to be applied to the 3x3x64 input components of the small block. If this layer has 256 outputs, then 3×3×64×256=147,456 multiplications must be performed for each output position. Those familiar with the art will understand that this is for a single layer in a deep neural network that can contain more than 40 layers.

The number of multiplications applied to each element of the tile is equal to the number of lanes in the layer. In a standard CPU, these multiplications must be done in a certain sequence. Many modern CPUs have the ability to perform multiple sets of multiplications simultaneously, especially if the data format is small (i.e., 8 bits). In a GPU or TPU, the number of available multipliers is much higher, but each multiplier is designed to produce a product from two different and unrestricted factors.

In current technology processors, CPU, TPU or GPU do not take advantage of the simple fact that in CNN implementations, one of the factors used for multiplication is common to all weights applied to the input channels during processing for a tile.

In this application, the inventors propose a large number of multipliers that perform all multiplications in a single step, which otherwise are performed sequentially in a learned manner. When the weights for a set of multiplications all have a certain small precision (typically 8 bits for a TPU), there are a finite number (2 ⁸ = 256) of different weights and a corresponding number of different multiples of a common input (which can be of any size; regardless of the precision of the common factor, there are still only 256 possible multiples when 8-bit weights are applied). In this case, there is a clear advantage in implementing a circuit that produces all the desired outputs simultaneously with far fewer elements than the same number of unrestricted multipliers.

In an embodiment of the present invention, an equivalently large number of multipliers are dedicated to a single input channel and are not always shared. Therefore, the operation has the option of using several clock cycles and multiple register stages. This allows the operation to take a very simple and efficient form without affecting the overall throughput of the system.

In the common case where a single dynamic value is multiplied by many constants, as in embodiments of the present invention, replacing an equivalent set of independent single-stage multiplier circuits with a single multi-stage mass multiplier circuit produces a system that performs the same calculations with substantially higher output throughput and substantially lower power and footprint. Even if the set of outputs is less than the actual number of multiples used, significant power and space savings can still be achieved.

Having established the clear advantages of the unique large number of multipliers in the embodiments of the present invention over independent multipliers, reordering the sequence of operations can further increase the advantages.

The mathematics of neural network (or other similar image processing) algorithms does not require any particular sequence of operations. If the same operations are performed in any order, the same correct operation will be performed.

The inventors of this case observed that the common order in which software is executed on CPU, GPU or TPU based designs is to generate all output channels for a given position at the same time by multiplying the weights by the inputs and summing them immediately. Generating all output channels for a given position at the same time by multiplying the weights by the inputs and summing them immediately minimizes the number of times the inputs must be read from RAM and limits the number of times the weights must also be read from RAM. It does not eliminate multiple reads of inputs because there is no place to keep the inputs except RAM when processing the next row.

However, if, in an embodiment of the invention, the sequence of operations of a core or other aperture function defined to operate on M by N blocks of array inputs is flipped, that is, effectively flipped inside out, each input value is used only once, and no RAM buffer is required. Rather than generating outputs one at a time by redundantly reading the inputs as the aperture function passes through each row, this unique operation processes the inputs only one at a time as they are initially presented and retains partial sums of all incomplete outputs. The partial sums can be retained in hardware shift registers or standard hardware first-in, first-out registers (FIFOs), and the number of registers required to hold the values retained is proportional to the height of the core and the width of the input rows.

Since the function implementing the aperture function can be decomposed into a series of subfunctions, each of which operates on the results of the immediately preceding subfunction, the implementation of the core can be achieved by synthesizing the subfunctions sequentially over time, so that each subfunction operates on the received data immediately and produces the same sequence of operations as applying the core in the summary. We refer to this re-synthesized function (including any initialization) as the aperture function, and the individual steps as subfunctions. As used in this article, an aperture function refers to any M by N calculation to be implemented at multiple locations on a sliding window or tile of M by N inputs in a larger R by C input array. As with the implementation of the full CNN core, the aperture function may also include initialization and termination operations. In the case of CNNs, initialization preloads bias values into the accumulators and ends by transforming the raw output of the core via any activation functions.

In this example of the invention, when the components of each new input position are presented, the component at that position represents the first element of the tile downward and to the right, and simultaneously represents the last element of the tile upward and to the left and the intermediate elements of all other tiles that intersect the current position. This allows operation circuits to be developed as embodiments of the invention that always have a fixed number of elements in process (with some possible anomalies near the edges of the input), and produce output at the same rate as it accepts input.

There are a number of special cases and problems that arise when the guided algorithm needs to evaluate the aperture function on patches that extend beyond the edge of the input array, but they are not insurmountable. Special case logic can be added to make partial results for overlapping patches compatible with the normal case without affecting the overall throughput.

In an embodiment of the present invention, this inverted form of the aperture function operation accepts inputs as a stream and produces outputs as a stream. The inputs do not need to be buffered in RAM because they are each referenced only once. Since the outputs are also in stream form, they can also be processed by subsequent layers without RAM buffering, which is a result of the present invention, which significantly increases processing speed compared to many other necessary read and write operations to RAM.

In an embodiment of the present invention, instead of having many layers sharing a single set of independent multipliers execute, store, and then read back the results to process the next layer in sequence, a pipeline can be created using a dedicated large number of multipliers that process all layers simultaneously, thereby streaming the output of each layer into the input of the next layer without waiting for any layer to complete.

Thus, the fully implemented pipeline of an embodiment of the present invention can achieve effective throughput measured by two orders of magnitude greater than known output-centric sorting processes, and eliminates the contention for RAM (since the pipeline does not use RAM). This contention for RAM forms a major bottleneck for GPU- and TPU-based processing.

In an embodiment of the present invention, the latency of such a system is reduced to the time from the input of the last pixel to the output of the final result. Since, by definition of the algorithm, the last pixel of the image must be the last data required to complete all final operations of all layers, the latency of the system is strictly the clock rate multiplied by the number of different clock stages in the pipeline including the final output.

In embodiments of the present invention, the use of a single dedicated bulk multiplier for each input channel in the entire neural network (instead of a finite set of independent multipliers that must be reused and dynamically allocated) makes it possible to build a pixel-synchronous pipeline where all multiplications are performed in parallel because it only employs a single bulk multiplier to process any number of weights applied.

Having described the necessary features of a large number of multiplier innovations, and having also described the advantages of flipping, the inventors of this case assume the following specific example:

FIG. 1 is a diagram illustrating an embodiment of the present invention in which each of a plurality of one or more source channels 1 to N (labeled 101a to 101d) has an assigned dedicated mass multiplier 102a to 102d. Since each source channel in this example has a dedicated mass multiplier circuit to create a set of multiples of the value of that channel, the source channel format can vary between signed, unsigned, fixed or floating point for any accuracy convenient for the processing algorithms implemented in hardware. Certain outputs of each mass multiplier circuit (such as mass multiplier circuit 102c) can be fed directly into one or more operational units 103a to 103d, which can perform calculations requiring multiples of any or all of the source channels. Such an operation unit may be used to implement a single algorithm or independent output channels of unrelated algorithms to be operated on the same source channel. The output of the operation may be forwarded for further processing, as shown at 104, as may be required by one or more algorithms implemented in hardware. This may occur, for example, when implementing a neural network in a field programmable gate array (FPGA), where the weight values applied as multiplicands will not change.

FIG. 2 illustrates an embodiment of the present invention, wherein the output of each of the mass multipliers (such as mass multiplier 102a of FIG. 1 ) is fed to the operation units 203a to 203d via a set of multiplexers 201a to 201d, so that the selected multiples can be selected at the initialization of the system or dynamically selected during its operation. The output of the operation can then be forwarded for further processing at 204, as described above. This situation arises when implementing a neural network in an application specific integrated circuit (ASIC), where the structure of the operation is submitted, but the weight values used need to be changeable.

Fig. 3 illustrates the internal structure of the mass multiplier 102a of Fig. 1 and Fig. 2 in one embodiment. This structure can be common to other mass multipliers in mass multipliers 102b, 102c and 102d and other embodiments of the present invention. In this structure, the products 303a to 303f of all possible multipliers of the source channel multiplicand 101a of A bits by B bits are generated in parallel and delivered to the multiple 304. In this example, the A bits of the source multiplicand 101a are copied and shifted upward by appending a 0 bit to the least significant position and filled by filling a 0 bit to the most significant position so that a full set of all required shift values 0 to B-1 are available in the form of a vector of A+B bit entries 302a to 302d. These terms may be formed solely by routing circuit connections, and no registers or logic circuitry is required. Where the clock cycle is sufficient to allow up to B terms of A+B bits to be constructed in a single cycle, no registers or sub-assemblies may be required. Individual products of the sum terms 303a to 303f may be locally buffered or forwarded for further processing as combinatorial logic. Each product of 1 to 2^B-1 times the source multiplicand 101a may be formed by adding any or all of the B corresponding terms 302a to 302d at the location where a 1 bit occurs in each multiplier. Any and all source multiples of 0 are constants of all 0 bits and may be included in multiples 304 for completeness when multiplexers are used, but no circuitry is otherwise required. Any unused products 303a-303f may be omitted by excluding them from the circuit specification, thereby allowing synthesis tools to remove them, or by any other method. Unused terms 302a-302d may also be omitted, but since they do not occupy logic, such omission generally has no effect. In this way, all required multiples 304 of source multiplicand 101 may be formed as a single stage of pipeline or combinatorial logic.

FIG. 4 shows an optimized embodiment in which a set of terms 401 includes all required individual terms 302a to 302e from 0 to B (inclusive) formed by A+B+1 bits. This allows the products 402a to 402f to include subtracting smaller terms from larger terms rather than adding smaller terms, and can be used to reduce the overall size of the circuit, which can also increase the maximum allowable clock frequency. For example, for any given input a and multiplier 15, 8a+4a+2a+1a=15a combines four components, while 16a-1a=15a combines only two components and can generally be expected to be more compact and efficient. Each product 402a-402f may be constructed from any addition and subtraction of terms 302a-302e that produces the correct result, and each particular variation may be chosen based on the best compromise for a particular implementation. For example, subtraction of two N-bit quantities may require more logic than addition of two N-bit quantities, but in general, addition of three N-bit quantities will always require more logic than subtraction of two N-bit quantities. The handling of required multiples 304 does not change with the details of synthesizing individual products 402a-402f.

FIG. 5A illustrates an embodiment of a large number of multipliers in which the clock cycle is such that only a single addition of A+B bit values (or A+B+1 bit values if subtraction is used) is possible per cycle. In this case, in order to accommodate multiples of more than two terms, it is necessary to configure the required elements into a multi-stage pipeline. Term 401 is formed by each source channel 101, as previously described, but is retained one or more times in pipeline registers 501a and 501b for later reference. The pair 502 of the two terms being summed is calculated and stored, and then saved 503 as needed. A triplet 504 is formed as the sum of the pair 502 and the retained term 501. A quad 505 of the term value is formed as the sum of the pair 502. Any and all unused elements may be omitted, and to increase overlap, only a descending sequence of addends may be specified. This ensures that redundant sums (e.g., a+b and b+a) are not utilized and are retained in the final circuit. Products 506a-506f may utilize any addition or subtraction operation of any pair of stored subcomponents that meets the timing constraints. By consistently using the largest elements available, the overall size and therefore power may be reduced, but any combination of operations that produces the correct result is acceptable.

The embodiment of FIG. 5A is sufficient to generate all required multiples, where B=8. For larger multiples, the sub-compositions shown may be reorganized in further pipeline stages so that all required multiples 506a to 506f for any value of B may be constructed by single-clock operations on an expanded set of sub-compositions including the previously disclosed reserved item 501b, reserved pair 503, triplet 504, and quad 505, together with such other sub-compositions as required, to form a combination sufficient to form multiples 506a to 506f by single-clock operations.

FIG. 5B illustrates an embodiment in which multiples are formed directly from a set of fixed cases without reference to standard arithmetic operations. For each of the required multiples, the set of output values a*b is enumerated for each source channel value a. This allows the hardware circuit synthesis tool to determine the best logic circuit 507 to generate the full set of required multiples. The specification of the output values required for any given input value is typically formulated by enumeration in a Verilog "case" or "casex" statement. This is different from a lookup table, in which the output values are stored and accessed via an index formed from the input, because logic gates are used to implement the smallest subset of operations required to generate the full set of output values, and the redundant logic used to generate the associated sub-expression will be combined.

Which of methods 5A and 5B is most efficient in terms of space, frequency, and power depends on the specific values of A and B and the core efficiency of arithmetic operations versus arbitrary logic. The choice of which method to use can be based on direct observation, simulation, or other criteria.

FIG. 6 illustrates an embodiment in which the clock cycle is such that sufficient logic levels permit composition by addition and/or subtraction of four elements during each single clock cycle. By selecting from a set of subsets, each product 605a to 605f can be produced by combining no more than four stored elements. As previously described, the entries are retained in registers 501a and 501b, but the triplet 601 retained in 602 is constructed directly from entry 401 and no pairs are used. Seven bytes 603 and eight bytes 604 are formed from triplet 601 and the retained entry 501a.

The exemplary embodiment of FIG. 6 is sufficient to produce all required multiples where B=32. For larger multipliers, the shown subcombinations may be reorganized four at a time in further pipeline stages to produce all required multiples for any value of B. The shown subcombination of elements is necessary and sufficient to produce all products where B=32, but other subcombinations (perhaps chosen for consistency between different values of B) are acceptable.

When the set of multipliers is fixed, as is common for FPGA applications, even a large set of sparse multipliers can be implemented efficiently because common elements are merged and unused elements can be omitted. When the synthesis tool performs this function automatically, the expression of the circuit can include all possible elements without explicitly stating which multiples are used.

If the operation on the A+B or A+B+1 bit values cannot be completed in a single clock cycle, multiple stages of pipeline adders can be inserted for any single stage of logic, with additional pipeline registers inserted as needed to make all paths have the same number of clock cycles. The pipeline stage cycle can be a single edge-to-edge clock transition, or a multi-cycle clock if the input throughput constraints allow. The use of multiple clock stages per operation and multi-cycle clocks does not require architectural changes to any embodiment, except for the issues just mentioned above.

An important object of the present invention is to provide an industrial mass multiplier implemented in an integrated circuit for use in a variety of applications. To this end, the inventors of the present invention provide, in one embodiment, a mass multiplier implemented as an integrated circuit having: a port for receiving a stream of discrete values, a circuit system for multiplying each value received at the port by a plurality of weight values simultaneously, and an output channel for providing the products produced by the mass multiplier.

In one version, the received discrete values may be fixed-width unsigned binary values, the weight values may be fixed-width unsigned binary values of two or more bits, and each multiple may be constructed as a sum of bit-shifted copies of the inputs. In another version, the set of shifted copies may be increased to allow the use of reduction operations to reduce or otherwise optimize the circuit. Unused outputs in the set may be omitted explicitly or implicitly.

In one embodiment, the set of output products may be generated by combinatorial logic. In another embodiment, the set of output products may be generated by a single-stage pipeline using single or multiple clock cycles. In another embodiment, the set of output multiples may be generated by a multi-stage pipeline by combining no more than two addends per stage. Unused elements of intermediate components may be eliminated from the circuit either explicitly or implicitly.

In one embodiment, the set of output products may be produced by a multi-stage pipeline by combining three or more addends per stage, and the sub-assemblies may be adjusted accordingly. Unused elements of intermediate sub-assemblies may be explicitly or implicitly eliminated from the circuit.

Another object of the present invention is to provide a large number of multiplications in an integrated circuit to implement substantially improved convolutional neural networks in the continued evolution of deep learning and artificial intelligence. In this effort, the inventors of this case provide a first convolutional neural network (CNN) node implemented as an integrated circuit, the first CNN node having a first input channel defined as a stream of discrete values of a first component of an element of an array.

In this description, the inventors of this case intend that the nomenclature of the elements of the array represent elements that may have a single component or multiple components. A good example is an image that may have pixels as elements, and if the image is monochrome, each pixel may have a single component, or in one example, if the image is in RGB color form, each pixel may have three color values. In this example, each color value is a component of an element, which is a pixel.

Continuing with the above description of a first convolutional neural network (CNN) node implemented as an integrated circuit, the first CNN node has a first input channel of a stream of discrete values of a first component defined as an element of an array, and further in the CNN there is a first plurality of multiplier circuits that simultaneously multiply the received discrete values of the first component by a plurality of weight values. The output channel provides an output stream of discrete values.

In one embodiment of a CNN node, a first output stream is formed from a first plurality of multiplier circuits by combining the products with a constant in some cases and by applying an activation function in some cases.

In another embodiment, the CNN node further includes a second input channel defined as a stream of discrete values of a second component of the elements of the array, and a second large number of multiplier circuits that simultaneously multiply the received discrete values of the second component by a plurality of weight values. In another embodiment, there may be a third input channel defined as a stream of discrete values of a third component of the elements of the array, and a third large number of multiplier circuits that simultaneously multiply the received discrete values of the third component by a plurality of weight values.

Having described a CNN node with one, two or three input component streams and a dedicated large number of multipliers, the inventors of the present case further provide a convolutional neural network (CNN) having: a first convolutional neural network (CNN) node implemented as an integrated circuit, and a second CNN node having an input that depends at least in part on the output of the first node, the first CNN node comprising: an input channel of a discrete value stream of components defined as elements of an array; a large number of multiplier circuits dedicated to individual input channels, the large number of multiplier circuits multiplying the received discrete values of the components by multiple weight values simultaneously; and an output channel providing an output stream of discrete values. This CNN may have consecutive nodes and may operate as a deep neural network (DNN). It is not required that the consecutive nodes after the first node be CNN nodes.

Pipeline aperture function calculation

Now returning to the previous description in this specification, discussing the order of operations when processing a CNN or other similarly selected aperture function that passes an array of operator subfunctions over an input array to produce a final result, a specific description of the flipped form of the aperture function operation in an embodiment of the present invention is now provided, which accepts inputs as a stream and produces outputs as a stream. In this embodiment of the present invention, the inputs are not and need not be buffered in RAM because each input is only referenced once. The output is also produced in the form of a stream, so the output stream can be processed by subsequent layers without RAM buffering. The inventors of this case believe that this innovation significantly increases processing speed compared to many other necessary read and write operations in other processing systems.

In an embodiment of the invention, an apparatus and method are provided in which the action of passing a two-dimensional aperture function over a two-dimensional array is implemented by acting on an incoming stream of inputs, such that all inputs are processed immediately and partially completed operations are retained until such time as all required inputs are received and processed, and outputs are produced in the form of a conforming stream, which generally has the same or lower data rate as the input stream. All inputs are accepted and processed at the rate provided and need not be stored or accessed in any order other than the order presented. If the application of the aperture function is defined so that more outputs are produced than inputs, the circuit can still operate at the incoming data rate by selecting a processing clock rate that is incremented enough so that the system is not unable to accept and process the input when it is presented.

The known way to implement a convolution of a kernel or more general aperture function over a large input array is to collect the required input chunks, apply the function to the inputs, and output the results. As the aperture passes over the input array, each subsequent chunk will overlap the one just processed, so some inputs can be preserved and reused. Various mechanisms such as FIFOs can be used to avoid redundant reading of inputs from source registers as chunks advance to new rows, but the source data will still be applied sequentially to each location in the kernel to produce each output whose input chunk overlaps each particular data input location.

If there are many output channels and many independent aperture functions to be operated on, a large number of multipliers can be used to provide products of small blocks of input values under consideration to all aperture functions in parallel. But with this configuration and order of operations, each position of the source data will require a set of products for each position in the core as the various positions of the source data are combined into overlapping various output positions.

The mechanism of the invention is to flip (i.e., inside out) the order of operations to obtain the specific advantage of using a single large multiplier per input channel that is applied only once to a given input value. Rather than retaining or re-reading source values for later use in the form of computing later products, the process in an embodiment of the invention computes all required products for each input as it is presented and maintains a running total of each element of the aperture function that is complete up to the point at which the current input is presented.

Any aperture function that can be mathematically decomposed into a series of subfunctions applied sequentially can be implemented in this way. This mechanism can be easily applied because the CNN core is just a sequence of additions of weights times the products of the inputs, and the order of operations is compatible with the order in which the source inputs are taken from left to right, top to bottom.

In an embodiment of the invention, an array of synthesizers is implemented on an IC, the synthesizers corresponding to sub-function elements of an aperture function, each of which maintains a running total of the value of the aperture function as it progresses through the input stream. The complete value of the final synthesizer output function in the array, and partial values of all other synthesizer output functions.

In the simple case of applying a 3x3 kernel, the output of the top left synthesizer reflects the first element of the kernel applied to the current input plus any initialization constants, the output of the top middle synthesizer reflects the first two steps, and the output of the top right synthesizer reflects the first three steps. The output of the top right synthesizer needs to be delayed until it can be used again by the next row. The next row of synthesizers continues the pattern of accepting partially completed function values plus the contribution of each new input and passing it onward. The last row of synthesizers completes the last step of the function and outputs the completed value for any further processing.

Note that the partial values of a function usually progress from left to right in the first column, then from left to right in subsequent columns, and finally to the last combiner in the last column. We can think of the flow of partial values as a stream and refer to combiners and flows as upstream or downstream.

Each synthesizer always maintains a partial sum of aperture functions up to and including the current source input. Each synthesizer always operates on a different tile position of the output, specifically, on the tile in the synthesizer's relative position in the array of aperture subfunctions where the current input appears.

u=k+a ₁₁ w ₁₁+a ₁₂ w ₁₂+a ₁₃ w ₁₃+a ₂₁ w ₂₁+a ₂₂ w ₂₂+a ₂₃ w ₂₃+a ₃₁ w ₃₁+a ₃₂ w ₃₂+a ₃₃ w ₃₃ If the 3×3 kernel W is expressed as a function of input A, then

u = k + a ₁₁ w ₁₁ + a ₁₂ w ₁₂ + a ₁₃ w ₁₃ + a ₂₁ w ₂₁ + a ₂₂ w ₂₂ + a ₂₃ w ₂₃ + a ₃₁ w ₃₁ + a ₃₂ w ₃₂ + a ₃₃ w ₃₃

The implementation core functions can be decomposed into equivalent sub-functions.

v ₀ ( a )= k + aw ₁₁ v ₁ ( t , a )= t + aw ₁₂ v ₂ ( t , a )= t + aw ₁₃ v ₃ ( t , a )= t + aw ₂₁ v ₄ ( t , a )= t + aw ₂₂ v ₅ ( t , a )= t + aw ₂₃ v ₆ ( t , a )= t + aw ₃₁ v ₇ ( t , a )= t + aw ₃₂ v ₈ ( t , a )= t + aw ₃₃ u = v ₈ ( v ₇ ( v ₆ ( v ₅ ( v ₄ ( v ₃ ( v ₂ ( v ₁ ( v ₀ ( a ₁₁ ) ), a ₁₂ ), a ₁₃ ), a ₂₁ ), a ₂₂ ), a ₂₃ ), a ₃₁ ), a ₃₂ ), a ₃₃ ) u =((((((( k + a ₁₁ w ₁₁ )+ a ₁₂ w ₁₂ )+ a ₁₃ w ₁₃ )+ a ₂₁ w ₂₁ )+ a ₂₂ w ₂₂ )+ a ₂₃ w ₂₃ )+ a ₃₁ w ₃₁ )+ a ₃₂ w ₃₂ )+ a ₃₃ w ₃₃ u = k + a ₁₁ w ₁₁ + a ₁₂ w ₁₂ + a ₁₃ w ₁₃ + a ₂₁ w ₂₁ + a ₂₂ w ₂₂ + a ₂₃ w ₂₃ + a ₃₁ w ₃₁ + a ₃₂ w ₃₂ + a ₃₃ w ₃₃ = u ( A , W )

The circuitry required to compute those subfunctions is then configured in the corresponding synthesizer arrays.

and partially completed and maintained as the output value of the synthesizer

where a _i is the current value from the input stream and in each case a _i-1 to a _i-8 are the previously processed inputs for a particular tile in which a _i appears in a position relative to the output of each individual synthesizer. Each synthesizer will operate on the value of the aperture function up to and including the position that the synthesizer corresponds to in the aperture array. Each synthesizer takes the current value of the input stream and combines it with the previous value to produce a different partial sum corresponding to the partially processed tile in the input array in which the current input value appears in a relative position of that tile corresponding to each synthesizer's position in the aperture function.

In this way, partial values of the aperture function, computed in standard order and accuracy, are maintained on the input stream over time until the completed value is ready for output.

While this technique is fairly straightforward inside an input array, complications arise when applied to small tiles that overlap the edges of the input array because the aperture function is defined differently when all inputs are not available. In the case of a CNN core, the extra operations are discarded, which is equivalent to using zero as input. The present invention is about maintaining a steady flow of partial sums through the synthesizer while handling those anomalies, as described below.

FIG. 7 is a diagram showing the structure and connectivity of receiving an input stream, preprocessing the input stream, and feeding the result through a unique digital device to generate an output stream in an embodiment of the present invention.

The input channel set 701 and associated control signals 702 are used by common circuitry 703 to generate any and all products of the input channel set and weights for use in subsequent subfunctions. The source channel products are then distributed to the bank of subfunction computation circuits 704a, 704b, and 704c, each of which generates a single channel in the output channel set 705. Any number of independent output channels may be supported by common circuitry 703.

FIG. 8A is a diagram of a large number of multipliers 801a, 801b and 801c in the common circuit system 703 of FIG. 7, which use each channel in the input channel group 701 and produce the sparse or complete set multiples required by the defined subfunction. It should be noted that this diagram assumes three channels in the input channel group, such as for the case of red, green and blue pixel values when processing RGB images. In other embodiments, there may be one, two or more than three channels. Any or all products 802 (multiples of the source input array values constructed by the large number of multipliers) can be used by the synthesizer, as shown in FIG. 9A, FIG. 9B, and FIG. 9C described in detail below. The synthesizer is an example of a hardwired circuit system in the unique device of the present invention that performs a subfunction on the source channel products generated by the large number of multipliers of Figure 8A.

FIG8B is a diagram illustrating the structure of a synchronous circuit system that provides both normal and abnormal processing signals to all synthesizers of all output channels.

The control circuit system 803 synchronizes all output and control counters with the source input stream and implements setting the output and control counters to the initial state whenever RST or INIT is asserted.

In this example, the colSrc counter 805 counts the internal dimensions of the array row by row across columns and advances as each set of source channel products is processed. In this example, at the end of each column, the colSrc counter rolls back to the leftmost position (0) and the rowSrc counter 804 advances by one. At the end of the source array stream, the rowSrc and colSrc counters return to their initial state and are ready to receive new input arrays.

In this example, the colDst counter 807 and rowDst counter 806 function together in a similar manner as the counters for all output channels. The colDst and rowDst counters are enabled by the output enable signal (DSTEN) 813 and determine when the post-processing enable signal (POSTEN) 812 is asserted.

It should be noted that the system depicted in this example produces a single output of the aperture function, but will generally be used to produce a stream of channel outputs that is compatible with the dimensions of the source input stream. Each independent output channel will share at least some of the computational circuitry via a large number of multipliers and common control logic.

至M-2之每列合成器將與最後完整輸出同時產生最終經截斷輸出，必須在所有完整小塊輸出之後保留並依序發射該等最終完整輸出，以便符合陣列串流格式。 The output enable (DSTEN) signal 813 controls when the terminator function accepts and processes results from the synthesizer. Although the first several rows are accepted from the source input array, valid results are not presented to the terminator function (see Figure 9C). The output enable signal 813 (DSTEN) is asserted when the rowDst and colDst counters indicate that a valid result is available, or alternatively when a delayed truncated result is being processed. The POSTEN signal 812 is asserted continuously or periodically to match the timing of the SRCEN signal 801. These signals are required to sequence the final outputs of all truncated synthesizers when processing the last row of the source input stream array.

Each row of synthesizers through M-2 will produce a final truncated output concurrently with the last complete output, which must be retained and emitted in sequence after all the complete chunk outputs in order to conform to the array stream format.

In this example, the POSTEN and DSTEN signals and the colDst and rowDst counter values are independent of the SRCEN signal and the colSrc and rowSrc counter values, and delayed results continue to be processed until all delayed results have been finalized and sent to the output stream. The system can accept new input while previous output is completing, thus allowing the system to process multiple frames of the source input stream without pausing between frames. When the source stream data has not reached the end of the array, POSTEN is not asserted and the final result is obtained from the synthesizer. Immediately after reaching the end of the source array, the POSTEN signal is asserted for each additional output and the final result is obtained by truncating delay lines 909, 910a and 910b, as shown in Figure 9C described below, until the rowDst counter reaches the full number of output rows, thereby resetting rowDst and colDst to the initial conditions in preparation for the next data frame.

When the rowSrc counter indicates the first row of the source data group representation array from the stream, the first row signal 808 (ROWFST) is asserted.

When the rowSrc counter indicates the last row of the source data group representation array from the stream, the last row signal 809 (ROWLST) is asserted.

The first row signal 810 (COLFST) is asserted when the colSrc counter indicates the first row of columns of the source data set representation array from the stream.

When the colSrc counter indicates the last row of columns of the source data set representation array from the stream, the last row signal 811 (COLLST) is asserted.

FIG9A, FIG9B and FIG9C illustrate the unique device mentioned above in a general case, wherein M times N sub-function elements of an aperture function are applied to each overlapping M times N small block of an array of R times C inputs, including those small blocks overlapping with edges, the inputs appearing as a stream of related components at regular or irregular time intervals to produce a corresponding stream of R times C outputs, wherein each output is the aggregate effect of the M times N functional elements applied to the input small block as specified by the rules of the aperture function. The functional element applied to each position in the array is in this device a hard-wired synthesizer for each of the M times N sub-functions, as shown in the synthesis of FIG9A, FIG9B and FIG9C.

The effect of the circuit is to compute the overlapped value of the aperture function at each position of the array of R times C inputs using the same sequence of operations that would be used to compute the aperture function individually on each tile. If any positions are not needed in the output stream, circuitry can be added to omit those positions in order to produce a tiled or spaced output rather than a fully overlapped one.

Source channel products 802 and source control signals 814 are available to each of synthesizers 901, 902a, 902b, 902c, 903a, 903b, 903c, 904, 905a, 905b, 905c, 906, 907a, 907b, and 907c. Source control signals are also connected to delays 908a, 908b, 908c, 908d, 908e, and 908f. Output channel control and counter 815 are available to delays 909, 910a, and 910b and termination function 911. Additional pipeline stages may be inserted manually or by automated tools to make the circuit routing feasible for a given clock frequency, provided that the order of operations is not changed. Timing control and counter signals are available to all components of the circuit and are not shown individually.

Each synthesizer has a dedicated direct connection to a specific input product or alternatively to a programmable multiplexer that selects one of the products for each input value in the group and is preconfigured prior to execution of the circuit. Each dedicated connection is a parallel path having a number of wires sufficient to carry the bits representing the desired product in a single input interval. The use of an optional preconfigured multiplexer to select which product for each group element is sent to each synthesizer enables the weight values to be upgraded in the field. Fixed connections are used when the weights are not upgraded and remain fixed for the life of the device. Because the weight selection does not change during operation, the choice of fixed or variable product selection does not affect the operation of the circuit.

Each synthesizer receives the set of products corresponding to the weights of the sub-function from a number of multipliers, one product per input channel, and performs the sub-function operation, typically simply adding them all together to form this synthesizer's contribution to the value of the overall aperture function. Except for those synthesizers corresponding to the left row of aperture functions, each synthesizer also receives partially completed results from the synthesizer immediately to the left. Except for those synthesizers corresponding to the top column of aperture functions, each synthesizer may also receive delayed partially completed results from the synthesizer on the upper column. Each synthesizer has at most one connection from the left and one delayed connection from the top, each of which is a parallel path with a number of conductors sufficient to carry bits representing partially completed results as inputs to the synthesizer. Each synthesizer performs one of three operations, defined by a subfunction with respect to the position of the current input tile relative to the edge of the input array: a combination of the partial result of this synthesizer with an initialization value (if any), or a combination of the partial result of this synthesizer with a partial result from a synthesizer to the left, or a combination of the partial result of this synthesizer with a delayed partial result. The modified result is placed in an output register large enough to contain the result and is made available to the right-side synthesizer and/or delay and termination circuits in subsequent input intervals. This modified result can be a partial result, a complete result, or a truncated result, depending on the position of the synthesizer in the aperture function and the state of the input stream position.

The combiner (0,0) is unique in that there are no combiners to the left or above it in the aperture function, and therefore the operation is always initialized with each set of inputs received.

The synthesizer (M-1, N-1) is unique in that the result produced is always final, but is structurally identical to all other synthesizers 903a, 903b, or 903c.

Some synthesizer outputs are tapped for delay or post-processing, in which case the path through such delay or post-processing is wide enough to transmit bits representing partial, truncated, or completed results. Some synthesizer outputs are used only by the right-hand synthesizer. The internal operations of the synthesizer and the output data format do not need to change based on the use of the output.

The finalization circuit takes results from several possible sources and multiplexes them to select which possible source to process at any interval. After applying the finalization function (if any), the width of the final output can be reduced and will form the output stream of an embodiment of the present invention, which can be the input stream containing the next final output of the system of the present invention, or can be used for further processing.

The data paths on the unique device in the embodiment of the present invention are indicated in FIG. 9A , FIG. 9B and FIG. 9C by thick lines with directions indicated by arrows, and the ellipsis indicates the position of the last row or column in the range of all repetitions. The data path (a) from the source channel product 802 is a set of parallel conductive paths, one path dedicated to each product of the input components, each product being the value of the input component multiplied by one of the multiple weight values of the aperture function. It should be understood that the 5 times 5 aperture function has 25 weight values for each input component. For the case of an aperture function for an R times C input array of R, G and B color pixels, there are 75 weight values. So, in this case, line (a) has 75 parallel paths, each with a set of parallel conductors wide enough to accommodate the required number of bits to ensure accuracy. Line (a) is referred to in the art as a point-to-point connection, not a bus.

The data paths (b) in Figures 9A, 9B and 9C are not extensions of line (a), but are dedicated connections to a specific subset of the paths in line (a). Line (b) is not labeled in each of the examples in Figures 9A, 9B and 9C, but each connection from line (a) directly to an individual one of the synthesizers is a dedicated line (b). The dedicated connection for each synthesizer is to that subset of the paths that carry the product of each input component and the weight value required by that synthesizer.

The data paths (c) in Figures 9A, 9B, and 9C are point-to-point paths between each synthesizer and the output register in the next right synthesizer. These data paths are dedicated paths with accuracy bandwidth that typically carry a portion of and, as described in detail elsewhere in the specification. Not every path (c) is labeled in the figure, but it can be assumed that in this example, every direct connection from one synthesizer to another is a path (c). It should be noted that there are instances where output paths (c) branch to alternative circuit systems.

Another different data path in an embodiment of the present invention is marked as (d) in Figures 9A, 9B and 9C. These data paths are dedicated data paths from delay circuits such as circuits 908A to 908f back to the synthesizers below the row and the left synthesizer or directly to other delay circuits. The delay circuits are constructed to accept partial sums at the right end of a row of synthesizers, delay the partial sums for a specific number of source intervals, and then pass those partial sums to another synthesizer and/or other processing at an appropriate time. The overall functionality is described in detail elsewhere in this specification. Path (d) between delay circuit systems is a similar dedicated path that is generally used for partial sums to be passed at certain source intervals.

If either M or N decreases so that the last column or row of a range is not needed, an implementation is made in which the end element is omitted and the first column or row of the range is retained. In the degenerate case where either or both M or N decreases to 2, the first and last columns or rows are retained and the middle columns or rows are omitted. In the degenerate case where either M or N decreases to 1, an implementation is made in which the first and last synthesizers are combined and no special initialization is required. In the special case where both M and N are 1, no inversion of the aperture function is required, but the use of a large number of multipliers still provides various advantages.

The source channel products 802 may be any set of binary values simultaneously associated with a particular position of the R by C array and presented in some predefined sequence. The source channels of the input stream may be any combination of integer or fractional values in any format of any nature defined for the input to the aperture function. An example is pixel values from one or more video frames and/or any other sensor values scaled to match the array size R by C, and feature component values produced as output of a CNN layer. It is emphasized that each node embodying the present invention may accept outputs from other nodes in addition to or in lieu of the primary source input. Although in embodiments of the present invention, one or more first nodes typically accept image pixels as the primary input to the system, there is no restriction on the nature of the data being processed if the data can be formatted as a stream representing an R by C array.

In one embodiment of the invention, source stream element groups may be presented in column priority order, with each subsequent row presented in strictly ascending order. In some embodiments of the invention, columns and rows need not correspond to horizontal or vertical axes, but may be arbitrary, such as when scanning rows up or down and scanning from left to right. Columns R and rows C refer here only to the major and minor axes of the stream format. Circuitry need not be adjusted for input signals that generate input streams in orientations other than standard video left-to-right, top-to-bottom order. Aperture subfunctions may be oriented to produce the same output for each input array position.

In this example, the source inputs are presented as the product of the source values required by the aperture function and the weights, with a signal indicating when each new set of elements is valid (SRCEN, see Figure 8B). The inputs can be paused and resumed at any time. In some examples, a minimum spacing between inputs can be defined, and the circuit can use multiple cycles or higher speed clocks to reduce size, power, or otherwise utilize, and the output channel groups can use the same minimum spacing.

Common control and synchronization circuitry 803 (FIG. 8B) provides counters and control signals describing the current input position in the R by C array. The counters can continue to run additional columns and rows after the final input to help the termination function 911 (FIG. 9C) output the accumulated output generated by the last column input over the input rows. (See FIG. 12, FIG. 13 and FIG. 14 and the description below) The control signals are available to all other components and are not shown in FIG. 9A, FIG. 9B and FIG. 9C.

Synthesizer circuits 901, 902a, 902b, 902c, 903a, 903b, 903c, 904, 905a, 905b, 905c, 906, 907a, 907b and 907c each operate on that portion of the aperture function assigned to their position in the M times N function. All synthesizers operate on the same set of source channels and on the column and row counter states provided by control 803. Details of the data handling of the aperture function are further described below with reference to additional figures.

When a source input set is received from an input stream, the partially completed operation of the aperture function applied to all tiles overlapping the current position in the input stream is passed from left to right and top to bottom within the synthesizer's M by N array. This operation accumulates the complete operation of the aperture function over time and outputs the correct implementation of the aperture function on each tile of the input array, thereby producing the same results through the same order of operations as if the aperture function was implemented by reading the input values directly from the array. Replacing random access to the array with stream access is an important feature of the present invention and eliminates the requirement for redundant access to random access memory.

至N-1處，部分輸出經傳遞至延遲級908a、908b、908c、908d、908e及908f，在該等延遲級中該等部分輸出經保持用於所需之輸入間隔數目，使得當接收到對應於小塊之下部列的輸入時，該等部分輸出可用於同一邏輯小塊位置之進一步運算。 In the right row of synthesizers except the bottom row

At N-1, the partial outputs are passed to delay stages 908a, 908b, 908c, 908d, 908e and 908f where they are retained for the required number of input intervals so that they can be used for further operations at the same logic tile location when inputs corresponding to the lower row of tiles are received.

至N-1及列0至M-2之所有合成器亦表示針對包括輸入陣列之最後行的小塊之彼列的最後運算，並且其值經轉發至延遲級908a、908b、908c、908d、908e及908f且需要特殊處理以便插入在序列中，使得當接收到後續輸入列時，該等合成器將在正確時間可用於繼續運算孔徑函數。參見圖11及相關聯的描述。 When processing the last row C-1 of each input column, the

All synthesizers to N-1 and columns 0 to M-2 also represent the last operation for that column of the tile that includes the last row of the input array, and their values are forwarded to delay stages 908a, 908b, 908c, 908d, 908e and 908f and require special processing to be inserted in the sequence so that when subsequent input columns are received, these synthesizers will be available to continue operating the aperture function at the correct time. See Figure 11 and the associated description.

至N-1之所有合成器亦表示孔徑函數元素之經完成但經截斷之累加，並且直接發送至終結函數911以進行處理以便插入至輸出串流中。 In this example, the combiner 903c at the (M-1, N-1) position always produces a completed accumulation of M times N subfunction elements, but is otherwise indistinguishable from the other combiners of that configuration 903c. As described above, when processing the last row C-1 of each input column, the sum of the elements from row M-1 is calculated.

All synthesizers through N-1 also represent a completed but truncated accumulation of aperture function elements and are sent directly to the finalizer function 911 for processing for insertion into the output stream.

至M-1之合成器亦表示子函數元素運算之經完成但經截斷之累加，並且經發送至經截斷輸出延遲線909、910a及910b且經保持直至來自列M-1之主要輸出已在911處終結為止。在如圖8B中所示之控制信號的情況下，附加的M-

列經截斷輸出自延遲線909、910a及910b傳送並在911終結，並且最終以任何所需時序間隔提供至輸出串流匯705。 In this example, when processing the last column R-1 of the input, the

The synthesizer to M-1 also represents the completed but truncated accumulation of the subfunction element operation and is sent to the truncated output delay lines 909, 910a and 910b and is held until the main output from column M-1 has terminated at 911. With the control signal as shown in FIG. 8B, the additional M-

The truncated outputs are sent from delay lines 909, 910a and 910b and terminate at 911 and are ultimately provided to output bus 705 at any desired timing interval.

FIG. 15 is a diagram illustrating a specific case of pipeline operation in an embodiment of the present invention implementing a 5x5 product node.

Source channel products 802 and source control signals (not shown here) are available to each of synthesizers 901, 902a, 902b, 903a, 903b, 904, 905a, 905b, 906, 907a, and 907b. Source control signals are also connected to delays 908a, 908b, 908c, and 908d. Output channel controls and counters are available to delays 909, 910a, and termination 911. Additional pipeline stages may be inserted manually or by automated tools to make the circuit routing feasible for a given timing clock frequency, provided that and only if the order of operations is not changed. Timing control and counter signals are available to all elements of the circuit and are not shown individually.

As each set of source channel products is presented in turn, each synthesizer selects the appropriate product to compute for the subfunction corresponding to the position in the aperture function. Each 5 by 5 tile that intersects the current position in the input array is modified to include the operation based on the product at that position. The net effect is that a single source input stream is transformed into a set of 5 by 5 parallel partial operation streams that are passed between synthesizers until all operations on each tile are completed, which usually happens in synthesizer (4,4), and sometimes in other cases when processing the right or bottom edge of the input array.

Note that only the width of the input array affects the size of the delayed elements, since each delayed element must delay a fraction of the number of source input intervals corresponding to receiving input at one row and input at the same row on the next row.

FIG16 shows a 4×4 implementation of the IC of the invention. Known cores can have an odd number of subfunctions in columns or rows, or an even number of subfunctions. This even version is degenerate in the sense of element 910* as shown in the general case of FIG9C, and does not occur at all in the specific case of FIG15 for a 5×5 aperture function (odd number of columns and rows) because the extra line of output processing is omitted.

,

)處之自然劃分的右側及下方。在本發明之替代實施例中，電路可經修改以將中心定位在自然劃分的上方及左側。 The odd-sized cores are symmetrical about the center in both directions, but the center is offset in the case of even-sized cores. The IC in the embodiment of the present invention places the center for even-sized cores at position (

,

) to the right and below the natural division. In an alternative embodiment of the invention, the circuit may be modified to position the center above and to the left of the natural division.

Except for these comments, the operation of the particular IC of FIG. 16 is as described for the other versions described.

FIG. 10A is a diagram showing the internal structure and operation of synthesizers 905a, 905b, and 905c of FIG. 9A and FIG. 9B or FIG. 15 in an embodiment of the present invention. A source input set 1001 of stream values in a channel set (which may be a single or a mixture of data types required by the aperture function) is used by circuit system 1004 to calculate the contribution of each individual synthesizer.

Circuit system 1005 uses the output of 1004 to calculate the initial value of the sub-function. Circuit system 1006 uses the output of 1004 and the partial value previously calculated by the synthesizer 1002 immediately to the left to calculate the ongoing partial value of the sub-function. Circuit system 1007 uses the output of 1004 and the partial value previously calculated and delayed from one of 908a, 908b, 908c, 908d, 908e and 908f on the synthesizer row 1003 immediately above to calculate the ongoing partial value of the sub-function.

The operations of circuit systems 1005, 1006, and 1007 may be performed simultaneously (in the same clock cycle) with the operations of circuit system 1004 using their common outputs or may be implemented by a series of pipeline stages synchronized by the same clock.

Multiplexer 1008 selects which variant of the partial result to forward as the partial value of the subfunction as the output of synthesizer 1009. If COLFST 811 is not confirmed, the output of 1006 is selected, otherwise if ROWFST 808 is not confirmed, the output of 1007 is selected, otherwise the output of 1005 is selected.

This conditional processing is a natural consequence of allowing the M times N aperture function to extend over the edges of the source input stream of the R times C array representing the value group. The single position on the leftmost edge or the topmost edge will be the first operable element of the aperture function for several small blocks adjacent to or overlapping those edges. Therefore, each synthesizer located in the first operable position of the overlapping small blocks needs to be initialized with the basis value of the aperture function. In addition, each synthesizer located in the first operable position of the subsequent column of the small block must be combined with the previous value of the partial value of the same small block operated from the immediately preceding column. In this way, a single circuit is used to ensure correct operation of all tiles that overlap, are adjacent to, or are inside the top and left edges.

In FIGS. 10B to 10G , all components described in FIG. 10A and using the same component numbers are functionally identical to those components described with reference to FIG. 10A .

FIG. 10B is a diagram showing the internal structure and operation of synthesizers 902a, 902b, and 902c of FIGS. 9A and 9B or FIG. 15 in an embodiment of the present invention. A source input set 1001 of stream values is used by circuit system 1004 to calculate the synthesizer's contribution to the aperture function.

Circuit system 1005 uses the output of 1004 to calculate the initial value of the sub-function, and circuit system 1006 uses the output of 1004 and the partial value previously calculated by synthesizer 1002 immediately to the left to calculate the ongoing partial value of the sub-function.

Multiplexer 1010 selects which variant of the partial result to forward as the partial value of the subfunction as the output of synthesizer 1009. If COLFST 811 is not confirmed, the output of 1006 is selected, otherwise the output of 1005 is selected.

FIG. 10C is a diagram showing the internal structure and operation of the synthesizer 904 of FIG. 9A or FIG. 15 in an embodiment of the present invention. The source input set 1001 of stream values is used by the circuit system 1004 to calculate the contribution of each individual synthesizer.

Circuit system 1005 uses the output of 1004 to calculate the initial value of the sub-function, and circuit system 1007 uses the output of 1004 and the partial value previously calculated and delayed from one of 908a, 908b, 908c, 908d, 908e and 908f on the synthesizer row 1003 immediately above to calculate the in-progress partial value of the sub-function.

Multiplexer 1011 selects which variant of the partial result to forward as the partial value of the subfunction as the output of synthesizer 1009. If ROWFST 808 is not confirmed, the output of 1007 is selected, otherwise the output of 1005 is selected.

FIG. 10D is a diagram showing the internal structure and operation of the synthesizer 901 of FIG. 9A or FIG. 15 in an embodiment of the present invention. The source input set 1001 of stream values is used by the circuit system 1004 to calculate the contribution of each individual synthesizer.

Circuit system 1005 uses the output of 1004 to calculate the initial value of the sub-function, and the initial value is forwarded as a partial value of the sub-function as the output of synthesizer 1009.

Cell 901 (Fig. 9A, Fig. 15) is always the first value in any complete or truncated tile used, and therefore always produces the initialization value for the tile.

FIG. 10E is a diagram showing the internal structure and operation of synthesizers 903a, 903b, and 903c of FIG. 9B and FIG. 9C or FIG. 15 in an embodiment of the present invention. A source input set 1001 of stream values is used by circuit system 1004 to calculate the contribution of each individual synthesizer.

Circuit system 1006 uses the output of circuit system 1004 and the partial value previously calculated by synthesizer 1002 on the immediate left side to calculate the in-progress partial value of the sub-function, and the in-progress partial value is forwarded as the partial value of the sub-function as the output of synthesizer 1009.

FIG. 10F is a diagram showing the internal structure and operation of synthesizers 907a, 907b, and 907c of FIG. 9A and FIG. 9B or FIG. 15 in an embodiment of the present invention. The source input set 1001 of the stream value is used to calculate the contribution of each individual synthesizer 1004.

Circuit system 1006 uses the output of circuit system 1004 and the partial value previously calculated by synthesizer 1002 on the immediate left side to calculate the ongoing partial value of the subfunction. Circuit system 1007 uses the output of 1004 and the partial value previously calculated and delayed from one of 908a, 908b, 908c, 908d, 908e and 908f on the synthesizer row 1003 immediately above to calculate the ongoing partial value of the subfunction.

Multiplexer 1012 selects which variant of the partial result to forward as the partial value of the subfunction as the output of synthesizer 1009. If COLFST 811 is not confirmed, the output of 1006 is selected, otherwise the output of 1007 is selected.

FIG. 10G is a diagram showing the internal structure and operation of the synthesizer 906 of FIG. 9A or FIG. 15 in an embodiment of the present invention. The source input set 1001 of stream values is used by the circuit system 1004 to calculate the contribution of each individual synthesizer.

Circuit system 1007 computes the in-progress partial value of the subfunction using the output of circuit system 1004 and the partial value previously computed and delayed from one of 908a, 908b, 908c, 908d, 908e, and 908f on the immediately upper synthesizer row at 1003. The output of circuit system 1007 is forwarded as the partial value of the subfunction as the output of synthesizer 1009.

FIG11 is a diagram showing the internal structure and operation of intra-row delay lines 908a, 908b, 908c, 908d, 908e, and 908f (FIG. 9C). The delay lines are used to retain the results of partial operations from each row synthesizer for use in the next row.

(1101)至N-2(1102)之合成器之輸出分別由暫存器1104至1105保留以供未來參考。 When COLLST is asserted, the current position of the source input stream is at the rightmost edge and the column

The outputs of the synthesizers (1101) to N-2 (1102) are retained by registers 1104 to 1105 for future reference.

，則多工器1106以由索引計算(N-2)-colSrc所定義的自右至左之反向次序自所保留值中進行選擇，否則該多工器自列m(1103)之最後合成器選擇當前值。 If the current position of the source input stream colSrc is less than

, then multiplexer 1106 selects from the retained values in reverse right-to-left order defined by index count (N-2)-colSrc, otherwise the multiplexer selects the current value from the last synthesizer in row m (1103).

時，列之最右合成器將不包含有效資料，此使得此等時槽可用於插入所保留資料。 It should be noted that when the source input string pop position is less than

, the rightmost synthesizer in the row will contain no valid data, making this time slot available for inserting the retained data.

The partial output selected by multiplexer 1106 is fed to a first-in-first-out (FIFO) circuit 1107 having C-N positions, which is configured so that the source input stream positions are processed so that exactly one value is inserted and a value is retrieved in the same order as it was inserted. Since the partially completed result from one position will not be needed until the source input stream returns to the same small block position on the next row, this implements a delay so that the partial result of an operation on one row will be presented to the next row exactly when needed.

The partial output selected by multiplexer 1106 also feeds the same value (1114) into the final result delay lines 909, 910a and 910b.

The partial output captured from FIFO 1107 is routed at 1108 to the leftmost synthesizer on the next row (1111) and to a series of parallel access registers 1109 to 1110 which further delay the partial output by one source input stream interval as the data passes through the register chain.

When the current position of the source input stream is at the leftmost edge, the FIFO directs the output data at 1108, and the delayed results 1109 to 1110 are available to the cells in the next row at 1111, 1112 to 1113, respectively.

It should be noted that the additional values from the right side of the source input array stream inserted into FIFO 1107 by multiplexer 1106 are accessed via path 1111 only when the source input array stream is located close to the right edge, while the additional parallel paths 1112-1113 are used only when the source input array stream is at the leftmost position to access data normally inserted from path 1103. The obvious similarity in structure and requirements between right edge processing and left edge processing is a natural consequence of the overlapping symmetry of the subfunction with the right and left edges of the source input stream array. When the value of N is even, the number of additional cells processed to support the right edge and the left edge is different.

FIG12 is a diagram showing the internal structure and operation of the final truncated result delay line 909 (FIG. 9C).

When processing the last row of the source input stream array, the partial result from the auxiliary output 1201 of the intra-row delay line 908d is considered as the final result of the final row of the truncated chunks and is retained in a FIFO 1202 whose number of elements C is equal to the width of the source input stream array.

Immediately after recording the final result of the truncated small block, if the value of M is such that no other delay line intervenes, the output of FIFO 1202 will be transmitted to other delay lines 910a via 1203 or directly to the final processing 911.

FIG. 13 is a diagram showing the internal structure and operation of the final truncated delay lines 910a and 910b.

When processing the last row of the source input stream array, the partial result 1301 from the auxiliary output of the intra-row delay lines 908e to 908f is considered as the final result of the final row of truncated chunks and is retained in a FIFO 1304 whose number of elements C is equal to the width of the source input stream array.

When POSTEN is asserted, multiplexer 1303 switches between obtaining the value from 1302 to obtaining the value from the final truncated delay line of the row above, which will have the effect of presenting the final truncated result in a row-first order that is compatible with the ordering of all previous output results.

It should be noted that during that cycle of the input frame when POSTEN is first asserted, the contents of FIFOs 1202 and 1304 are the final values of the truncated chunks overlapping the last row of the source input stream array. Any data contained in FIFOs 1202 and 1304 prior to that cycle will not be processed, so any suppression performed when not processing the last row of the source input stream array is optional.

Immediately after recording the final result of the truncated small block, if the value of M is such that no other delay lines intervene, the output of FIFO 1304 is transmitted to other delay lines via 1305 or directly to the final processing 911.

Figure 14 is a diagram showing the internal structure and operation of the final processing of all complete and truncated results.

(1101)至N-2(1102)之列M-1之胞元的輸出分別由暫存器1104至1105保留以供未來參考。 As in FIG11 and having the same structure and function, if the current position of the source input stream is at the rightmost edge, then

The outputs of the cells in rows M-1 (1101) to N-2 (1102) are retained by registers 1104 to 1105 for future reference.

，則多工器1106以自右至左之反向次序自所保留值中進行選擇，否則該多工器自列M-1(1103)之最後合成器選擇當前值。 If the current position of the source input stream is less than

, then the multiplexer 1106 selects from the retained values in reverse order from right to left, otherwise the multiplexer selects the current value from the last synthesizer in column M-1 (1103).

While processing the source input stream array, multiplexer 1402 feeds the result selected by multiplexer 1106 directly to the finalization (1403). When in the post-processing stage, the output of the truncated result delay line 1401 is instead selected for the finalization (1403).

Finalization circuitry 1403 performs all additional operations (if any) to produce the final form of the output stream from the synthesized tile results (1404). This may typically take the form of a rectified linear unwinding (RELU) function, whereby negative values are set to zero and out-of-limit values are set to the maximum acceptable value, or any other desired conditioning function such as a sigmoid or hyperbolic tangent. Post-processing functions need not be completed within a single source input stream loop, but rather need to accept each final result at the rate of the source input stream array.

When DSTEN is asserted, termination circuitry 1403 presents the final result as a value in the destination output stream. At any time when DSTEN is not asserted, any partial or incorrect value produced by termination circuitry 1403 is ignored, so any inhibition of operation when the result is not used is optional.

In one embodiment, the destination output stream array is processed by circuitry similar to that described above. In that case, it is advantageous for the timing of the final truncated result to be the same as all previous final results. To this end, control of FIFOs 1202 and 1304 is coordinated by control circuitry 702 to maintain an output rate that is the same as the primary output rate.

In another embodiment, the destination output stream array is the final stage of the system and requires no further processing. In that case, it is advantageous to complete the timing of the final truncated results as quickly as possible. To this end, control of FIFOs 1202 and 1304 is coordinated by control circuitry 702 to output those results at the maximum frequency supported.

It should be noted that the implementation described above generates a single output element from a full set of input elements. In a complete system that generates a large set of output elements from an input set, the entire mechanism described is repeated once for each output channel, with the exception of control circuitry 702, which can be shared by the output channels because the timing of all individual subfunctions is the same for the entire output set.

The inventors of this case have constructed working prototypes of the IC in the embodiments of this invention to test and verify the details and features of this invention, and the operation of the prototypes has confirmed the above description. The inventors of this case have also developed a software-supported simulator, which has been used to test and verify the above details and descriptions until the time of filing this application.

In another aspect of the invention, a system is provided for accepting an input stream of three-dimensional data, such as is commonly found in medical imaging, including additional circuitry and buffering to allow a three-dimensional aperture function to be passed over the three-dimensional input array, wherein the corresponding operation is correctly performed for both the interior and edge conditions of the first and last planes.

In another aspect of the present invention, a hardware-assisted neural network training system is provided for the complex process of training a deep neural network (DNN), wherein most of the work is done by a forward inference engine, and the training algorithm only needs to use statistics collected from the forward inference to periodically adjust the weights and biases of the entire network to converge the model to the desired state. With the addition of an appropriate accumulator that sums the input states as the forward inference process is calculated, the present invention forms a hardware-assisted neural network training system.

In yet another aspect of the invention, with respect to the well-known problem in which floating point accuracy limitations prevent convergence of DNN models (referred to in the art as the "descent gradient problem"), a single massive multiplier with finite bit-width precision can be cascaded with additional adders to produce floating point products with arbitrarily large precision. While this innovation is not typically required for forward propagation operations, it can be extremely important in DNN trainers to avoid problems that arise when the computed gradients become too small to be measured.

N-up parallel processing

In the embodiments and implementations of the present invention described above, the focus is on apparatus and methods for performing a large number of multiplications in functions requiring multiplications and the execution of novel ICs for aperture functions in convolutional neural networks (CNNs). However, as is well known in the art, a full deep neural network (DNN) must implement a full set of disparate aperture functions, many of which may require only minimal computation.

To comply with embodiments of the invention, each such implementation must comply with an overall system-wide pipeline format that accepts input as a parallel stream of values representing arrays in a consistent order and simultaneously produces output as a parallel stream of values representing arrays in that same order. The final node of the DNN may return a conclusion reflecting an array of positions, or a conclusion about the input array as a whole. The embodiments of the invention described below are for executing a DNN in a novel IC in which pipeline execution is supported.

In aspects of the present invention, the inventors have developed a method and apparatus for significantly accelerating pipeline operations in CNNs and DNNs. The inventors in some embodiments propose pipeline operations for streaming inputs to an IC multiple times in parallel. In the embodiments described above, in all embodiments, the inputs are typically streamed from left to right across rows and then from top to bottom across columns. For RGB data, for example, three separate channels of typically 8 bits per channel will be used at each pixel location to represent each of the three independent RGB color values observed at each pixel location. The inventors of this case refer to this as a 1-up implementation. 1-up means streaming the input value of one pixel at a time. Or in a more general sense, streaming the value of one input position at a time in an input array.

The inventors of this case believe that considerable advantage can be gained by streaming inputs to more than one input location at a time, such as in the case of pixels. To do this, circuitry must be added to a novel IC that performs the input streaming to produce the output stream. The change is generally a change in size rather than complexity, since the circuitry implemented in the 1-up case is repeated in the IC to process input values for the additional input locations (in this case, pixels) in parallel.

While the circuitry is least problematic when the width of each row is an integer multiple of the input count to be streamed in parallel, this is not a required limitation of the present invention. For the pixel example, for a resolution of 1920×1080, the number of pixels on a row (1920) is divisible by 1, 2, 3, 4, 5, 6, 8, 10, and 12. Therefore, streaming the RGB values of two pixels (called 2-up) is an efficient approach, as are 3-up and 4-up. As the number of pixels increases, the absolute size of the IC used to handle all the processing increases by a factor directly related to the number of pixels to be considered in parallel, so the user must make reasonable decisions.

But as the stream passes down through the nodes of the DNN, the input array size typically decreases in dimension, when the stride of the aperture function is not 1 (not every input position will produce an immediate output position) or when the aperture function is defined to avoid overlapping with the edges of the input array. In these common cases, the width of the input array cannot be restricted to be an integer multiple of any given number N of parallel positions. One solution is to always align the left edge of each column of the input array with a specific position (nominaly the left side) in the group of N positions. The right edge can then be represented by an incomplete group, always starting from the first position in the group of N positions. Additional circuitry is then used to prevent invalid data from being used in calculations and also to suppress any output derived from that invalid data.

In an embodiment of the invention, for a 2-up implementation in a pixel instance, the R, G, and B values of each of two neighboring pixels are transmitted as a pipeline input stream to the IC. The first two pixels are the first two pixels from the left in the top row. For an RGB instance, there will be six input values, which are the R, G, and B values of each of the first two pixels. The next two pixels in the row are the next in the stream, and so on across the top row, followed by the R, G, and B values of the first two pixels in the second row, and so on through the input array. For 3-up or 4-up, the same general protocol is followed.

Figures 17A and 17B illustrate a 1-up pipeline solution for a well-formed minimal DNN model that can be used to understand images and respond to the relative excitation strengths of the various objects that the model has been trained to recognize. Input channels 1701 are presented as input values for individual pixels in a particular order, typically from left to right across the columns and then from top to bottom, as just described above. For RGB data, this takes the form of three individual channels, typically 8 bits per channel, representing three independent color values observed at that location. Eight-bit channels do not limit the scope of the invention.

If the input to this DNN circuit is the output of another DNN circuit, as would naturally occur if a large DNN is broken down into smaller parts to aid processing, the channels presented will be one for each feature passed into the DNN. For example, if a particular piece of the model requires 64 feature channels as input, then each value will be presented in parallel as an unsigned or signed integer or floating point value in the specified format, with the desired bit of precision.

It is important to understand that the blocks depicted in FIG. 17A (and in the other figures described) do not represent steps that are performed sequentially. Each block represents an input channel or circuitry that performs a function such as an aperture function. The arrows between blocks represent sets of parallel conductors that pass values between processing circuits. All processes are simultaneously active whenever an input is presented to that block. When the input stream begins, the circuitry represented by the blocks becomes active one by one until all processes are active and output streams are also generated in multiple channels. The emission of the final output at the first corner (nominal upper left corner) of the input array begins while the input is still being accepted.

The first 7x7 convolution node 1702 in the model is typical for RGB input in a DNN for visual understanding. The 7x7 kernel can be applied only if the kernel tile fits within the bounds of the input array (typical for RGB input), or it can be applied to every input position and missing values synthesized (typical for reprocessing features). In general, a large number of output channels are generated (typically 64), and the number of channels throughout the rest of the system is usually increased as feature values are passed through additional nodes.

Each of the subsequent convolution nodes 1703, 1704, 1705 also accepts and produces a multi-channel array stream of the same dimension as its input. The number of output channels of each convolution node is arbitrary and can be more, less, or the same as the number of input channels.

The concatenation node 1706 in this model accepts the parallel input array streams produced by nodes 1704 and 1705 and synchronizes them to produce a combined set of channels. The values of the channels from the convolution node are not changed. However, due to the nature of the pipeline, each output from the 1x1 convolution corresponding to a particular array position will be produced before the output from the 3x3 convolution, so the concatenation function will have to provide a buffer in the form of a first-in, first-out (FIFO) circuit so that all channels can output data corresponding to the same position presented at the same time.

The MaxPool node 1707 in this model utilizes an aperture function that compares all values of a small block and outputs only the maximum value for each channel independently. The number of channels is not affected, but the array dimension of the input stream will be reduced in the output stream. If the MaxPool node typically reduces the horizontal dimension by a factor of two and the vertical dimension by a factor of two, the output array will be one-fourth the size of the input array.

Since the frame rates of the input and output streams must be the same (outputs cannot be generated faster than the inputs they are based on, and outputs cannot be generated slower than inputs or data will be lost), the net effect is that the clock rate used to scale the output array stream will be proportionally reduced.

In this MaxPool example, since only one output is produced for a small block of four input positions, the required output rate is only one quarter of the input rate. Therefore, all subsequent nodes in the pipeline will operate with a reduced effective output throughput. As the number of channels becomes larger and larger, reducing the effective output throughput can be advantageous. When there are more cycles available to perform the required calculations, some of the resources that can be dedicated to each channel can be shared between channels, resulting in an overall reduction in circuit size with only a small increase in power. The reduction in dimensionality also forms an important basis for the present invention.

Subsequent nodes of the depicted model may utilize similar or dissimilar connection schemes, as long as each scheme supports a system-wide interface that simultaneously presents all channels corresponding to data at a given location in any input array stream.

After the MaxPool node 1707 value is streamed to additional Convolution nodes, Concatenation nodes, and MaxPool nodes in this model as depicted, but since these nodes are functionally identical to those already described, they do not have component numbers.

The global average node 1708 in Figure 17B is different in that the aperture function of node 1708 covers the entire residual dimension of the previous input array stream and simply returns the average of each channel over the entire array. Therefore, the output array dimension is 1 by 1 and forms the output channel 1709 of the entire circuit.

Figures 18A and 18B illustrate the overall structure and flow of a 4-up pipeline implementing the same form of DNN model as shown in Figures 17A and 17B.

The input channels 1801 are presented in parallel as four sets of data for each channel. For RGB data, this would take the form of four individual pixels representing four adjacent rows of the input array, each pixel containing four RGB values, for a total of 12 inputs accepted in parallel at the same time. Alternatively, the input channels may come from another DNN circuit, in which case they take the form of four complete sets of input channels representing four adjacent rows of the input array. For example, if the model requires 64 feature channels as input, the four sets would contain a total of 256 parallel inputs.

The first 7 by 7 convolution node 1802 is typical for RGB input in a DNN for visual understanding. In this 4-up implementation, node 1802 accepts input four pixels at a time and produces output four pixels at a time. The number of output channels is typically quite large compared to the number of input channels, 64 or more, and no longer represents color information. Throughout the remainder of the DNN in this model, a channel represents the detected strength of a feature or combination of features found in the input array and has an independent value for each position. Each of the subsequent convolution nodes 1803, 1804, 1805 also accepts and processes input four pixels at a time for each channel. Concatenation node 1806 accepts four sets of channels from convolution nodes 1804 and 1805 and outputs the combined channels in sets of four.

The first MaxPool node 1807 is labeled 4-up to 2-up. Node 1807 takes the maximum of four samples representing a small block of input array positions containing two adjacent rows on two consecutive columns. Since the effect is to reduce the dimension of the input array stream to produce an output array stream that is half the width and half the height, the effective throughput of all subsequent nodes is reduced by a factor of four. When using single input processing, subsequent processing clocks can be reduced to take advantage of more compact circuitry.

When using N-up parallel input processing, the reduction in output array width actually serves to reduce the number of parallel outputs. Since parallel inputs represent adjacent rows on the same column in the input array stream, only the reduction in width is relevant. While it is possible to retain N-up parallel outputs at a reduced frequency, there is no size or power advantage to doing so. The net effect of the MaxPool node 1807 is to reduce parallelism in the horizontal dimension from 4-up to 2-up (as marked), and to reduce the processing frequency by a factor of two rather than four as in the 1-up case described above.

Nodes 1808, 1809, 1810, and 1811 process data in 2-up parallel tracks, and each of these nodes is roughly half the size of its 4-up counterpart. This does not correspond to a reduction in power, since the total number of operations required for a 4-up, 2-up, or 1-up circuit is the same, and only the overhead for managing N-up coordination is reduced.

The second 2x2 MaxPool node 1812 similarly obtains the maximum of four samples representing a small block of input array positions containing two adjacent rows on two consecutive columns. The net effect of node 1812 is to reduce the parallelism from 2-up to 1-up in the horizontal dimension and reduce the processing frequency by a factor of two. All subsequent nodes as shown in FIG18B operate on a single set of their respective input and output channels, and the final output 1813 takes the form of a single sample of each channel presented simultaneously in parallel.

FIG19 and FIG20 are tables describing array stream sizes for a typical small DNN applied to an input stream compatible with images in HD RGB format. The table of FIG19 describes a DNN that implements only 1-up processing, as depicted in FIG17A and FIG17B, and the table of FIG20 describes the same DNN that initially implements 4-up processing and transitions to 1-up processing in subsequent nodes, as depicted in FIG18A and FIG18B.

Having described the nomenclature and general process of N-up parallel processing, the inventors of this case now provide a specific example of an apparatus and method for applying a 3x3 convolution function to an input array using 4-up parallel processing. In this example, the input array is an array of pixels in RGB color, as used in many other examples in this specification. It should be noted that this is not a limitation on the scope of the invention, as 3x3 convolution with 4-up parallel processing can be used for many other formats of input arrays. In this example, it should also be understood that the 3x3 blocks shown represent the circuit system that executes the core function on the input stream.

FIG21 illustrates an example of a circuit system on an IC that implements a 3 by 3 convolution node using a 4-up data stream. In FIG21 , a set of four inputs 2101 is reserved from the immediately preceding input interval and is reserved along with the current set of four inputs 2102 to provide all the inputs required for all four output channels of the 3 by 3 convolution. Using the inputs from the immediately preceding input interval along with the inputs from the current interval is necessary to fully compute the outputs in pipeline processing, as described in detail above.

_p0 , _p1 , _p2 , and _p3 represent the input channel values of positions 0, 1, 2, and 3 in the first row of the input array, respectively. For simplicity, only a single symbol is used, but each symbol represents all channels of the input position. For the pixel case, each data point _px represents the R, G, and B values of that pixel.

w _0,0 to w _2,2 represent the weight sets to be applied to the values in the input channels. Since each weight is applied to one and only one input channel, the number of input channels does not affect the structure of the circuit, so multiple channels are not shown.

The weights in core columns 2103, 2104, and 2105 are applied in parallel (simultaneously) to input channels _p0 , _p1 , and _p2 , and the partial products of each set of weights in each column are summed directly according to the rules of the aperture function of the 3-by-3 convolution. As described in detail above for pipeline processing, the partial sums are passed from each functional circuit to the next functional circuit, and the output is produced when all necessary parts are completed. The application of the weights in column 2105 produces the final output of the core of the current column from the previous column by combining the partial products with the sum of the products of the weights from the application column 2104. The application of the weights of column 2104 produces intermediate values from the previous column by combining the partial products with the sum of the weights of the application column 2103. The weights of the applied columns 2103 are generated by summing the partial products and retaining the partial products for later use to generate initial values. Bias (if any) can be introduced at any stage. The activation function (if any) will be applied to the final output 2105.

The complete circuit implementing the weights of columns 2103, 2104, and 2105 (including any biasing and activation functions) produces the first output channel of the 4-up set.

When the first 4-up group is presented from the input array stream, there is not enough data to compute all four required outputs, so computation of all outputs is delayed until the second 4-up group is obtained and valid data is available for computation using inputs from both groups 2101 and 2102.

Circuits 2106, 2107 and 2108 apply weights in circuits that are copies of the previous circuits, and the functions differ only in the location of the inputs where the weights are applied. It should be noted that the set of weights _w0,0 to _w2,2 is the same for all output channels, but each combination of a weight and an input channel is unique.

The output of the weight calculation using row 2105 of the first core replica generates the first parallel channel set q ₀ of the output array stream, while the output of the weights of the other core replicas 2106 , 2107 , and 2108 generates the remaining parallel channel sets q ₁ , q ₂ , and q ₃ of the output stream 2109 , respectively.

Since the first output _q0 corresponds to a 3x3 core centered at _p1 , the circuit corresponding to the configuration in Figure 21 is a solution to an inserted or "valid" version of the 3x3 convolution. Therefore, the width of the output array stream is reduced by two positions compared to the width of the input array stream, as defined by the aperture function of the variation. (The height is also typically reduced by two rows, but this is not relevant for horizontal processing.)

Figure 22 illustrates the required configuration of a circuit for generating outputs for a 4-up input channel of the "same" version of a 3 by 3 product, i.e., where the dimension of the output array stream is not reduced and one output position is generated for each distinct position of the input array stream. In this variation, input group 2203 presents the current value of the 4-up input array stream, while input groups 2202 and 2201 present the retained values from the previous two groups.

The application of core circuits 2204, 2205, 2206 and 2207 respectively generates values _q0 , _q1 , _q2 and _q3 of the 4-up output array stream 2208, and is now aligned so that the center of each core corresponds to a position in the 4-up input array stream.

When the first 4-up channel group appears from the input array stream, there is not enough data to compute all four required outputs, so the computation is deferred until the second 4-up group is presented and valid data is available for both groups 2202 and 2203. Valid data is not yet available for group 2201, and core circuitry 2204 will suppress the weights including _p3 applied to 2201 or force uninitialized values to zero, as consistent with applying a 3 by 3 convolution aperture function to locations that cause the core to overlap the edge of the input array. This suppression mechanism is triggered for the first group of each row, but subsequent groups on that row will utilize the _p3 value group 2201 to compute the full core for that output location _q0 .

In processing full DNNs, there are cases where the 4-up streaming technique is applied to a stream of input arrays whose width is not an even multiple of four. In such cases, invalid values in the final 4-up group are suppressed by forcing them to zero or by other means, and the final output position in the last 4-up group of the row is ignored. This is consistent with both the interpolated ("valid") and the exact ("identical") variations of the 3x3 aperture function.

In all cases, the first position of each row of the input array stream always appears in the first position of the 4-up input set.

In the case where the input row length is not an even multiple of the processing group width, the processing clock is increased to make the overall throughput of the N-up processing compatible with the throughput of the 1-up input source, and a special buffer is required to pack the incoming values into N-up groups. This special buffer is described below.

Figure 23 shows the required configuration of the circuitry for two variations of a 1-row by 7-row convolution on the output 4-up data. Based on the previous discussion of the 3-by-3 convolution, one skilled in the art will recognize that the specific number of rows in the core affects only the number of partial sums preserved over time, not the mapping of core weight rows to input group rows. Therefore, the data configuration shown in Figure 23 applies equally to a 7-by-7 core, a 3-by-7 core, or any other core with a width of 7.

As described above, input group 2303 is the currently presented 4-up data group from the input array stream, and groups 2302 and 2301 were previously presented and retained data groups from the immediately preceding group and the second preceding group, respectively.

Core processing circuits 2304, 2305, 2306, and 2307 represent the alignment required to produce the inserted ("valid") convolution output 2308, and circuits 2309, 2310, 2311, and 2312 represent the alignment required to produce the exact ("identical") convolution output 2313.

_w0,0 of circuit 2304 is aligned with _P0 of input set 2301 to produce an insertion variant, and _w0,3 of circuit 2308 is aligned with _P0 of input set 2302 to produce a full variant, where both circuits 2304 and 2309 produce output _q0 for their respective usage scenarios.

Those skilled in the art will appreciate that the two sets of cores have a considerable overlap of identical functionality, and that it is simple to configure a single circuit using only five uniquely mapped core circuits to produce any variation as desired. Those skilled in the art will also appreciate that any M-up stream data set (including 1-up) can be repackaged as needed into any other N-up stream format (where M≠N) to keep the overall throughput of the system high enough to accept and process the input array streams at the presented rate. This is done at the cost of requiring N copies of some of the core processing circuits, but the overall effect is to allow the circuit to limit the processing clock to reasonable limits for the implementation method, while still accepting the input stream at full speed.

Figures 24A and 24B illustrate a typical implementation of a 2x2 MaxPool node, where the maximum value of each channel is selected for different tiles at two adjacent row positions on two adjacent columns.

Figure 24A shows the configuration of a 2x2 MaxPool node on a 4-up data stream 2401. When the first row of each pair is presented, comparator 2402 evaluates inputs _p0 and _p1 and passes the larger one to FIFO circuit 2403 to be retained for use when the second row is presented. Comparator 2404 and FIFO 2405 perform the same operation on inputs _p2 and _p3 at the same time. When the second column of each pair is presented, comparator 2402 accepts the retained maximum value from FIFO 2403 for the same row position from the first column and compares the retained maximum value with inputs _p0 and _p1 and outputs the larger of the three values as output _q0 , while comparator 2404 and FIFO 2405 perform the same operation on inputs _p2 and _p3 to produce output _q1 .

Output set 2406 includes two sets of channels, each of whose individual values is the maximum of four samples for each particular channel (values from different channels do not interact in this aperture function). Therefore, output 2406 of FIG. 24A is a 2-up output data stream generated from a 4-up input data stream.

24B shows the configuration of the same 2x2 MaxPool node on a 2-up data stream 2407. The comparators 2408 and FIFOs 2409 are functionally identical to those described above, but only a single set is required to accept the 2-up inputs _p0 and _p1 to produce a single set of output channels 2410. Therefore, the output 2410 of the second example is a 1-up output data stream generated from a 2-up input data stream, and all downstream nodes can adopt the smaller 1-up format.

The flattened MaxPool function, along with any other aperture function with a 2x2 stride, reduces the size of the input array by a factor of 2 in each dimension. Since the total width of an N-up array stream is N times the number of groups presented, the reduction can be effected by reducing the width within a group or by reducing N, as long as N is divisible by the horizontal stride. Since N is the replication factor for the copies of the circuit executed in parallel, it is better to reduce N as much as possible.

FIG25 illustrates a hypothetical example where it is not possible to reduce N. It applies a 2x2 MaxPool node, but in this case to a 5-up input stream. As before, in the case of a 3x3 convolution, input set 2501 is retained and used with the current input set 2502 to present a minimum set such that all outputs can be produced on the same clock cycle. (Other configurations are possible, such as switching the first comparator to process _p0 and _p1 or _p1 and _p2 on alternating input sets, while setting the middle comparator to process alternating inputs _p4 and _p0 . This would reduce the number of required copies of the aperture function from five to three, and would be advantageous where the aperture function implementation is significantly more complex than a simple comparison.)

In this example, comparator 2503 and FIFO 2504 operate on the retained values of _p0 and _p1 , comparator block 2506 operates on the retained values of _p2 and _p3 , and comparator block 2507 operates on the retained value of _p4 and the current value of _p0 . Comparator block 2508 operates on the current value of _p1 and _p2 , and comparator block 2509 operates on the current value of _p3 and _p4 .

Since it is not possible to implement a 2.5-up data stream within the constraints of the pipeline, in this example, a dimensionality reduction must be applied to the width of the input array, and therefore, output 2510 is a 5-up output reflecting a 5-up input stream.

As described above, in some cases it may be reasonable to repack an M-up stream into an N-up stream of the same array dimensions. Specialized FIFO circuitry may be used to perform this function. FIG. 26A illustrates such a FIFO used to repack a 4-up stream 2601 into a 2-up stream 2603. FIFO 2602 accepts inputs 4 at a time and stores them as individual input entries. Outputs 2 are produced at a time whenever 2 entries are available in the FIFO. The data flow in FIG. 26 (and the following figure) flows from the inputs down through the circuitry to the outputs.

In the common case where the width of the input stream is not an integer multiple of the input stream group size, a counter must be included to keep track of the number of valid entries presented for each row. For example, if the input array width is 10, using 4-up input groups where 3 sets of 4 are required to cover a full row, the FIFO must ignore the last two entries in the 3rd set of input presented, and output 5 sets of 2-up output instead of 6. After each row, the counter is reset and starts counting entries on the next row. Array width limits can be fixed or presented via preload registers. If it is known that the array width is always an integer multiple of both the input group size and the output group size, this logic can be omitted.

Figure 26B illustrates the repackaging of 3-up stream 2604 into 5-up stream 2606. FIFO 2605 accepts inputs 3 at a time but stores them as individual input entries. Whenever 5 entries are available in the memory, the FIFO produces outputs 5 at a time.

As described above, additional operations must be implemented to account for invalid entries that may appear at the end of a row whose array width is not an integer multiple of the input group size. A similar problem arises when the array width is not an integer multiple of the output group size. In this case, the final group must be emitted when each row has been completely received, the final group containing the last entry of the row in the first output and containing invalid entries with no specific value in the remaining channel groups. For convenience, the practice of placing all zeros in invalid entries can be used to reduce the overall circuit size in subsequent nodes where zeros have no effect, such as in convolution and MaxPool.

The FIFO must be large enough to hold as many input sets as possible to ensure that no data is lost. To maintain overall system throughput, output is issued as soon as enough entries are available to generate output sets.

。 Although any group size can be repacked into any other group size, the required processing frequency will change in proportion to the ratio of the sizes. For any M-up input that is repacked into an N-up output, the required processing frequency can be described as

.

In the entire system, for the simplest operation, each circuit that accepts rows should provide and ignore unused invalid entries at the end of all rows where the row width is not an integral multiple of the group size. This is not a strict restriction, as the circuit can work anyway with additional logic not shown here. This ensures that each row position maps to the same channel set within the parallel set presented for each row and minimizes the complexity of operations that combine values for the same row position on multiple rows.

FIG. 27A illustrates an implementation of a concatenation node where channels from one source 2701 are concatenated on a per-position basis with channels from another source 2702 or more sources (not shown) so that the output 2706 includes all channels from all sources. This node does not mix or alter channel values. In the common case where the sources have different timings, one or both of the FIFOs 2703 and 2704 will hold the input channel values until the full set of output channels are available. Interleave circuit 2705 will concatenate all channels from group p ₀ of each source to produce q ₀ , concatenate all channels from group p ₁ to produce q ₁ , and so on.

A common example where this solution is needed would be the combination of the output of a 3x3 convolution node and the output of a 1x1 convolution node, each of which is applied to the same input array stream. Although both nodes process the stream at the same rate, the output of the 3x3 node cannot terminate until the third row of the input stream is presented, whereas the output of the 1x1 node can terminate as soon as any data from the input stream is presented. The net effect is that the output of the 1x1 node corresponding to a particular position in the input array stream will be presented to the concatenated node significantly before the output of the 3x3 node for those same positions. Since the next node after a concatenated node will need all channels at any given position to be present before any computation can be done, the concatenated node must buffer input streams presented earlier and wait for input streams presented later to arrive at the same position before it can present the full set of all channels at a given position on the output. This is true for 1-up data streams or N-up data streams.

If each input array position of the slowest path is always presented after the same position by all other paths, then the FIFO for that path can be omitted. If under some conditions (usually the final position of the stream) the slowest path will not be presented last, then the data in the FIFO of that path must be retained with the minimum number of entries required to prevent data loss under those special conditions.

If the data path widths of the various sources are different, the path widths can be repacked to match each other, as in Figures 26A and 26B, or the function can be combined with a FIFO for cascading buffers. Those skilled in the art will appreciate that any number of paths can be cascaded into a single operation by adjusting the size of the FIFOs in each of the earlier paths to retain as many values as possible that can be presented by each path in worst case timing before the corresponding location is presented by the slowest path.

FIG27B illustrates an implementation of a 4-up dense node. A dense node is mathematically equivalent to a convolution with a kernel size equal to the size of the input array. Therefore, to create each output channel, there is a different weight applied to each input position of each input channel. The number of output channels is independent of the number of input channels, and the resulting output array is always a 1 by 1 array. Since the inputs 2707 are submitted in groups of four in this exemplary implementation, the weights 2708 specific to each input position are loaded from local storage (not shown) and multiplied by the current input in the circuit system 2709 to form a partial product of the full kernel. All partial products from all input channels presented are summed to produce a single 1-up group 2710 of output channels.

27C illustrates an implementation of a 4-up global average node that takes all values at all positions of each input channel and averages them to produce the same number of output channels. The global average node is mathematically equivalent to a convolution with a kernel size that is the same as the size of the input array, and is only applied to each input channel individually (rather than all together as just described above), with a common constant value equal to the inverse of the number of elements in the kernel. Since it is mathematically equivalent to multiplying by the inverse before or after the summation operation, circuit 2712 simply sums all values at each position of each input channel 2711, and then multiplies it by the inverse of the number of elements when all input values have been summed to produce each output channel. Since all input positions are combined into a single value, the output 2713 is a single 1-up set of channels with a 1 by 1 array size.

Figure 28 illustrates a 4-up implementation of a 3 by 3 local average node that uses a sliding aperture function to compute the average of each input channel on a subset of positions to generate an output channel. This implementation forms an inserted or "valid" output group in which the aperture does not overlap the edge of the input array and the number of samples is the same for all output positions. Each output channel corresponds to a single input channel and data is not mixed between channels. As with the implementation of the convolution node with similar size and input mapping shown above in Figure 21, the current input group 2802 is retained by register 2801 so that the current input group and the immediately preceding input group can be accessed simultaneously. Each of circuits 2803, 2804, and 2805 applies the same summation to each input channel of groups _p0 , _p1 , and _p2 , but applies that summation to three different partial sums over time to produce group _q0 of output array stream 2809. Circuit 2803 initializes the running sum of the first column, circuit 2804 produces the running sum of the middle columns using the output of circuit 2803 delayed by a FIFO (not shown), and circuit 2805 produces each final summation using the delayed output of circuit 2804. Circuit 2805 then multiplies the final summation by the inverse of the number of elements (in this case 1/9) to produce output group _q0 . The activation function can be integrated into the circuit or equivalently placed between nodes.

Equivalent circuit 2806 generates output set _q1 from channel set _p1 , _p2 and _p3 of previous input set. Similarly, circuit 2807 generates _q2 from _p2 and _p3 of previous input set 2801 together with _p0 of current input set 2802, and circuit 2808 generates _q3 from _p3 of previous input set 2801 together with _p0 and _p1 of current input set 2802.

If a local average aperture function is to be generated for each valid position, the output 2809 has a reduced array size compared to the input, in which case the width and height are each reduced by two positions, but this is generally not enough to significantly reduce the 4-up stream. If a horizontal step size other than one is used, that is, not every possible output position is utilized, then the reduction in horizontal dimension can be implemented in the circuit as a reduction in N. For example, if the horizontal step size is 2, only every other value is required, and the circuit can generate a 2-up output channel by operating only on _q0 and _q2 and omitting the unused circuitry for _q1 and _q3 . Similarly, if the horizontal step size is greater than 4, then the various circuits used to operate on _q0 through _q3 can be used in turn to generate a 1-up output stream.

Figure 29 shows another 4-up implementation of a 3x3 local averaging node that forms a complete or "identical" set of inputs where the aperture overlaps the edge of the input array and the output array dimension is the same as the input array dimension. In this case, the number of input positions sampled at the edge is not the same as the full set of samples taken internally, so the final inverse for each output position must reflect the number of samples used for that output position.

In a manner similar to the exemplary circuit shown in FIG. 22 , the variation in FIG. 29 utilizes input set 2903 to present the current value of the 4-up input array stream, while input sets 2902 and 2901 present the retained values from the previous two input sets.

The application of summation circuits 2904, 2905, 2906 and 2907 respectively produces the values _q0 , _q1 , _q2 and _q3 of the 4-up output array stream 2908, and is now aligned so that the center of each summation corresponds to a position in the 4-up input array stream. In this example, when the first 4-up input is presented at the beginning of each row, only summation circuit 2904 will intersect the left edge of the input array, but all four summation circuits may intersect the right edge of the input array, depending on the number of groups filled at the end of the row, so the selection reflecting the inverse of the number of samples obtained will vary accordingly.

Observing the close correspondence of the exemplary circuits of FIG. 21 and FIG. 28 and also observing the close correspondence of the exemplary circuits of FIG. 22 and FIG. 29, one skilled in the art will appreciate that the structure and replication of the operations are not affected by the nature of the aperture function implemented, and further, that the apparatus and method are equally applicable to any aperture function defined on a similar sliding window.

Figure 30A illustrates an implementation of a 4-up subgroup node that passes only certain channels to the next node but passes the certain channels with equivalent array dimensions and timing. This node type is typically used to split incoming channels so that different types of processing can be applied to each group of incoming channels. If the group of channels routed to the output is fixed, then the connection between input 3001 and output 3003 can be made by direct wiring of physical conductors. Otherwise, routing circuitry 3002 will affect the required selection of channels using the multiplexer.

FIG30B illustrates a typical implementation of a 4-up trim node that presents a subset of the positions of the input array stream to the output array stream. Typically, entire rows at the top edge or the bottom edge, or both, are omitted, along with rows at the left edge or the right edge, or both. To allow for a number of rows omitted at the left edge that is not an integer multiple of the data set size N, the current input set 3005 is combined with the previous input set 3004 in the repackaging circuit system 3006 to produce the channel set _q0 , _q1 , _q2 , and _q3 of the output 3007, so that _q0 is always used for the first row of each row. When no omissions are required on the left edge of the input array stream or the number of omitted rows is an integer multiple of N, the previous input set 3004 can be omitted from the simplified circuit. If the output array is sufficiently reduced from the input array, the N-up input stream can be repacked into an M-up output stream within the position selection circuitry.

In any of the nodes described above, large numbers of multipliers or individual multipliers may be used with the same facility. In situations where many weights are applied to each input, large numbers of multipliers have advantages over individual multipliers based on the bit width of the multiplicands and products. In other cases, individual multipliers of equivalent accuracy may be smaller or lower in power usage. The N-up pipeline is independent of the type of multiplier used.

In another aspect of the invention, an IC may have one or more interconnected functional circuits and input ports and output ports, each IC implementing a portion of a neural network, as described above with reference to Figures 17A and 17B and Figures 18A and 18B. Individual of such ICs in a system embodiment may be connected from a first IC receiving a primary input from a source array to other ICs in a linear order or in an interconnect chain with parallel connections, from output port to input port. The output port of the last IC in the connected group will then provide the output of the neural network containing the functionality of all ICs.

FIG. 31 illustrates such a system 3100 of ICs interconnected to implement a neural network. IC 3101 has an input port 3102 that receives a stream of input values. The input values may be in the form of any protocol as described above for input arrays, which may have a single value per position in the array, or multiple values per position, as in the example of an HDMI image with RG and B values for each position in the input array, or the input stream may be ordered as an N-up stream as described in the above embodiments.

In FIG. 31 , five ICs 3101, 3105, 3106, 3107, and 3108 are shown interconnected between input ports and output ports. IC 3101 is depicted as having functional circuitry 3104 interconnected on the IC, resulting in output port 3103 connected to the input port of IC 3105. The functional circuitry is implementing the aperture function as described above in various embodiments. In this example, ICs 3105, 3106, 3107, and 3108 are shown with functional circuitry having the same interconnections as IC 3101, but it should be emphasized that the ICs are different and the interconnections from functional circuit to functional circuit are not the same. The diagrams are representative.

IC 3105 is connected via output ports to input ports for both ICs 3106 and 3107 to illustrate that simple linear connections may not exist in ICs. The output ports of both ICs 3106 and 3107 are shown connected to input ports of IC 3108. Again, the diagram is representative. In any system of interconnected ICs, the interconnects can be more complex. IC 3108, as the last IC in the system, outputs an output stream for a neural network implemented by the system of interconnected ICs. The connections between the input ports and the output ports are parallel paths of conductors for delivering bits of the value of each output interval. The system of ICs implements a neural network of some depth. In this aspect of the invention, an unlimited variety of neural networks can be implemented by interconnecting individual ICs having different nodes and interconnects on individual ICs.

Application of 3D Image Data

In the embodiments and examples of the present invention described in detail above in many examples, the primary input data source is in the form of pixel values of a two-dimensional image, such as an RGB image as an HDMI frame, which is a 1080 by 1920 matrix of RGB values, each pixel of which is a 3 by 1 vector of color components. However, in the operation of the apparatus and methods in various embodiments of the present invention, not all input data sets will be in the form of a two-dimensional (2D) array such as an HDMI frame. However, on page 41 above, the case where the primary input data source is a three-dimensional array of data points is introduced.

As an example of a three-dimensional image that can serve as an input in a neural network, many medical devices, such as magnetic resonance imaging (MRI) devices, capture three-dimensional (3D) image data. The following description in this application extends the unique 2D processing apparatus and method described in detail above to process a stream of values representing 3D image data.

To understand the application of embodiments of the present invention to 3D data, we can reconsider the 2D data samples used in the previous description, such as an HDMI frame, which has been described above as a series of pixels arranged in a 2D plane. The aperture function is described as being based on small blocks, such as a 3 by 3 small block, meaning three pixels wide and three pixels high. The 3 by 3 aperture function manages operations involving data values of nine pixels or features from the previous node, which depend on the position of the small block centered on a particular pixel in the image. If we now consider a third dimension that is orthogonal to the plane of the 2D array, we can consider a 3 by 3 by 3 3D small block with 27 data points. A 3D patch must have multiple data points in each dimension, and a common number such as 3 by 3 by 3 is typical. In 3D images, data points are called stereo pixels rather than pixels. It is not necessary for the three dimensions of the 3D aperture function to be the same. This is not limiting in the embodiments of the present invention. Therefore, for the purposes of this specification, since the 2D patch is referred to above as M by N, the 3D aperture function has dimensions L by M by N.

Figure 32 depicts a configuration of a synthesizer on an integrated circuit, which is configured to implement a 3 by 3 by 3 convolution as a 3D aperture function on twenty-seven individual data samples. In this 3D aperture function, L, M, and N are all equal to three. As in the example using HDMI frames, the data samples may be monochrome, or may have three color values, or may feature more than three values per sample. In embodiments of the present invention, operations are always pipelined so that the values of the data samples are input as a stream in a predetermined order. In one protocol, the data values first appear in the input stream across the rows of the data array, then proceed down the columns, and thus to the planes in the third dimension. The value at each data point is processed only once, and the partial sum representing the intersection of each 3D aperture location overlapping each data point is calculated and forwarded for further processing as it would be with the operation of the device in a 2D implementation.

The 3 by 3 by 3 arrays of combiner 3201 each apply one of the 27 weights of a single output channel to the data point and forward the partial sum for further processing. Row buffer FIFO 3202 presents the appropriately delayed portion from the previous row, and plane buffer FIFO 3203 presents the appropriately delayed portion from the previous plane. Once the last weight W _2,2,2 has been applied, the summation is complete and the full sum is passed to final processing circuit 3204. Those skilled in the art will appreciate that the subscripts for the weights at each combiner refer to plane, row, and column, respectively.

It does not matter whether the input data point contains a single scalar value or multiple values (such as features from previous neural network nodes). Any number of parallel output channels can be generated for the same input source array by expanding the parallel weights and summing them throughout the circuit.

Special case logic is embedded in the synthesizer 3201 and FIFO 3202 to handle edge cases for the first and last rows, first and last columns, and first and last planes. Those skilled in the art will appreciate that the edge cases for the third dimension correspond closely to those for the second dimension, and similar solutions will suffice.

It should also be understood that a fully functional IC having a synthesizer array as shown in FIG. 32 will also have input ports, output ports, and control circuitry that operates at least one counter and generates control signals coupled to the synthesizers, delay circuits, and termination circuits as described above for a system operating on a 2D data array.

Figure 33 illustrates an embodiment in which data from multiple planes may be buffered and presented simultaneously, allowing a single synthesizer to apply weights to multiple planes. This embodiment may be preferred when the number of input channels is much lower than the number of output channels, in order to reduce the total size of the required plane buffers at the expense of increasing the number of multipliers required to be shared.

For an exemplary 3x3x3 convolution, for each of the three most recently rendered planes, input stereo pixels are retained in registers 3301 by means of a FIFO 3302 whose size is equal to RC-1. Data from these registers are merged into a bus 3303 that distributes source input data for the same 2D position to all compositors 3304 across the three planes.

Each synthesizer 3304 applies one weight for each plane of the 3x3x3 convolution to the corresponding source input for that plane and sums the results. Partial sums are passed to other synthesizers and appropriately delayed by FIFO 3305, as in a 2D implementation. Edge condition conditions (including those for the first and last planes) are embedded in the various synthesizers and closely match those implemented by the fully flipped form shown in FIG. 32.

Note that using the partially flipped form in Figure 33 breaks the strict ordering of the decomposed aperture function, since the source values from the upper left corners of three different planes are combined as the first operation. If the aperture function is a convolution where all products can be added in any order to get the same result, then this technique is equivalent to the fully flipped variant. For any aperture function that relies on a temporal sequence of operations to compute a valid result, the fully flipped variant in Figure 32 must be used instead.

Considering again the 3x3x3 example on the PxRxC input array volume, where the input is a single scalar value for each stereo pixel, the first form in FIG. 32 requires only a single bulk multiplier for all output channels, but requires two RxC FIFOs per channel to forward the partial sums. In contrast, the alternative embodiment of FIG. 33 requires three bulk multipliers, but only two RxC FIFOs total to buffer the raw scalar data. In this case, the second form may be preferred if the product of RxC is large enough to dominate the size of the FIFOs compared to the size of the bulk multipliers. But if the number of input channels is large compared to the number of output channels, then both the total number of large multipliers required and the total size of the FIFOs are reduced when using the embodiment of FIG. 32 relative to the embodiment of FIG. 33. The choice between the two embodiments can be made based solely on the number of input and output channels and the total size of the buffers and multipliers. When the order of operations is not important, the two embodiments are numerically equivalent, and the choice between the two embodiments is only one of overall cost and convenience, as long as the aperture function is correctly and completely calculated.

FIG. 34 depicts an implementation of a typical 3x3x3 convolution applied to a 4-up input stream. As previously described, the 4-up input stream presents data for four input array locations in parallel. The source input set is presented by register 3402 and then retained by register 3401 so that both sets are presented to all four synthesizer sets 3403 simultaneously in presentation order. Each synthesizer set sequences the data between rows and planes (FIFOs, not shown) as was the case for the 1-up embodiment described with reference to FIG. 32, with the primary difference being that the rows are processed simultaneously rather than sequentially.

Each synthesizer group 3403 has a unique edge condition embedded in it because each synthesizer group can be exposed to different subgroups in the horizontal direction. Even if the horizontal operations are completed simultaneously, the operation sequence can still be the same, so this embodiment is applicable to any aperture function.

FIG35 illustrates a fully inverted implementation of the same 3x3x3 convolution example described above with reference to FIG34 applied to a 4-up data stream. In this implementation, each source stereo pixel is processed only once, and a total of four bulk multipliers per input component are required to support all output channels in a parallel group.

Source input data is presented in register 3501 and distributed to all synthesizer groups. Synthesizer group 3502 is similar to synthesizer group 3403 described with reference to Figure 34. The synthesizers in group 3504 accept data from _P2 and _P3 and forward a portion to the synthesizers in group 3503, where data from _P0 of the next source input data group is applied. The synthesizers in group 3506 accept data from P3 and forward a portion to the synthesizers in group 3505, where data from _P0 and _P1 of the next source input data group is applied. The inter-row FIFO provides a standard delay function in synthesizer groups 3503 and 3505 and is not included in synthesizer groups 3504 and 3506. The inter-plane FIFO provides equivalent delay function for synthesizers 3502, 3503 and 3505.

The final output is produced by the combiners implementing weights W _2,2,2 , which are depicted here as the combiners farthest below the weights W _0,2,2 for all four outputs.

It should be noted that synthesizer group 3502 produces outputs one input source interval before synthesizer groups 3503 and 3505, and therefore must be delayed to produce all four outputs simultaneously.

Those skilled in the art will appreciate that any such function that can be decomposed into a sequence of sequential steps can be computed continuously over time by such circuits, with appropriate restrictions to meet the requirements of a particular aperture function. Furthermore, while the number and form of the synthesizer banks are dictated by a particular combination of N-up (including 1-up) data representations and three-dimensional arrays of sample sizes per output, the basic form, timing, and exception rules are common to all combinations.

Other aperture functions typically used in deep neural networks (such as MaxPool) can be adapted within the general form described.

Synthetic scaling for shared neural networks

In yet another aspect of the invention, a system is provided that uses a single instance of an aperture function implemented as an IC circuit to process multiple input data sources presented as independent parallel input array streams or as dynamically composited scales of input array streams.

The nature of applying an aperture function across a data array with more than one dimension necessitates retaining partially completed subfunction values from each row position on each column and combining them with the subfunction values at the corresponding row position on the subsequent column. If the number of input dimensions is greater than two, corresponding values from the first plane to the next plane, from the first volume to the next volume, and so on, must also be retained. In this discussion, the particular data item that needs to be retained for reassembly during later processing is referred to as the context of the position under consideration. In the above description, the required context for processing an ordered stream of input values column by column, circuitry for ordered retention of context values (such as FIFO circuitry), and other registers are described as part of an IC that also implements an aperture function.

In the following description of applying an aperture function to multiple independent parallel input array streams or as multiple dynamic synthesis scales of an input array stream, the context of the current row of the input stream processed by the aperture function circuit (based on the results retained from the previous row) is synchronously provided to the aperture function circuit by the independent IC circuit system.

In the case of data divided into columns, presenting the input data in a continuous stream means that there is a discontinuity at the end of each column where the implementation circuitry must suspend the subfunction value operated on for the right edge and resume processing the value at the left edge. When this context switch occurs, it does not matter which column is processed next. The only requirement for correct operation is that the context presented corresponds to the input value currently presented.

Thus, a single aperture function circuit can continually process rows of data presented as a series of input positions, and those rows can come from different sources subject only to the constraints of the context also presented for those rows. Furthermore, the rows need not all be of the same width.

，並且該系列之任何經截斷有限序列將始終較小。 A common technique in computer graphics is to use a set of pre-computed scaled-down 2D textures to reduce the workload and enhance visual quality when applied to 3D models. This is often called the MIPMAP technique and utilizes a series of sample sets where each set has ½ the width and ½ the height of the previous set. In this form of MIPMAP, both the height and width are reduced by 2 for each subsequent set, and the area of each subsequent scaled image is reduced by 4. The sum of the infinite series shown below is considered to be

, and any truncated finite sequence of that series will always be smaller.

，其中

,in

Thus, for a single circuit operating an aperture function on an alternating set of half-scaled (in two dimensions) input arrays, the circuit only needs to operate at a 33% increase in frequency to ensure that the operation at all scales is completed synchronously with the presentation of 1:1 scale data.

A typical example is processing an HD-compatible input video stream running at 60 frames per second (FPS) and rendering individual RGB pixel samples at 148.5MHz. If 150MHz is sufficient to process the 1:1 native scale of the stream, 200MHz is sufficient to process any limited series of half-scaled images at the same input rate.

：1大小範圍內之辨識任務，並且隨著面積減小一因數或

，頻率之所需增加藉由下式給出

，其中

When the aperture function is implemented as a node of a CNN to provide image understanding, 2:1 scaling will require the model to learn to recognize each object category within the 2:1 scale range. In cases where using a narrower range is more accurate or otherwise necessary, the model can learn

: 1 size range of identification tasks, and as the area decreases by a factor of

, the required increase in frequency is given by

,in

：1組的運算。 Therefore, a processing frequency of 300 MHz will be sufficient to accomplish the scaled implementation for the examples referenced above.

: 1 group of operations.

In a CNN processing image data, the first layer accepts input in the form of an array of pixels or samples, typically in RGB or grayscale format. Subsequent layers accept output from the upstream layer in the form of feature intensities, typically in the range [0.0, 1.0).

Multiple sets of scaled image arrays of the first layer can be synthesized on the fly as the data is presented. For 2:1 ratio scaling, there are multiple valid sampling schemes that are compatible with the proposed circuit. For smooth scaling, as each pair of pixels is received, the individual components (e.g., RGB) are summed separately and retained. On each odd column, the sum of the current pair is combined with the sum from the previous column, and the final sum is divided by four to fit the original value range. This scheme avoids sampling artifacts and is generally better for images presented to human viewers. But simply discarding every other column and every other row is also valid. This results in a smaller and simpler circuit, and can be better as long as it matches the training scheme of the model. Subsequent layers receive features that have already been created in a reduced form and do not require modification or manipulation. The circuit operates by interleaving data streams at each scale in real time at each layer.

One such configuration, using the 2:1 scaling example, switches scale as needed at each context change (i.e., at the end of each row at a given scale). Initially, full-scale pixels are presented to the circuitry implementing the first layer, and at the end of the first row, a context switch is made to continue processing at the left edge of the second row. The scaler circuitry simultaneously samples the original data as needed while the aperture function processes the full-scale samples. At the end of the second row, instead of switching the context to the third row at 1:1 scale, the context is switched to the first row at 2:1 scale, and the scaler now begins subsampling the 2:1 data and feeding it into the aperture function in preparation for operating on the 4:1 scale.

After processing the first row of the 2:1 scale input array, the context switches back to the third row of the 1:1 scale, and after processing the fourth row of 1:1 data, the context switches to the second row of the 2:1 scale, after which the first row of the 4:1 scale is available. After processing the first row of the 4:1 scale, the context switches back to the fifth and sixth rows of the 1:1 scale, followed by the third row of the 2:1 scale, followed by the seventh and eighth rows of the 1:1 scale, followed by the fourth row of the 2:1 scale, followed by the second row of the 4:1 scale, and the first row of the 8:1 scale.

The above method can be continued to any desired finite degree of subsampling. A fixed buffer is used to retain incoming samples at 1:1 scale while processing lower scales. The sampling buffer performs this function for all lower scales. The circuit implementation of the aperture function must operate at a high enough frequency to process pending results and pending inputs before any single buffer overflows. The increments indicated by the above formula are the minimum possible; operation at higher speeds can be used to further simplify the buffering logic.

The output of the described configuration is a single stream of interleaved sets of feature columns in the ordering described above. Subsequent layers do not have to subsample or buffer the 1:1 feature input; lower-scale features are passed at expected times so that the pattern of context switching occurs in exactly the same pattern as that produced.

：1縮放要複雜得多。各像素經組合成加權子取樣以產生C/

個樣本每列及R/

列每圖框，而非組合或捨棄離散像素以產生經縮小輸入陣列的固定模式。呈現給孔徑函數電路之列的切分排序將不再以簡單規則模式發生；替代地，當各列經取樣資料完成時，處理列。後續層必須以完全相同之次 序針對各經取樣尺度處理資料。此可藉由複製用於產生取樣模式之計數器邏輯或藉由發送與複合特徵串流並行之信號以指示上下文何時將切換及切換至何種尺度或藉由其他手段來達成。 Implementation

:1 Scaling is much more complicated. Each pixel is combined into a weighted subsample to produce C /

samples per row and R /

Instead of combining or discarding discrete pixels to produce a fixed pattern of the reduced input array, the rows are sliced and diced per frame. The ordering of the rows presented to the aperture function circuit no longer occurs in a simple regular pattern; instead, the rows are processed as the sampled data for each row is complete. Subsequent layers must process the data for each sampled scale in exactly the same order. This can be accomplished by duplicating the counter logic used to generate the sampling pattern or by sending a signal in parallel with the composite feature stream to indicate when the context is to be switched and to what scale, or by other means.

Other rational or irrational sampling patterns for subscale sorting can be implemented in a similar manner. The circuit design can be tailored to any scaling configuration or other considerations discovered during CNN training.

Although the examples described thus far produce a downscaled sample stream, this is not limiting in the present invention. In some embodiments, sampling may produce an upscaled stream.

The configuration of scales does not change the core implementation of the aperture function. The difference between this change described above and the previous single-scale implementation is that the single context switch from the right edge to the left edge based on the row counter is replaced by an external mechanism that manages multiple contexts for multiple scales. The operation and edge rules of the aperture function used to combine the current input value with the context for the current position remain unchanged, and the overall circuit size increases minimally.

Another application of context switching is to use the same aperture function to process interleaved rows from unrelated streams. As in the scaling example described above, the input rows for the various arrays do not have to all be of equal width. All inputs whose processing must be delayed are buffered, and the overall frequency of the aperture function implementation must be increased so that the entire set of input streams is processed before any single buffer overflows.

Single-scale and multi-scale processing of different streams can be mixed freely. And because the full context of any given position at any given scale includes whether that position is on the top row or the bottom row, different input streams do not need to be synchronized to start and end together, or even to be the same height.

36 illustrates the application of an aperture function IC circuit 3602 to an input array stream 3601 of ordered samples of image pixels or features, such as those operated on by an upstream CNN node. For any row position of the currently presented column, the context of the current column is synchronously presented to the aperture function circuit 3602 by a separate context management circuit 3603 and combined with the value operated on for the immediately preceding row position to produce data for the final output stream 3604 of the aperture function, assuming there was a previous column, which is a number of values operated on for the corresponding row position on the previous column together with exception flags maintained by the context manager (including first and last row and first and last column signals). The partial subfunction values for the current position are also computed by context management circuit 3603 and maintained as context to be assembled on subsequent rows. In standard sensor presentation order from left to right, top to bottom for individual samples, the values of individual elements of the aperture subfunction from the previous row are used immediately; in the edge case of the first row of each column, these values are either omitted or synthesized from the computation according to the definition of the aperture function.

Other non-standard presentation orders are also possible, such as sensors that deliver data in staggered rows or in a serpentine fashion (alternating left-to-right and right-to-left), which requires context and computational circuitry to allow this presentation order.

The partially computed sub-function values for each row position are retained and become context for subsequent columns. Both retention and presentation can be combined into the implementation of the IC circuit system of the aperture function 3602, but can be separated from the implementation of the aperture function without affecting the size or efficiency of the system as a whole.

Whenever a given span of input samples has been processed and processing of a different non-contiguous span must begin, the context of the last row processed must be preserved and set aside, and the context of the first row of the next span must become accessible. In standard single-sample left-to-right, top-to-bottom presentation order, this occurs when the row transitions from the rightmost edge to the leftmost edge. For clarity, in this discussion, potentially arbitrary spans will be referred to below as rows. In this simplest example, the values preserved as context on the previous row are presented as context for the next row in the order captured.

Since there is no additional data required to process the currently presented row, the implementation of the aperture function does not require or depend on the subsequent processing of the immediately following row, so any row can be presented at any time as long as the context for that row is also presented.

FIG37 illustrates a simple example that receives two independent input array streams, a first stream 3701 and a second stream 3702, and alternately presents columns from each stream by means of a store and forward multiplexer 3703 that retains input from one stream while processing the other stream. Since values from one stream are never mixed with values from the other stream, the aperture function circuit 3602 is unchanged from the first example (FIG36), where context management was external to the aperture function circuit. In the system of FIG37, context management is performed by a context circuit 3704 that is separate from the aperture function circuit.

The retained context now contains the values of each stream captured alternatively, and the presented context alternately presents the context for each stream. If the two streams are identical in dimension, then the capture and presentation can be combined into a single FIFO whose width is twice that required by the aperture function and whose number of columns is the same as that required by the aperture function, which will satisfy the requirement that the context for each column be presented simultaneously with the input array samples for that column. The final output 3705 is then presented with the two streams interleaved over time, and any subsequent node must accept this time-interleaved input array form. Since the input streams are independent, the complexity required to compute the aperture function for a single stream of interleaved columns will not be applied to any subsequent aperture nodes.

The two streams need not be of the same dimensions, nor need they start and end together. Any changes in array dimensions and the start and end of frames must be accommodated by the capture context and presentation context operable in context circuitry 3704, which will take a form sufficient to satisfy the concurrency requirements, but aperture function 3602 remains unchanged. The streams need not be presented at the same frame or pixel rate, in which case interleaving circuitry 3703 will buffer incoming data and pass it through on the completion column at a processing frequency sufficient to maintain all input streams without data loss.

This method of combining two or more independent streams of an input array can be applied to a variety of other processing situations. Of particular note are systems that accept a single input video stream, combine the frames into a set of sampled scales, and process all scales with the same aperture function.

FIG. 38 illustrates a sequence of full data rows and reduced data rows for a series of four 2:1 reductions. The first unscaled substream 3801 depicts 16 rows of pixel data labeled 1:1, meaning no reduction. In system operation similar to that represented by FIG. 37 , data from rows R ₀ through R ₁₆ (and beyond) in substream 3801 may be presented to multiplexer 3703 as a first data stream. When presenting the data from substream 3801, the data may be reduced (2:1 reduction) by, for example, averaging pairs of rows over each pair of rows of substream 3801, thereby producing a set of 8 half-width data rows as substream 3802. The resulting data array represented by substream 3802 as R' ₀ to R' ₇ is one quarter the area of the data array represented by substream 3801. When the downscaled data is created for substream 3802, that data may be presented to multiplexer 3703 as a second parallel data stream. Substream 3803 represents the data from substream 3802 further downscaled by a 2:1 ratio as R" ₀ to R" ₃ , and substream 3804 represents the data from substream 3803 further downscaled by a 2:1 ratio as R''' ₀ to R''' _1. The data from substreams 3803 and 3804 are also presented to multiplexer 3703 as separate data streams.

：1之無理縮放的完全列(子串流3901)及經縮小列(子串流3902)之序列。應注意，各列呈現之不規則性反映了列之無理取樣。後續尺度在相同意義上將不會為不規則的：下一子尺度將為1：1尺度之2：1減小，並且此後之該子尺度將為

：1尺度之2：1減小。同樣，經縮小子串流經動態地產生且作為獨立資料串流呈現給多工器3703。藉由直接傳信始終呈現之特定子尺度，將在後續節點中消除複製列之初始不規則定序的需要。 Figure 39 shows the

:1. Note that the irregularity of the appearance of the columns reflects the irrational sampling of the columns. Subsequent scaling will not be irregular in the same sense: the next subscaling will be a 2:1 reduction of the 1:1 scale, and the subscaling thereafter will be

Likewise, the shrunken substreams are dynamically generated and presented as independent data streams to the multiplexer 3703. By directly signaling the specific subscale that is always presented, the need to replicate the initial irregular ordering of the rows is eliminated in subsequent nodes.

Figure 40 illustrates the application of full scale data and scaled data to an aperture function 3602 where the data is presented as an array 3601 of full scale samples (typically pixels) as in Figure 36 and is reduced for processing by a common aperture function. The output of the aperture function is a time interleaved stream of outputs at different scales in the same pattern as the interleaved substreams described in detail above.

A single input array stream 3601 is accepted by a cascaded multi-scale sampler 4001 which presents samples at any and all desired scales as a time-interleaved sequence 4002. There is no need to change the aperture function 3602; the presentation of the sample row and its associated context is maintained as needed. Context management circuitry 4003 manages the partial output generated by the aperture function so that context data at various scales is accepted and presented at times corresponding to subsequent rows at the same scale. This can be accomplished by embedding knowledge of the expected sequence, such as for the 2:1 case, or by direct signaling from the sampler (not shown), such as for any irrational scaling ratio. The final output from the aperture function is presented as an interleaved multi-scale array stream 4004 of the function specific operation (usually the detected feature).

Figure 41 illustrates the processing of interleaved streams by subsequent CNN nodes that no longer require any scaling logic. The streams can be any mixture of independent streams and synthesized, sub-scaled frames. Context management circuitry 4102 implements split context switching based on the established pattern of column presentation. Interleaved input stream 4101 from the output of the previous node is fed into the aperture function 3602 unchanged, and at the same time, context management circuitry 4102 manages partial outputs of the aperture function by either directly embedding the presentation sequence or by accepting signals (not shown) that describe column dimensions and transitions. The final output 4103 is a compatible interleaved stream that may or may not have the same dimensions as the input stream 4101 and may not be presented in the same order.

As an example, if the aperture function is a 2x2 tiled MaxPool node, the output stream will produce half-width output rows for every two input rows. For the 2:1 scaling case, the sequence of stream elements will be the same; for any irrational case, the sequence will be different for a particular scale.

Figure 42A illustrates the sampling and slicing logic required to generate interleaved streams of 1:1, 2:1, 4:1, and 8:1 scales. The complete input array stream 3601 of scalable values is passed directly to FIFO 4202, which holds any values received while processing other scales. A 2:1 sampler 4201 accepts multiple samples from multiple columns to produce a single sample value, which is then forwarded to FIFO 4203 upon completion to be held until processing. Another 2:1 sampler 4201 accepts 2:1 samples and forwards the completed 4:1 samples to FIFO 4204. Another 2:1 sampler 4201 accepts 4:1 samples and forwards the completed 8:1 samples to FIFO 4205. The demultiplexer 4206 ostensibly selects from the available data as each scaled row becomes available and forwards that data to the interleaved sample stream 4002 along with any signaling required to describe the interleaving pattern if it is not embedded in the retention logic.

：1、2：1、2

：1及4：1尺度之交錯串流所需的取樣及切分邏輯。將可縮放值之完全輸入陣列串流3601直接傳遞至FIFO 4202，該FIFO保留在處理其他尺度時所接收之任何值。

：1取樣器4207接受來 自多個列之多個樣本以產生單個取樣值，該單個取樣值隨後在完成時轉發至FIFO 4208以供保留直至處理為止。用於構成經縮放值之列及樣本的實際數目將根據經取樣區域之無理寬度及高度而變化；一些輸入列及行用於產生多於一個輸出。2：1取樣器4201接受1：1樣本(繞過取樣器4207)且將經完成樣本轉發至FIFO 4203。另一2：1取樣器4201接受來自4207之

：1樣本且將經完成2

：1樣本轉發至FIFO 4209。另一2：1取樣器4201接受2：1樣本且將經完成4：1樣本轉發至FIFO 4204。切分多工器4210表面上在各經縮放列變得可用時自可用資料進行選擇，並且將該資料連同在交錯模式並未嵌入在保留邏輯中時描述該交錯模式所需之任何信號轉發至交錯樣本串流4002。 Figure 42B shows the generation of 1:1,

:1,2:1,2

The sampling and slicing logic required for interleaving streams at 4:1 and 4:1 scales is provided. The complete input array stream 3601 of scalable values is passed directly to the FIFO 4202 which retains any values received when processing other scales.

4203. The 2:1 sampler 4201 accepts 1:1 samples (bypassing sampler 4207) and forwards the completed sample to FIFO 4203. Another 2:1 sampler 4201 accepts 1:1 samples from 4207 and forwards the completed sample to FIFO 4203.

：1 sample and will be completed2

:1 samples are forwarded to FIFO 4209. Another 2:1 sampler 4201 accepts 2:1 samples and forwards completed 4:1 samples to FIFO 4204. The demultiplexer 4210 ostensibly selects from the available data as each scaled row becomes available and forwards that data to the interleaved sample stream 4002 along with any signals needed to describe the interleaving pattern if it is not embedded in the retention logic.

Figure 43A illustrates the subsampling and slicing logic required to generate an interleaved stream from various scaled down streams. The full input array stream 3601 of scalable values is passed directly to FIFO 4202, which holds the values received while processing other scales. U:1 sampler 4301 accepts multiple samples from multiple columns of the 1:1 stream to produce a single value, which is then forwarded to FIFO 4304 upon completion to be held until processing. V:1 sampler 4302 accepts U:1 samples and forwards completed UV:1 samples to FIFO 4305. W:1 sampler 4303 accepts UV:1 samples and forwards completed UVW:1 samples to FIFO 4306.

Demultiplexer 4307 ostensibly selects from the available data as each metric row becomes available and forwards that data to interleaved sample stream 4002 along with any signaling required to describe the interleaving pattern if it is not embedded in the retention logic.

The interleaved data may be in any form or order convenient for downstream processing. The span of completed rows reduces the complexity of the retention logic, but it is also feasible to produce a sequence of individual scaled samples as they become available; the only requirement that must be met is that the context of the individual samples must be captured and presented, which adds additional circuitry to the retention section (since the results from the immediately preceding row will not always be available and must be included in the context), but it can be achieved if there is some advantage for a particular node type. If it is necessary to produce output for the full scale input array before proceeding to other scales, it is also feasible to retain the individual input arrays by FIFOs 4304, 4305 and 4306 while FIFO 4202 is replaced by immediate pass-through.

FIG. 43B illustrates another embodiment of generating an interleaved multi-scale sample stream. In FIG. 43B , W:1 sampler 4303 samples the U:1 downscaled stream instead of the V:1 downscaled stream, thereby generating the UW:1 downscaled stream to FIFO 4309. V:1 sampler 4302 samples the 1:1 stream instead of the U:1 downscaled stream, thereby generating the V:1 downscaled stream to FIFO 4308. The downscaled stream is processed by the demultiplexer 4307, thereby generating the interleaved stream 4002.

FIG. 43C illustrates the generation of an interleaved multi-scale sample stream in yet another embodiment. FIG. 43C illustrates all of the elements of FIG. 43A, but with the addition of an additional 1:T upsampling sampler 4310. Thus, in the embodiment of FIG. 43C, there is a 1:1 full-scale stream retained in FIFO 4202, three downscaled streams generated by samplers 4301, 4302, and 4303, and one upscaled stream generated by sampler 4310 and retained in FIFO 4311, all five streams being interleaved by multiplexer 4312 to generate multi-scale sample stream 4002. Those skilled in the art will appreciate that in other embodiments, there may be more upscaled streams, as well as multiple samples of a single upscaled or downscaled stream.

Implementation of CNN Model on Fixed ASIC of Configurable Device

In yet another aspect of the invention, a system is provided whereby a fixed form circuit utilizing a number of repeated pipeline circuit elements can be configured to operate a CNN on a stream of input arrays. One or more convolution nodes having a particular core size can be combined with a particular number of parallel input and output connections and replicated to provide a basis for other combinations of parallel input and output connections and core sizes other than the size directly implemented.

In one embodiment of the invention, an application specific integrated circuit (ASIC) is provided that includes many copies of the same core processing block, which are configured in a pattern selected to allow unimpeded forward connections required for implementing both stock deep neural networks and custom deep neural networks. In other embodiments of the invention, the selection of core sizes present in the core processing block group is optimized to support specific model forms. Additional auxiliary blocks may be included to perform calculations other than convolutions. Because results are not required to flow upstream, not all blocks need to be accessible to all other blocks. For efficiency, blocks are configured on the ASIC in groups, which may be linear rows or other forms for efficient layout.

An example of an ASIC in an embodiment of the present invention is depicted in FIG. 44 , where the ASIC is diagrammatically illustrated where the core processing block includes pipeline convolution circuitry for a common core size (3 by 3 in this example), constructed with selected parallel input and output connection sizes, namely 16 each in this example. The primary input 4401 to the system is presented as a multi-channel input stream. In some embodiments, the channels are three channels of RGB or YUV video and are provided to input bus 4402 and may be provided to a first group of blocks 4405 via multiplexers 4403 and 4404.

Those skilled in the art will appreciate that interconnects shown as single lines are actually parallel conductors having a number determined at least in part by the desired accuracy of implementation in the system. Where branches of a bus are connected, the connection is shown with a point of magnification. Other locations showing bus crossings have no connection between the bus crossings.

Primary input 4401 may include at least one of the following: a direct camera interface, a DMA interface suitable for access from the CPU bus, video stream decompression circuitry, or streams limited to parallel channels are streamed to other stream interfaces in input bus 4402. Input streams do not need to be multiples of the nominal 16 parallel connection size, as unused connections are disabled and ignored in any portion of the circuitry not utilizing the connection.

In FIG. 44 , core processing blocks 4405 that are identical in physical construction in this example are shown configured in four rows. In this example, there are six core processing blocks shown in the first row (upper). This first number of core processing blocks differs from other groups of core processing blocks on the ASIC in that each of these first number of core processing blocks is coupled to input bus 4402 via multiplexer 4403 and processes the first layer of the CNN. It should be understood that the number of core processing blocks in this upper row connected to input bus 4402 via multiplexer is arbitrary. In some minimum requirement embodiments, one is sufficient, but the goal of the ASIC in embodiments of the present invention is to enable the ASIC to be used in situations with a wide variety of input and output channels and for different core sizes.

In this example, the core processing block is the same as 16 parallel input connections, 16 parallel output connections, and the block implements a 3x3 core. The interconnects and methods are described below, where there can be any number of input and output channels, and the core size can be other than 3x3, such as 5x5, 7x7, or 9x9. Adaptability can be provided by combining the functionality of multiple 3x3 cores.

Each core processing block 4405 in the first row receives its primary input from input bus 4402 via multiplexer 4403 in the form of a set of 16 parallel input connections. Those skilled in the art will appreciate that the multiplexers providing input to each core processing block 4405 are identical and therefore are not all labeled with component numbers. Each core processing block also accepts the same form of input from the immediately preceding core processing block, which may or may not be physically to the left as shown in FIG. 44 . The first core processing block in each row receives an auxiliary input from multiplexer 4404 from the output bus of the row above (except the first row which has no row above), which allows a composite core to be split across multiple rows. Each core processing block 4405, except the last one in the row, provides a primary output to an output bus 4406 and provides the same output to the next adjacent core processing block.

Input bus 4402 and all output buses 4406 are unidirectional connections to a single driver for each connection set and provide input to multiple multiplexers 4403, 4407, 4409 and 4412 and hence to the core processing blocks and other components. The buses are never used for bidirectional data flow and the depiction in Figure 44 only indicates that the outputs of one row can be used as inputs to the same row.

The values on output bus 4406 are time multiplexed. When the model is configured so that the values presented on the connected entity set are the same as the processing frequency of the system, each entity connection carries only a single data channel for each array stream position. When the model is configured to present values on the connected entity set at a multiple less than the processing frequency, each entity connection may carry multiple time multiplexed values for each array stream position or may hold a single value constant for multiple processing cycles. Various forms of time multiplexing are advantageous for implementations of model nodes with large numbers of input and output channels.

As an illustrative example, a model in which the processing path flows through four 2x2 MaxPool nodes has a data rate reduced by an exact factor of 256 and can carry 256 data channels on each physical connection. Provision is built into each core processing block and auxiliary function blocks to exploit this potential configuration by adding configuration logic and multiple indexes so that each block can adapt to the configuration presented. The end result is that the set of physical blocks required to implement large models is reduced by multiple orders of magnitude. A full description of the use of configurable time multiplexing is given below with respect to Figure 54.

Dual multiplexer 4407 in this example provides two sets of 16 parallel input connections to auxiliary function block 4408 and is equivalent to two of the 4403 multiplexers. The outputs of the 16 parallel connections are provided by each auxiliary function block 4408 to one of the sets of 16 connections on output bus 4406.

One or more sets of 16 parallel output connections (depicted as 3) are provided by multiplexer 4409 to external functional circuitry 4410 which may or may not reside on the same ASIC die or in the same IC package. One or more sets of 16 parallel input connections 4411 are returned from external functional circuitry 4410 as distinct bus connections and are available on output bus 4406.

The output bus 4406 of each row of core processing blocks provides input to the next row, thereby replacing the function of the input bus 4402 with the first row, and combined with the output bus of the other row, it can be used by the core processing block of the other row through multiplexers 4403, 4404 and 4407, and can be used by the external function interface of the other row through multiplexer 4409.

Due to the inherent nature of the time pipeline that processes the data stream, data does not flow upstream, so not all possible connections are necessarily available. If the assignment of each specific block is done by allocating them in order from left to right, the unavailable connections of each bus 4406 can be omitted, while reducing the overall circuit size at the cost of no function. The output of each core processing block is then available to all core processing blocks on the row below and any core processing block to the right of the core processing block on the same row that produced the output.

Multiplexer 4412 selects one or more groups of the 16 parallel input connections and provides them to the main output circuitry 4413, which may include final output processing (typically SoftMax) and may output results via direct parallel connections, standard SERDES (serializer/deserializer), direct memory access (DMA), or any other interface required to produce a known result for the model.

Figure 45 depicts a configuration of combining core processing blocks of a fixed 3x3 core that handles 16 parallel input and output connections to configure a 3x3 core with more inputs, outputs, or both. The first two core processing blocks 4501 and 4502 at the upper left are configured (by selection via a multiplexer, not shown) to receive the same set of 16 input connections to produce 32 output channels in two different sets of 16 parallel output connections. The next two core processing blocks 4503 and 4504 are configured to compute 16 output channels from different weights applied to two different sets of 16 input channels by passing partial sums from the first core processing block 4503 to the second core processing block 4504, where the partial sums are combined with the remaining partial sums to produce outputs on a single set of parallel output connections. The final four blocks 4505, 4506, 4507 and 4508 are configured to take inputs from two sets of 16 parallel input connections to produce two sets of partial sum pairs of 3 times 3 products having a total of 32 inputs and 32 outputs.

The combination of 3x3 core processing blocks in Figure 45 is achieved in practice by the operation of multiplexers that connect the core processing blocks in each configuration to a bus. Those skilled in the art will appreciate that a 3x3 convolution pipeline node can be configured with any number of input and output channels by grouping together an arbitrarily large set of core processing blocks. Any node whose inputs are not integer multiples of the data channel group size (nominal 16) will simply ignore the unused channels by setting their weights to zero or otherwise disabling them in computations. Any node whose outputs are not integer multiples of the channel group size can avoid computing the values of the unused channels, which will be ignored by downstream nodes.

The choice of the parallel connection group size (16 in this example) is arbitrary, and the only effect of the chosen granularity is the fraction of unused connections in the full configuration of a given model. No requirement is made, and no advantage is foreseen, for limiting the group size to a power of two. Some greater efficiency of physical layout can be achieved by making all connections the same width, but even this is not a requirement, and irregular or varying widths of connection sizes may be optimal in some cases.

FIG46 illustrates the internal structure of the core processing block 4405. The set of parallel input connections 4601 selected by the multiplexer 4403 (not shown, see FIG44) is split into different single connections (16 in this example), and each individual connection is provided to a large number of multipliers 4603, which operate on the full set of multiples that may come from that input. All multiples of all inputs are provided to each convolution unit 4604 along with a single connection from the auxiliary connection set 4602. The resulting output of each convolution unit is grouped in a set of 16 parallel output connections 4605 and is available to other blocks on the output bus 4406 (not shown, see FIG44).

FIG. 47 shows the internal structure of each convolution unit 4604. The full set of input products 4701 is provided by internal bus 4703 to each of the nine weighted sum cells 4704 used in this 3 by 3 example. As with previously disclosed versions of pipeline circuitry for convolution, a pair of array stream width FIFOs 4705 delay the partial sums of products to accommodate the requirement for a single circuit to process 3 by 3 blocks of data as presented by the input stream. In this example, the final sum of each convolution is combined with a bias value in adder 4707 together with an optional value received from auxiliary input 4702 after delay by FIFO 4706. Once the final sum is combined with the bias and optional auxiliary inputs, the sum is output 4708 to the containing block, where it forms an element of the parallel output connection set.

All FIFOs 4705 and 4706 delay values based on input stream positions rather than clock cycles and pass a given time-multiplexed data. In the example described in FIG. 45 above, FIFO 4706 can be configured to pass data without delay. FIFO 4706 is presented to support the construction of a complex core, shown in FIG. 51 and described below.

Figure 48 depicts a single summing cell 4704 applying each of the presented input channel multiples 4801 and selecting a particular multiple via configuration register 4802 and multiplexer 4803. The selected multiple is then passed through a variable shift register 4805 controlled by configuration register 4804 before being forwarded to adder 4806 where it is combined with all other selected and scaled multiples for the individual input channels.

The combination of configurable index 4802 and configurable scale 4804 allows floating point weight values to be applied to fixed point features or pixel values. The summation of one weight per input channel combined with configured bias value 4807 completes the operation of this step of the convolution over time. Summing cell 4704 may also add delayed value 4808 from the previous column via FIFO 4705 with the forwarded partial sum 4809 from the cell to the left. When both exist, they are combined by adder 4810. On the first column of cells, there is no column above, so delayed connection 4808 will not exist and adder 4810 will be omitted and forwarded value 4809 will be connected directly to adder 4811 where the value is combined with bias value 4807. On the first row of cells, there is no row on the left, the forwarded value does not exist, and adder 4810 is again omitted. In the single top left cell, there is neither a delayed connection nor a forwarded connection, both adders 4810 and 4811 are omitted, and bias value 4807 is routed directly to final adder 4812, where the bias value is combined with the adder tree sum to form output 4813.

The present invention does not require a large number of multipliers to be used to function. If the combination of large bus width and large multiplexers is taxing, the actual input values can be spread out (over a much smaller bus) and a local two-input fixed multiplier can be used, with the actual values to be multiplied configured rather than indices. Shifters and scale registers are maintained to allow full floating point weights to be applied from fixed point products.

If the chosen precision of the system is very large, e.g. 12 bits of precision in the mantissa, then the bulk multiplier and transport bus may be oversized. In this case, a smaller bulk multiplier with a correspondingly smaller bus may be used, which is then indexed multiple times and summed to produce each desired product. In this case, a 6-bit bulk multiplier may be used with two index values and two (much smaller) multiplexers to select two independent multiples which are then combined with appropriate scaling to produce the same result as the 12-bit bulk multiplier.

The operation of the system as a whole is not affected by the choice of multiplication method, and only the path from the block input 4601 to the scaler 4805 of each summing cell is affected. The choice of multiplication method and the configuration of the bulk multiplier bus width (if used) can be deferred until the ASIC is laid out and the optimum form in terms of size and power is determined.

Figure 49 depicts the internal structure of auxiliary function block 4408. In this example, the main parallel input connection set 4901 as selected by dual multiplexer 4407 is routed through variable FIFO 4902, delayed by configuration, and optionally combined with auxiliary input 4903 also from multiplexer 4407 by adder 4904. If the sum is not required in the current configuration, multiplexer 4905 can feed the delayed input value directly into common lookup table 4906.

Common lookup table 4906 is a set of static registers configured to map each possible index value to some arbitrary output value. Each of the input channels controls the multiplexer into this set of register outputs so that the same function is applied to all input channels individually. This allows any activation function required by the implementation model, such as but not limited to RELU, sigmoid, or hyperbolic tangent, to be implemented without having to include various circuit systems to operate on each such function.

If the lookup table is not used in the configuration of this block, the input can bypass the lookup table via multiplexer 4907 and lookup 4906 can be disabled to save power.

Only one of the MaxPool 4908, Averaging 4909, Sampling 4910, Expanding 4911, and Bypass or Channel Cascading functions can be selected by the configurable multiplexer 4914 for use on all channels and form an output 4915 that drives a set of parallel output connections on the output bus 4406.

MaxPool functional block 4908 allows computing the maximum value of a configurable chunk of the input stream over time and directly implementing a stride mechanism that has the effect of reducing the downstream data rate.

Averaging function block 4909 provides calculation of average values over configurable tiles and can share circuitry with MaxPool 4908. Sampling function block 4910 provides trimming of input arrays and skipping strides and can also share circuitry with MaxPool 4908 and averaging block 4909.

Each functional block implementing a non-uniform stride mechanism effectively reduces the dimensionality of the input array stream. Since the frame rate of the stream is generally constant, the time allowed by the downstream node to process each input stream position is proportionally increased. This provides the basis for time multiplexing of bus connections and dictates the degree of time multiplexing available. The core processing block can use the increased time interval to transmit and process multiple data channels on a fixed parallel connection set. The weights are expanded to accommodate the additional values, but the multipliers and accumulators are reused, allowing the expansion of the input and/or output channels of the node without the use of multiple core processing blocks. Control logic coordinates the placement of values between connected blocks over time.

Extension function block 4911 provides padding of input arrays and copying of values to align the reduced input array stream with the unreduced input array stream.

Dedicated multiplexer 4912 concatenates channels obtained from primary parallel input connection 4901 with channels obtained from auxiliary parallel input connection 4903 to effectively reroute channels to specific parallel output connections. In this example using a fixed 16 input channels per block, multiplexer 4912 can obtain 1 to 15 lowest channels from input 4901 and the corresponding 15 to 1 lowest channels from input 4903 to produce a single set of 16 channels to be selected by multiplexer 4914. Since the assignment of data channels to specific locations in the core is arbitrary (any input data channel and corresponding weight can occupy any location in the core without changing the result) when all used channels are placed at the lowest location available in each set of 16 parallel connections, this configuration is sufficient to perform all the rerouting required by the CNN model to be implemented. The use of this multiplexer is limited to data channels with equivalent time multiplexing.

Another dedicated multiplexer 4913 connects two input channels in series into one output channel by alternating samples from each parallel input connection set. Using this circuit requires retaining each input value on the two channels for two or more stream processing cycles. The output value will retain half as many input values as needed and will only occupy a single parallel output connection set on the bus.

If a small block function or concatenation is not selected by configurable multiplexer 4914, the block operates in a bypass mode which may be useful for providing a delayed path between the parallel input connection set and the core processing block to which it will be applied on subsequent rows.

Figure 50 depicts the components needed to implement any of the small block functions included in the auxiliary block. A single input channel 5001 is fed into the small block circuitry along with the delay value emitted from the previous row by the small block function circuitry 5002 and output 5004 as the final value for each small block. This allows the operation to process any function uniformly across all input stream locations.

For MaxPool 4908, when the chunk function is defined to span multiple columns, the function selects the maximum value seen and FIFO 5003 is used to associate the value of the chunk from the previous column with the current column. For Average 4909, the function accumulates the sum of all values within each chunk and FIFO 5003 is used to present the sum from the previous column. For Sample 4910, in the case where a selected position within each chunk is to be output as the value of the chunk as a whole, FIFO 5003 is used to retain the selected value from the previous column when the selected value does not fall on the last column of the chunk being processed. Each of these chunk functions produces only a single value per chunk and has the net effect of both reducing the size of the input stream array passed downstream and maintaining the throughput required for stream processing.

For extension 4911, the value from each individual position of the input stream is repeated one or more times to the output stream, and FIFO 5003 is used to retain previously encountered values for repetition again on subsequent rows, where the function is defined to produce more than one row. This function has the effect of increasing the area of the input stream array passed downstream and maintaining the throughput required for stream processing, but requires matching array sizes when different paths through the model have different sizes but need to be reassembled.

FIG51 depicts a configuration for connection to external circuitry. Inputs 5101 represent a set of external parallel input connections and may be in any of a parallel buffer, SERDES, or other form that may be convenient for connection to other circuitry, and provide the set of parallel output connections to output bus 4406. Configurable multiplexer 5102 selects a set of parallel input connections from bus 4406 and passes it to external output 5103 which may be any output form. It is expected that at least some of the external inputs and outputs are compatible with each other so that they can be used to connect multiple units of the ASIC to form models that are too large to fit in the blocks provided.

An important use of the external circuitry is to provide arbitrary functionality not included in the auxiliary function block 4408. This feature effectively makes the ASIC "future-proof" and circumvents the requirement to predict the results of future developments in the model design.

Figure 52 depicts the configuration of four 3x3 core processing blocks 4405 for computing 5x5 products. All components that do not participate in this configuration are omitted from this figure and are disabled by configuration.

The core processing block in the upper left position is configured to perform a 3x3 convolution on the upper left 3x3 values of the 5x5 block of the input stream, while the upper right core processing block is configured to perform a 2x3 convolution on the upper right 2x3 values of the 5x5 block.

The lower left core processing block is configured to compute a 3x2 product of the lower left 3x2 values, and the lower right core processing block is configured to compute a 2x2 product of the lower right 2x2 values of the 5x5 block.

Since the left row of the block will produce a final result at a time corresponding to two input stream positions before the right row of the block will produce the final result, the two FIFOs 4706 are configured for a two-position delay.

The output of the upper row adder 4707 is selected from output bus 4406 and routed as the primary input to FIFO 4902. Since the upper row of the block will complete the operation for the upper 5 by 3 segment of the 5 by 5 convolution at a time corresponding to two array widths before the lower row of the block will complete, FIFO 4902 must be configured to delay the partial sum input into the stream position by two array widths.

The output of the lower column adder 4707 is selected from output bus 4406 and routed as an auxiliary input to adder 4904 where it is combined with the delayed partial sums from the upper column to produce the final result of a 5 by 5 product. It is then passed through a lookup table 4906 where the activation function is applied.

FIG. 53 depicts the configuration of nine 3x3 core processing blocks configured in a similar manner to implement a 7x7 core. Since the timing differences between the core processing blocks are the same as in the previous example, the FIFOs are configured for the same delays. The auxiliary adder 4904 on the left combines the partial results from the first two columns, and the adder 4904 on the right combines those values with the partial results from the lower column and forwards them to the lookup table as the final result.

Those skilled in the art will appreciate that any arbitrary convolution kernel size can be constructed from any core processing block kernel size using a similar configuration of partially disabled elements and appropriate delays. This approach in combination with the configuration of the blocks shown in FIG. 45 allows configuration of any core with any number of input and output channels.

Multiplexers 4404 are included in each column block specifically to provide large volumes that can span multiple groups of blocks configured within the ASIC. Although it is expected that regular columns of repeated core processing blocks may be optimal in some cases, the operation of the present invention is in no way limited to regular configurations. When designing an ASIC implementing the present invention, any mixture of core processing block sizes and groupings of blocks may be selected to reflect the needs of a particular model, or a mixture of statistical decisions may be selected to cover the widest range of models within a single ASIC die. If the model requires more resources than a single ASIC block can accommodate, multiple ASICs can be chained together to further expand the ability to cover arbitrarily large models.

FIG54 illustrates an abstract example of a functionally complete convolutional neural network. Input 5401 provides RGB pixel data to 3 of the 16 parallel connections in our exemplary implementation; the other 13 parallel connections are not used.

Convolution 5402 is a 3-input, 32-output, 7x7 convolution with a RELU activation function, which in this example is implemented by two different groups of nine 3x3 core processing blocks and two auxiliary blocks to produce a total of 32 output data channels. The RELU activation function is implemented by a lookup table in the final auxiliary block for each group of 16 parallel output connections.

Sample 5403 is a 2 by 2 sub-sampling of the convolution output, a typical configuration found in ResNet and YOLO model variations. The sampling function can be selected in each of the final auxiliary blocks contained within the 7 by 7 convolution, so no additional blocks are required. The output of the sampling function produces a stream of arrays of one quarter area at one quarter the processing rate per position. Each output value remains constant for four stream processing cycles before the next value appears on the parallel output connection. This provides an opportunity for four channels of time-multiplexed data in downstream nodes.

Convolution 5404 is a 32-input, 64-output, 5x5 convolution with a RELU activation function. Since the 32 input channels are presented as two sets of 16 parallel input connections to the multiplexer, two sets of four 3x3 core processing blocks are grouped together to apply the weights of each individual output channel to the input. But since the input is presented at one-quarter the streaming rate, four sets of output channel values can be computed and placed on a single set of 16 parallel output connections, each carrying the time-multiplexed data.

MaxPool 5405 is a 64-input, 64-output, 2-by-2 maximum function configured to accept and process four time-multiplexed values on each of the 16 parallel input connections. The output is the maximum value of each individual channel found in a block that is two places wide and two places high. The output is placed on a single set of 16 parallel output connections, and each value remains constant for four stream processing cycles before the next value is presented. Only a single auxiliary block is required to process all 64 channels of time-multiplexed data. This provides the opportunity for sixteen channels of time-multiplexed data in downstream nodes.

Convolution 5406 is a 64-input, 128-output, 3 by 3 convolution with an S-type enable function that accepts 64 time-multiplexed inputs on a single set of 16 parallel input connections and produces 128 time-multiplexed output values on a single set of 16 parallel output connections. Each output value is maintained for two stream processing cycles instead of the four stream processing cycles passed in. A helper block with the appropriate values loaded into the lookup table implements an S-type enable function with equivalent timing on the data channel.

MaxPool 5407 is a 128-input, 128-output, 2-by-2 maximum function configured to accept and process eight time-multiplexed values on each of the 16 parallel input connections. The output is the maximum value of each individual channel found in a block that is two places wide and two places high. The output is placed on a single set of 16 parallel output connections, and each value remains constant for eight stream processing cycles before the next value is presented. Only a single auxiliary block is required to process all 128 channels of time-multiplexed data. This provides the opportunity for sixty-four channels of time-multiplexed data in downstream nodes.

Convolution 5408 is a 128-input, 256-output, 3-by-3 convolution with arbitrary start function that accepts 128 time-multiplexed inputs on a single set of 16 parallel input connections and produces 256 time-multiplexed output values on a single set of 16 parallel output connections. Each output value is maintained for four stream processing cycles instead of the eight passed in. A helper block with the appropriate values loaded into the lookup table implements the arbitrary start function with equivalent timing on the data channel.

Extension 5409 is a 256-input, 256-output, 2-by-2 extension that repeats each input value twice on each of the two rows. The 256 time-multiplexed output channels are placed on a single set of 16 parallel output connections, but each repeat value remains constant for only one stream processing cycle instead of the incoming four. This function is needed to make the output array size compatible with the output of convolution 5410 described below so that concatenation of multiple channels at equivalent locations can be implemented according to the definition of the model. This reduces the chance of time-multiplexing sixteen channels of data in downstream nodes.

Convolution 5410 is a 128-input, 256-output, 3-by-3 convolution that accepts 128 time-multiplexed inputs on a single set of 16 parallel input connections and produces 256 time-multiplexed output values on a single set of 16 parallel output connections. Each output value is maintained for only one stream processing cycle, rather than two stream processing cycles passed in. A helper block with the appropriate values loaded into the lookup table implements an activation function with equivalent timing on the data channel.

The concatenation 5411 is presented with two different streams of 256 input channels with compatible timing and array stream positions, making concatenation into a single set of 512 output channels feasible. Since the values on the two sets of 16 parallel connections are only maintained for one stream processing cycle, no further multiplexing is required or is not feasible. Therefore, the concatenation function is represented in the circuit simply by the configuration of the time-multiplexed data on the bus connections, and no auxiliary blocks are required in this case.

MaxPool 5412 is a 512-input, 512-output, 2-by-2 maximum function configured to accept and process 16 time-multiplexed values on two sets of 16 parallel input connections. Since the incoming streams are presented on two different sets of parallel input connections, the outputs are initially placed on two sets of 16 parallel output connections, and each value remains constant for four stream processing cycles before the next value is presented. These two sets of 16 parallel output connections are then routed to another auxiliary block where they are passed through a time multiplexer section to produce 512 data channels carried by a single set of 16 parallel output connections, where each data value is held for two stream processing cycles instead of four.

Convolution 5413 is a 512-input, 1024-output, 1-by-1 convolution that accepts 512 time-multiplexed inputs on a single set of 16 parallel input connections and produces 1024 time-multiplexed output values on a single set of 16 parallel output connections. Each output value is maintained for only one stream processing loop, rather than two stream processing loops passed in. The 1-by-1 convolution is implemented by utilizing only the bottom right output summing cell of the nine cells of the 3-by-3 core processing block.

The Average5414 accepts 1024 channels of time-multiplexed data on a single set of 16 parallel input connections and is configured to compute the average of the input values over a chunk size equal to the entire reduced array stream.

The output 5415 of the model is delivered as 1024 time-multiplexed values on 16 external connections, representing the presence or absence of 1024 different categories.

This model form is not intended as a robust example, but rather is demonstrated to exploit many of the properties of the invention and to illustrate how the circuit actually works.

Those skilled in the art will appreciate that the embodiments depicted in the figures and described above are exemplary and do not describe every form that the invention may take. There may be many other forms that may be implemented within the scope of the invention.

The scope of this invention is limited only by the scope of the patent application.

4401: Main input 4402: Input bus 4403,4404,4407,4409,4412: Multiplexer 4405: Core processing block 4406: Output bus 4408: Auxiliary function block 4410: External function circuit system 4411: 16 parallel input connections 4413: Main output circuit system

Claims (21)

An application specific integrated circuit (ASIC) for computing a convolutional neural network (CNN), comprising: a first input bus that receives an ordered stream of values from an array, each position in the array having one or more data channels; A first ordered group of core processing blocks, the core processing blocks having a fixed number of parallel input connections and a fixed number of parallel output connections, each core processing block of the first ordered group coupled to the input bus through one of a first set of configurable multiplexers, the core processing blocks being adapted to compute a convolution of a common core size and pass the computed value to a first output bus and to an adjacent downstream core processing block of the first ordered group, the first output bus being connected back as an input to each configurable multiplexer in the first set of configurable multiplexers; A second ordered group of core processing blocks, the core processing blocks having the fixed number of parallel input connections and the fixed number of parallel output connections, each of the core processing blocks of the second ordered group coupled to the first output bus through one of a second set of configurable multiplexers, the core processing blocks of the second ordered group adapted to compute a convolution of the common core size and pass the computed value to a second output bus and to an adjacent downstream core processing block of the second ordered group, the second output bus being connected back as an input to each of the configurable multiplexers in the second set of configurable multiplexers; and A third ordered group of core processing blocks, the core processing blocks having the fixed number of parallel input connections and the fixed number of parallel output connections, each of the core processing blocks of the third ordered group being coupled to the second output bus through one of a third set of configurable multiplexers, the core processing blocks of the third ordered group being adapted to compute a convolution of the common core size and to pass the computed value to a third output bus and to an adjacent downstream core processing block of the third ordered group, the third output bus being connected back as an input to each of the configurable multiplexers in the third set of configurable multiplexers, the third output bus also being connected to a primary output circuit through a single primary output multiplexer, the primary output circuit being adapted to perform primary output processing and provide final output. A special application integrated circuit as claimed in claim 1, further comprising: an additional configurable multiplexer coupled to the first output bus, which provides the selected value to the first core processing block in the second ordered group; and an additional configurable multiplexer coupled to the second output bus, which provides the selected value to the first core processing block in the third ordered group. The special application integrated circuit of claim 1 further includes one or more auxiliary function blocks that provide functions other than the functions of the core processing blocks. A special application integrated circuit as claimed in claim 3, wherein the one or more auxiliary functional blocks receive input from a dual multiplexer connected to the input bus and the first output bus and provide output to the first output bus. A special application integrated circuit as claimed in claim 3, wherein the one or more auxiliary functional blocks receive input from a dual multiplexer connected to the first output bus and the second output bus and provide output to the second output bus. A special application integrated circuit as claimed in claim 3, wherein the one or more auxiliary functional blocks receive inputs from a dual multiplexer connected to the second output bus and the third output bus and provide outputs to the third output bus. The special application integrated circuit of claim 1 further includes an external functional circuit system that selects input from the first output bus through a configurable multiplexer and provides output to the first output bus. The special application integrated circuit of claim 7 further includes an external functional circuit system that selects input from the second output bus through a configurable multiplexer and provides output to the second output bus. The special application integrated circuit of claim 8 further includes an external functional circuit system that selects input from the third output bus through a configurable multiplexer and provides output to the third output bus. A special application integrated circuit as claimed in claim 1, wherein the common core size is a 3×3 core. A special application integrated circuit as claimed in claim 1, wherein the fixed number of parallel input connections is 16, and the fixed number of parallel output connections is 16. A special application integrated circuit as claimed in claim 1, wherein the ordered value stream is provided by one of a direct camera output of RGB values, a DMA interface suitable for access from a CPU bus, or a video stream decompression circuit, thereby producing three parallel channels of red, green and blue (RGB) values for an image. A special application integrated circuit as claimed in claim 11, comprising combining the operations of two or more core processing blocks of a 3x3 core having 16 parallel input and output connections to configure a 3x3 core having more than 16 inputs or more than 16 outputs or more than 16 inputs and outputs. A special application integrated circuit as claimed in claim 10, which is adapted by additional circuitry to compute a volume having a core greater than 3 times 3 by combining operations of a plurality of said 3 times 3 core processing blocks. The special application integrated circuit of claim 14, wherein the special application integrated circuit is suitable for calculating a 5 times 5 product, a 7 times 7 product or a 9 times 9 product. A special application integrated circuit as claimed in claim 1, wherein the core processing blocks present each input channel value to a large number of multipliers which operate on the full set of possible multiples of the input and provide those multiples together with the single channel values from an auxiliary parallel connection set to a single convolution unit, the resulting outputs from each convolution unit being grouped in a set of 16 parallel output connections and available to other core processing blocks on the output bus. A special application integrated circuit as claimed in claim 1, wherein the core processing block input value is processed by a local dual-input fixed multiplier. A special application integrated circuit as claimed in claim 3, wherein each of the auxiliary function blocks receives parallel input connections from two independent buses through a dual multiplexer and outputs one of a MaxPool function, an averaging function, a sampling function and an expansion function selected by an output multiplexer. A special application integrated circuit as claimed in claim 18, wherein the auxiliary function block sums the values from the parallel input connections via individual channels and multiplexes the summed values into a lookup table, the lookup table being suitable for providing any activation function that can be represented in a tabular form, including a RELU, S-type or hyperbolic tangent activation function. A special application integrated circuit as claimed in claim 18, wherein the input channels received from independent parallel input connections are input to a first dedicated multiplexer, which first dedicated multiplexer connects the parallel input connections in series to effectively reroute the data channels to specific parallel output connections and provides the serialized output to the output multiplexer as a candidate for selection as an output of the auxiliary functional block. A special application integrated circuit as claimed in claim 18, wherein the input channels received from independent parallel input connections are input to a second dedicated multiplexer, which connects the two parallel input connections in series into a parallel output connection by alternating samples from each connection and provides the result to the output multiplexer as a candidate for selection as an output of the auxiliary function block.