Towards Methods to Exploit Concurrent Data Structures on Heterogeneous CPU/iGPU Processors

Heterogeneous processors, consisting of CPU cores and an integrated GPU on the same die, are currently the standard in desktop and mobile platforms. The number of CPU cores is increased with every new generation, and integrated GPUs are constantly being improved in performance and energy efficiency. This raises the importance of developing programming methods and techniques to benefit general purpose applications on heterogeneous processors as more parallelism can be achieved. This dissertation addresses this challenge by studying new ways of exploiting parallelism on CPU cores as well as the integrated GPU, focusing on blocking and non-blocking data structures.A new thread synchronization mechanism for parallel geometric algorithms dubbed Spatial Locks is first introduced. This synchronization mechanism ensures thread synchronization on geometric algorithms that perform concurrent operations on geometric surfaces in two- or three-dimensional spaces. A parallel algorithm for mesh simplification is chosen to illustrate the Spatial Locks usefulness when parallelizing geometric algorithms with ease on multi-core machines. Experimental results show the advantage of using this synchronization mechanism where significant computational improvement can be achieved compared to alternative approaches.Non-blocking data structures are commonly used by many multi-threaded applications, and their implementation is based on the use of atomic operations. New computing architectures, such as Intel CPU/iGPU processors, have incorporated data-parallel processing through SIMD instructions, including in some cases support for atomic SIMD instructions and SIMT processing on the integrated GPU. A new framework called \textit{SIMD-node Transformations} to implement non-blocking data structures using multi-threaded and SIMD processing is proposed. As a result, it is shown that one- and multi-dimensional data structures, such as skiplists, k-ary trees and multi-level lists, can embrace SIMD processing through these transformations. Finally, important performance gains obtained when applying these transformations to concrete data structures are reported