Research PaperNo Access

RDMKE: Applying Reuse Distance Analysis to Multiple GPU Kernel Executions

Mohsen Kiani

Department of Computer Engineering and Information Technology, Razi University, Kermanshah, Iran

E-mail Address: kiani.mohsen@razi.ac.ir

Search for more papers by this author

and

Amir Rajabzadeh

http://orcid.org/0000-0002-5826-9147

Department of Computer Engineering and Information Technology, Razi University, Kermanshah, Iran

E-mail Address: rajabzadeh@razi.ac.ir

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0218126619502451Cited by:1 (Source: Crossref)

Abstract

Modern GPUs can execute multiple kernels concurrently to keep the hardware resources busy and to boost the overall performance. This approach is called simultaneous multiple kernel execution (MKE). MKE is a promising approach for improving GPU hardware utilization. Although modern GPUs allow MKE, the effects of different MKE scenarios have not adequately studied by the researchers. Since cache memories have significant effects on the overall GPU performance, the effects of MKE on cache performance should be investigated properly. The present study proposes a framework, called RDMKE (short for Reuse Distance-based profiling in MKEs), to provide a method for analyzing GPU cache memory performance in MKE scenarios. The raw memory access information of a kernel is first extracted and then RDMKE enforces a proper ordering to the memory accesses so that it represents a given MKE scenario. Afterward, RDMKE employs reuse distance analysis (RDA) to generate cache-related performance metrics, including hit ratios, transaction counts, cache sets and Miss Status Holding Register reservation fails. In addition, RDMKE provides the user with the RD profiles as a useful locality metric. The simulation results of single kernel executions show a fair correlation between the generated results by RDMKE and GPU performance counters. Further, the simulation results of 28 two-kernel executions indicate that RDMKE can properly capture the nonlinear cache behaviors in MKE scenarios.

This paper was recommended by Regional Editor Zoran Stamenkovic.

Keywords:

References

1. W.-M. Hwu , What is ahead for parallel computing, J. Parallel Distrib. Comput. 74 (2014) 2574–2581. Web of Science, Google Scholar
2. B. Jang, D. Schaa, P. Mistry and D. Kaeli , Exploiting memory access patterns to improve memory performance in data-parallel architectures, IEEE Trans. Parallel Distrib. Syst. 22 (2011) 105–118. Web of Science, Google Scholar
3. D. Li, M. Rhu, D. R. Johnson, M. O’Connor, M. Erez, D. Burger, D. S. Fussell and S. W. Redder , Priority-based cache allocation in throughput processors, 2015 IEEE 21st Int. Symp. High Performance Computer Architecture (HPCA) (IEEE, New York, 2015), pp. 89–100. Google Scholar
4. M. Kiani and A. Rajabzadeh , Efficient cache performance modeling in gpus using reuse distance analysis, ACM Trans. Archit. Code Optim. 15 (2018) 1–24. Web of Science, Google Scholar
5. F. Candel, S. Petit, J. Sahuquillo and J. Duato , Accurately modeling the on-chip and off-chip gpu memory subsystem, Future Gener. Comput. Syst. 82 (2018) 510–519. Web of Science, Google Scholar
6. A. Bakhoda, G. L. Yuan, W. W. Fung, H. Wong and T. M. Aamodt , Analyzing cuda workloads using a detailed gpu simulator, IEEE Int. Symp. Performance Analysis of Systems and Software (IEEE, New York, 2009), pp. 163–174. Google Scholar
7. K. Beyls and E. D’Hollander , Reuse distance as a metric for cache behavior, Proc. IASTED Conf. Parallel and Distributed Computing and Systems, Vol. 14 (IASTED, Anaheim, USA, 2001), pp. 350–360. Google Scholar
8. D. Wang and W. Xiao , A reuse distance based performance analysis on gpu l1 data cache, 2016 IEEE 35th Int. Performance Computing and Communications Conf. (IPCCC) (IEEE, New York, 2016), pp. 1–8. Google Scholar
9. M. Kiani and A. Rajabzadeh, Rdgc: A reuse distance-based approach to gpu cache performance analysis, to appear in Comput. Inform. (2019). Google Scholar
10. C. Nugteren, G.-J. van den Braak, H. Corporaal and H. Bal , A detailed gpu cache model based on reuse distance theory, 2014 IEEE 20th Int. Symp. High Performance Computer Architecture (HPCA) (IEEE, New York, 2014), pp. 37–48. Google Scholar
11. NVIDIA, Kepler white paper (2012). Accessed on 20 February 2017. Google Scholar
12. S. Hong and H. Kim , An analytical model for a gpu architecture with memory-level and thread-level parallelism awareness, Proc. 36th Annual Int. Symp. Computer Architecture (ACM, New York, 2009), pp. 152–163. Google Scholar
13. J. Sim, A. Dasgupta, H. Kim and R. Vuduc , A performance analysis framework for identifying potential benefits in gpgpu applications, Proc. 17th ACM SIGPLAN Symp. Principles and Practice of Parallel Programming (ACM, New York, 2012), pp. 11–22. Google Scholar
14. S. S. Baghsorkhi, M. Delahaye, W. D. Gropp and W. H. Wen-Mei , Analytical performance prediction for evaluation and tuning of gpgpu applications, Workshop on EPHAM2009, in Conjunction with CGO (Citeseer, Seattle, WA, 2009), pp. 1–10. Google Scholar
15. S. S. Baghsorkhi, M. Delahaye, S. J. Patel, W. D. Gropp and W.-M. Hwu , An adaptive performance modeling tool for gpu architectures, Proc. 15th ACM SIGPLAN Symp. Principles and Practice of Parallel Programming (ACM, New York, 2010), pp. 105–114. Google Scholar
16. S. S. Baghsorkhi, I. Gelado, M. Delahaye and W.-M. Hwu , Efficient performance evaluation of memory hierarchy for highly multithreaded graphics processors, Proc. 17th ACM SIGPLAN Symp. Principles and Practice of Parallel Programming (ACM, New York, 2012), pp. 23–34. Google Scholar
17. J.-C. Huang, J. H. Lee, H. Kim and H.-H. S. Lee , Gpumech: Gpu performance modeling technique based on interval analysis, Proc. 47th Annual IEEE/ACM Int. Symp. Microarchitecture (IEEE Computer Society, New York, 2014), pp. 268–279. Google Scholar
18. M. Kiani and A. Rajabzadeh , Vlag: A very fast locality approximation model for gpu kernels with regular access patterns, 2017 7th Int. Conf. Computer and Knowledge Engineering (ICCKE) (IEEE, New York, 2017), pp. 260–265. Google Scholar
19. T. Tang, X. Yang and Y. Lin , Cache miss analysis for gpu programs based on stack distance profile, 2011 31st Int. Conf. Distributed Computing Systems (ICDCS) (IEEE, New York, 2011), pp. 623–634. Google Scholar
20. M. Kiani and A. Rajabzadeh , Skerd: Reuse distance analysis for simultaneous multiple gpu kernel executions, 2017 19th Int. Symp. Computer Architecture and Digital Systems (CADS) (IEEE, New York, 2017), pp. 1–6. Google Scholar
21. J. T. Adriaens, K. Compton, N. S. Kim and M. J. Schulte , The case for gpgpu spatial multitasking, IEEE 18th Int. Symp. High Performance Computer Architecture (HPCA), 2012 (IEEE, New York, 2012), pp. 1–12. Google Scholar
22. S. Pai, M. J. Thazhuthaveetil and R. Govindarajan , Improving gpgpu concurrency with elastic kernels, Proc. Eighteenth Int. Conf. Architectural Support for Programming Languages and Operating Systems (ACM, New York, 2013), pp. 407–418. Google Scholar
23. J. J. K. Park, Y. Park and S. Mahlke , Dynamic resource management for efficient utilization of multitasking gpus, Proc. Twenty-Second Int. Conf. Architectural Support for Programming Languages and Operating Systems (ACM, New York, 2017), pp. 527–540. Google Scholar
24. Z. Wang, J. Yang, R. Melhem, B. Childers, Y. Zhang and M. Guo , Simultaneous multikernel: Fine-grained sharing of gpus, IEEE Comput. Archit. Lett. 15 (2016) 113–116. Web of Science, Google Scholar
25. Q. Xu, H. Jeon, K. Kim, W. W. Ro and M. Annavaram , Warped-slicer: Efficient intra-sm slicing through dynamic resource partitioning for gpu multiprogramming, Proc. 43rd Int. Symp. Computer Architecture (IEEE Press, New York, 2016), pp. 230–242. Google Scholar
26. A. Jog, O. Kayiran, T. Kesten, A. Pattnaik, E. Bolotin, N. Chatterjee, S. W. Keckler, M. T. Kandemir and C. R. Das , Anatomy of gpu memory system for multi-application execution, Proc. 2015 Int. Symp. Memory Systems (ACM, New York, 2015), pp. 223–234. Google Scholar
27. Y. Liang and X. Li , Efficient kernel management on gpus, ACM Trans. Embedded Comput. Syst. 16 (2017) 115. Web of Science, Google Scholar
28. M. Kiani and A. Rajabzadeh , Analyzing data locality in gpu kernels using memory footprint analysis, Simul. Model. Pract. Theory 91 (2019) 102–122. Web of Science, Google Scholar
29. NVIDIA, Cuda best practice (2017). Accessed on 12 January 2017. Google Scholar
30. G. Diamos, A. Kerr, S. Yalamanchili and N. Clark , Ocelot: A dynamic compiler for bulk-synchronous applications in heterogenous systems, 19th Int. Conf. Parallel Architecture and Compilation Techniques (PACT-19) (ACM, New York, 2010), pp. 353–364. Google Scholar
31. V. Narasiman, M. Shebanow, C. J. Lee, R. Miftakhutdinov, O. Mutlu and Y. N. Patt , Improving gpu performance via large warps and two-level warp scheduling, 2011 44th Annual IEEE/ACM Int. Symp. Microarchitecture (MICRO) (2011), pp. 308–317. Google Scholar
32. L.-N. Pouchet, Polybench: The polyhedral benchmark suite, (2012), http://www.cs.ucla.edu/pouchet/software/polybench. Google Scholar
33. S. Che, M. Boyer, J. Meng, D. Tarjan, J. W. Sheaffer, S.-H. Lee and K. Skadron , Rodinia: A benchmark suite for heterogeneous computing, IEEE Int. Symp. Workload Characterization, 2009. IISWC 2009 (IEEE, New York, 2009), pp. 44–54. Google Scholar
34. NVIDIA, Nvprof pforiler (2017). Accessed on 12 February 2017. Google Scholar
35. D. Eklov and E. Hagersten , Statstack: Efficient modeling of lru caches, 2010 IEEE Int. Symp. Performance Analysis of Systems & Software (ISPASS) (IEEE, New York, 2010), pp. 55–65. Google Scholar
36. A. Jooya, N. Dimopoulos and A. Baniasadi , Gpu design space exploration: Nn-based models, 2015 IEEE Pacific Rim Conf. Communications, Computers and Signal Processing (PACRIM) (IEEE, New York, 2015), pp. 159–162. Google Scholar