## 3 GPS SDR Design for CRPA Using General-Purpose Parallel Processors
### Hardware Parallelism  
The GPU kernel performing the data synthesis and the carrier and code wipeoff handles (1,080\(N+360N\))/1,504\(N\approx 96\%\) computational load of the CRPA processing. The remaining \(64N/1504N\approx 4\%\) computation is for the signal covariance calculation (Table 2). Since the CPU and GPU are different hardware, they can perform different tasks in parallel. The covariance calculation can be also performed by another GPU kernel, but the quad-core CPU (Intel Core i7 950) is powerful enough to complete the covariance calculation while the GPU kernel performs the data synthesis and the carrier and code wipeoff. Thus, we assign the covariance calculation to CPU and run it with GPU  
Figure 7: Simple example of parallel reduction for the summation of four numbers. in parallel (Figure 8). For parallel processing on the quad-core CPU, we generate 10 CPU threads for the covariance calculation. The covariance matrix \(\mathrm{X}^{\star}\mathrm{X}^{T}\) in Equation (4) is a Hermitian matrix (_i.e._, it is equal to its own conjugate transpose). For a four-element antenna array, \(\mathrm{X}^{\star}\mathrm{X}^{T}\) is a 4-by-4 matrix. Since it is a Hermitian matrix, we need to calculate the upper triangular part only (_i.e._, 10 numbers) and take complex conjugate of calculated numbers to obtain the lower triangular part. Thus, we assign one CPU thread for calculating each of 10 numbers in the upper triangular part of the covariance matrix. Further, we assign five CPU threads for signal tracking operations based on the correlation results from a previous millisecond (1 thread per antenna and 1 thread for beamsteering channels result in 5 threads). Although we generate 15 threads for the covariance calculation and signal tracking, the quad-core CPU can run up to eight threads simultaneously by its hyper-threading technology. Hence, the generated 15 threads run together only by splitting CPU time. The multi-threaded covariance calculation on CPU is further optimized by single instruction multiple data (SIMD) instructions. The execution time of 10 CPU threads for the covariance calculation is about 0.29 ms. The tracking operation is relatively light weight, and the execution time of five CPU threads for tracking is about 0.07 ms. Figure 8 shows the timing diagram of the parallel operations by CPU and GPU. Although the tracking and the covariance calculation by CPU seem to run independently and simultaneously in this figure, it is not exactly true. As already explained, five threads for tracking and 10 threads for covariance calculation share CPU time. However, the CPU operations and the GPU operations run completely in parallel because they are different hardware. Another important hardware parallelism exists within the graphics card. The input data should be copied from host memory to device global memory first before any GPU operations, and the latency of this memory copy is significant due to limited PCI-E bandwidth (Figure 6). However, NVIDIA GPUs have dedicated DMA engines. Thus, the latency of the host-to-device memory copy by the GPU DMA engine can be completely hidden behind the GPU computation provided that the memory copy  
Figure 8: Hardware parallelism with CPU, GPU compute engine, and GPU DMA engine in addition to thread-level parallelism by multi-core CPU and GPU. Total processing time for 1 ms data is about 0.75 ms.  
requires less execution time than the computation. In order to realize this parallelism, we implement two data buffers (so called \"ping-pong\" buffers) and perform the GPU computation on 1 ms data within one buffer while the DMA engine copies next 1 ms data to the other buffer and vice versa. In addition, two CUDA streams should be created (one for data copy and the other for computation) and GPU memories should be allocated as page-locked memory to utilize asynchronous CUDA functions (see [46] for a detailed discussion of overlapping data copy and computation). Page-locked memory allows faster memory access as an additional benefit.