Patent Description:
Machine learning is the science of inducing computing systems to act without being explicitly programmed. Classical machine learning includes various clustering and classification techniques, including K-means clustering, linear and logistic regressions, stochastic gradient decent, association rule learning, and the like. Deep learning is a newer frontier in machine learning. Deep learning is a class of machine learning algorithms that uses multiple layers of nonlinear processing units for feature extraction and transformation. Deep learning algorithms can be unsupervised (e.g., pattern analysis) or supervised (e.g., classification). The deep learning algorithm can be implemented using layers of an artificial neural network (ANN) (referred to herein as a "neural network").

In general, a neural network is a collection of nodes (i.e., the "neurons") that are connected in a graph. A node in a neural network computes a sum of weighted inputs and adds an optional bias to the sum. The output of the node is a function of the final sum (referred to as an "activation function"). Example activation functions include the sigmoid function, the hyperbolic tangent (tanh) function, the Rectified Linear Unit (ReLU) function, and the identity function. Neural network models are often organized into layers of nodes, which define a specific topology, and corresponding weights and biases. The weights and biases are referred to as network parameters.

In general, a neural network includes an input layer and an output layer and can optionally include one or more hidden layers between the input and output layers. A neural network used in deep learning applications typically includes many hidden layers, which gives rise to the term deep neural network (DNN). The layers of a neural network can be densely connected (e.g., each node in a layer is fully connected to all nodes in a previous layer) or sparsely connected (e.g., each node in a layer is connected to only a portion of the nodes in a previous layer). A convolutional neural network (CNN) is a type of DNN that includes one or more sparsely connected layers, referred to as convolutional layers. A CNN is well-suited for processing image or video data. Other types of DNNs include recurrent neural network (RNNs), which are well-suited for processing speech and text data.

A modern field programmable gate array (FPGA) provides millions of look-up tables and thousands of configurable logic blocks (CLB), digital signal processing (DSP) and random access memory blocks (BRAM) that can be utilized to create massively parallel hardware systems. Existing FPGA systems are configured using either a hardware description language (HDL) or program code (e.g., C or C++) which is scheduled using a high level synthesis (HLS) tool.

In the HDL approach, all processes are scheduled manually with very complex state machines and data management logic. However, this process is time consuming for large scale FPGA systems. In a single thread software function, the complexity of scheduling thousands of processes grows exponentially and in some cases the scheduling is unable to converge.

<CIT> discloses a method and an apparatus for implementing layers on a convolutional neural network accelerator. Herein, one or more processing elements are utilized to implement a standard convolution layer. A computer system includes a processor for processing data signals. The processor is coupled to a bus for transmitting data signals between the processor and other components such as a memory of the computer system. The one or more processing elements are utilized to implement a fully connected layer in response to a change in data flow.

<NPL> discloses techniques for compiling and implementing convolutional neural networks on systolic arrays.

So that the manner in which the above recited features can be understood in detail, a more particular description, briefly summarized above, may be had by reference to example implementations, some of which are illustrated in the appended drawings. It is to be noted, however, that the appended drawings illustrate only typical example implementations and are therefore not to be considered limiting of its scope.

Various features are described hereinafter with reference to the figures. It should be noted that the figures may or may not be drawn to scale and that the elements of similar structures or functions are represented by like reference numerals throughout the figures. It should be noted that the figures are only intended to facilitate the description of the features. They are not intended as an exhaustive description of the description or as a limitation on the scope of the claims. In addition, an illustrated example need not have all the aspects or advantages shown. An aspect or an advantage described in conjunction with a particular example is not necessarily limited to that example and can be practiced in any other examples even if not so illustrated, or if not so explicitly described.

Embodiments herein describe techniques for statically scheduling a neural network implemented in a massively parallel hardware system. The neural network may be scheduled using three different levels referred to herein as an upper level, an intermediate level, and a lower level. In one embodiment, the upper level includes a hardware or software model of the layers in the neural network that establishes a sequential order of functions (e.g., convolution, max pooling/max pool, rectified linear units (ReLU), and scaling functions) that operate concurrently in the hardware system. The model may include data channels that interconnect the different functions in the layer.

In the intermediate level, identical processes in the layers defined in the upper level are connected to form a systolic array or mesh of processing elements and balanced data flow channels are used to minimize latency. The systolic arrays are designed using source code (e.g., C or C++) which is parallelized by a HLS compiler when converting the source code into register transfer level (RTL) code which is then used to configure programmable hardware such as an FPGA. In the lower level, the HLS compiler assigns the operations performed by the processing elements in the systolic array to different portions of the programmable hardware. For example, if the processing element is implemented using different digital signal processing (DSP) blocks, the different operations performed by the processing element (e.g., read, write, multiple, add, etc.) can be performed in parallel. By dividing the scheduling of the neural network into different levels, a compiler can generate a parallelized pipeline such that the hardware elements in the system can operate concurrently.

<FIG> illustrates a multi-layer neural network <NUM>.

As used herein, a neural network <NUM> is a computational module used in machine learning and is based on a large collection of connected units called artificial neurons where connections between the neurons carry an activation signal of varying strength. The neural network <NUM> can be trained from examples rather than being explicitly programmed. In one embodiment, the neurons in the neural network <NUM> are connected in layers - e.g., Layers <NUM>, <NUM>, <NUM>, etc. - where data travels from the first layer - e.g., Layer <NUM> - to the last layer - e.g., Layer <NUM>. Although seven layers are shown in <FIG>, the neural network <NUM> can include hundreds or thousands of different layers.

Neural networks can perform any number of tasks such as computer vision, feature detection, speech recognition, and the like. In <FIG>, the neural network <NUM> detects features in a digital image such as classifying the objects in the image, performing facial recognition, identifying text, etc. To do so, image data <NUM> is fed into the first layer in the neural network which performs a corresponding function, in this example, a 10x10 convolution on the image data <NUM>. The results of that function is then passed to the next layer - e.g., Layer <NUM> - which performs its function before passing the processed image data to the next level, and so forth. After being processed by the layers, the data is received at an image classifier <NUM> which can detect features in the image data.

The layers are defined in a sequential order such that Layer <NUM> is performed before Layer <NUM>, Layer <NUM> is performed before Layer <NUM>, and so forth. Thus, there exists a data dependency between the lower layers and the upper layer(s). Although Layer <NUM> waits to receive data from Layer <NUM>, in one embodiment, the neural network <NUM> can be parallelized such that each layer can operate concurrently. That is, during each clock cycle, the layers can receive new data and output processed data. For example, during each clock cycle, new image data <NUM> can be provided to Layer <NUM>. For simplicity, assume that during each clock cycle a part of new image is provided to Layer <NUM> and each layer can output processed data for image data that was received in the previous clock cycle. If the layers are implemented in hardware to form a parallelized pipeline, after seven clock cycles, each of the layers operates concurrently to process the part of image data. The "part of image data" can be an entire image, a set of pixels of one image, a batch of images, or any amount of data that each layer can process concurrently. Thus, implementing the layers in hardware to form a parallel pipeline can vastly increase the throughput of the neural network when compared to operating the layers one at a time. The timing benefits of scheduling the layers in a massively parallel hardware system improve further as the number of layers in the neural network <NUM> increases.

<FIG> is a system <NUM> for establishing a neural network pipeline <NUM> in an FPGA <NUM>. In addition to the FPGA <NUM>, the system <NUM> includes a computing device <NUM> which configures programmable logic <NUM> in the FPGA <NUM>. For example, the computing device <NUM> can be a laptop, desktop, or server. The computing device <NUM> includes a processor <NUM> which represents any number of processing elements which each can contain any number of processing cores. The device <NUM> also includes a memory <NUM> which can have volatile or non-volatile memory elements.

The memory <NUM> includes a compiler <NUM> which is a software application (e.g., an HLS compiler) that converts source code such as C or C++ into RTL code which configures the programmable logic <NUM> to establish the neural network pipeline <NUM>. When compiling the source code, the compiler <NUM> uses a scheduler <NUM> to generate RTL which statically schedules the neural network pipeline <NUM> such that the different hardware elements forming the pipeline <NUM> (e.g., DSP blocks <NUM> or CLBs <NUM>) can operate concurrently. The static schedule is fixed so that the order in which the hardware elements execute does not change during runtime. The scheduler <NUM> receives or generates an upper level, an intermediate level, and lower level which the compiler <NUM> uses to generate statically scheduled RTL code for establishing the neural network pipeline <NUM>. The upper level of the schedule is a layer design which includes a hardware or software model of a layer (or multiple layers) in the neural network. The layer design can be defined by parameterizations of the layer instructions <NUM> which can be a sequential order of a plurality of functions in the layer that can operate concurrently such as convolution, max pooling, ReLU, and scaling functions.

The intermediate level of the schedule is a systolic array <NUM> which includes a plurality of processing elements (PEs) that are interconnected using data channels. In one embodiment, each of the PEs includes one or more of the DSP blocks <NUM> or one or more CLBs <NUM> (or a combination of both) in the FPGA. The DSP blocks <NUM> are specialized logic blocks that can perform DSP at faster rates than CLBs <NUM> and lower system power consumption. Moreover, adding the DSP blocks <NUM> can reduce the overall size of the FPGA since achieving the same DSP performance using CLBs <NUM> would result in larger integrated circuits. The DSP blocks <NUM> include adders, pre-adders, sub-tractors, accumulators, summation units, and the like.

The systolic array <NUM> defines how the DSP blocks <NUM> or CLB <NUM> forming the PEs are interconnected in order to perform a function defined in the layer. For example, to perform convolution, the systolic array <NUM> may include a plurality of interconnected PEs that in turn each includes multiple multiply-accumulator (MAC) blocks formed from the programmable DSP blocks <NUM> in the FPGA <NUM>. In another embodiment, when implementing the max pooling or ReLU functions, the PEs may include CLBs <NUM> which perform the corresponding operations. Like the functions defined in the parameterization of the layer instructions <NUM>, the compiler <NUM> can generate RTL code corresponding to the systolic array <NUM> such that the PEs can operate concurrently.

The lower level of the schedule is a PE design <NUM> which defines the operations performed by the PEs in the systolic array <NUM>. Continuing the example above, if the PEs include MAC blocks, the PE design <NUM> can list the read, write, multiple, and add operations performed by the these blocks. Of course, MAC blocks are just one example of implementing a PE and other operations may be performed by PEs that are part of a max pooling unit or ReLU.

The FPGA <NUM> includes the programmable logic <NUM> and memory <NUM>. The programmable logic <NUM> can include an array of programmable logic blocks and a hierarchy of reconfigurable interconnects that enable the logic blocks to be communicatively coupled. One example of the programmable logic blocks includes the DSP blocks <NUM> which are useful when performing convolutions or fully connected layers in the neural network pipeline <NUM>. The programmable logic blocks can also include one or more CLBs <NUM> which may be used when performing scaling or max pool functions. In one embodiment, the neural network pipeline <NUM> includes programmable logic <NUM> for converting received image data into a 2D matrix (referred to as im2col) so that matrix multiplication can be used to perform convolution.

Although an FPGA <NUM> is shown, the scheduling techniques described herein can be performed to implement the neural network pipeline <NUM> on other types of non-programmable hardware system such as a graphics processor unit (GPU) or an application specific integrated circuit (ASIC) specially designed to implement a neural network. That is, when designing or implementing a neural network on these systems, the parameterizations of the layer instructions <NUM>, systolic array <NUM>, and the PE design <NUM> can be used such that the hardware elements are statically scheduled such that the hardware elements can operate concurrently.

<FIG> is a flowchart of a method <NUM> for scheduling a neural network pipeline. At block <NUM>, the scheduler receives a model for the layers in a neural network establishing a sequential order of a plurality of functions that operate concurrently in the FPGA. The model is a layer design as described in <FIG> which includes parameterizations of the layer instructions <NUM>. Further, the model can be a software or a hardware model that represents the complete neural network as implemented in the massively parallel hardware system - e.g., an FPGA.

In one embodiment, the model is provided to the scheduler by a user. For example, the user may design the model according to the type of neural network the user desires to implement on the FPGA. For example, different neural networks can have different layers and functions within those layers. As mentioned above, neural networks can be designed to perform different tasks such as feature detection in digital images, audio processing, or processing text. Non-limiting examples of neural networks include CNN, RNN, long short-term memory (LSTM) neural networks, and neural networks that use feature base learning or supervised/unsupervised learning. Moreover, the structure of the same type of neural networks can vary widely. For example, some CNNs can include tens of layers while others can include hundreds of layers where each of the layers can be configured differently - e.g., a layer that performs 3x3 convolution, a layer that performs 11x11 convolution, a fully connected (FC) layer, a pooling layer, etc..

The model defines the upper level schedule for each of the layers in the neural network. <FIG> illustrates a hardware model of an architecture description <NUM> of the layers in a neural network. The architecture description <NUM> includes a layer scheduler <NUM>, a convolution unit <NUM>, a max-pooling unit <NUM>, a multiplexer (mux) <NUM>, a ReLU <NUM>, a mux <NUM>, a scaling unit <NUM>, and a mux <NUM> for performing feature detection in an image which are referred to generally as pipelined functions. The model of the architecture description <NUM> defines a sequential order of the pipelined functions when executing one or more layers of the neural network. In one embodiment, the convolution unit <NUM> performs matrix multiplication using a matrix multiplier and weights received image data using any number of weights (or kernels). In one embodiment, the max-pooling unit <NUM> amplifies features in the image so the features are not lost when the image is scaled later in the pipeline. The ReLU <NUM> is a type of activation unit or ramp function which, in one embodiment, is defined as f(x) = max(<NUM>,x) where x is the output from a neuron. The scaling unit <NUM> can adjust the values of the processed data to minimize numerical errors due to quantization.

The layer scheduler <NUM> determines where the data flow starts. For example, for some layers, the input image data may first be sent to the convolution unit <NUM>. In other layers in the neural network, the image data bypasses the convolution unit <NUM> and instead is sent by the layer scheduler <NUM> to the max-pooling unit <NUM> or the scaling unit <NUM>. Furthermore, the manner in which the data propagates through the architecture description <NUM> can vary depending on the layer. For example, for a first layer, after the image data is processed by the convolution unit <NUM>, the mux <NUM> may forward the processed data directly to the ReLU <NUM> thereby bypassing the max-pooling unit <NUM>. Alternatively, in a second layer, the data outputted by the convolution unit <NUM> is first processed by the max-pooling unit <NUM> before the mux <NUM> transmits the data to the ReLU <NUM>. In this manner, the multiplexers <NUM>, <NUM>, and <NUM> can alter how the image data flows through the architecture description <NUM> according to control signals provided by, e.g., the layer scheduler <NUM>.

The architecture description <NUM> is a block diagram illustrating the complete system needed to execute a neural network. Put differently, the architecture description <NUM> represents, at an abstracted level, the hardware blocks needed in an FPGA (or other hardware system) to execute the neural network and its corresponding layers. Although not shown, the architecture description <NUM> may include dataflow channels inserted between different blocks to allow the blocks to execute concurrently. The dataflow channels can be properly sized to minimize the overall system latency. Moreover, the architecture description <NUM> illustrated in <FIG> can be software defined meaning the user simply expresses a sequence of scalar operations (represented here as the different blocks) and adds parallelization pragmas. That is, the user can define the sequence at which the blocks are executed without scheduling these blocks (i.e., without defining when the blocks should be executed). The parallelization pragma is a directive pragma which specifies to the compiler that the defined blocks should be scheduled to operate in parallel. By converting the hardware model shown in <FIG> into source code and using the parallelization pragma, the compiler can create an optimal static schedule for executing architecture description <NUM>. The resulting static schedule enables the different blocks shown in <FIG> to execute concurrently.

Rather than expressing the architecture description <NUM> as a hardware model, the architecture description <NUM> can be represented as a software model. On example of a C++ implementation of a software model for the architecture description <NUM> is provided in Table <NUM>.

The source code in Table <NUM> is untimed functional code for a neural network with "cnnLayers" number of layers. Further, the code is ordered in a defined sequence but is not explicitly scheduled. In this embodiment, the HLS DATAFLOW is a parallelization pragma for the dataflow. This pragma permits the neural network designer to use a RTL concept by instantiating parallel blocks without having to schedule the blocks. After compiled into RTL, the different functions in the code (e.g., Conv, MaxPool, Relu, and Scale) operate concurrently. Although not shown, the code may include FIFOs (or other buffers) which interconnect the different functions.

The resulting compiled RTL generated from the code shown in Table <NUM> contains a statistically scheduled state machine for all layers of the neural network. Within each layer, all the blocks (or functions) run concurrently. The hardware model illustrated in <FIG> and the software code in Table <NUM> illustrate the ease with which a designer can express hardware behavior in a high level software defined system.

Returning to method <NUM>, at block <NUM> the scheduler receives a systolic array for executing identical processes in the neural network layers. In one embodiment, the designer provides software code which defines the configuration of the systolic array which the scheduler (or the compiler) then parallelizes such that the different operations in the systolic array execute concurrently in hardware.

In one embodiment, the systolic array is a two dimensional array which simplifies overall scheduling as well as maintains consistent data flow to make placing and routing in the hardware system easier. The systolic array includes a plurality of PEs that is interconnected in order to execute concurrently. For example, each PE can be a multiple-accumulator (MAC) block. However, the PE can vary depending on the processes performed by the systolic array. For example, a systolic array used to perform convolution may have MAC blocks while a systolic array used to perform pooling, ReLU, or scaling have different PEs. By arranging the PEs in a multi-dimensional array, each of the PEs can receive an exponentially larger bandwidth data path. The two dimensional mesh shown here provides a compromise between bandwidth and difficulty of placement and routing.

<FIG> illustrates a systolic array <NUM> in a neural network. In <FIG>, the systolic array <NUM> is configured as a convolution block. In one embodiment, the convolution unit <NUM> illustrated in <FIG> is formed from one or more of the systolic arrays <NUM> shown in <FIG>. The other blocks in <FIG> - i.e., the max-pooling unit <NUM>, ReLU <NUM>, and the scaling unit <NUM> - may be formed using a same systolic array <NUM> or different systolic arrays.

In <FIG>, the two dimensional systolic array <NUM> includes a plurality of PEs that are interconnected to form a 4x4 matrix. In one embodiment, the scheduler forms the systolic array <NUM> using software code provided by the user or designer. In this example, the systolic array <NUM> can be derived from a for loop (and optional unroll pragmas for the HLS compiler) which performs the multiplication of AxB for N number of times. The scheduler then generates the systolic array <NUM> illustrated in <FIG> which includes performing the matrix multiplication of matrices formed from the A and B inputs.

In this example, the four top PEs - i.e., PEs <NUM>, <NUM>, <NUM>, and <NUM> - receive data from a B operand matrix while the four leftmost PEs - i.e., PEs <NUM>, <NUM>, <NUM>, and <NUM> - receive data from an A operand matrix. In one embodiment, the scheduler generates synchronization signals which synch the PEs so that each individual PEs performs its function concurrently with the others. In one embodiment, the PEs receive input during each clock cycle and provide an output each clock cycle. The PEs may need one clock cycle to process received data or use multiple clocks cycles to process received data. In any case, the PEs can be scheduled such that during each clock cycle some operation is being performed on received data.

In one embodiment, the PEs in the array <NUM> exchange data using buffers. For example, FIFOs may be disposed at each of the locations where the PEs exchange data as indicated by the arrows. Moreover, the FIFOs can be part of data flow channels which are balanced to minimize latency. In one embodiment, the PEs are expressed as software defined stream classes.

As illustrated in <FIG>, the scheduler can receive software code that defines a systolic array (e.g., the "for loop" described above) which the scheduler can convert into the parallelized systolic array <NUM>. For example, the software definition provided by the user can include an expression that includes a single PE or core which the scheduler unpacks into the systolic array <NUM> or mesh of PEs shown in <FIG>.

Returning to <FIG>, at block <NUM> the compiler compiles high-level code into RTL code that provides a static schedule for a pipeline of the neural network. In one embodiment, the compiler uses source code corresponding to the model received at block <NUM> and the systolic array received at block <NUM> to generate the RTL code. For example, the compiler can schedule the individual blocks in the model or layer design rather than attempting to schedule the entire neural network as a whole. Referring to <FIG>, the compiler can separately schedule the convolution unit <NUM>, max-pooling unit <NUM>, ReLU <NUM>, and the scaling unit <NUM> in order to simplify the scheduling processing and increase the likelihood that the scheduling converges. That is, by scheduling the individual blocks, the compiler can schedule the hardware forming the blocks and then generate data flow channels for sharing data between the blocks when performing the upper level of the scheduling process.

When scheduling the individual blocks in the upper level, the compiler can divide the blocks into one or more systolic arrays. That is, the systolic arrays represent the intermediate level of scheduling which further subdivides the blocks in the upper level - i.e., the functional blocks in the architecture description <NUM>. The systolic arrays are used when identical processes are being performed in the functional block (such as convolution which relies on performing multiple multiplications). Put differently, because convolution can be performed using the same PEs (e.g., the same MAC blocks), these PEs can be arranged into the multi-dimensional systolic array <NUM> which operate in parallel. In contrast, in one embodiment, different processes in the blocks in the upper level are connected with data flow channels and scheduled during the lower level of scheduling without forming systolic arrays or meshes.

During the lower level of scheduling, the compiler schedules the hardware blocks forming the processes and functions in the upper and intermediate levels of the schedule. For example, the PEs forming the blocks in the architecture design shown in <FIG> and the systolic arrays can be divided into hardware elements which are then scheduled by the compiler. In one embodiment, the scheduler can pipeline the operations of the hardware elements so that these elements receive input operands and produce an output every clock cycle. By subdividing scheduling into multiple levels, the compiler and scheduler can generate hardware level code (e.g., RTL code) which configures a hardware system such that the different blocks, software functions/methods, and processing elements operate concurrently.

<FIG> illustrates a pipelined PE <NUM> in a digital signal processing block.

In this embodiment, the PE <NUM> is a MAC block <NUM> for performing convolution, but can be any hardware element or elements. In <FIG>, the MAC block <NUM> performs a floating point operation which cannot be performed in a single clock cycle. As such, an HLS compiler can divide this floating point operation into sub-operations that can each be performed in one clock cycle. Here, the floating point operation can be performed in four clock cycles by first performing a read operation <NUM>, followed by a multiple operation <NUM>, followed by an addition operation <NUM>, and a write operation <NUM>.

In the first clock cycle, the read operation <NUM> retrieves the operands A and B. In the second clock cycle, the multiply operation <NUM> multiplies the A operand with the B operand. In the third clock cycle, the addition operation <NUM> adds the result of this multiplication to the previous multiplication acting as an accumulation operation. In the fourth clock cycle, the write operation writes the result of the addition operation (e.g., output C) to a memory. In this manner, the overall operation of the MAC block <NUM> can be divided into multiple steps that can be completed during each clock cycle.

In one embodiment, to perform the operations <NUM>, <NUM>, <NUM>, and <NUM> in parallel or concurrently, the operations are performed by different hardware elements in the FPGA. That is, the read operation <NUM> may be performed by a first memory interface hardware element while the write operation <NUM> is performed by a second memory interface hardware element. As long as these hardware elements are attempting to read from and write to separate memories (i.e., different Block RAM (BRAM) elements in the FPGA are assigned to store the operands A and B and the output C), the read and write operations <NUM> and <NUM> can be performed concurrently. Similarly, the multiply operation <NUM> can be performed by a first DSP block while the addition operation <NUM> is performed by a second DSP block so that these operations can be performed concurrently.

<FIG> illustrates the status of the PE <NUM> during seven clock cycles (i.e., Cycle <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>) during which the PE <NUM> processes four chunks or packets of image data (i.e., image data 105A-D). During Cycle <NUM>, the operands A and B corresponding to image data 105A are read from memory in the FPGA. During Cycle <NUM>, the operands A and B corresponding to image data 105A are multiplied at the same time the operands A and B corresponding to image data 105B are read from memory. During Cycle <NUM>, the results of performing the multiplication on the image data 105A are added by the addition operation <NUM> at the same time the operands A and B corresponding to image data 105B are multiplied and the operands A and B corresponding to image data 105C are read from memory. By Cycle <NUM>, all of the hardware elements making up the PE <NUM> execute concurrently. In this example, at Cycle <NUM>, the results of performing the addition for the image data 105A are written into the memory of the FPGA while the results of performing the multiplication on the image data 105B are added, the operands A and B corresponding to image data 105C are multiplied, and the operands A and B corresponding to image data 105D are read from memory. As long as additional image data is available (i.e., there is more image data in the neural network pipeline that needs to be processed by the PE <NUM>), the hardware elements execute concurrently. Put differently, the compiler can schedule the hardware elements into a pipeline using the hardware elements in the FPGA such that the hardware elements operate concurrently. Because the compiler can perform a similar scheduling process for all the hardware elements in the upper, intermediate, and lower levels of the schedule, the neural network pipeline as a whole can be schedule such that the hardware elements operate concurrently.

Returning to method <NUM>, at block <NUM>, the computing device configures programmable hardware logic in the FPGA according to the RTL code generated at block <NUM>. That is, the computing device configures the FPGA such that the hardware elements selected to perform the PEs shown in <FIG> can operate concurrently. Moreover, the RTL code can define data flow channels between the hardware elements which may include buffers. Although RTL is specifically mentioned, the compiler (or a synthesis tool) could generate any kind of hardware level design which provides a static schedule when executing the neural network in a hardware system such as a GPU or ASIC.

<FIG> is a block diagram depicting a system <NUM> for implementing neural networks. The system <NUM> includes a computer system <NUM> and one or more computer systems <NUM>. The computer system <NUM> includes conventional computing components configured to execute software that provides one or more design tools <NUM>. Each computer system <NUM> executes one or more neural networks <NUM>. The neural network(s) <NUM> are implemented using applications <NUM>, acceleration libraries <NUM>, and one or more hardware accelerators <NUM>.

In an example, the hardware accelerator(s) <NUM> include programmable ICs, such as FPGAs. The acceleration libraries <NUM> provide application programming interfaces (APIs) to interface with the hardware accelerator(s) <NUM>. The acceleration libraries <NUM> can also include libraries that provide neural network functions, including predefined and optimized implementations of neural network layers and other types of neural network structures. Thus, the neural network(s) <NUM> can include both hardware portions implemented in the hardware accelerator(s) <NUM>, as well as software portions implemented in the acceleration libraries <NUM>. The applications <NUM> invoke the APIs of the acceleration libraries <NUM> to program and control the hardware accelerator(s) <NUM> to implement the neural network(s) <NUM>.

A designer interacts with the design tool(s) <NUM> to define the neural network(s) <NUM>. The design tool(s) <NUM> can generate files for programming the hardware accelerator(s) <NUM> (e.g., configuration bit streams for FPGAs), files that provide the acceleration libraries <NUM>, and files that provide the applications <NUM>. The designer can define the hardware portions of the neural network(s) <NUM> using a register transfer language (RTL) or using a programming language, such as C, C++, OpenCL, and the like, or a combination of RTL and programmable language(s). The user can define the software portions of the neural network(s) <NUM> using a programming language, such as C, C++, OpenCL, etc. The design tool(s) <NUM> compile the software-defined neural networks to generate files for programming the hardware accelerator(s) <NUM> and library files for the acceleration libraries <NUM>. The designer can make use of libraries <NUM> that provide class libraries, template libraries, and the like to assist in developing the hardware and software portions of the neural network(s) <NUM>.

A user can define the applications <NUM> using a programming language (e.g., C, C++, Python, etc.). The user can make use of neural network frameworks and libraries, such as Caffe, TensorFlow, MXNet, and the like.

<FIG> is a block diagram depicting a computing system <NUM>. The computing system <NUM> includes hardware <NUM> and software <NUM> executing on the hardware <NUM>. The hardware <NUM> includes a processing system <NUM>, system memory <NUM>, storage devices ("storage <NUM>"), and a hardware accelerator <NUM>. The software <NUM> includes an operating system (OS) <NUM>, the acceleration libraries <NUM>, and the applications <NUM>.

The processing system <NUM> includes a microprocessor <NUM>, support circuits <NUM>, and a peripheral bus <NUM>. The microprocessor <NUM> can be any type of general-purpose central processing unit (CPU), such as an x86-based processor, ARM®-based processor, or the like. The microprocessor <NUM> can include one or more cores and associated circuitry (e.g., cache memories, memory management units (MMUs), interrupt controllers, etc.). The microprocessor <NUM> is configured to execute program code that perform one or more operations described herein and which can be stored in the system memory <NUM> and/or the storage <NUM>. The support circuits <NUM> include various devices that cooperate with the microprocessor <NUM> to manage data flow between the microprocessor <NUM>, the system memory <NUM>, the storage <NUM>, the hardware accelerator <NUM>, or any other peripheral device. For example, the support circuits <NUM> can include a chipset (e.g., a north bridge, south bridge, platform host controller, etc.), voltage regulators, firmware (e.g., a BIOS), and the like. The support circuits <NUM> manage data flow between the microprocessor <NUM> and the peripheral bus <NUM>, to which various peripherals, such as the hardware accelerator <NUM>, are connected. In some examples, the microprocessor <NUM> can be a System-in-Package (SiP), System-on-Chip (SoC), or the like, which absorbs all or a substantial portion of the functionality of the chipset (e.g., north bridge, south bridge, etc.). The peripheral bus can implement an expansion bus standard, such as Peripheral Component Interconnect Express (PCIe). In the example, the processing system <NUM> is shown separate from the hardware accelerator <NUM>. In other examples discussed further below, the processing system <NUM> and the hardware accelerator <NUM> can be implemented on the same IC using a System-On-Chip (SoC).

The system memory <NUM> is a device allowing information, such as executable instructions and data, to be stored and retrieved. The system memory <NUM> can include, for example, one or more random access memory (RAM) modules, such as double-data rate (DDR) dynamic RAM (DRAM). The storage device <NUM> includes local storage devices (e.g., one or more hard disks, flash memory modules, solid state disks, and optical disks) and/or a storage interface that enables the computing system <NUM> to communicate with one or more network data storage systems. The hardware <NUM> can include various other conventional devices and peripherals of a computing system, such as graphics cards, universal serial bus (USB) interfaces, and the like.

The hardware accelerator <NUM> includes a programmable IC <NUM>, a non-volatile memory <NUM>, and RAM <NUM>. The programmable IC <NUM> can be an FPGA or the like or a SoC having an FPGA or the like. The NVM <NUM> can include any type of non-volatile memory, such as flash memory or the like. The RAM <NUM> can include DDR DRAM or the like. The programmable IC <NUM> is coupled to the NVM <NUM> and the RAM <NUM>. The programmable IC <NUM> is also coupled to the peripheral bus <NUM> of the processing system <NUM>.

The OS <NUM> can be any commodity operating system known in the art, such as such as Linux®, Microsoft Windows®, Mac OS®, or the like. The acceleration libraries <NUM> includes drivers and libraries that provide APIs for command and control of the hardware accelerator <NUM>. The applications <NUM> include software executing on the microprocessor <NUM> that invokes the APIs of the acceleration libraries <NUM> to implement neural network(s).

In operation, the programmable IC <NUM> is configured with an acceleration circuit <NUM> (e.g., a neural network acceleration circuit or kernel acceleration circuit). The acceleration circuit <NUM> generally includes a base platform 830A and a kernel 830B. For example, the acceleration circuit <NUM> can be implemented using a static region <NUM> and a programmable region <NUM>. The static region <NUM> includes support circuits <NUM> for providing an interface to the peripheral bus <NUM>, the NVM <NUM>, and the RAM <NUM>. The programmable region <NUM> can include one or more kernel circuits ("kernel(s) <NUM>"). The base platform 830A is implemented using the static region <NUM>, and the kernel 830B is implemented using the programmable region <NUM>. In another example, the base platform 830A can also be implemented using a portion of the programmable region <NUM>. Thus, in some examples, the programmable region <NUM> also includes some interface circuits. In some examples, the acceleration circuit <NUM> can include more than one programmable region <NUM>, each of which can be individually configured with kernel(s) <NUM>.

The static region <NUM> is "static" in that the circuitry thereof remains constant across reconfigurations of the programmable region <NUM> and is different from the static scheduling discussed above. In an example, the support circuits <NUM> include PCIe endpoint circuits, a direct memory access (DMA) controller, interconnects, a memory controller, a memory interface circuit (e.g., a DDR interface), decoupler circuits (to support partial reconfiguration), flash programmer, debug circuits, and the like. In some examples, the programmable region <NUM> does not include any of the support circuits <NUM>. In other examples, some support circuits are implemented in the programmable region <NUM>. In such case, the programmable region <NUM> can be referred to as an "expanded programmable region. " In either case, in one example, some support circuits <NUM> are always present in the static region <NUM>, such as the PCIe circuits and the DMA circuits.

<FIG> is a block diagram depicting an acceleration circuit <NUM>. The acceleration circuit <NUM> includes the support circuits <NUM> and a kernel <NUM>. In the example, the support circuits <NUM> include a PCIe endpoint circuit ("PCIe endpoint <NUM>"), a PCIe DMA controller <NUM>, interconnect circuits ("interconnect <NUM>"), memory controllers <NUM>, and memory interfaces <NUM>. The support circuits <NUM> can include other circuits, which are omitted for clarity (e.g., decoupler circuits, debug circuits, etc.). The PCIe endpoint <NUM> provides a physical interface to the peripheral bus <NUM>. The PCIe DMA controller <NUM> facilitates DMA operations to the RAM <NUM> and the kernel <NUM>. The interconnect <NUM> couples the PCIe DMA controller <NUM> to the memory controllers <NUM> and to the kernel <NUM>. The memory controllers <NUM> are coupled to the memory interfaces <NUM>. The memory interfaces <NUM> are coupled to the RAM <NUM>.

In operation, the acceleration libraries <NUM> can access the RAM <NUM> directly through the PCIe DMA controller <NUM>. The acceleration libraries <NUM> can also access the kernel <NUM> through the PCIe DMA controller <NUM>. The kernel <NUM> can access the RAM <NUM> through the memory controllers <NUM>. Data can be exchanged between the software <NUM> and the kernel <NUM> using DMA operations between the system memory <NUM> and the RAM <NUM>.

In the example, the kernel <NUM> uses interfaces <NUM>, <NUM>, and <NUM> to communicate with the interconnect <NUM>. In particular, these interfaces may include a first read interface <NUM>, a second read interface <NUM>, and a read/write interface <NUM>. For example, the read interface <NUM> can be used as a control interface for controlling the kernel <NUM>. The read interface <NUM> can be used to read from the RAM <NUM> through a first one of the memory interfaces <NUM>. The read/write interface <NUM> can be used to read and write from the RAM <NUM> through a second one of the memory interfaces <NUM>.

The kernel <NUM> includes an interconnect interface <NUM>, control logic <NUM>, and processing circuits <NUM>. The processing circuits <NUM> include an IM2COL circuit ("IM2COL <NUM>"), a read control circuit ("read control <NUM>"), a multiplexer <NUM>, first-in-first-out circuits ("FIFOs <NUM>"), DSP array <NUM>, a scaler circuit ("scaler <NUM>" such as a ReLU activation circuit), a max pool circuit ("max pool <NUM>"), a multiplexer <NUM>, FIFOs <NUM>, write control circuit ("write control <NUM>"), a cache <NUM>, a read control circuit ("read control <NUM>"), and FIFOs <NUM>. The interconnect interface <NUM> is coupled to the interfaces <NUM>, <NUM>, and <NUM>, the control logic <NUM>, and the processing circuits <NUM>. The interconnect interface <NUM> can include switches, clock converters, and the like to facilitate communication between the control logic <NUM> and the interface <NUM>, as well as between the processing circuits <NUM> and the interfaces <NUM> and <NUM>.

In the example, the interconnect interface <NUM> is coupled to inputs of the IM2COL circuit <NUM>, the read control circuit <NUM>, the cache <NUM>, and the write control circuit <NUM>. Outputs of the IM2COL circuit <NUM> and the read control circuit <NUM> are coupled to inputs of the multiplexer <NUM>. An output of the multiplexer <NUM> is coupled to an input of the FIFOs <NUM>. An output of the FIFOs <NUM> is coupled to a first input of the compute array <NUM>. An output of the cache <NUM> is coupled to an input of the read control circuit <NUM>. An output of the read control circuit <NUM> is coupled to an input of the FIFOs <NUM>. An output of the FIFOs <NUM> is coupled to a second input of the compute array <NUM>. An output of the compute array <NUM> is coupled to an input of the scaler <NUM>. An output of the scaler <NUM> is coupled to an input of the max pool circuit <NUM> and an input of the multiplexer <NUM>. An output of the max pool circuit <NUM> is coupled to another input of the multiplexer <NUM>. An output of the multiplexer <NUM> is coupled to an input of the FIFOs <NUM>. An output of the FIFOs <NUM> is coupled to the write control circuit <NUM>.

In operation, the compute array <NUM> performs matrix multiplication operations for implementing a neural network. The inputs of the compute array <NUM> receive input activation matrices from the FIFOs <NUM> and weight matrices from the FIFOs <NUM>. The input activation matrices can be read directly from the RAM <NUM> using the read control circuit <NUM>. Alternatively, the input activations can be read from the RAM <NUM> and processed by the IM2COL circuit <NUM> for input to the compute array <NUM>. Embodiments of the IM2COL circuit <NUM> are described below. Weight matrices can be read from the RAM <NUM> by the read control circuit <NUM> and cached in cache <NUM>. The scaler <NUM> can scale the output of the compute array <NUM>. The max pool circuit <NUM> can implement a max pooling function on the scaled output of the compute array <NUM>. In one example, the max pool circuit <NUM> is implemented using CLBs or other configurable logic. Either the output of the max pool circuit <NUM> or the scaler <NUM> can be stored in the FIFOs <NUM>. The write control circuit <NUM> writes data in the FIFOs to the RAM <NUM>. The control logic <NUM> controls the various circuits in the processing circuits <NUM>, such as the IM2COL circuit <NUM>, the read control circuit <NUM>, the multiplexers <NUM> and <NUM>, the read control circuit <NUM>, and the scaler <NUM>, the max pool circuit <NUM>, and the write control circuit <NUM>.

<FIG> is a block diagram depicting a programmable IC <NUM>. The programmable IC <NUM> includes programmable logic <NUM>, configuration logic <NUM>, and configuration memory <NUM>. The programmable IC <NUM> can be coupled to external circuits, such as the NVM <NUM>, the RAM <NUM>, and other circuits <NUM>. The programmable logic <NUM> includes logic cells <NUM>, support circuits <NUM>, and programmable interconnect <NUM>. The logic cells <NUM> include circuits that can be configured to implement general logic functions of a plurality of inputs. The support circuits <NUM> include dedicated circuits, such as transceivers, input/output blocks, digital signal processors, memories, and the like. The logic cells and the support circuits <NUM> can be interconnected using the programmable interconnect <NUM>. Information for programming the logic cells <NUM>, for setting parameters of the support circuits <NUM>, and for programming the programmable interconnect <NUM> is stored in the configuration memory <NUM> by the configuration logic <NUM>. The configuration logic <NUM> can obtain the configuration data from the nonvolatile memory <NUM> or any other source (e.g., the DRAM <NUM> or from the other circuits <NUM>). In some examples, the programmable IC <NUM> includes a processing system <NUM>. The processing system <NUM> can include microprocessor(s), memory, support circuits, IO circuits, and the like. For example, the processing system <NUM> can include circuits similar to the processing system <NUM>. In some examples, the processing system <NUM> can be used in place of the processing system <NUM>. In such case, the entire computing system <NUM> can be implemented using the programmable IC <NUM>, where the software <NUM> executes on the processing system <NUM>.

<FIG> illustrates an FPGA implementation of the programmable IC <NUM> that includes a large number of different programmable tiles including transceivers <NUM>, CLBs) <NUM>, BRAMs <NUM>, input/output blocks ("IOBs") <NUM>, configuration and clocking logic ("CONFIG/CLOCKS") <NUM>, DSP blocks <NUM>, specialized input/output blocks ("I/O") <NUM> (e.g., configuration ports and clock ports), and other programmable logic <NUM> such as digital clock managers, analog-to-digital converters, system monitoring logic, and so forth. The FPGA can also include PCIe interfaces <NUM>, analog-to-digital converters (ADC) <NUM>, and the like.

In some FPGAs, each programmable tile can include at least one programmable interconnect element ("INT") <NUM> having connections to input and output terminals <NUM> of a programmable logic element within the same tile, as shown by examples included at the top of <FIG>. Each programmable interconnect element <NUM> can also include connections to interconnect segments <NUM> of adjacent programmable interconnect element(s) in the same tile or other tile(s). Each programmable interconnect element <NUM> can also include connections to interconnect segments <NUM> of general routing resources between logic blocks (not shown). The general routing resources can include routing channels between logic blocks (not shown) comprising tracks of interconnect segments (e.g., interconnect segments <NUM>) and switch blocks (not shown) for connecting interconnect segments. The interconnect segments of the general routing resources (e.g., interconnect segments <NUM>) can span one or more logic blocks. The programmable interconnect elements <NUM> taken together with the general routing resources implement a programmable interconnect structure ("programmable interconnect") for the illustrated FPGA.

In an example implementation, a CLB <NUM> can include a configurable logic element ("CLE") <NUM> that can be programmed to implement user logic plus a single programmable interconnect element ("INT") <NUM>. A BRAM <NUM> can include a BRAM logic element ("BRL") <NUM> in addition to one or more programmable interconnect elements. Typically, the number of interconnect elements included in a tile depends on the height of the tile. In the pictured example, a BRAM tile has the same height as five CLBs, but other numbers (e.g., four) can also be used. A DSP tile <NUM> can include a DSP logic element ("DSPL") <NUM> in addition to an appropriate number of programmable interconnect elements. An IOB <NUM> can include, for example, two instances of an input/output logic element ("IOL") <NUM> in addition to one instance of the programmable interconnect element <NUM>. As will be clear to those of skill in the art, the actual I/O pads connected, for example, to the I/O logic element <NUM> typically are not confined to the area of the input/output logic element <NUM>.

In the pictured example, a horizontal area near the center of the die (shown in <FIG>) is used for configuration, clock, and other control logic. Vertical columns <NUM> extending from this horizontal area or column are used to distribute the clocks and configuration signals across the breadth of the FPGA.

Some FPGAs utilizing the architecture illustrated in <FIG> include additional logic blocks that disrupt the regular columnar structure making up a large part of the FPGA. The additional logic blocks can be programmable blocks and/or dedicated logic.

Note that <FIG> is intended to illustrate only an exemplary FPGA architecture. For example, the numbers of logic blocks in a row, the relative width of the rows, the number and order of rows, the types of logic blocks included in the rows, the relative sizes of the logic blocks, and the interconnect/logic implementations included at the top of <FIG> are purely exemplary. For example, in an actual FPGA more than one adjacent row of CLBs is typically included wherever the CLBs appear, to facilitate the efficient implementation of user logic, but the number of adjacent CLB rows varies with the overall size of the FPGA.

The descriptions of the various embodiments of the present invention have been presented for purposes of illustration, but are not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.

In the preceding, reference is made to embodiments presented in this disclosure. However, the scope of the present disclosure is not limited to specific described embodiments. Furthermore, although embodiments disclosed herein may achieve advantages over other possible solutions or over the prior art, whether or not a particular advantage is achieved by a given embodiment is not limiting of the scope of the present disclosure. Thus, the aspects, features, embodiments and advantages described herein are merely illustrative and are not considered elements or limitations of the appended claims.

Claim 1:
A method (<NUM>) for scheduling a neural network (<NUM>), the method comprising:
using one or more computing processors (<NUM>):
receiving (<NUM>) a model (<NUM>) defining a sequential order, in a pipeline (<NUM>), of a plurality of functions defined in and performed when executing at least one layer (Layer <NUM>-<NUM>) in the neural network (<NUM>), wherein the model (<NUM>) represents the neural network (<NUM>) comprising a plurality of layers;
generating (<NUM>) a systolic array (<NUM>) including interconnected processing elements, PEs, (PE <NUM>, <NUM>, <NUM>, <NUM>), generating the systolic array (<NUM>) being based on the model (<NUM>) and by connecting identical processes in the at least one layer of the neural network (<NUM>), wherein the processes relate to operations that are performed by the PEs, the systolic array (<NUM>) being for executing the identical processes for executing the plurality of functions, the interconnected processing elements of the systolic array (<NUM>) being for executing concurrently; and
compiling (<NUM>) source code corresponding to the model and the systolic array (<NUM>) into a hardware level design that provides a static schedule when executing the neural network (<NUM>) in a hardware system (<NUM>), wherein compiling the source code of the systolic array (<NUM>) comprises:
converting the source code corresponding to the systolic array (<NUM>) into a two- dimensional array of interconnected processing elements using register transfer level code for configuring programmable logic;
identifying a plurality of operations performed by each of the interconnected processing elements, wherein each of the interconnected processing elements perform the same plurality of operations; and
assigning the plurality of operations to different hardware elements in the hardware system (<NUM>) such that the plurality of operations are able to perform concurrently.