Week 5: The Difficulty of Parallelizing Recursion

Recursion is a powerful technique for tackling tough problems through the implementation of a process that calls itself – i.e. breaks down a problem by dividing it into smaller, more easily executable tasks. The FFT, which happens to be the mathematical sister of the ANTT, is traditionally implemented via recursion. It works brilliantly at dividing a large polynomial into two parts, dealing with each of those and combining them again. Using a standard CPU, recursion does the job without any trouble.

Not so much with GPUs.

Let’s take a closer look at the problem of memory. Every time a recursive function is called on a computer, the current data is stored in special memory called the “stack”. CPUs are equipped with enormous stacks, allowing them to deal with recursion without any issue. However, GPUs gain phenomenal processing speeds due to their ability to run multiple threads concurrently. Since when we try and parallelize recursion, and all the threads try to build their respective stacks, the localized memory in the GPU will get overloaded immediately, resulting in either a bottleneck or crash.

To allow our program to harness the power of the GPU hardware, we have to completely break away from recursion. We don’t allow the algorithm to call itself anymore but rewrite it into an iteration. That means unrolling the mathematics of the operation into a simple, bottom-up loop process called a butterfly network. Iteration eliminates the need for stack memory and allows for the mapping of the procedure onto the concurrent threads of the GPU while allowing for the recursive ANTT structure to be preserved.