Scalable Split and Gather Primitives for the GPUSuryakant Patidarskp@research.iiit.ac.inCVIT, IIIT HyderabadP. J. Narayananpjn@iiit.ac.inCVIT, IIIT HyderabadAbstractWe present efficient implementations of two primitives for datamapping and distribution on the massively multithreaded architec-ture of the GPUs in this paper. The split primitive distributes el-ements of a list according to their category. Split is an importantoperation for data mapping and is used to build data structures,distribute work load, etc., in a massively parallel environment.The gather/scatter primitive performs fast, distributed data move-ment. Efficient data movement is critical to high performance onthe GPUs as suboptimal memory accesses can pay heavy penalties.The split we implement is a generalization ofthe binary split [Blel-loch 1990] and is implemented using the shared memory and theatomic operations available on them. The split performance scaleslogarithmically with the number ofcategories, linearly with the listlength, and linearly with the number of cores on the GPU. Thismakes it useful for applications that deal with large data sets. Wealso present a variant of split that partitions the indexes of records.This facilitates the use ofthe GPU as a coprocessor for split or sort,with the actual data movement handled separately. We can computethe split indexes for a list of32 million records in 180 millisecondsfor a 32-bit key and in 800 ms for a 96-bit key. The instantaneouslocality ofmemory references play a critical role in data movementon the current GPU memory architectures. For scatter and gatherinvolving large records, we use collective data movement in whichmultiple threads cooperate on individual records to improve the in-stantaneous locality. The split, gather, and their combinations findmany applications and expect our primitives will be used by fu-ture GPU programmers. We show sorting of 16 million 128-byterecords in 379 milliseconds with 4-byte keys and in 556 ms with8-byte keys.1IntroductionThe Graphics Processor Unit (GPU) has been increasingly used fora wide range of problems involving heavy computations in graph-ics, computer vision, science, etc. The main attraction is the highcomputation powerperunit cost; today’s off-the-shelfGPUs deliver1 TFLOPs ofsingle precision power for under $400. The program-ming model available on them have also become general purposewith the advent of CUDA [Nvidia 2008] and the newly-adoptedstandard of OpenCL [Khronos 2009]. However, extracting the bestperformance from the GPU requires a deep knowledge of its inter-nal architecture including the core layout, memory, scheduling, etc.A lot of this information is not publicly available; the architecturealso changes much more frequently than the architecture of multi-core microprocessors.One way to exploit the GPU’s computing power effectively isthrough high level primitives upon which other computations arebuilt. All architecture specific optimizations can be incorporatedinto the primitives by designing and implementing them carefully.An application can gain high performance ifits computationally in-tensive parts can be broken down into such primitives. The map-reduce primitive has recently been very effective in distributingcompute intensive applications to a cluster ofprocessors [Dean andGhemawat 2004]. GPUs essentially follow the data parallel modelin which kernels of code are applied on many data elements inparallel. Blelloch defined several data parallel primitives includ-ing scan, reduce, and binary split [Blelloch 1989; Blelloch 1990].Sengupta et al. implemented these primitives on the GPU underCUDA [Sengupta et al. 2007] which has been made available underthe CUDPP libarary [Harris et al. 2007]. Several applications havebeen built using these primitives including kd-trees [Zhou et al.2008], octrees [Zhou et al. April, 2008], BVH trees [Lauterbachet al. 2009], etc.In this paper, we present efficient and scalable implementations oftwo data mapping primitives with wide applications on the GPU.Data mapping and distribution are used in distributed applicationsfor data structure building, load balancing, etc. We present the splitprimitive that distributes data elements based on a category eachbelongs to. This is a generalization of the binary split and has beenfound to be critical for all throughput computing [Siggraph AsiaCourses 2008]. We also define index-variants of split that defer theactual data movement, which is useful to handle bulky data records.We also present efficient implementations ofthe scatter and gatherprimitives on the GPU that work in conjunction with the index-variants of split. The separation of index computation from datamovement enables the use of the GPU as a fast co-processor forsplit and sort, with data movement handled separately. The GPUperformance is highly sensitive to memory access patterns; subop-timal implementation can pay heavy penalty. Optimized primitivesare basic building blocks using which many regular and irregularapplications can be built.The main contributions ofthis paper are the following:1. We present efficient and scalable implementations ofthe splitand split-index primitives for the GPU. These can be used tosplit a list to its category or to sort a list of numbers. We cansplit 32 million numbers using a 16 bit key and 32 bit indexvalue in 91 ms and a 96 bit key and 32 bit index value in 804ms. We can compute the split-index for 64 million recordswith 32-bit keys in 350 milliseconds.2. We improve and exploit the instantaneous locality of mem-ory references to improve the data movement performance onthe GPU. The coherence in memory access between differentcompute elements is critical to memory performance on theGPUs, like caching on the CPUs.3. We present efficient implementaiton of the gather and scatterprimitives for fast data movement within the GPU, taking ad-vantage of the instantaneous locality of memory references.We can randomly scatter 16 million 128-byte records in about290 milliseconds and 8 million 256-byte records in under 150ms.4. We show a few applications ofthe split and gather primitives.We can sort 128 million 32-bit numbers in about 650 mil-liseconds, 128 million 64-bit numbers in about 1.5 secondsand 128 million 128-bit numbers in about 4 seconds. Sort-ing large records maps to a split-index followed by a gather.We show sorting of 16 million 128-byte records in 379 mil-liseconds with 4-byte keys and in 556 ms with 8-byte keys.We also discuss how these primitives can be used to build dis-tributed data structures for applications like ray tracing and
