Abstract
NVIDIA’s Compute Unified Device Architecture (CUDA) enabled GPUs become accessible to mainstream programming. Abundance of simple computational cores and high memory bandwidth make GPUs ideal candidates for data parallel applications. However, its potential for executing applications that combine task and data parallelism has not been explored in detail. CUDA does not provide a viable interface for creating dynamic tasks and handling load balancing issues. Any support for such has to be orchestrated entirely by the CUDA programmer today.
In this work, we introduce a finish-async style API to GPU device programming as first step towards task parallelism. We present the design and implementation details of our new intra-device inter-SM work-stealing runtime system. We compare performance results using our runtime to direct execution on the device as well as past work on GPU runtimes. Finally, we show how this runtime can be targeted by extensions to the high-level CnC-CUDA programming model.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
National Supercomputing Center in Tianjin, Tianhe-1A (November 2010), http://www.top500.org/system/details/10587
Nvidia, CUDA (2011), http://developer.nvidia.com/cuda-action-research-apps
Charles, P., et al.: X10: an object-oriented approach to non-uniform cluster computing. In: OOPSLA, NY, USA, pp. 519–538 (2005)
Grossman, M., Simion Sbîrlea, A., Budimlić, Z., Sarkar, V.: CnC-CUDA: Declarative Programming for GPUs. In: Cooper, K., Mellor-Crummey, J., Sarkar, V. (eds.) LCPC 2010. LNCS, vol. 6548, pp. 230–245. Springer, Heidelberg (2011)
Duran, A., et al.: Barcelona openmp tasks suite: A set of benchmarks targeting the exploitation of task parallelism in openmp. In: ICPP 2009, pp. 124–131 (2009)
Cederman, D., Tsigas, P.: GPU-quicksort: A practical quicksort algorithm for graphics processors. J. Exp. Algorithmics 14 (January 2010)
The Java Grande Forum benchmark suite, http://www.epcc.ed.ac.uk/javagrande/javag.html
Lastras-Montano, M.A., et al.: Dynamic work scheduling for GPU systems. In: International Workshop of GPUs and Scientific Applications, GPUScA 2010 (2010)
X10 2.1 CUDA, http://x10.codehaus.org/x10+2.1+cuda
Cederman, D., Tsigas, P.: On sorting and load balancing on GPUs. SIGARCH Comput. Archit. News 36 (June 2009)
Augonnet, C., Thibault, S., Namyst, R., Wacrenier, P.-A.: StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures. In: Sips, H., Epema, D., Lin, H.-X. (eds.) Euro-Par 2009. LNCS, vol. 5704, pp. 863–874. Springer, Heidelberg (2009)
Augonnet, C., Thibault, S., Namyst, R., Wacrenier, P.A.: Starpu: a unified platform for task scheduling on heterogeneous multicore architectures. Concurr. Comput.: Pract. Exper. 23, 187–198 (2011)
Ayguadé, E., Badia, R.M., Igual, F.D., Labarta, J., Mayo, R., Quintana-Ortí, E.S.: An Extension of the StarSs Programming Model for Platforms with Multiple GPUs. In: Sips, H., Epema, D., Lin, H.-X. (eds.) Euro-Par 2009. LNCS, vol. 5704, pp. 851–862. Springer, Heidelberg (2009)
Opencl 1.1, http://www.khronos.org/opencl/
Habanero-C, https://wiki.rice.edu/confluence/display/habanero/habanero-c
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chatterjee, S., Grossman, M., Sbîrlea, A., Sarkar, V. (2013). Dynamic Task Parallelism with a GPU Work-Stealing Runtime System. In: Rajopadhye, S., Mills Strout, M. (eds) Languages and Compilers for Parallel Computing. LCPC 2011. Lecture Notes in Computer Science, vol 7146. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36036-7_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-36036-7_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36035-0
Online ISBN: 978-3-642-36036-7
eBook Packages: Computer ScienceComputer Science (R0)