Week 4: Memory Coalescing

In working towards speeding up the ANTT, I’ve had to face some major obstacles when programming GPUs. One of the most significant is memory access patterns.

It turns out, despite the fact that GPUs allow for massive parallelization to quickly execute the ANTT computations, there is a drawback to using GPUs. Namely, if a GPU has a lot of threads executing computations, how do you transfer data to these threads fast enough so that you minimize the number of idle threads?

The answer lies in a technique known as memory coalescing. In a GPU, each group of threads, referred to as “warps,” requests some information from the global memory. Now, when a GPU requests memory, it does not just grab one variable at a time. Rather, it gets large blocks of data from the global memory, as accessing only one variable at a time would be inefficient. If our threads request memory addresses that are scattered randomly across the board, the GPU has to perform multiple, slow transactions to get all threads the data they need. However, if we align our code so that adjacent threads access sequential memory addresses, the hardware can “coalesce” those requests into a single, highly efficient transaction.

For a computationally intensive algorithm like ANTT, it is important to optimize every aspect of our implementation so we save as much time as possible. By carefully choosing how our threads access data from the global memory, we end up saving a lot of time by ensuring our GPU threads are always busy.