Back to results
US 10,242,311 B2Granted
Zero coefficient skipping convolution neural network engine
AssigneeVivante Corporation
InventorMankit Lo
Life of this patent
Estimating the term…
Abstract
A convolution engine, such as a convolution neural network, operates efficiently with respect to sparse kernels by implementing zero skipping. An input tile is loaded and accumulated sums are calculated for the input tile for non-zero coefficients by shifting the tile according to a row and column index of the coefficient in the kernel. Each coefficient is applied individually to tile and the result written to an accumulation buffer before moving to the next non-zero coefficient. A 3D or 4D convolution may be implemented in this manner with separate regions of the accumulation buffer storing accumulated sums for different indexes along one dimension. Images are completely processed and results for each image are stored in the accumulation buffer before moving to the next image.
Claims20
A method for performing convolution, the method comprising:
- providing an array of coefficients C(kz, Z, kx, ky) defining a Z dimension, a kz dimension, a kx dimension, and a ky dimension;
- providing a plurality of input images each corresponding to an index in the kz dimension;
- (a) selecting, by an electronic device, a next tile position of a plurality of tile positions as the current tile position;
- (b) selecting, by an electronic device, a next input image I(kz1) of the plurality of input images as the current image and an index kz1 corresponding to the current image as a current kz index;
- (c) loading, by the electronic device, a tile of the current image I(kz1) at the current tile position into a buffer as the current tile;
- (d) individually and sequentially performing, by the electronic device, for each coefficient of at least a portion of coefficients C(kz1, Z, kx, ky) of the array of coefficients having an index in the kz dimension equal to kz1:
- setting a ky shift amount of the current tile according to a ky index of the each coefficient in the ky dimension;
- setting a kx shift amount of the current tile according to a kx index of the each coefficient in the kx dimension;
- applying the ky shift amount to the tile and applying the kx shift amount to the current tile in the buffer to obtain a shifted tile;
- multiplying the shifted tile by the each coefficient such that each row of the shifted tile is multiplied by the each coefficient in parallel by a series of multipliers to obtain a set of products;
- adding the set of products to set of accumulated sums stored in an accumulation buffer to obtain a set of updated sums;
- and
- overwriting the set of accumulated sums with the set of updated sums;
- (e) performing (b) through (d) until all input images of the plurality of images have been processed according to (b) through (d);
- (f) outputting current values of the accumulated sums as an output image;
- (g) performing (a) through (f) until all tile positions of the plurality of tile positions has been processed according to (a) through (f);
- wherein the ky shift amount and kx shift amount are selected such that the accumulated sums are a three dimensional convolution of the current tile with the plurality of images upon completion of (f).
14 more elements
An apparatus for performing convolution, the apparatus comprising an electronic device programmed to:
- receive an array of coefficients C(kz, Z, kx, ky) defining a Z dimension, a kz dimension, a kx dimension, and a ky dimension;
- receive a plurality of input images each corresponding to an index in the kz dimension;
- (a) select a next tile position of a plurality of tile positions as the current tile position;
- (b) select a next input image I(kz1) of the plurality of input images as the current image and an index kz1 corresponding to the current image as a current kz index;
- (c) load a tile of the current image I(kz1) at the current tile position into a buffer as the current tile;
- (d) individually and sequentially perform, for each coefficient of at least a portion of coefficients C(kz1, Z, kx, ky) of the array of coefficients having an index in the kz dimension equal to kz1:
- setting a ky shift amount of the current tile according to a ky index of the each coefficient in the ky dimension;
- setting a kx shift amount of the current tile according to a kx index of the each coefficient in the kx dimension;
- applying the ky to the current tile and applying the kx shift amounts to the current tile within the buffer to obtain a shifted tile;
- multiplying the shifted tile by the each coefficient to obtain a set of products;
- adding the set of products to set of accumulated sums stored in an accumulation buffer to obtain a set of updated sums;
- and
- overwriting the set of accumulated sums with the set of updated sums;
- (e) perform (b) through (d) until all input images of the plurality of images have been processed according to (b) through (d);
- (f) output current values of the accumulated sums as an output image;
- (g) perform (a) through (f) until all tile positions of the plurality of tile positions has been processed according to (a) through (f);
- wherein the ky shift amount and kx shift amount are selected such that the accumulated sums are a three dimensional convolution of the current tile with the plurality of images upon completion of (f).
14 more elements
Dependencies are inferred from the claim text.