Parallel patterns: merge sort
An introduction to tiling with dynamic input data identification
Li-Wen Chang and Jie Lv
Abstract
This chapter introduces the merge sort pattern whose parallelization requires each thread to dynamically identify its input position ranges. The fact that the input ranges are data dependent also creates extra challenges when we use the tiling technique to conserve memory bandwidth. As a result, we introduce the use of circular buffers to allow us to make full use of the memory data loaded. We show that introducing a more complex data structure such as a circular buffer can significantly increase the complexity of the code that uses these data structures. Thus, we introduce a simplified buffer access model ...
Get Programming Massively Parallel Processors, 3rd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
