Understanding the Performance of Concurrent Data Structures on Graphics Processors

In this paper we revisit the design of concurrent data structures -- specifically queues -- and examine their performance portabilitywith regard to the move from conventional CPUs to graphics processors. We have looked at both lock-based and lock-free algorithmsand have, for comparison, implemented and optimized the same algorithms on both graphics processors and multi-core CPUs.Particular interest has been paid to study the difference between the old Tesla and the new Fermi and Kepler architecturesin this context.We provide a comprehensive evaluation and analysis of our implementations on all examined platforms.Our results indicate that the queues are in general performance portable, but that platform specific optimizations are possibleto increase performance. The Fermi and Kepler GPUs, with optimized atomic operations, are observed to provide excellent scalabilityfor both lock-based and lock-free queues