Paper Info
Title
Using Dynamic Parallelism for Fine-Grained, Irregular Workloads: A Case Study of the N-Queens Problem.
Abstract
GPU compute devices have become very popular for general purpose computations. However, the SIMD-like hardware of graphics processors is currently not well suited for irregular workloads, like searching unbalanced trees. In order to mitigate this drawback, NVIDIA introduced an extension to GPU programming models called dynamic parallelism. This extension enables GPU programs to spawn new units of work directly on the GPU, allowing the refinement of subsequent work items based on intermediate results without any involvement of the main CPU. This work investigates methods for employing dynamic parallelism with the goal of improved workload distribution for tree search algorithms on modern GPU hardware. For the evaluation of the proposed approaches, a case study is conducted on the n-queens problem. Extensive benchmarks indicate that the benefits of improved resource utilization fail to outweigh high management overhead and runtime limitations due to the very fine level of granularity of the investigated problem. However, novel memory management concepts for passing parameters to child grids are presented. These general concepts are applicable to other, more coarse-grained problems that benefit from the use of dynamic parallelism.
Year
DOI
Venue
2015
10.1109/CANDAR.2015.26
CANDAR
Keywords
Field
DocType
GPU computing,dynamic parallelism,irregular workload,fine-grained tasks,n-queens
Graphics,Search algorithm,Computer science,Task parallelism,Parallel computing,Memory management,Data parallelism,Eight queens puzzle,General-purpose computing on graphics processing units,Granularity
Conference
ISSN
Citations 
PageRank 
2379-1888
4
0.44
References 
Authors
7
4
Name
Order
Citations
PageRank
Max Plauth1267.53
Frank Feinbube2287.30
Frank Schlegel381.21
Andreas Polze426851.57