RELATED APPLICATIONS

[0001] This application claims the benefit of U.S. Provisional Application No. 62/195,921 , entitled "Mireplica Visual-Processing Architecture: Convolutional Neural Networks" and filed on July 23, 2015, which application is hereby incorporated by reference in its entirety and for all purposes as if completely and fully set forth herein.

BACKGROUND

[0002] Many applications involve two-dimensional data sets. Visual processing applications are one example. The term "visual processing" as used herein refers to a general class of processing of image and video picture elements ( ^" 'pixels") and related data. This includes applications such as enhancing images and converting pixels formats, motion detection and tracking, and identifying features or objects in either still-image or video frames. Other applications involving data that can be expressed in two-dimensional sets include modeling of physical quantities such as forces or electromagnetic fields. Three- dimensional data sets can in some cases be represented in two-dimensions, such as by projection or transformation into a two-dimensional plane, or as multiple adjacent two- dimensional data sets.

[0003] Convolutional neural networks encompass a large variety of detection and classification algorithms. Recently, two-dimensional (2D) convolutional neural networks (CNNs) have gamed widespread attention for their ability to detect and classify a large number of image objects. CNNs have many different configurations, but the configurations are composed of basic elements that permit the network to be '"trained" to recognize objects by adjusting network parameters and interconnection topologies to achieve a high level of detection reliability, typically over 90% in state-of-the-art implementations.

[0004] CNNs are generally classified as '"deep" neural networks, often with four or more layers. A "convolutional" layer of a CNN generally has more output values than inputs, the outputs in turn becoming inputs to the next convolutional layer. As discussed further below, the resulting number of operations is quite large, and the number of clock cycles needed to perform a detection process on one input image frame can easily be on the order of one billion. Real-time image recognition is desirable for many applications, such as sign-reading for automatically-operated vehicles or face recognition in security situations. Accordingly, improvements in detection speed can greatly enhance the performance and capabilities of such image-recognition applications.

BRIEF DESCRIPTION OF THE DRAWINGS

[0005] The following detailed description of various disclosed embodiments makes reference to the accompanying drawings in which:

[0006] Figure 1 is a simplified block diagram illustrating certain aspects of an exemplary convoiutional neural network;

[0007] Figure 2 is a diagram illustrating a convolution operation in a convoiutional neural network;

[0008] Figure 3 is a diagram illustrating the number of image, signal, weight and bias elements that a detection output associated with a single pixel depends upon;

[0009] Figure 4 is a simplified block diagram illustrating certain aspects of a tile processor dataflow implementation;

[0010] Figure 5 is a histogram showing latency for data requests performed during operation of an exemplary CNN detection process;

[0011] Figure 6 is a simplified block diagram illustrating certain aspects of an embodiment of an instruction generation unit used in some embodiments with the tile processor described herein;

[0012] Figure 7 is a diagram illustrating an exemplary subsampling operation in a convoiutional neural network;

[0013] Figure 8 is a diagram illustrating data vector widths resulting from subsampling operations in an exemplary convoiutional neural network;

[0014] Figure 9 is a diagram illustrating tile processor data memory storage during execution of an exemplary convoiutional neural network with subsampling;

[0015] Figure 10 is a diagram illustrating a data reorganization scheme providing improved parallelism and faster execution of an exemplar)' convoiutional neural network;

[0016] Figure 11 is a diagram illustrating tile processor data memory storage during execution of an exemplary convoiutional neural network with subsampling and vector concatenation; [0017] Figure 12 is a diagram illustrating row and column inputs to an exemplary convolution operation in the absence of a data reorganization scheme;

[0018] Figure 13 is a diagram illustrating row and column inputs to an exemplary convolution operation using a data reorganization scheme;

[0019] Figure 14 is a diagram illustrating input shuffling of data as part of a data reorganization scheme;

[0020] Figure 15 is a diagram illustrating input shuffling of data as part of a data reorgan izati on s cheme;

[0021] Figure 16 is a histogram showing latency for data requests performed during operation of an exemplary CNN detection process employing data reorganization;

[0022] Figure 17 is a diagram illustrating an interleaved data reorganization scheme for an exemplar) _' - convolutional neural network;

[0023] Figure 18 is a diagram illustrating input shuffling of data as part of a data reorganization scheme; and

[0024] Figure 19 is a histogram showing latency for data requests performed during operation of an exemplary CNN detection process employing an interleaved data reorganization scheme,

DETAILED DESCRIPTION

Overview

[0025] Methods and systems are disclosed for increased speed of processing operations on data in two-dimensional arrays, and for detecting a feature in an image. An embodiment of a processor-implemented method for detecting a feature in a two-dimensional image includes storing, in a set of data memories within a parallel processing system, first image data representing pixels of a first image. The parallel processing system includes a row of multiple substantially identical data processors connected by an instruction pipeline, where the instruction pipeline is adapted for sequential conveyance of instructions from a first one of the multiple data processors to each adjacent data processor in turn. Each of the data processors comprises a respective data memory of the set of data memories that the first image data is stored in. In addition, each of the data memories is partitioned to include multiple memory regions of substantially identical storage capacity, and storing the first image data comprises storing data representing successive vertical slices of the first image in respective adjacent memory regions of the data memories of the parallel processing system.

[0026] This embodiment of the method continues with storing, in a memory of a host processor coupled to the parallel processing system, feature kernel data comprising weight data representing a set of weight matrices. The method further includes, for each of multiple selected pixels within the first image, performing a set of convolutions over a two- dimensional pixel region including the selected pixel and applying a nonlinear function to a result of each convolution to produce a feature map pixel corresponding to the selected pixel. Each convolution in the set of convol utions is performed using a respective one of the set of weight matrices, and a feature map pixel is produced for each of the weight matrices. The method continues with storing, for each of the weight matrices, a feature map comprising ail of the feature map pixels, where storing the feature map comprises storing data representing separate pixels of the feature map in respective separate memory regions of the data memories of the parall el processing system. For each pixel of a feature map, data representing the corresponding pixel from each of the feature maps produced using all of the weight matrices is stored in the same memory region. This embodiment of the method further includes processing the feature maps to produce a decision as to whether a particular feature or class of features is detected within the first image.

[0027] In a further embodiment of the above method, the feature kernel data further includes bias data representing a bias value associated with each weight matrix in the set of weight matrices, and each one of the set of convolutions is performed using the bias value associated with the respective one of the set of weight matrices. In an embodiment, performing the set of convolutions for each of the multiple selected pixels comprises sequentially executing, in adjacent data processors of the parallel processing system, instructions for performing the sets of convolutions. In a further embodiment, a single iteration of sequentially executing the instructions in adjacent data processors of the parallel processing system comprises performing the set of convolutions for all selected pixels within one h orizontal row of the first image.

[0028] In a further embodiment of this method, the multiple selected pixels consist of pixels spaced apart, in horizontal and vertical directions withm the first image, by a number of pixels defined by an integer subsampling factor n. In a still further embodiment, a single iteration of sequentially executing the instructions in adjacent data processors of the parallel processing system comprises performing the set of convolutions for all selected pixels within n horizontal rows of the first image, where the n horizontal rows are adjacent rows within a series of horizontal rows spaced n pixels apart.

[0029] In a further embodiment, storing the feature map also includes, during a single iteration of sequentially executing the instructions in adjacent data processors, storing feature map pixels corresponding to selected pixels in the uppermost of the n horizontal rows of the first image in a first group of adjacent memory regions of data processors within the parallel processing system, where the first group of adjacent memory regions are in data processors positioned closest to the beginning of the instruction pipeline of the parallel processing system. In this embodiment, storing the feature map also includes, during the single iteration of sequentially executing the instructions in adjacent data processors, storing feature map pixels corresponding to selected pixels in a next lower row of the n horizontal rows of the first image in a next group of adjacent memory regions adjacent to the first group of adjacent memory regions, where the next group of adjacent memory regions are in data processors positioned further along the instruction pipeline of the parallel processing system. This embodiment also includes, during the single iteration of sequentially executing the instructions in adjacent data processors, storing feature map pixels corresponding to selected pixels in any additional lower rows of the n horizontal rows in successive groups of adjacent memory regions in data processors positioned further along the instruction pipeline of the parallel processing system.

[0030] In another embodiment, storing the feature map includes, during a single iteration of sequentially executing the instructions in adjacent data processors, storing each feature map pixel in a first series of n feature map pixels corresponding to the first selected pixel in each of the n horizontal rows, in order from the uppermost to the lowermost of the n horizontal rows, in a respective adjacent memory region of the data processors in the parallel processing system. These feature map pixels are stored in memory regions beginning with the first memory region of the data processor positioned closest to the beginning of the instruction pipeline of the parallel processing system. In this embodiment, storing the feature map also includes, dunng the single iteration of sequentially executing the instructions in adjacent data processors, storing each feature map pixel in a second series of n feature map pixels corresponding to the second selected pixel in each of the n horizontal rows, in order from the uppermost to the lowermost of the n horizontal rows, in a respective adjacent memory region of the data processors in the parallel processing system. In addition, storing the feature map includes, during the single iteration of sequentially executing the instructions in adjacent data processors, storing each feature map pixel in any additional series of n feature map pixels corresponding to additional selected pixels in each of the n horizontal rows, in order from the uppermost to the lowermost of the n horizontal rows, in a respective adjacent memory region of the data processors in the parallel processing system, beginning with the memory region immediately following the memory region storing the last feature map pixel in the previous series of feature map pixels.

[0031] In an embodiment of ihe method for detecting a feature in a two-dimensional image, processing the feature maps to produce a decision includes rearranging the stored data representing the feature map pixels so that data representing feature map pixels

corresponding to selected pixels having the same horizontal position in the first image is all stored within the same memory region of the data processors in the parallel processing system. In this embodiment, processing the feature maps also includes, for each of multiple selected feature map pixels within each feature map, subsequently performing an additional set of convolutions over a two-dimensional feature map pixel region including the selected feature map pixel, wherein each one of the additional set of convolutions is performed using a respective one of an additional set of weight matrices stored in the memory of the host processor. In another embodiment, the first image constitutes a horizontal slice of a larger image, and the method further includes, subsequent to completion of the set of convolutions for first image data representing an uppermost row of the first image, overwriting the first image data representing the uppermost row of the first image with data representing a row of the larger image just below the lowest row of the larger image previously included in the first image.

[0032] An embodiment of a data processing system for detecting a feature in a two- dimensional image includes a row of substantially identical data processors, where the data processors are connected by an instruction pipeline adapted for sequential conveyance of instructions from a first one of the multiple data processors to each adjacent data processor in turn, and each of the data processors includes a data memory partitioned to include multiple memory regions of substantially identical storage capacity. This embodiment of the data processing system further includes a host processor coupled to the row of data processors, where the host processor includes a data memory adapted to store feature kernel data comprising weight data representing a set of weight matrices and bias data representing a bias value for each weight matrix within the set of weight matrices. The host processor further includes a control module adapted to fetch and provide to the instruction pipeline instructions for execution by the multiple data processors, and stored program instructions which, when provided to the instruction pipeline and executed by ihe row of data processors, are operable to implement certain steps of the method described above for detecting a feature in a two- dimensional image.

[0033] In a further embodiment of the data processing system, the control module includes an instruction generation unit coupled to the host processor and to the row of data processors. The instruction generation unit is adapted to provide an interface between the host processor and the row of data processors, and to translate custom compiler instructions received from the host processor into instructions executable by the data processors in the row of data processors.

[0034] An embodiment of a processor-implemented method for increased speed of processing operations on data in two-dimensional arrays comprises storing, in a set of data memories within a parallel processing system, first array data representing elements of a first array. The parallel processing system includes a row of multiple substantially identical data processors connected by an instruction pipeline adapted for sequential conveyance of instructions from a first one of the multiple data processors to each adjacent data processor in turn. Each of the data processors includes a respective one of the set of data memories, and each of the data memories is partitioned to include multiple memoiy regions of substantially identical storage capacity. In this embodiment of the method, storing the first array data comprises storing data representing successive columns of the first array in respective adjacent memory regions of the data memories of the parallel processing system.

[0035] The method for increased speed of processing operations further includes, for each of multiple selected elements within the first array, performing a processing operation on the selected element to produce an output element corresponding to the selected element. In this embodiment, the multiple selected elements consist of elements spaced apart, in horizontal and vertical directions within the first array, by a number of elements defined by an integer subsampling factor n. Performing the processing operation for each of the multiple selected elements comprises sequentially executing, in adjacent data processors of the parallel processing system, instructions for performing the processing operation, and a single iteration of sequentially executing the instructions in adjacent data processors of the parallel processing system comprises performing the processing operation for all selected elements within n horizontal rows of the first array , where the n horizontal rows are adjacent rows within a series of horizontal rows spaced n elements apart. The method further includes storing an output array comprising all of the output elements, where storing the output array- comprises storing data representing separate elements of the output array in respective separate memory regions of the data memories of the parallel processing system. [0036] In a further embodiment of the method for increased speed of processing operations, performing the processing operation comprises performing one or more convolutions over a two-dimensional element region including the selected element, and each one of the one or more convolutions is performed using a coefficient matrix stored in a data memory of a host processor coupled to the parallel processing system.

[0037] In another embodiment of the method for increased speed of processing operations, storing the output array further includes, during a single iteration of sequentially executing the instructions in adjacent data processors, storing output elements corresponding to selected elements in the uppermost of the n horizontal rows of the first array in a first group of adjacent memory regions of data processors within the parallel processing system. The first group of adjacent memory regions is in data processors positioned closest to the beginning of the instruction pipeline of the parallel processing system. In this embodiment, storing the output array further includes, during the single iteration of sequentially executing the instructions in adjacent data processors, storing output elements corresponding to selected elements in a next lower row of the n horizontal rows of the first array in a next group of adjacent memory regions adjacent to the first group of adjacent memory regions. The next group of adjacent memor ' regions is in data processors positioned further along the instruction pipeline of the parallel processing system. Storing the output array also includes, during the single iteration of sequentially executing the instructions in adjacent data processors, storing output elements corresponding to selected elements in any additional lower rows of the n horizontal rows in successive groups of adjacent memory regions in data processors positioned further along the instruction pipeline of the parallel processing system.

[0038] In another embodiment of the method, storing the output array further includes, during a single iteration of sequentially executing the instructions in adjacent data processors, storing each output element in a first series of n output elements corresponding to the first selected element in each of the n horizontal rows, in order from the uppermost to the lowermost of the n horizontal rows, in a respective adjacent memory region of the data processors in the parallel processing system. The output elements are stored in memory regions beginning with the first memory region of the data processor positioned closest to the beginning of the instruction pipeline of the parallel processing system. In this embodiment, storing the output array further includes, during the single iteration of sequentially executing the instructions in adjacent data processors, storing each output element in a second series of n output elements corresponding to the second selected element in each of the n horizontal rows, in order from the uppermost to the lowermost of the n horizontal rows, in a respective adjacent memory region of the data processors in the parallel processing system. These output elements are stored in memory regions beginning with the memory region

immediately following the memory region storing the last output element in the first series of output elements. Storing the output array also includes, during the single iteration of sequentially executing the instructions in adjacent data processors, storing each output element in any additional series of n output elements corresponding to additional selected elements in each of the n horizontal rows, in order from the uppermost to the lowermost of the n horizontal rows, in a respective adjacent memory region of the data processors in the parallel processing system. These output elements are stored in memory regions beginning with the memor ' region immediately following the memory region storing the last output element in the previous series of output elements.

[0039] In another embodiment, the method for increased speed of processing operations further comprises rearranging the stored data representing the output elements so that data representing output elements from the same column of the output array is all stored within the same memory region of the data processors in the parallel processing system, and, for each of multiple selected output elements within the output array , subsequently performing an additional processing operation on the selected output element.

[0040] An embodiment of a data processing system for increased speed of processing operations on data in two-dimensional arrays includes a row of substantially identical data processors, where the data processors are connected by an instruction pipeline adapted for sequential conveyance of instructions from a first one of the multiple data processors to each adjacent data processor in turn. Each of the data processors includes a data memory

partitioned to include multiple memory regions of substantially identical storage capacity. The system further includes a host processor coupled to the row of data processors, where the host processor includes a data memory adapted to store fixed data for use in processing operations on array data stored in the data memories of the row of data processors. The host processor further includes a control module adapted to fetch and provide to the instruction pipeline instructions for execution by the multiple data processors, and stored program instructions which, when provided to the instruction pipeline and executed by the multiple data processors, are operable to implement certain steps of the method described above for increased speed of processing operations.

[0041] In a further embodiment of the data processing system, the control module comprises an instruction generation unit coupled to the host processor and to the row of data processors, where the instruction generation unit is adapted to provide an interface between the host processor and the row of data processors, and to translate custom compiler instructions received from the host processor into instructions executable by the data processors. In another embodiment of the system, performing the processing operation comprises performing one or more convolutions over a two-dimensional element region including the selected element, and each one of the one or more convolutions is performed using a coefficient matrix stored in the data memory- of the host processor.

[0042] The methods and systems described herein result in substantial improvement in the speed of 2D CNN implementations and other operations on two-dimensional arrays involving subsampling. Certain aspects of a novel tile processor architecture described herein are explained further in commonly owned U.S. Patent Application No. 13/602,958, now U.S. Patent No. 9,183,614, and U.S. Patent Application No. 15/054,118, each of which is hereby incorporated by reference herein in its entirety. Unlike other approaches, the tile processor architecture permits simultaneous processing across the entire width of the image frame, and supports low-latency communication throughout the neural network, including the distribution of a very large number of network parameters with essentially no communication overhead. Furthermore, the architecture provides opportunities for data reorganization that enables parallelism beyond what is possible with existing solutions - up to a factor of at least 4 times the parallelism. In an embodiment, the CNN is directly implemented by a single- threaded C++ source program.

CNN Overview

[0043] CNNs are very computation- and communication- intensive, and operate on contexts that are very difficult to partition across parallel processing elements. Figure 1 illustrates generalized components of an example CNN based on reference code provided for the Embedded Processor Architecture course at Eindhoven University of Technology, available at https:/7sites. google.com/site/5kk73gpu2013/assignmeniycnn (this particular example detects and classifies traffic signs). The neural network 100 consists of four layers, labeled Layer 1 through Layer 4. Each layer employs a number of feature maps that determine, for pixels in the input image and for each feature map, to what degree a region defined by a pixel (in this case, the region with the pixel at its top-left corner) matches the feature map. This is roughly analogous to a neuron making this determination at each position, hence the term "neural network." Exemplar) _' - sets of possible feature maps are shown in Figure 1. Set 102 of 24 feature maps can be used in Layer 1 , set 104 of 40 feature maps can be used in Layer 2, and set 106 of 24 feature maps can be used in Layer 3. In the embodiment of Figure I, the feature maps used in successive layers represent progressively more complex features. This is often the case in convolution^ neural networks. As labeled in Figure 1 , feature map sets 102, 104 and 106 are used for recognition of faces. Other exemplar) _' - feature map sets suitable for recognition of other objects are shown in Figure 1. Although not shown in Figure 1, similar feature map sets suitable for recognition of traffic signs would be used for recognition of input image 108, a traffic sign. Feature maps as illustrated in Figure I are fixed data, and may also referred using other terms, such as "feature detectors." The term "feature map" may also be used to describe the output "image" that results from the comparison of a feature map to the input image.

[0044] With this comparison of an image portion to a feature map as the basic concept used for object detection, there are number of underlying operations in the network

implementation, as shown in Figure 1 :

* Subsampiing ("SAMP " in the figure). Image objects can be at varying distances from the viewport (i.e., viewing position), so the pattern matching must consider a range of distances in matching features. This is accomplished by subsampiing the image at various layers, which places image information (with some acceptable loss) into denser representations (smaller width and height). The final layer, Layer 4, compares a summary of all layers to indicate whether an object has been detected at a given position, and optionally to classify the object (for example, the speed indicated on a sign).

* 2D convolution ("CONV" in the figure). This is the basic operation for matching regions of the image to the feature maps. The dimensions of these regions are fixed for any given network, but can vary from one layer to the next and one network to the next. This is part of the network design.

® A non-linear activation function ("ACTV" in the figure). This function determines the degree to which the region matches the feature, and discards regions that don't have a match above a certain threshold (by discarding the output of the single pixel that defines the region, again in this case the top-left pixel). Optionally, it can assign relatively larger values to outputs that are further above the threshold, to emphasize these positions.

* Partial interconnect of outputs from different feature maps from layer 1 ("PCNT" in the figure). This operation considers various combinations of feature-map comparisons from the previous layer, forming a richer set of information about the features that have matches in the previous layer. * Full interconnect of outputs from different feature maps from layer 2 ("FCNT" in the figure). This also forms a richer set of information, but results in many more combinations, so is done only in layer 3 in this example.

* A final threshold computation ('THRESH" in the figure). This summarizes the "decision" made by the network at any given position - whether a feature is detected at that position. This is indicated by some value, after a final convolution, being greater than zero. If this is true, then other convolutions can be used to sort the detection into a certain class of detected object, with the magnitude of this convolution indicating the level of confidence in the classification.

[0045] The most time-consuming operation in a convolutional neural network such as that of Figure 1 is the 2D convolution of the image data, illustrated in Figure 2. This operation computes a signal output, S _y _ _x , at a given vertical position y and horizontal position x. The figure shows a 6x6 convolution, meaning that it computes the output using, for example, a region 202 within input image 108, where region 202 is 6 pixels high and 6 pixels wide, with x and y defined by the top-left comer. The various features being compared are defined by kernels, consisting of a bias B and a weight matrix W _m „. In the embodiment of Figure 2, weight matrix 204 has 36 elements W _VjX representing the intensity variation of a feature map 206 within feature map set 208.

[0046] The convolution operation is defined by the following equation;

[0047] The convolution sums the products of image data with the corresponding elements of the w cighi matrix, resulting in a single value that is added to the bias to produce the signal The convolution therefore results in an output signal value corresponding to the spatial position of the pixel having input intensity value IN^. Informally, this operation produces a larger signal value for regions which have a higher degree of correspondence between pixel values and weight values. For example, if the image is lighter at the same positions that the weights have a higher value (also lighter), the product of the two has a relatively large value (and, applying a positive bias using negative weights results in relatively large values for darker regions that match). The larger the convolution sum, the higher the degree of match. The AC TV function discards convolution outputs that have relatively weak values, so they do not participate in further convolution layers.

[0048] The convolution is computationally intense in and of itself, since it is performed across the entire image (in a test implementation described herein, an image 1280 pixels wide and 720 pixels high). However, this is only pail of the operation's complexity. Figure 3 illustrates the dependencies that a single output of the example network has, tracing from the output ("1 detect") back through the network, and considering all convolution kernels and interconnect operations (combinations of inputs sets result in more output sets than inputs sets depending on the number of combinations).

[0049] A single output classification depends on 38,280 signal elements ("s," including the input image), and 272,588 kernel elements (counting both bias "b" and weights "w"). Note that layer 2 has to be repeated 25 times to form the 5x5 signal inputs to layer 3, and layer 1 has to be repeated 36 times to form the 6x6 signal inputs to layer 2, or a total of 36*25=900 times to form the 5x5 inputs to layer 3. The output detection is formed at each output location, each with a different set of data dependencies. There is overlap in these

dependencies, because adjacent outputs have adjacent context sets, but each one is unique.

[0050] A conventional implementation of the example network of Figure 1 (using an nVidia GeForce GTX 460) requires approximately 1 ,400,000,000 cycles to execute on a frame of input image. In contrast, one embodiment of a mapping to the tiled architecture requires approximately 32,000,000 cycles for the same network, a factor of almost 44 times faster. ^' This embodiment includes subsampling by a factor of two in layers 1 and 2, and a 2D convolution in all four layers. The underlying number of processing elements, and the operations, are comparable between the conventional implementation and the tile processor implementation, but there is a very large difference in how the dataflow is implemented - that is, how the data dependencies in Figure 3 are satisfied.

[0051] Conventional processor solutions implement dataflow such that the signal and kernel data have to be communicated to the processing elements. This can be implemented by moving data from a shared memory to the processing elements (in general-purpose graphics processors), or by explicitly moving data between processing elements (in "vision processors"). This movement not only requires time to do the transfer, but also requires that the processing elements synchronize so that the transfers occur at a meaningful point in the program, which typically requires that the either the source or destination of the data stalls until the appropriate point is reached. [0052] In contrast, in the systems and methods described herein, the tile processor array leaves all of the context (e.g., image data for surrounding pixels) in place, in local memory, in a way that is shared between all processing elements with little or no overhead for either data movement or synchronization. Figure 4 illustrates key aspects of a tile processor array as used for the methods and systems described herein . A group of four interconnected tile processors 401 is shown. The term "tile" refers to a rectilinear region, or two-dimensional array, of pixels in a frame, that is either 4, 8, or 16 pixels wide and up to 256 pixels high. Each processing element, or tile processor, operates on a unique tile of pixels, with adjacent tiles mapped to adjacent tile processors. Although tile processing is described herein mainly for image processing applications, it should be understood that the disclosed embodiments are believed to be suitable for any applications involving data processing of two-dimensional data sets, particularly two-dimensional interrelated data sets.

[0053] The tile processor 401 has many components in common with a conventional processor, with the notable exception of having no instruction memory and no instruction fetch logic. The depiction of Fig. 4 is intended to illustrate the non-conventional components of tile processor 401, and depict the grouping of multiple tile processors 401. The arrangement of components of tile processor 401 may not reflect all interconnections between the components. Except as stated otherwise herein, tile processor 401 includes the components of a conventional processor (including, for example, power supplies), interconnected in the manner of a conventional processor as is known in the art. Instead of using conventional instruction memory and instruction fetch logic, tile processor 401 uses instructions that are fetched by a control module and distributed using an instruction pipeline composed of serial instruction buffer, or I-Buffer, registers 400 that couple all tile processors to the same sequence of instructions.

[0054] Instructions received in I-Buffer 400 are decoded by decode logic 402, and operations are performed on the contents of registers in banked register-file 408 by functional units 406, using loads and stores to fetch operands and write results into partitioned data memory 10 (DMEM). Particularly novel features of the tile processor include the region state logic 404, the register-file banking mechanism 408, the data-memory partitioning mechanism 410, remote access logic 412, tile interconnect network 414, and combinations of these. Network 14 is not shown as a discrete hardware block because it represents a fully connected network that couples all tile processors to the DMEM of all other tile processors. The remote access logic 412 of each tile processor couples to local access interconnect 416, which routes requests from any of the four tile processors to any of the others in a single cycle. The remote access logic 418 concurrently determines whether any request is not directed to a processor in the local group, and presents any such request to non-local tile interconnect 420, which couples this non-local request to the ultimate destination. Local access interconnect 416, remote access logic 418, and non-local tile interconnect 420 are specific levels of interconnect network 414.

[0055] Each datapath ("tile path") can access shared context by executing a load instruction that targets a memory in another tile path (or a different region of memory in the same tile path). This load is implemented in a way that ensures that the targeted data has been computed, normally without adding cycles to the instruction.

[0056] Figure 5 shows a histogram of the dataflow latency for signal traffic between tile paths in a first tile processor implementation embodiment. The round-trip latency is shown on the horizontal axis (cycles from the load request to the data response), and the number of accesses with the given latency is on the vertical axis. (There are two peaks in the histogram, because subsampling operations occur over large spans of data, and require more relatively remote communication.) Almost ail requests are satisfied within 12 cycles, including synchronization. The tile paths multi-task across positions, in this case 4 positions, executing the same sequence of instructions 4 times. So, for example, a sequence of 4 instructions, at 3 other positions, provides adequate time to receive a response before it is required by the next sequence of instructions.

[0057] In addition to this low-overhead movement of data, the tile array has two further significant advantages in the dataflow implementation compared to conventional solutions. First, the data at each level of the network remains in place in the shared memory, and doesn't have to be communicated from one layer to the next. Conventional solutions require on the order of 35,000,000,000 data transfers of signal data to computing elements, as can be seen by extension of the dependencies shown in Figure 3. In contrast, the tile array requires approximately 38,000,000 transfers in this embodiment (the total of the distribution in Figure 5). Input data is transferred once, all network layers are performed on this input, and then any detections are output to a table. The only data transfers required are for subsamplmg and for accessing the signal regions for the convolution. No other transfers are required for layer interconnect or transferring data between network lay ers.

[0058] Second, this ability to operate on data that remains in place is due to the fact that the tile array requires no overhead to communicate kemel data. In more conventional solutions, this kernel data has to accompany the signal data, which requires either swapping kernel data or image data into the local memories of the computing elements. Kernel data is much larger than signal data - a total of 290,000,000,000 transfers. These are required because the total storage per computing element is 311,000 memory locations for all kernel data, too large to remain in place in multiple computing elements without inefficient memory usage.

[0059] In the tile array, kernel data is in one memory l ocation, in the host memory, and is communicated with no overhead to the tile paths. A block diagram illustrating an embodiment of an instruction generation unit (IGU) for interfacing between a host processor and a tile processor is shown in Figure 6. The tasks involved in interfacing between a host processor and tile processor depend upon the nature of the program instructions to be executed. Even when a program has been specially adapted for execution by a tile processor, a control module to fetch instructions and provide them to the instruction pipeline of the tile processor with proper sequencing is needed. The IGU of Figure 6 also performs translation of custom instructions from a conventional compiler to instructions suitable for execution by the tile processor. In this way, programs written for conventional processors may be executed using the tile processor.

[0060] The IGU is implemented as a functional unit in the host's datapath. This functional unit has a typical configuration in that it has two input operands - Host dataA and Host dataB - and returns a single result - Host result. The implementation of the IGU is distributed over three pipeline stages, corresponding to the upper, middle, and lower portions of the figure: Attribute Stage 602, Decode Stage 604, and I-Buffer Stage 606. The attribute stage implements the main interface to the host processor, receiving host opcode and dataA and dataB operands, and returning an object tracker result, where an object tracker identifies a multivalued vector generated by operation of the tile processors. This stage also assembles information required by the decode stage to convert the custom instructions from the host into tile-path instructions. The decode stage of the IGU receives instruction and attribute information from the attribute stage, and handles allocation and de-allocation of registers using register allocation flags and a register allocation queue. The decode stage also forms the instruction for the specialized processor and passes the instruction to the instruction buffer stage.

[0061] The I-buffer stage of the IGU includes scalar registers and a scalar functional unit for receiving scalar data from the specialized processor, operating on scalar data with other scalar operands provided by the host processor, and storing scalar results. The IGU is connected to the host data memory through scalar functional unit 608. The I-buffer stage also includes an optimization queue and an instruction replay buffer for managing execution of instructions by the specialized processor. In an embodiment having a tile array as the specialized processor, the I- buffer stage implements the instruction fetching and sequencing operations of a "master processor" described in U.S. Patent No. 9,183,614. The instruction generation unit for the tile processor is described further in U.S. Patent Application No. 15/054, 1 18, entitled "Hardware Instruction Generation Unit for Specialized Processors," filed February 25, 2016, which application is incorporated by reference herein in its entirety and for all purposes.

[0062] For implementation of a CNN, kernel data consists of nothing but constant values, which vary depending on the class of objects being detected, but which do not vary for a given set of detections. Consequently, kernel data are part of the host program, stored as constants in host memor ', and are provided directly on the "Host dataB" input port (used for immediate data). This data flows directly through the instruction pipeline ("Vector 1-Pipe"), and is applied across all contexts with no communication or synchronization overhead. CNN Optimization - Data Reorganization

[0063] The dataflow capability of the tile array enables a unique optimization that adds some amount of dataflow overhead for a large increase in performance. The baseline implementation discussed so far, and having the latency results shown in Figure 5 above, is based on a direct mapping of the example algorithm from the reference code described above to the tile-based programming model. This includes directly subsampiing the inputs to layers 1 and 2, as illustrated by Figure 7. There are various forms of subsampiing, but this form simply performs convolutions on regions defined by every other input signal and on every other scan-line to form input to the convolution. Figure 7 includes a source image 700, which could more generally be any two-dimensional data array. A convolution window 702 is used to perform a convolution at a selected pixel (or array element) for performing the convolution. For window 702, the selected pixel is pixel 704 at position 0,0. In the embodiment of Figure 7, each pixel having even numbers for both row index v and column index x is a selected pixel for the convolution. The set of these selected pixels for source image 700 is shown in array 706.

[0064] The convolution itself uses contiguous signal values, as shown by the shaded region of the input image within convolution window 702, but because the positions of the convolution regions are subsampled by a factor of two in both layers 1 and 2, the vector width at the output of each of these layers is reduced by a factor of two, as illustrated by- Figure 8. Figure 8 illustrates operation of the convolutions in Layers 1 and 2 of the example CNN, from the standpoint of width of the row of elements available for processing at each stage. Within layer 1 , row stack 802 represents incoming image data stored in the processor (in this case, in the data memories of the tile processors). Because the convolution in the example CNN is a 6x6 convolution, six input rows, from y to y+5, are needed to perform a first Layer 1 convolution. In an embodiment, the CNN processing is done on a continuous basis on a horizontal slice of the source image, storing as many rows at a time as are needed to perform the convolutions. In such an embodiment, when upper rows of the stored image data are no longer needed, they may be overwritten by new rows of image data. Similarly, signal data resulting from a convolution may also be retained as a horizontal slice with a number of rows needed to perform the next layer of convolutions.

[0065] Row stack 804 in Figure 8 illustrates, from the standpoint of vector width, the fraction of the image data pixels that are selected pixels for the layer 1 convolutions. When the layer 1 convolutions are earned out on selected pixels in row y of layer 1, the resulting signal values become input row 806 (line y) in layer 2. Spaces for subsequent input rows in layer 2 are shown below row 806; these rows are generated when sufficient input data is received in layer 1 to perform convolutions starting on additional rows. Because in the embodiment of Figure 8 layer 2 also subsamples by a factor of 2, row 808, representing the fraction of input line y pixels that are selected pixels for the layer 2 convolution, is half as wide as row 806.

[0066] An illustration of data storage i tile processor data memories when performing a convolution with subsampling such as that described above is shown in Figure 9. The columns in Figure 9 represent four data memories 902, 904, 906 and 908. These are similar to data memories 410 of the tile processor array of Figure 4, but the surrounding tile processors and the interconnections between them are not shown in Figure 9. In the embodiment of Figure 9, the instruction pipeline connecting the data processors moves from left to right, so tha data memor ' 902 is in the data processor closest to the beginning of the instruction pipeline. Each of the data memories is partitioned into four memory regions, such as regions 910, 912, 914 and 916 of data memory 902. Along the left side of each of the memory regions of Figure 9 is a column of image data, denoted with "IN" at the top, and referenced by y,x position i the source image. The way that image data, or other two- dimensional array data, is stored in tile processors is by mapping pixels or elements at each horizontal position to successive memory regions while moving horizontally across the image. Therefore, the pixels in region 910, the first region of first processor 902, have an x index of 0, while pixels in the next region, 912, have an x index of 1, and so on throughout the group of data memories, moving from the region at the bottom of one memory to the region at the top of the next. In the embodiment of Figure 9, the source image is 16 pixels wide, so that x ranges from 0 to 15. Other tile processor arrays may of course have more data processors, and data memories may also he partitioned into a greater number of regions, though the number of regions should be a power of two.

[0067] In addition to source image data, each of the data memories in Figure 9 stores signal data resulting from the convolutions performed. These output elements may be referred to as feature map pixels herein, or as output elements for more generalized array processing operations. For the CNN implementation example described in this disclosure, there are 6 layer 1 feature maps, resulting in six layer 1 convolutions per selected pixel, and six resulting signal values. In the embodiment of Figure 9, the notation s ¹¹ refers to a signal output from layer 1 , feature map 1, while S ²² denotes an output from layer 1, feature map 2, As noted in Figure 9, signal outputs from the layer 2 convolution are also stored in the data memories. In an embodiment for which the image pixel data shown is the first data received from a source image, there have not been enough image rows received to produce any layer 2 convolution outputs.

[0068] As shown in Figure 9, six rows of image data have been stored in each of the memory regions, and layer 1 convolutions have been performed for the selected pixels on the top row of the stored horizontal image slice, in this embodiment, the instructions to the tile processors have caused first tile processor 902 to perform convolutions starting at the first four selected pixels, those for ay index of 0 and x indices of 0, 2, 4 and 6. The signal data from these convolutions is stored sequentially in the 4 regions of tile processor 902, This operation continues across the tile processors until the processors '"run out" of selected pixels at x=10. Because the convolution requires a window of 6 pixels in each direction, the 10 ^tB horizontal pixel is the last one for which a convolution can be performed for this image, and the 1 l ^lh through 15 ^th regions have "apr" designations to note that they are in the "apron" and would not have signal data even in the absence of subsampling. Because the convolutions require the five pixels to the right of the subsampled locations, tile processors 906 and 908 did not participate in the convolutions. In a more realistic scenario having a wider source image using more tile processors, the apron effect at the edge of the image would be minor. The loss of tile processor activity from a subsampling factor of two would amount to nearly half of the av ailable processors in such a scenario, however.

[0069] Data processors in a tile processor are designed to work in parallel; they execute the same instructions, with an offset of one clock cycle between each adjacent processor. Since convolution operations are performed in parallel across the entire vector, the reduction in vector lengths shown in Figures 8 and 9 directly reduces the available parallelism by a factor of two at layer 2 and by another factor of two at layers 3 and 4. This impacts performance more than a factor of two, because layers 3 and 4 perform more total operations - a total of 640 convolutions per vector in layer 3 and 80 or 640 in layer 4 (depending on whether an object is detected), in contrast to 6 convolutions in layer 1 and 60 in layer 2.

[0070] The convolution operation is the same at each position, and in the tiled

implementation is performed on data that is stationary in the data memory. There is no data communication required to interconnect or to communicate signal data between layers. For this reason, it is advantageous to reorganize subsampied vectors from multiple lines to appear within a single vector that is wider than the subsampied line. This adds some overhead for data reorganization, but permits the large number of convolutions in layers 2-4 to be performed for each reorganization operation.

[0071] In the embodiment of Figure 10, the data in layer 1 is reorganized so that the vector organization in the vertical direction permits the vertical convolution to be done in parallel on the six lines v through y+.5 and lines y+2 through y+ ^" /. This results in two adjacent output lines appearing within the same output vector. Within layer 2, a similar operation is performed, resulting in layer 2 output that has four adjacent lines appearing within the same output vector. Row stack 1002 of Figure 10 is similar to stack 802 of Figure 8, except that stack 1002 includes 8 image lines instead of 6. In order to do convolutions for two rows, line j and line y+2, during one tile processor iteration, the convolutions are delayed until two more lines are received so that there is enough data to perform the line y+2 convolutions. Row stack 1004 represents the selected pixels from both line y and line y+2; these are performed in one tile processor array iteration so that twice as many convolutions are done in parallel during the iteration. It is noted that the image data is not actually mo v ed from one tile processor region to another to effect this reorganization at level 1. Instead, the tile processor array is programmed so that the processors on one side of the array perform convolutions on the selected pixels in row y, while the processors on the other side perform convolutions on the selected pixels in row y+2. After the iteration in which the convolutions for the selected pixels along lines y and y+2 are performed, the next iteration can start four lines lower, at the row combining lines y+ 4 and y+6.

[0072] Figure 1 1 illustrates an example of data storage in tile processor memories when implementing the layer 1 reorganizatio shown in Figure 10. Figure 11 depicts the same array of tile processor data memories shown in Figure 9, but in the embodiment of Figure 11 the tile processors are programmed to perform the layer 1 convolutions using selected pixels along line y for the results stored in regions 1102 through 1 1 12, and using selected pixels along Ime y+2 for the results stored in regions 1114 through 1124. Each of the memory regions includes 8 lines of image data rather than 6, and the first group of memory regions has signal data corresponding to the y=0 row of the source image, while the second group of memory regions has signal data corresponding to the y=2 row. On the left sides of the memory regions indices vi are shown for designating the input rows to layer 1 (in the source image), and on the right sides of the memory regions indices y ₂ are shown for designating the input rows to l ayer 2 (in each of the l ayer 1 output feature maps). Because of the subsampling by a factor of two, the Vj+2 row in layer 1 becomes the y ₂ +1 row in layer 2.

[0073] To understand how this reorganization is done, it is useful to first understand how the data is subsampled for the baseline implementation, without reorganization. This is illustrated in Figure 12. The horizontal convolution is performed across spans 1202 of 6 pixels ("per-column iteration"): for parallel operation on vectors, pixels are extracted from the input by subsampling with offsets of 0-5 from the subsampled positions. The figure highlights ("x") the pixels selected for the third subsampled position in the first two iterations of the horizontal convolution. The vertical convolution is accomplished by repeating the horizontal iteration across each of the 6 lines y+0 through y+5. Note that multiple convolutions (six in this example), using multiple kernels, are applied to the same subsampled data,

[0074] To double the size of the subsampled vector, as illustrated in Figure 13, a similar operation is performed on two horizontal lines, at ' and>'+2, with the second subsampled line concatenated at the end of the vector for the first subsampled line. The class library permits this to be accomplished in a single statement using a range mask for the assignment. This enables the horizontal convolutions to be performed on two horizontal lines at the same time (both lines use the same kernels). This approximately doubles the performance, at the cost of the setup time to do the concatenation. Since multiple kernels are convolved for a single vector reorganization, most of the potential performance benefit is realized.

[0075] As shown in Figure 1 0, performing the convolution on the reorganized data in layer 1 results i two adjacent output lines appearing within a single vector at the input of layer 2. For example, row 1006 of Figure 10 concatenates line y of layer 2 and line y+1 of layer 2. This organization is not convenient for use within layer 2, because adjacent lines should preferably appear at the same positions vertically - instead, this organization has every other line adjacent in the vertical direction. However, a better organization can be formed by shuffling the input data, after subsampling, to form input to the layer 2 convolution. [0076] This shuffling operation is illustrated in Figure 14. Unlike the layer 1

reorganization at the top of Figure 10, the shuffling of Figure 14 is an actual movement of layer 1 signal data from one tile processor memory region to another. The idea is to get the image data for the next convolution arranged so that pixels intended to be adjacent to one another vertically are stored in the same memory region. Subsampling permits 4 horizontal convolution lines to be placed in approximately the same vector width (somewhat smaller because the convolution cannot be done at the right boundary, and a few positions don't appear in the output). To accomplish this, 4 vertical lines are subsampled and concatenated within the same vector: from the left-hand side of the vector for even lines, and from the right-hand side for odd lines. It should be understood that this operation applies to all horizontal convolutions {.v 0 through v .5) and all vertical convolutions (y+0 though JH- J). However, this reorganization applies to sixteen convolutions within layer 2, so again there is a net gain despite the overhead of reorganization.

[0077] A similar reorganization is performed in layer 3 to position the input so that is it more amenable to the convolution operation (in this case 5x5). However, layer 3 doesn't use subsampling in this neural network example, so this is a simple rotation of the input vector so that successive horizontal lines are adjacent in the vertical direction, as illustrated by Figure 15. As with other layers, this results in output for successive lines appearing in a single vector, in 4 adjacent subvectors of the output. This organization can be used directly in layer 4 of the reference CNN code for detection and classification without requiring further reorganization.

[0078] This embodiment of an optimized CNN implementation using the data

reorganization and shuffling described above executes in 10,200,000 cycles, about 3.1 times the performance of the baseline tile processor implementation described above (32,000,000 cycles) and about 137 times the performance of the prior-art implementation mentioned above (1 ,400,000,000 cycles). Figure 16 shows the latency histogram of this implementation. Data reorganization has added about 21 ,000,000 transfers to the baseline implementation, but the dataflow implementation of the tile array supports these transfers with very little impact to the latency profile, a key advantage to enabling the data reorganization that makes this optimization possible.

[0079] The versions of the tiled CNN implementation presented so far all require relatively large spans of data movement, either for subsampling or for concatenating vectors into larger ones. This can be avoided with another style of creating large vectors, illustrated in Figure 17. Instead of concatenating vectors, elements of vectors from different lines are interleaved, so that elements from different lines alternate in positions of the input to the convolution. The outputs of the convolution are also in alternate positions. As in the case of the layer 1 reorganization shown in Figure 1 1 , this interleaving at layer 1 is accomplished by the way the tile processors fetch the data for the convolutions.

[0080] This interleaving technique has the advantage that subsarapling requires only a small movement of data elements, because these elements are moved into a nearby position instead of across roughly half the vector width. It also doesn't require a large movement of data to concatenate vectors. It does require input shuffling similar to that shown in Figure 14 and Figure 1 , but this is simply a different form of input indexing. Figure 18 shows this shuffling for layer 2. Other layers use a similar style - this implies that objects are detected in a different order in layer 4 compared to previous cases, but this doesn ^' t affect correctness.

[0081] This interleaved embodiment of the tested CNN image recognition example completes in 7,170,000 cycles, about 4.5 times the baseline case, and 19.5 times the prior-art performance. The data-memory requirements are also smaller: the previous optimized version uses 256 registers and 205 memory locations (include 89 locations for spilled registers); the dataflow-optimized version uses 208 registers (with no spills) and 1 00 memory locations (for shared data only).

[0082] Figure 19 illustrates the benefit of dataflow optimization. The distribution of latency is much tighter, with very few accesses above 7 cycles and no second peak due to accesses over larger spans of the vectors. The total number of accesses is the smallest of all shown so far. The total number of transfers is 34,300,000 compared to 55,100,000 for the previous optimized case. It is also smaller than the 37,600,000 transfers required in the baseline case, since fewer iterations are performed to process an image frame.

[0083] The description provided herein is meant to be illustrative of the principles and embodiments of the present invention. Numerous variations and modifications will become apparent to those skilled in the art once the above disclosure is fully appreciated. It is intended that any claims be interpreted to embrace all such variations and modifications.