For a project I need to do convolution and i use gpu for calculations. Sometimes I have to deal with kernel sizes of 50x50 and this size of kernel is sufficiently large that it chokes the gpu. (not enough memory svailable by the gpu) I need to find a way to break the kernel into smaller sizes (8x8 or similar) and do the convolution this way (i.e. piece by piece and later stitch together) so that I can realize gpu enhancements. What is the best way to break these kernels into smaller pieces? (I have no prior knowledge of kernel size so the solution must be something I can deal with in run time. )

  • $\begingroup$ It's not clear from your description what the bottleneck of your application is, so you may not get very specific answers. If you can share more details, that may help. $\endgroup$
    – Jason R
    Commented Dec 18, 2012 at 16:37
  • $\begingroup$ @JasonR the bottleneck is the kernel size. The internal scratch memory of the gou cannot deal with large kernels. I need to break this operation 10x10 type kernels and run. I just don't know how to break the kernels. $\endgroup$
    – Ktuncer
    Commented Dec 19, 2012 at 0:06
  • 1
    $\begingroup$ This link blogs.msdn.com/b/nativeconcurrency/archive/2011/11/01/… might help $\endgroup$
    – Naresh
    Commented Dec 19, 2012 at 4:18

2 Answers 2


Yes, you can split them up. Convolution is a linear process, which means that superposition holds. Thus, you can break up any convolution kernel $k$ into multiple parts ($k_1, k_2, ... k_N$) such that $k = \sum k_i$.

For example, if you had a convolution kernel that looked like [1 2 3 4] (granted this is a silly kernel, but does fine for purposes of illustration), you could break it up into the following kernels, [1 2 0 0] and [0 0 3 4]. Now, you could simply do the convolutions like normal and then add the results together. The sum would be equal to the convolution product of the original kernel.

Doing that would be inefficient, though, both in terms of computations and memory. Instead, you could simply drop the 0's at the ends of the "sub-kernels", and do the convolutions using [1 2] and [3 4]. The one tricky part to this is that you have to offset the results before adding them together to get the correct answer.

  • $\begingroup$ +1 , very nice. Though you will need twice the amount of memory (at least) for this method. $\endgroup$ Commented Dec 20, 2012 at 0:43

The convolution operation is associative.

$(S ** g) ** h = S ** ( g ** h ) $

This means that if you find two kernels $g,h$ such that $g**h = k$, (where $k$ is your kernel), you can split your kernel into several parts, and apply each one individually. Each of the kernels can be smaller in size. The most known example of such kernels are Gaussian kernels.

Sometimes, it is even possible to split the kernel into two parts, such that each works only on one dimension. This quality is also possessed by Gaussian kernels.

To sum up, check if your kernel can be represented as convolution of two smaller kernels. This can be found out by checking the rank of the matrix. If it is equal to 1, it is separable. (That is because all of the rows are linear combinations of the first row).

  • $\begingroup$ I don't know the kernel until run time. What is the best way to separate kernels? Or is there an operation to find out if the kernel is separable ? $\endgroup$
    – Ktuncer
    Commented Dec 19, 2012 at 16:26
  • $\begingroup$ @Ktuncer, please see edit $\endgroup$ Commented Dec 19, 2012 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.