Faster full convolution for GpuCorrMM

As a follow-up to #2023, this PR adds [caffe's backward pass wrt. inputs](https://github.com/BVLC/caffe/blob/master/src/caffe/layers/conv_layer.cu#L98) to GpuCorrMM to implement `border_mode="full"`. It passes all the tests and it's about 2-4x faster than simulating a full convolution with a padded valid convolution. On the way, it cleans up the code and adds some more elaborate documentation.

There are some caveats, though, all stemming from the fact that the implementation in caffe is meant as a backward pass for a valid correlation:
* With `border_mode="valid"`, `GpuCorrMM` doesn't flip the kernels, but with `border_mode="full"`, it does.
* With `border_mode="valid"`, `subsampling` is for subsampling the output, but with `border_mode="full"`, it is for upsampling the input.
* With `border_mode="valid"`, `pad` is for padding the input, but with `border_mode="full"`, it is for cropping the output.
* With `border_mode="full"`, it needs a different memory layout for the kernels.

Currently, `GpuCorrMM` directly wraps the underlying algorithm, and `local_conv_gemm()` copes with the different peculiarities, because I wasn't sure whether the `GpuCorrMM` Op should be inserting dimshuffles, kernel flips and `gpu_contiguous`es on its own.

Looking at the end result, although it's quite fast, `local_conv_gemm()` now basically undoes everything that `ConvOp.grad()` does. It might be possible to write an optimizer that replaces the gradient of a valid convolution with a properly parameterized `GpuCorrMM` Op, instead of just replacing the full convolution Op that is part of the gradient (introducing redundant dimshuffles etc. on the way). This way we would leverage the caffe implementation better.
The alternative would be to modify the CUDA code to perform a subsampled, padded, full correlation, as would be expected from a Gpu Correlation Op. This would be cleaner, but it would also mean a lot more work and we wouldn't profit as much from caffe's implementation for the case of `subsampling != (1,1)` or `padding != (0,0)` (granted, this may be an uninteresting case in practice anyway).
/edit: Another alternative would be splitting this into two Ops: `GpuCorrMM` for valid correlation with padding and subsampling (the caffe forward pass), and `GpuConvMM` for full convolution with upsampling and cropping (the caffe backward pass). This way it would be obvious how the operations differ, but the memory layout required for the second Op would still be unintuitive.
Yet another alternative would be splitting it into `GpuCorrMM` and `GpuCorrMM_gradInput`. This way it would be obvious how to use `GpuCorrMM_gradInput` for computing the gradient of `GpuCorrMM`. We could even add `GpuCorrMM_gradKernel` for the gradient wrt. weights; it seems caffe does things slightly different there as well.
In both cases, `GpuCorrMM` should get a `grad()` method to define its gradient (so it can be used directly in a CNN to avoid kernel flipping and whatnot) and `local_conv_gemm()` should still be able to replace any `GpuConv` instances with a gemm-based Op (so it can be used with existing CNN implementations).
We use c_code_helper in a few other op. So I would go with that name.


I'm good with the idea of merging ops later. If this PR is stable and give
more performance then the current master, it can be merged. But I think we
need to figure out how to fix @stencilman bug.


@stencilman, I understand your script is complicated. Can you dump your
Theano function and make a small python scrip that load it and init good
input value to the function that generate the error?

http://www.deeplearning.net/software/theano/tutorial/debug_faq.html?highlight=dump%20function#dumping-a-function-to-help-debug

I suppose the problem happen in the first call to the theano function. Is
that the case?

@f0k, it is easy to add the batch size to the GpuConv op. You just need to
add a parameter to the GpuConv.__init__, store it as a member, modify
__eq__ and __hash__ to check it and modify the op in cuda/opt.py to pass it
to it. My sentence is long, but it is about 5-10 lines of codes. If you
want me to do it, just ask and I'll do it. That way, you can take into
account the fact when it is set. Just make sure the opt don't crash if only
some of the shapes are know. It is fine to do it only if we know all shapes.

thanks





On Tue, Aug 19, 2014 at 10:15 AM, Jan Schlüter <notifications@github.com>
wrote:

> In theano/sandbox/cuda/opt.py:
>
> > -        kern = gpu_contiguous(kern)
> > -        return [GpuCorrMM(node.op.border_mode, node.op.subsample)(img, kern)]
> > +        border_mode = node.op.border_mode
> > +        subsample = node.op.subsample
> > +        pad = (0,0)
> > +        if (border_mode == 'full') and (subsample != (1,1)):
> > +            # need to simulate this via a padded valid convolution
> > +            pad = 'auto'
> > +            border_mode = 'valid'
> > +        if (border_mode == 'valid'):
> > +            # need to flip the kernel for valid convolution
> > +            kern = kern[:, :, ::-1, ::-1]
> > +            # call GpuCorrMM
> > +            # TODO: call GpuCorrMM_gradWeights instead if appropriate
> > +            return [GpuCorrMM('valid', subsample, pad)(
> > +                    gpu_contiguous(img), gpu_contiguous(kern))]
>
> Okay, from my benchmark the magic formula seems to be:
>
> if batchsize * kernelHeight * kernelWidth < inputChannels * outputHeight * outputWidth:
>     use GpuCorrMMelse:
>     use GpuCorrMM_gradWeights
>
> Unfortunately, even if ConvOp knows about the shapes, GpuConv only knows
> about image and kernel width and height and the number of input channels,
> but not about the batchsize. So for now I'll have the optimizer decide
> based on kernel and output size, following your suggestion -- this gets
> most cases correct already.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/Theano/Theano/pull/2033/files#r16416429>.
>