PPoPP 2016
Sat 12 - Wed 16 March 2016 Barcelona, Spain
Mon 14 Mar 2016 16:45 - 17:10 at Mallorca+Menorca - GPUs and Scheduling Chair(s): Christophe Dubach

Multisplit is a broadly useful parallel primitive that permutes its input data into contiguous buckets or bins, where the function that categorizes an element into a bucket is provided by the programmer. Due to the lack of an efficient multisplit on GPUs, programmers often choose to implement multisplit with a sort. However, sort does more work than necessary to implement multisplit, and is thus inefficient. In this work, we provide a parallel model and multiple implementations for the multisplit problem. Our principal focus is multisplit for a small number of buckets. In our implementations, we exploit the computational hierarchy of the GPU to perform most of the work locally, with minimal usage of global operations. We also use warp-synchronous programming models to avoid branch divergence and reduce memory usage, as well as hierarchical reordering of input elements to achieve better coalescing of global memory accesses. On an NVIDIA K40c GPU, for key-only (key-value) multisplit, we demonstrate a 3.0-6.7x (4.4-8.0x) speedup over radix sort, and achieve a peak throughput of 10.0 G keys/s.

Mon 14 Mar
Times are displayed in time zone: (GMT+01:00) Greenwich Mean Time : Belfast change

PPoPP-2016-papers
16:20 - 18:00: Main conference - GPUs and Scheduling at Mallorca+Menorca
Chair(s): Christophe DubachUniversity of Edinburgh
PPoPP-2016-papers16:20 - 16:45
Talk
Yangzihao Wang, Andrew DavidsonUniversity of California, Davis, Yuechao PanUniversity of California, Davis, Yuduo WuUniversity of California, Davis, Andy RiffelUniversity of California, Davis, John D. OwensUniversity of California, Davis
Link to publication DOI
PPoPP-2016-papers16:45 - 17:10
Talk
Saman AshkianiUniversity of California, Davis, Andrew DavidsonUniversity of California, Davis, Ulrich MeyerGoethe-Universitat Frankfurt am Main, John D. OwensUniversity of California, Davis
Link to publication DOI
PPoPP-2016-papers17:10 - 17:35
Talk
Tiziano De MatteisUniversity of Pisa, Gabriele MencagliUniversity of Pisa
Link to publication DOI
PPoPP-2016-papers17:35 - 18:00
Talk
Jing LiWashington University in St. Louis, Kunal AgrawalWashington University in St. Louis, Sameh ElniketyMicrosoft Research, Yuxiong HeMicrosoft Research, I-Ting Angelina LeeWashington University in St. Louis, Chenyang LuWashington University in St. Louis, Kathryn S McKinleyMicrosoft Research
Link to publication DOI