shogun-toolbox/shogun — pull request #2118 by msahasrabudhe (2014-04-09 10:26:22+00:00)
Title: An optimised version of convolution (GSoC task)

An optimised implementation of the convolution operation in src/shogun/mathematics/Convolve.cpp. The function uses OpenMP for parallel computing, if a processor with multiple cores is being used. Compile using

```
c++ -o convolve convolve.cpp -g -lrt -fopenmp -O3
```

Test using

```
./convolve
```

The program outputs a running time in milliseconds a matrix and kernel, both randomly initialized and conforming to the size given during execution. The matrix and kernel are always assumed to be square matrices.

**Optimisations done**

1. Matrices are stored as contiguous memory blocks.
2. Use of multiple cores to perform computations: Since the computation at pixel (i, j) is independent of pixel (m, n) (m != i and n != j), computations can be distributed to several cores.
3. Flipping the kernel horizontally and vertically before computing the convolution: Saves us several addition and multiplication operations which would be done refer to elements of the kernel.
4. Pre-computing offsets to elements that would be involved in a computation: If we fix a pixel (x, y), an offset is computed which can be used to refer to the region around (x, y) directly, thus reducing the number of addition and multiplication operations required.

**Results of tests**

Tabulated below are runtimes for several matrix and kernel sizes, compared between the optimised and non-optimised version. All times are in milliseconds.

System information: Linux 3.2.0-60-generic, Ubuntu 12.04 64-bit, Intel(R) Core(TM) i3-2120 CPU @ 3.30GHz (quad core), 4 GB memory.

|Matrix size | Kernel size | Runtime, with optimisations | Runtime, without optimisations|
|-------------|-------------|-----------|------------|
| 10 | 2 | 0.062256 | 0.001485 |
| 10 | 4 | 0.055258 | 0.00115 |
| 10 | 8 | 0.054877 | 0.001431 |
| 100 | 2 | 0.10902 | 0.120909 |
| 100 | 4 | 0.140958 | 0.309394 |
| 100 | 8 | 0.248173 | 1.01533 |
| 100 | 16 | 0.683718 | 3.47518 |
| 100 | 32 | 1.63621 | 7.26863 |
| 100 | 64 | 2.07949 | 7.35253 |
| 1000 | 2 | 3.22446 | 6.1538 |
| 1000 | 4 | 8.22482 | 15.7314 |
| 1000 | 8 | 23.2947 | 55.5671 |
| 1000 | 16 | 87.6732 | 226.192 |
| 1000 | 32 | 328.684 | 875.173 |
| 1000 | 64 | 1382.11 | 3430.45 |
| 1000 | 128 | 4827.18 | 12065.5 |
| 1000 | 256 | 15185.1 | 35698.3 |
| 2000 | 2 | 12.9331 | 21.8078 |
| 2000 | 4 | 36.746 | 63.2698 |
| 2000 | 8 | 91.5461 | 224.739 |
| 2000 | 16 | 425.304 | 916.547 |
| 2000 | 32 | 1500.66 | 3612.84 |
| 2000 | 64 | 5505.56 | 14642.8 |
| 2000 | 128 | 19958.5 | 56051.6 |
| 2000 | 256 | 109162 | 192899 |