Various parallel algorithms can be decomposed into programming primitives that share similar patterns. This course focuses on studying these programming primitives and their applicability in computer graphics, specifically in the context of massively parallel processing on GPUs. The course begins by establishing a theoretical foundation, followed by practical examples and real-world applications. We explain two pivotal algorithms: parallel reduction and parallel prefix scan in detail, discussing their variants and different implementations. Afterward, we provide a collection of more advanced techniques and tricks applicable across various domains. At the end of the course, we also briefly discuss code optimization.

Ray-tracing has received great attention over the years due to the high demand for global illumination appliances. Due to its embarrassingly parallel characteristics, the ray-tracing algorithm has been ported to the graphics processing unit (GPU) on heterogeneous systems that run thousands of threads in a single-instruction-multiple-thread fashion. However, the irregularity of ray-tracing causes a performance penalty on the GPU. The control flow divergence and early-termination problems severely degrade the hardware utilization, which makes the GPU computation inefficient while traversing through each iteration of the algorithm. Furthermore, additional overheads caused by data marshalling and load unbalancing negate the benefits of using heterogeneous systems. To tackle these issues, we designed a pipeline-based runtime methodology that leverages the features of heterogeneous system architecture (HSA)-compliant heterogeneous frameworks, such as shared virtual memory and fast kernel dispatching. This method merges the workloads from different iteration stages and dispatches them simultaneously. The merged workload is further assigned to a heterogeneous queue to enhance load balancing and scalability. With the proposed technologies, the performance of ray-tracing is enhanced significantly while effectively increasing the utilization of HSA-compliant heterogeneous systems. Based on the experiment results, the throughput becomes 4.37 times greater than the original setup on average in a single GPU mode and would always yield a greater throughput with a heterogeneous queue on multiple cores.

The prevalence of real time multimedia delivery appliances has led to the developments of a variety of efficient architectures and supporting software technologies. Especially, Ray-Tracing, a well-known physically-based rendering algorithm, has been receiving great attention in research and development. Unfortunately, Ray-Tracing algorithm, being one of the irregular applications, suffers from the performance penalty on SIMT-based machines such as GPGPUs. Specifically, the branch divergence and early-termination issues caused by the irregularity severely degrade the overall hardware utilization, which makes the computation on GPGPU inefficient while traversing through each iterative stages of the algorithm. The probabilistic termination of ray-tracing paths poses a critical issue for efficient parallel execution on GPGPUs. Moreover, the conventional overhead of memory transfer limits the effectiveness of data marshaling for GPU computing. To address these problems, we proposed a pipeline-based Runtime technique which leverages the feature of Shared-Virtual-Memory (SVM) of the HSA-compliant systems that combines and regroups the workload from different stages into one kernel computation in Ray-Tracing and greatly improved the resource utilization of GPGPU. Our experiments illustrate that the proposed runtime technique can boost ray-tracing performance significantly while effectively increase the utilization of HSA-compliant heterogeneous systems.