fast 2D cross correlation algorithm
If your template or kernel is small, then straight convolution might be the fastest approach. There's a crossover point when performing convolution in the frequency domain is faster than straight time/spatial domain convolution and it can be hardware dependent, but usually when the kernel (template) approaches 1/4-1/2 the size of the image frequency domain convolution is faster.

If you have a multicore machine you can split the larger image into say 4 quadrants and run the spatial convolution on 4 threads and fuse the results together. That should actually be pretty speedy.