## 3 GPS SDR Design for CRPA Using General-Purpose Parallel Processors
### GPU-Based Parallel Correlator
#### 3.2.4 Parallel Reduction in Reallocated Shared Memory  
Once the carrier and code wipeoff is completed, the input inphase and quadrature data and a C/A code replica in shared memory are no longer used by the parallel correlator. Hence, the valuable resource, shared memory, is reallocated for the next operation. The next operation to complete correlation in Figure 5 is to sum the obtained values after the carrier and code wipeoff. Parallel reduction is a well-known parallel algorithm for fast summation of many values. Figure 7 shows a simple example of parallel reduction for summation of four numbers. Thread 1 adds numbers 2 and 3, and thread 2 adds numbers \(-1\) and 1 at the same instruction cycle in this example. Note that adjacent threads accesses adjacent numbers (_i.e._, 2 and \(-1\), or 3 and 1) to prevent shared memory bank conflicts. If thread 1 adds numbers 2 and \(-1\), and thread 2 adds numbers 3 and 1, bank conflicts would occur. (See [45] for detailed discussion of optimized parallel reduction algorithms in GPU.)Before the parallel reduction in Figure 5, each thread sums three values and assigns the sum to the reallocated shared memory. Thus, 256 numbers per thread block are ready for parallel reduction. The number of samples for parallel reduction should be a power of 2 because a half of the numbers are added to the other half of the numbers every instruction cycle. At the first instruction cycle, threads 1 through 128 add two numbers each. At the second instruction cycle, threads 1 through 64 add two numbers each, and so forth. Hence, 256 numbers are added after eight instruction cycles in this parallel algorithm, which is much faster than 255 instruction cycles of serial summation. This parallel reduction should be performed in shared memory rather than global memory because the algorithm requires repeated memory access. Once the summation is completed, the accumulated number is stored as the first element of the 256-element array used for parallel reduction.  
Since 27 thread blocks perform the correlation operation for one tracking channel, the result of parallel reduction of each thread block should be added together for a final result. Different thread blocks cannot communicate each other via shared memory. Thus, those numbers are atomically added to a variable in global memory in our implementation. Atomic addition of 32-bit floating-point numbers in global memory is supported by compute capability 2.x (Table 3). Atomic addition is a serial operation, but serial addition of 27 numbers from 27 thread blocks is not computationally intensive. Computationally intensive summations are already completed by parallel reduction in each thread block. The result of the parallel correlation in Figure 5 is six numbers (an early, a prompt, and a late correlation for inphase and quadrature samples) per tracking channel. The memory copy latency of these six numbers from global memory to host memory is negligible. The GPU kernel for the carrier and code wipeoff is executed for each 1 ms data block. Its execution time for 1 ms data is about 0.59 ms (averaged over 10,000 measurements).