Patent Description:
Neural networks are machine learning models that employ one or more layers of nonlinear computation units to predict an output for a received input. During an interference pass (i.e. the process performed by the neural network as a whole to generate a set of output(s) based on a corresponding set of inputs to the neural network at a certain timestep), the output of each hidden layer is used as input to the next layer in the network, i.e., the next hidden layer or the output layer.

Each layer of the network generates an output for the next layer in accordance with current values of a respective set of parameters for the layer and one or more transformation operations. The transformation operations of each layer can be performed by processing devices executing installed software kernels that implement the transformation operations of the layer. Thus, a layer being described as performing operations means that the processing devices implementing the transformation operations of the layer perform the transformation operations.

Naturally, as the size and complexity of neural networks increase, the time required to perform an inference pass through the network also increases. In general, the inference speed of a neural network is proportional to the number of parameters in the model. This can impose a significant processing bottleneck that can restrict the types of neural networks that can be implemented on certain types of processing hardware.

This is particularly a challenge for neural networks that have significant throughput requirements, significant latency requirements, or both. For example, real-time audio generation neural networks present significant computational challenges because of the basic high-throughput nature of generating raw audio waveforms. Realistic audio waveform generation typically requires on the order of multiple thousands of samples to be generated per second, e.g., <NUM>,<NUM> samples per second, which, for example, can require <NUM>,<NUM> inference passes to be performed per second. These performance requirements can make it difficult to implement high-throughput neural networks directly on consumer hardware, e.g., mobile phones and tablet computers, that lack the kind of high-performance or parallel processing hardware that might be available in a datacenter. As another example, neural networks that are executed for sensing or control of autonomous and semi-autonomous vehicles have significant latency requirements. In other words, neural networks used to perform sensing and control in real-world driving conditions have to be fast enough that the vehicle can reliably react within certain well-defined time periods, e.g., within microseconds or milliseconds.

One approach to improving the inference speed is to generate layers having sparse connections. In this context, a model having sparse connections between layers means that a substantial number of possible connections are deactivated by having values of zero. For example, between two layers having <NUM> neurons each, there are 1000x1000 possible connections, or <NUM> million possible connections. Instead of having <NUM> million connections, the connections can be pruned to a small fraction of the possible connections, e.g., only <NUM>,<NUM> or <NUM>,<NUM> connections.

The inference speed can be further improved by training the model to have square block sparsity in the connections. Square block sparsity imposes some structure on the sparsity pattern of the connections by computing, for square regions of parameter matrices, a single representative value, e.g., an average or the maximum value. Square block sparsity does impose some structure in the model parameters, but the pattern of the square blocks within the matrix has essentially uniform randomness.

<NPL>, quantitatively measures the trade-off between sparcity regularity and prediction accuracy, and finds that coarse-grained pruning can achieve a similar sparsity ratio to unstructured pruning without loss of accuracy. <NPL>, investigates two different approaches to induce block sparsity in recurrent neural networks.

This specification proposes a method as defined by claim <NUM>. The specification describes techniques for improving the inference speed of a neural network, and reducing the data storage requirement of the neural network, by arranging the parameter values into contiguous sparsity patterns. Training a model to have contiguous sparsity involves imposing a structured sparsity pattern in which substantial numbers of non-zero values are likely to be contiguous along the same dimension in a parameter matrix. This also means that substantial numbers of zero values are likely to be contiguous along the same dimension in the parameter matrix.

Experimentally, it is found that a neural network with contiguous sparsity performs broadly equivalently to a neural network with unstructured sparsity (i.e. the same sparsity, but with the non-zero values being distributed randomly), but, crucially, the sparsity pattern can be stored with reduced the data storage capacity.

Furthermore, as explained below, contiguous sparsity permits the neural network to be implemented with more efficient coding than unstructured sparsity, reducing the number of computational operations which are required to implement it.

Both of these advantages are critical in the case that the neural network, although possibly created on a server, is utilized by a client device, such as a mobile phone, with low memory capacity and limited computational power. Note that currently the amounts of computational power and memory bandwidth are respectively three and two orders of magnitude smaller on a mobile CPU (central processing unit) than on a (graphics processing unit) GPU.

What is considered a sufficiently substantial number of contiguous zero or non-zero parameters values is dependent on the underlying training set and design goals of the model. For example, the system can train the model according to hyperparameters that specify one or more of these constraints, e.g., a likelihood of having blocks of contiguous non-zero parameters of at least length l with at least frequency f within the parameter matrix.

For simplicity of presentation, this specification will use the term "sparse" to refer to a (two-dimensional) pattern of values (that is, a matrix) in which the number of zero values is greater than the number of non-zero values. Specifically, the proportion of zero values may be at least <NUM>%, at least <NUM>%, or at least <NUM>% (such as at least <NUM>% or at least <NUM>%), or even at least <NUM>%. The term "sparsity pattern" refers to the dataset indicating where the non-zero values of the parameter matrix are.

The term "block" is used to refer to a (non-square) rectangle of non-zero values within a pattern. Often, a block cannot be extended in either dimension without including at least one zero value of the sparsity pattern; thus, it is may be the largest contiguous block of non-zero values which can be formed. However, it is also possible for two or more such blocks to be adjacent.

We will use the term "contiguous sparsity" to refer to any sparsity pattern substantially composed of a plurality of zero values and blocks of non-zero values have block sizes in which one dimension is substantially larger (e.g. at least <NUM> times larger (e.g. exactly <NUM> times larger), or even at least <NUM> times larger (e.g. exactly <NUM> times larger)) than the other, and the number of zero values being greater than the number of non-zero values. Each of the blocks are of the same size; that is, they are nx1, where n is greater than one.

A parameter matrix having a contiguous sparsity pattern can have columnar sparsity in which non-zero parameter values are contiguous along columns of the parameter matrix (e.g. in the case of equally-sized blocks, n is greater than <NUM>. Note that in the case of column sparsity, there may be more than one block in each column of the parameter matrix (e.g. with the multiple blocks being spaced apart by zero values). In some parameter matrices, two or more blocks may be adjacent.

Here, it is to be understood that the horizontal (row) direction in the parameter matrix (i.e. the direction in which the blocks have an extent <NUM>) represents the different inputs of the layer, whereas the vertical (column) direction in the parameter matrix (i.e. the direction in which the blocks have an extent n) corresponds to the different outputs of the layer (or different neurons of the layer). For example, in one case, the layer performs multiplication between the parameter matrix and a vector x representing the inputs to the layer (in other words the parameter matrix R of network parameters is multiplied by a vector x representing the input values, in an operation such as R. x), and then performs a function on each of the results of the multiplication.

A contiguous sparsity pattern has blocks having dimensions nx1.

Using contiguous sparsity patterns allows neural networks with very significant throughput requirements, very significant latency requirements, or both, to be implemented on less powerful processing hardware, e.g., consumer hardware such as mobile phones (or other mobile devices) and tablet computers, having only CPUs and on-board processing devices that are used for controlling autonomous vehicle functions. In these computing environments, the neural network can be implemented locally on the hardware, which means that the network can execute without a network connection to a datacenter, without the use of dedicated parallel processing hardware like GPUs, and without requiring special-purpose hardware. This, for example, allows real-time audio waveform generation to be performed on handheld mobile devices, e.g., for text-to-speech applications. And it allows for more sophisticated and more complex neural networks to be implemented in environments with significant latency requirements. Another application of the neural network would be automatic generation of images. Another application of the neural network would be to generate text or any other appropriate one-dimensional data stream. A further application of the neural network would be to control an agent (e.g. a mechanical device) in an environment, such as a real-world environment, based on input to the network encoding information received by a sensor and characterizing the environment. In one application, the agent may be a transportation device, such as an autonomous or semi-autonomous vehicle.

If the input to the neural network is text, then the input to the neural network at successive times may comprise successive characters of a passage of text.

Alternatively, in other applications, the input to the neural network at successive times may comprise data characterizing an environment (e.g. audio data) obtained by sensors at corresponding successive times.

In one example, the neural network may be a recurrent neural network (RNN) in which a plurality of neurons each generate, in each time-step (e.g. during each inference pass), an output which depends upon a state of the neurons at a previous time-step (which is in turn dependent on the input(s) to the neuron in preceding inference passes). For example, a layer of the neural network may receive among its inputs at a given time-step the output of the neural layer at at least one preceding time-step, e.g. including the immediately preceding time-step.

<FIG> includes visualizations of parameter matrices that illustrate the structure of a contiguous sparsity pattern compared to a random sparsity pattern. In <FIG>, black regions represent zero parameter values, and white regions represent non-zero parameter values.

The random sparsity parameter matrix <NUM> has a random sparsity pattern. Therefore, the non-zero parameter values are distributed substantially uniformly throughout the matrix.

The contiguous sparsity parameter matrix <NUM> has a contiguous sparsity pattern. Therefore, substantial numbers of non-zero values are contiguous along rows of the parameter matrix.

Contiguous sparsity can be obtained during training by periodically sorting blocks of the parameters according to magnitude, and zeroing out all the parameters of blocks for which the parameters meet a criterion inactive of the parameters being small. For example, the sum of the magnitudes of the parameters of the block may be below a particular threshold. The result is a sparsity pattern that has more structure than a random sparsity pattern and which increases the inference speed relative to a square block sparsity pattern.

Contiguous sparsity can be used to improve the inference speed of a neural network in a number of ways.

<FIG> is a diagram of an example system <NUM> that uses a contiguous sparsity pattern. The system <NUM> is an example of a system that can implement the techniques described in this specification. The system <NUM> can, in one application, implement a signal generation neural network, e.g., a neural network that generates audio, images, text or any other appropriate one-dimensional data stream, on parallel processing hardware. In doing so, some matrix operations can be performed in parallel by all available processing units, and other matrix operations can be performed in parallel by subsets of available processing units.

The system <NUM> includes a neural network system <NUM> that is defined by a plurality of layers. In general, each layer has a respective parameter matrix. Thus, layer N has a separate parameter matrix from layer N+<NUM>. Each layer is implemented by a respective computing system. For simplicity, only two such layers are illustrated as being implemented by two respective computing systems, a layer N computing system <NUM>, and a layer N+<NUM> computing system <NUM>. Each of these computing systems can be implemented using any appropriate combination of general or special-purpose computing hardware. For example, each computing system can implemented using CPUs, GPUs, or application-specific integrated circuitry, e.g., a machine-leaming accelerator. The computing systems <NUM> and <NUM> can be implemented by separate computing hardware or the same computing hardware.

The layer N computing system <NUM> includes an activation engine <NUM> that is configured to receive an input <NUM>, e.g., an input vector. The components of the input vector are referred to in this document as "activation values". In the case that layer N is the first layer of the network, the activation values are the inputs to the neural network. The input vector may, in one application, be composed of elements have a pre-defined order (for example, they may be indicative of respective text characters in a passage of text; or data describing an environment at successive times). In the case that the layer N is a hidden layer of the neural network, the activation values are outputs from the preceding (i.e. N-<NUM>) layer. The activation engine <NUM> is configured to use the input <NUM> and the parameter matrix for layer N to generate multiple output values <NUM> using an activation function <NUM>.

The layer N computing system <NUM> includes a contiguous sparsity storage subsystem <NUM>. The contiguous sparsity storage subsystem <NUM> is a subsystem that is configured obtain the parameter matrix for layer N. The parameter matrix is composed on parameter values that are stored in contiguous sparsity patterns, as described below. In one case, the sparsity pattern is such that is it composed entirely of (i) zero values and (ii) blocks of non-zero values which extend vertically. In other words, in this case the contiguous sparsity storage subsystem <NUM> can obtain multiple contiguous non-zero values for a single input value. In some implementations, the contiguous sparsity storage subsystem <NUM> implements an application programming interface (API) that takes as an argument a number of contiguous parameter values to read next from the parameter matrix for layer N.

The contiguous sparsity storage subsystem <NUM> can be a separate storage subsystem for one or more layers, or the contiguous sparsity storage subsystem <NUM> can be a global storage subsystem for the entire neural network system <NUM>. In some implementations, the contiguous sparsity storage subsystem <NUM> is implemented by fast memory, e.g., SRAM, that is local to the processing components that perform the operations of the activation function <NUM>. In other words, the parameter matrix for the layer N can be stored in whole or in part in memory that is local to the activation engine <NUM>.

The layer N computing system <NUM> also includes a post-activation engine <NUM> that is configured to receive output values <NUM> generated by the activation engine <NUM> and to generate a layer N output <NUM> that is provided to the next layer <NUM> of the neural network system <NUM>. The post-activation engine <NUM> can perform aggregation operations on the outputs <NUM> generated by the activation function <NUM>, including summation, pooling, and soft-max operations.

To use the contiguously stored parameter values, the activation engine <NUM> can read each non-zero value from the input <NUM> and then read multiple contiguously stored parameter values from the contiguous sparsity storage subsystem <NUM>. The activation engine <NUM> can then generate multiple output values <NUM> for the single input value, e.g., by multiplying the input value by each of the contiguously stored parameter values and providing the individual products, or a partial summation of the products, to the post-activation processing engine <NUM>.

<FIG> is a flowchart of an example process for training a neural network to have a parameter matrix with a contiguous sparsity pattern. The example process can be performed by any appropriate computing system that that can implement the operations and training updates of a neural network system. Optionally, the process of <FIG> may be performed by a first computer system (e.g. a server) to produce a neural network model, and that neural network model may subsequently be transmitted to a second computer system (e.g. a mobile phone, or other client device) which has relatively lower computational power and memory capacity. For convenience, the example process will be described as being performed by a system of one or more computers programmed appropriately in accordance with this specification.

The system performs a training iteration (<NUM>). In general, each training iteration updates the weights of the parameter matrices of the neural network after performing one or more or inference passes through the neural network system. In some implementations, each training iteration performs a backpropagation process that updates the weights of the parameter matrices through the layers in a direction opposite to the direction of the inference pass.

The system determines whether to update the parameter sparsity pattern for a layer (<NUM>); in other words, to reset the parameter values such that the parameter matrix satisfies the constraint of contiguous sparsity. For example, the system may update the sparsity pattern after every training iteration, or regularly each time that a certain number of iterations occurs, or only once, after a predetermined number of iterations.

If the sparsity pattern is to be updated (<NUM>), the system may employ a partitioning of the parameter matrix into a plurality of nx1 blocks, where n is greater than one, The partitioning may be pre-defined (i.e. the positions of the blocks may be pre-defined), and may be the same each time the sparsity pattern is updated. The system sorts the partitioned blocks of parameters into an order according to the absolute magnitudes of the parameters in each block, e.g. according to the sum of absolute magnitude of the parameters in each block (branch to <NUM>); it then clears all the values of those blocks for which the parameters satisfy a threshold criterion indicative of the parameters being small. For example, the threshold criterion may be that the sum of the absolute magnitudes of the parameters of the block is less than a threshold (<NUM>). Clearing a value can include assigning a special value that will be disregarded during inference, e.g., zero or another reserved value (for simplicity, the term "zero value" is used here to cover both possibilities).

The threshold may be selected such that the proportion of the blocks for which the values are cleared is equal to a certain frequency value (this determines how many weights of are retained at a non-zero value; in other words, the frequency value determines the sparsity of the resulting parameter matrix). The order of the blocks obtained in step <NUM> makes it easy to determine such a threshold. Note that in variations of the method of <FIG>, the threshold may be predetermined, and in this case the ordering step (<NUM>) may be omitted.

Step <NUM> has the effect of distilling the neural network, i.e. dramatically reducing the amount of data which is required to store the neural network, and the computational power which is required to operate the neural network. This makes the neural network suitable for use by the second computer system.

The system can be configured to use hyperparameters K, k, and Z, where K specifies the iteration interval (i.e. the number of iterations which occur between the times that, in step <NUM>, the system determines to update the parameter sparsity pattern), k specifies how many weights to retain on each update, and Z represents a maximum value for k. In some implementations, the value of k increases as training progresses according to: <MAT> where t is the current iteration number, t<NUM> is the iteration on which the first update occurred, and S is the total number of desired update steps.

The system determines whether training is complete (<NUM>). If not, the system performs another training iteration (branch to <NUM>).

If training is complete (<NUM>), the system optionally performs one or more pre-inference optimizations (<NUM>). The pre-inference optimizations are each designed to take advantage of the contiguous sparsity pattern in the newly trained parameter matrix. The pre-inference optimizations can include low-precision delta encoding, sparsity pattern unrolling, and precise load balancing.

First, the system can encode the parameter matrix using low-precision delta encoding. The contiguous sparsity allows for additional data compression of the parameter matrix using delta encoding that provides advantages over using regular compressed sparse row (CSR) format. In particular, the system can delta encode the deltas between blocks using data types having lower precision than data types that encode the parameters. For example, instead of encoding the deltas using <NUM>-bit integers, the system can instead use <NUM>-bit integers. This reduces the storage space required to store a vast amount of metadata about the parameter matrix, which makes the storage requirements of the entire model smaller.

In addition, the contiguous pattern of parameter values allows the system to unroll the sparsity pattern into the source code of the neural network kernel itself. In other words, the system can automatically generate source code of the neural network kernel that encodes the sparsity pattern within the code. This allows the system to skip vast numbers of memory accesses that would otherwise be required to fetch, from memory, data that specifies the location of the next non-zero parameter value. Instead, the system can simply generate source code statements that directly encode the location of the next non-zero value. This also speeds up the inference time by reducing branches and memory stalls.

The contiguous pattern of parameter values also means that the entire sparsity pattern can be encoded with fewer source code statements than a random sparsity pattern. This means that the entire neural network kernel can often fit completely within a faster portion of the memory hierarchy, e.g., the L1 cache rather than main memory. In some implementations, the entire kernel is small enough to fit in the L1 cache while the encoded parameter matrix is small enough to fit within the data cache.

Consider the following example 8x8 matrix having a contiguous sparsity pattern <MAT>.

A compiler could unroll the program code that loops over reading these parameter values as shown by the pseudocode in the second column of TABLE <NUM>. In other words, instead of the source code having a for loop structure, the source code instead has a series of sequential Read instructions that read different parameter values from the matrix. For clarity, other operations of the neural network kernel, including multiply-accumulates and other operations, have been omitted.

As can be seen from this example, unrolling alone generates <NUM> Read instructions to read all values of the parameter matrix.

The last column in TABLE <NUM> illustrates unrolling with encoding. In particular, because the locations of the contiguous non-zero values of the parameter matrix are known at compile time, the system can generate Read instructions that directly encode the locations of the contiguous non-zero values.

In this example, the pseudocode instruction Read takes a first argument that specifies the position of a start of a block of non-zero parameter values, and a second argument that specifies how many contiguous values to read. These are known ahead of time from the sorting and clearing procedure described above. Therefore, the system can read all the non-zero values from the example parameter matrix with only <NUM> Read instructions instead of <NUM>. This optimization also makes the size of the code smaller, which further makes the storage requirements of the model smaller.

Lastly, the contiguous sparsity patterns allow the system to perform very precise load balancing on multi-compute element devices. Load balancing the operations of a sparse matrix-vector multiply having an unknown sparsity pattern among multiple processing units is challenging.

But during inference, models are fixed for long periods of time, and this allows the system to pre-compute the optimal load balancing among N processors ahead of time. For example, a system can assign a substantially equal number of contiguous blocks or block parameter values (i.e. parameter values which are within one of the blocks) to each processing core of a CPU, a GPU, or another parallel processing device, which makes the inference faster to compute than load balancing for a random sparsity pattern. As another example, a system can assign a substantially equal number of blocks to each processing element of an application-specific processor having multiple processing elements.

<FIG> is a flowchart of an example process for performing an inference pass over a neural network having a parameter matrix with a contiguous sparsity pattern. The example process can be performed by a computing system that is configured to implement the operations of one layer of a neural network system. For example, the layer N computing system <NUM> of <FIG> can perform the example process. For convenience, the example process will be described as being performed by a system of one or more computers programmed appropriately in accordance with this specification.

The system receives an input vector (<NUM>). As described above, the input vector can be the output generated by a previous layer of the neural network system, or the input vector can be an initial representation of an initial input to the neural network system.

The system determines whether all of the input vector has been processed (<NUM>).

If not, the system identifies a next non-zero input value of the input vector (branch to <NUM>). In other words, the system identifies the next non-zero input value of the input vector that has not yet been processed. For devices having multiple processors, this may skip over input values being processed by other processing components.

The system reads multiple contiguous non-zero parameter values for the input value (<NUM>). The system can identify a row of the parameter matrix corresponding to the input value and read the contiguous parameter values from that row. If the system used unrolling with location encoding described above, the system can immediately read the non-zero values from the parameter matrix in constant time without searching.

The system generates multiple output values for the input value and the multiple contiguous non-zero parameter values (<NUM>). For example, the system can multiply the input value by each of the multiple contiguous non-zero parameter values. The system can then optionally generate a partial sum to be added with the results for other input values.

If all the input values have been processed (<NUM>), the process ends (branch to end).

Performing inference passes using contiguous sparsity patterns thus speeds up the matrix-vector multiplications involved in an inference pass. When the parameters have contiguous columnar sparsity, the same input vector values can be read once from memory and used for multiplying with multiple parameter values. This may be done before reading any further input vector values from the memory. An nx1 block size means that while multiple memory operations are required to load the values from the input vector, the values can be reused n times. Blocks of size nx1 mean that multiple rows can share the same input activations.

A computer program which may also be referred to or described as a program, software, a software application, an app, a module, a software module, a script, or code) can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment.

To provide for interaction with a user, embodiments of the subject matter described in this specification can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and pointing device, e.g., a mouse, trackball, or a presence sensitive display or other surface by which the user can provide input to the computer. Also, a computer can interact with a user by sending text messages or other forms of message to a personal device, e.g., a smartphone, running a messaging application, and receiving responsive messages from the user in return.

While this specification contains many specific implementation details, these should not be construed as limitations on the scope of any invention, but rather as descriptions of features that may be specific to particular embodiments of particular inventions.

Particular embodiments of the subject matter have been described. Preferred embodiments of the invention are defined by the appended dependent claims. As one example, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In certain some cases, multitasking and parallel processing may be advantageous.

Claim 1:
A method comprising:
receiving, by a computing device, one or more parameter matrices of a neural network, wherein each parameter matrix corresponds to a layer of the neural network, wherein the row direction of the parameter matrix represents different inputs of the layer and the column direction of the parameter matrix represents different outputs of the layer, wherein at least a first parameter matrix has parameter values stored in a contiguous sparsity pattern, the contiguous sparsity pattern being a two-dimensional pattern composed of zero values and a plurality of non-square rectangular blocks of non-zero values, wherein each of the blocks has size nx1, where n is greater than one, the number of zero values in the first parameter matrix being greater than the number of non-zero values;
storing the first parameter matrix in storage associated with the computing device;
receiving, by the computing device, an input vector of activation values and storing the input vector of activation values in the storage associated with the computing device; and
performing, by the computing device, an inference pass of the neural network to generate an output vector, including performing operations comprising:
reading, from the storage associated with the computing device, a first activation value from the input vector,
reading (<NUM>), from the storage associated with the computing device, a block of n contiguous non-zero parameter values, and
generating (<NUM>) multiple output values of the output vector by a process comprising multiplying the first activation value by the block of n contiguous non-zero parameter values before reading another activation value from the input vector.