Eliminating Bank Conflicts in GPU Mergesort

Graphics Processing Units (GPUs) have emerged as popular architectures for high-performance computing due to their parallelism and low latency context switching capabilities. However, optimizing GPU implementations can be challenging due to the complexity of the architecture, such as the diverse characteristics of memory units. While most optimization efforts focus on parallelism and global memory access, for some algorithms memory conflicts in shared memory, known as bank conflicts, can significantly impact performance. This affects the accuracy of theoretical runtime analysis of GPU algorithms.