Methods and devices for efficient general deconvolution implementation on hardware accelerator

1 . A method for implementing a deconvolution operation between a multi-dimensional kernel in a pre-defined dimensional count and a multi-dimensional input map in the pre-defined dimensional count to obtain a multi-dimensional output feature map in the pre-defined dimensional count, comprising:

subsampling, by one or more hardware accelerators based on a deep neural network, the multi-dimensional kernel into a plurality of non-overlapping multi-dimensional sub-kernels, each in the pre-defined dimensional count, based on a pre-defined common stride parameter, wherein the multi-dimensional kernel comprises four sides, the plurality of multi-dimensional sub-kernels are positioned at different internal locations of the multi-dimensional kernel such that each multi-dimensional sub-kernel is located proximate to a respective pair of adjacent sides among the four sides of the multi-dimensional kernel;

obtaining, by the one or more hardware accelerators based on the deep neural network, a plurality of multi-dimensional sub-output feature maps in the pre-defined dimensional count, wherein the deep neural network comprises a deconvolution layer that deconvolves the multi-dimensional input map with each multi-dimensional sub-kernel in the plurality of non-overlapping multi-dimensional sub-kernels to obtain the plurality of multi-dimensional sub-output feature maps; and

in response to determining the pre-defined common stride parameter is not greater than two, using a pre-defined multi-dimensional interleave-concatenation method to interleave-concatenate and reorder, by the one or more hardware accelerators based on the deep neural network, the plurality of multi-dimensional sub-output feature maps into the multi-dimensional output feature map; and

wherein the deconvolution operation further comprises:

before the multi-dimensional input map is deconvolved with each multi-dimensional sub-kernel, virtually padding, by the one or more hardware accelerators based on the deep neural network, two adjacent input map sides of the multi-dimensional input map for each multi-dimensional sub-kernel based on each multi-dimensional sub-kernel's internal location of the multi-dimensional kernel, wherein the two adjacent input map sides are associated with a corresponding pair of adjacent sides of the multi-dimensional kernel.

2 . The method of claim 1 , further comprising:

in response to determining the pre-defined common stride parameter is greater than two, using the pre-defined multi-dimensional interleave-concatenation method to interleave-concatenate and reorder the plurality of multi-dimensional sub-output feature maps into a multi-dimensional intermediate output feature map in the pre-defined dimensional count, and then cropping the multi-dimensional intermediate output feature map into the multi-dimensional output feature map.

3 . The method of claim 1 , wherein the stride-dependent virtual padded deconvolution operation between the multi-dimensional input map and a multi-dimensional sub-kernel comprises:

deriving a virtual padding configuration for the multi-dimensional sub-kernel based on the pre-defined common stride parameter, a plurality of pre-defined common padding parameters with the plurality count equal to the pre-defined dimensional count, a plurality of dimensional measurements of the multi-dimensional sub-kernel, and a relative position of the multi-dimensional sub-kernel with reference to the multi-dimensional kernel; and

applying a pre-defined deconvolution operation between the multi-dimensional input map on one hand, and a virtual multi-dimensional sub-kernel in the pre-defined dimensional count, equivalent to the result of padding the multi-dimensional sub-kernel in accordance with the virtual padding configuration, on the other hand.

4 . The method of claim 1 , wherein the pre-defined multi-dimensional interleave-concatenation method comprises sequentially interleave-concatenating and reordering the plurality of multi-dimensional sub-output feature maps along each dimensional axis in a plurality of dimensional axes with the plurality count equal to the pre-defined dimensional count, following a pre-defined sequential order for the plurality of dimensional axes, in each intermediate step arriving at a plurality of intermediate interleave-concatenated multi-dimensional sub-output feature maps, and in the end arriving at the multi-dimensional output feature map.

5 . The method of claim 3 , wherein the pre-defined dimensional count is 2 and the plurality of pre-defined common padding parameters comprise a pre-defined common horizontal padding parameter and a predefined common vertical padding parameter; and

wherein the one or more hardware accelerators comprises one of the following circuitries:

application specific integrated circuits (ASICs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable gate arrays (FPGAs), controllers, micro-controllers, or microprocessors.

6 . The method of claim 5 , wherein the virtual padding configuration comprises:

to left and right sides of the 2-dimensional sub-kernel, a horizontal padding size equal to the result of subtracting first the number one and then the pre-defined common horizontal padding parameter from a horizontal dimensional measurement of the 2-dimensional sub-kernel; and

to top and bottom sides of the 2-dimensional sub-kernel, a vertical padding size equal to the result of subtracting first the number one and then the pre-defined common vertical padding parameter from a vertical dimensional measurement of the 2-dimensional sub-kernel.

7 . The method of claim 5 , wherein the virtual padding configuration comprises:

to the left side of the 2-dimensional sub-kernel, a horizontal padding size equal to the result of subtracting first the number one and then an integral division result of dividing the pre-defined common horizontal padding parameter by 2 from the horizontal dimensional measurement of the 2-dimensional sub-kernel, further reduced by a remainder of dividing the pre-defined common horizontal padding parameter by 2 if and only if the relative position of the 2-dimensional sub-kernel with reference to the 2-dimensional kernel is top-left or bottom-left;

to the right side of the 2-dimensional sub-kernel, a horizontal padding size equal to the result of subtracting first the number one and then an integral division result of dividing the pre-defined common horizontal padding parameter by 2 from the horizontal dimensional measurement of the 2-dimensional sub-kernel, further reduced by a remainder of dividing the pre-defined common horizontal padding parameter by 2 if and only if the relative position of the 2-dimensional sub-kernel with reference to the 2-dimensional kernel is top-right or bottom-right;

to the top side of the 2-dimensional sub-kernel, a vertical padding size equal to the result of subtracting first the number one and then an integral division result of dividing the pre-defined common vertical padding parameter by 2 from the vertical dimensional measurement of the 2-dimensional sub-kernel, further reduced by a remainder of dividing the pre-defined common vertical padding parameter by 2 if and only if the relative position of the 2-dimensional sub-kernel with reference to the 2-dimensional kernel is top-left or top-right; and

to the bottom side of the 2-dimensional sub-kernel, a vertical padding size equal to the result of subtracting first the number one and then an integral division result of dividing the pre-defined common vertical padding parameter by 2 from the vertical dimensional measurement of the 2-dimensional sub-kernel, further reduced by a remainder of dividing the pre-defined common vertical padding parameter by 2 if and only if the relative position of the 2-dimensional sub-kernel with reference to the 2-dimensional kernel is bottom-left or bottom-right.

8 . A computing device comprising:

one or more processors;

a non-transitory storage coupled to the one or more processors; and

a plurality of programs stored in the non-transitory storage that, when executed by the one or more processors, cause the computing device to perform a deconvolution operation between a multi-dimensional kernel in a pre-defined dimensional count and a multi-dimensional input map in the pre-defined dimensional count to obtain a multi-dimensional output feature map in the pre-defined dimensional count, comprising:

subsampling, by one or more hardware accelerators based on a deep neural network, the multi-dimensional kernel into a plurality of non-overlapping multi-dimensional sub-kernels, each in the pre-defined dimensional count, based on a pre-defined common stride parameter, wherein the multi-dimensional kernel comprises four sides, the plurality of multi-dimensional sub-kernels are positioned at different internal locations of the multi-dimensional kernel such that each multi-dimensional sub-kernel is located proximate to a respective pair of adjacent sides among the four sides of the multi-dimensional kernel;

obtaining, by the one or more hardware accelerators based on the deep neural network, a plurality of multi-dimensional sub-output feature maps in the pre-defined dimensional count, wherein the deep neural network comprises a deconvolution layer that deconvolves the multi-dimensional input map with each multi-dimensional sub-kernel in the plurality of non-overlapping multi-dimensional sub-kernels to obtain the plurality of multi-dimensional sub-output feature maps; and

in response to determining the pre-defined common stride parameter is not greater than two, using a pre-defined multi-dimensional interleave-concatenation method to interleave-concatenate and reorder, by the one or more hardware accelerators based on the deep neural network, the plurality of multi-dimensional sub-output feature maps into the multi-dimensional output feature map; and

wherein the deconvolution operation further comprises:

before the multi-dimensional input map is deconvolved with each multi-dimensional sub-kernel, virtually padding, by the one or more hardware accelerators based on the deep neural network, two adjacent input map sides of the multi-dimensional input map for each multi-dimensional sub-kernel based on each multi-dimensional sub-kernel's internal location of the multi-dimensional kernel, wherein the two adjacent input map sides are associated with a corresponding pair of adjacent sides of the multi-dimensional kernel.

9 . The computer device of claim 8 , further comprising:

in response to determining the pre-defined common stride parameter is greater than two, using the pre-defined multi-dimensional interleave-concatenation method to interleave-concatenate and reorder the plurality of multi-dimensional sub-output feature maps into a multi-dimensional intermediate output feature map in the pre-defined dimensional count, and then cropping the multi-dimensional intermediate output feature map into the multi-dimensional output feature map.

10 . The computer device of claim 8 , wherein the stride-dependent virtual padded deconvolution operation between the multi-dimensional input map and a multi-dimensional sub-kernel comprises:

deriving a virtual padding configuration for the multi-dimensional sub-kernel based on the pre-defined common stride parameter, a plurality of pre-defined common padding parameters with the plurality count equal to the pre-defined dimensional count, a plurality of dimensional measurements of the multi-dimensional sub-kernel, and a relative position of the multi-dimensional sub-kernel with reference to the multi-dimensional kernel; and

applying a pre-defined deconvolution operation between the multi-dimensional input map on one hand, and a virtual multi-dimensional sub-kernel in the pre-defined dimensional count, equivalent to the result of padding the multi-dimensional sub-kernel in accordance with the virtual padding configuration, on the other hand.

11 . The computer device of claim 8 , wherein the pre-defined multi-dimensional interleave-concatenation method comprises sequentially interleave-concatenating and reordering the plurality of multi-dimensional sub-output feature maps along each dimensional axis in a plurality of dimensional axes with the plurality count equal to the pre-defined dimensional count, following a pre-defined sequential order for the plurality of dimensional axes, in each intermediate step arriving at a plurality of intermediate interleave-concatenated multi-dimensional sub-output feature maps, and in the end arriving at the multi-dimensional output feature map.

12 . The computer device of claim 10 , wherein the pre-defined dimensional count is 2 and the plurality of pre-defined common padding parameters comprise a pre-defined common horizontal padding parameter and a predefined common vertical padding parameter; and

wherein the one or more hardware accelerators comprises one of the following circuitries:

application specific integrated circuits (ASICs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable gate arrays (FPGAs), controllers, micro-controllers, or microprocessors.

13 . The computer device of claim 12 , wherein the virtual padding configuration comprises:

to left and right sides of the 2-dimensional sub-kernel, a horizontal padding size equal to the result of subtracting first the number one and then the pre-defined common horizontal padding parameter from a horizontal dimensional measurement of the 2-dimensional sub-kernel; and

to top and bottom sides of the 2-dimensional sub-kernel, a vertical padding size equal to the result of subtracting first the number one and then the pre-defined common vertical padding parameter from a vertical dimensional measurement of the 2-dimensional sub-kernel.

14 . The computer device of claim 12 , wherein the virtual padding configuration comprises:

to the left side of the 2-dimensional sub-kernel, a horizontal padding size equal to the result of subtracting first the number one and then an integral division result of dividing the pre-defined common horizontal padding parameter by 2 from the horizontal dimensional measurement of the 2-dimensional sub-kernel, further reduced by a remainder of dividing the pre-defined common horizontal padding parameter by 2 if and only if the relative position of the 2-dimensional sub-kernel with reference to the 2-dimensional kernel is top-left or bottom-left;

to the right side of the 2-dimensional sub-kernel, a horizontal padding size equal to the result of subtracting first the number one and then an integral division result of dividing the pre-defined common horizontal padding parameter by 2 from the horizontal dimensional measurement of the 2-dimensional sub-kernel, further reduced by a remainder of dividing the pre-defined common horizontal padding parameter by 2 if and only if the relative position of the 2-dimensional sub-kernel with reference to the 2-dimensional kernel is top-right or bottom-right;

to the top side of the 2-dimensional sub-kernel, a vertical padding size equal to the result of subtracting first the number one and then an integral division result of dividing the pre-defined common vertical padding parameter by 2 from the vertical dimensional measurement of the 2-dimensional sub-kernel, further reduced by a remainder of dividing the pre-defined common vertical padding parameter by 2 if and only if the relative position of the 2-dimensional sub-kernel with reference to the 2-dimensional kernel is top-left or top-right; and

to the bottom side of the 2-dimensional sub-kernel, a vertical padding size equal to the result of subtracting first the number one and then an integral division result of dividing the pre-defined common vertical padding parameter by 2 from the vertical dimensional measurement of the 2-dimensional sub-kernel, further reduced by a remainder of dividing the pre-defined common vertical padding parameter by 2 if and only if the relative position of the 2-dimensional sub-kernel with reference to the 2-dimensional kernel is bottom-left or bottom-right.

15 . A non-transitory computer readable storage medium storing a plurality of programs for execution by a computing device having one or more processors, wherein the plurality of programs, when executed by the one or more processors, cause the computing device to perform a deconvolution operation between a multi-dimensional kernel in a pre-defined dimensional count and a multi-dimensional input map in the pre-defined dimensional count to obtain a multi-dimensional output feature map in the pre-defined dimensional count, comprising:

subsampling, by one or more hardware accelerators based on a deep neural network, the multi-dimensional kernel into a plurality of non-overlapping multi-dimensional sub-kernels, each in the pre-defined dimensional count, based on a pre-defined common stride parameter, wherein the multi-dimensional kernel comprises four sides, the plurality of multi-dimensional sub-kernels are positioned at different internal locations of the multi-dimensional kernel such that each multi-dimensional sub-kernel is located proximate to a respective pair of adjacent sides among the four sides of the multi-dimensional kernel;

obtaining, by the one or more hardware accelerators based on the deep neural network, a plurality of multi-dimensional sub-output feature maps in the pre-defined dimensional count, wherein the deep neural network comprises a deconvolution layer that deconvolves the multi-dimensional input map with each multi-dimensional sub-kernel in the plurality of non-overlapping multi-dimensional sub-kernels to obtain the plurality of multi-dimensional sub-output feature maps; and

in response to determining the pre-defined common stride parameter is not greater than two, using a pre-defined multi-dimensional interleave-concatenation method to interleave-concatenate and reorder, by the one or more hardware accelerators based on the deep neural network, the plurality of multi-dimensional sub-output feature maps into the multi-dimensional output feature map; and

wherein the deconvolution operation further comprises:

before the multi-dimensional input map is deconvolved with each multi-dimensional sub-kernel, virtually padding, by the one or more hardware accelerators based on the deep neural network, two adjacent input map sides of the multi-dimensional input map for each multi-dimensional sub-kernel based on each multi-dimensional sub-kernel's internal location of the multi-dimensional kernel, wherein the two adjacent input map sides are associated with a corresponding pair of adjacent sides of the multi-dimensional kernel.

16 . The non-transitory computer readable storage medium of claim 15 , further comprising:

in response to determining the pre-defined common stride parameter is greater than two, using the pre-defined multi-dimensional interleave-concatenation method to interleave-concatenate and reorder the plurality of multi-dimensional sub-output feature maps into a multi-dimensional intermediate output feature map in the pre-defined dimensional count, and then cropping the multi-dimensional intermediate output feature map into the multi-dimensional output feature map.

17 . The non-transitory computer readable storage medium of claim 15 , wherein the stride-dependent virtual padded deconvolution operation between the multi-dimensional input map and a multi-dimensional sub-kernel comprises:

deriving a virtual padding configuration for the multi-dimensional sub-kernel based on the pre-defined common stride parameter, a plurality of pre-defined common padding parameters with the plurality count equal to the pre-defined dimensional count, a plurality of dimensional measurements of the multi-dimensional sub-kernel, and a relative position of the multi-dimensional sub-kernel with reference to the multi-dimensional kernel; and

applying a pre-defined deconvolution operation between the multi-dimensional input map on one hand, and a virtual multi-dimensional sub-kernel in the pre-defined dimensional count, equivalent to the result of padding the multi-dimensional sub-kernel in accordance with the virtual padding configuration, on the other hand.

18 . The non-transitory computer readable storage medium of claim 15 , wherein the pre-defined multi-dimensional interleave-concatenation method comprises sequentially interleave-concatenating and reordering the plurality of multi-dimensional sub-output feature maps along each dimensional axis in a plurality of dimensional axes with the plurality count equal to the pre-defined dimensional count, following a pre-defined sequential order for the plurality of dimensional axes, in each intermediate step arriving at a plurality of intermediate interleave-concatenated multi-dimensional sub-output feature maps, and in the end arriving at the multi-dimensional output feature map.

19 . The non-transitory computer readable storage medium of claim 17 , wherein the pre-defined dimensional count is 2 and the plurality of pre-defined common padding parameters comprise a pre-defined common horizontal padding parameter and a predefined common vertical padding parameter; and

wherein the one or more hardware accelerators comprises one of the following circuitries:

application specific integrated circuits (ASICs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable gate arrays (FPGAs), controllers, micro-controllers, or microprocessors.

20 . The non-transitory computer readable storage medium of claim 19 , wherein the virtual padding configuration comprises:

to left and right sides of the 2-dimensional sub-kernel, a horizontal padding size equal to the result of subtracting first the number one and then the pre-defined common horizontal padding parameter from a horizontal dimensional measurement of the 2-dimensional sub-kernel; and

to top and bottom sides of the 2-dimensional sub-kernel, a vertical padding size equal to the result of subtracting first the number one and then the pre-defined common vertical padding parameter from a vertical dimensional measurement of the 2-dimensional sub-kernel.

21 . The non-transitory computer readable storage medium of claim 19 , wherein the virtual padding configuration comprises:

to the left side of the 2-dimensional sub-kernel, a horizontal padding size equal to the result of subtracting first the number one and then an integral division result of dividing the pre-defined common horizontal padding parameter by 2 from the horizontal dimensional measurement of the 2-dimensional sub-kernel, further reduced by a remainder of dividing the pre-defined common horizontal padding parameter by 2 if and only if the relative position of the 2-dimensional sub-kernel with reference to the 2-dimensional kernel is top-left or bottom-left;

to the right side of the 2-dimensional sub-kernel, a horizontal padding size equal to the result of subtracting first the number one and then an integral division result of dividing the pre-defined common horizontal padding parameter by 2 from the horizontal dimensional measurement of the 2-dimensional sub-kernel, further reduced by a remainder of dividing the pre-defined common horizontal padding parameter by 2 if and only if the relative position of the 2-dimensional sub-kernel with reference to the 2-dimensional kernel is top-right or bottom-right;

to the top side of the 2-dimensional sub-kernel, a vertical padding size equal to the result of subtracting first the number one and then an integral division result of dividing the pre-defined common vertical padding parameter by 2 from the vertical dimensional measurement of the 2-dimensional sub-kernel, further reduced by a remainder of dividing the pre-defined common vertical padding parameter by 2 if and only if the relative position of the 2-dimensional sub-kernel with reference to the 2-dimensional kernel is top-left or top-right; and

to the bottom side of the 2-dimensional sub-kernel, a vertical padding size equal to the result of subtracting first the number one and then an integral division result of dividing the pre-defined common vertical padding parameter by 2 from the vertical dimensional measurement of the 2-dimensional sub-kernel, further reduced by a remainder of dividing the pre-defined common vertical padding parameter by 2 if and only if the relative position of the 2-dimensional sub-kernel with reference to the 2-dimensional kernel is bottom-left or bottom-right.