Translated Titles

A GPGPU-based Alias Analysis for LLVM Compiler Infrastructure



Key Words

Inclusion-based Points-to Analysis ; Open Computing Language (OpenCL) ; Low Level Virtual Machine(LLVM) ; GPGPU ; Data Compression



Volume or Term/Year and Month of Publication


Academic Degree Category




Content Language


Chinese Abstract

別名分析 (Alias analysis) 在編譯器上,是用來決定兩次記憶體存取是否參考到相同的記憶體位置的一個方法,大部分的別名分析過程都採用循序執行 (Sequential execution) 程式架構。然而別名分析本身是一個NP問題 (NP-hard problem),在近年來軟體開發越來越龐大導致分析不易,在分析的過程中往往需要在有限制的記憶體內尋求時間與精度的平衡點。 在追求分析時間縮短的方式,不外乎硬體的演進、演算法的改良。隨著摩爾定律 (Moore's law) 硬體演進逐漸達到新的狀態,硬體開始改變成多核心 (multi-core),開始改變許多的議題延伸至用多核心執行平行化運算方式來改進分析的速度。 而近年來開始將議題延伸至通用圖形處理器 (General-purpose computing on graphics processing units, GPGPU),開始有利用GPU用來計算的程式語言,在本文中我們將在 LLVM (Low Level Virtual Machine) 編譯器上以 GPU 的計算程式語言 OpenCL(Open Computing Language )實作別名分析,進一步來提升計算效能。

English Abstract

On the compiler alias analysis, is used to determine whether two memory accesses refer to the same memory location of a method. Most of the alias analysis processes are performed using sequential program architecture. However alias analysis itself is an NP-hard problem. Software development increasingly large cause analysis is not easy in recent years. On the analysis of the process often requires limited memory seek time and precision balance. In the pursuit of ways to shorten the analysis time, the hardware or algorithm improvements evolution. With the gradual evolution of Moore's law hardware to reach a new state. Hardware began to change into multi-core and the issues extend to perform parallel implementation of multi-core to improve the speed of analysis. In recent years extends to GPGPU (General-purpose computing on graphics processing units), began to take advantage of GPU programming language to calculation. In this paper we will LLVM (Low Level Virtual Machine) compiler by GPU computing programming language OpenCL (Open Computing Language) implementations alias analysis and further to improve computing performance.

Topic Category 基礎與應用科學 > 資訊科學
工學院 > 資訊工程學系
  1. [1] Jungwon Kim, Honggyu Kim, Joo Hwan Lee, and Jaejin Lee. Achieving a single
  2. compute device image in opencl for multiple gpus. In Proceedings of the 16th
  3. 288. ACM, 2011.
  4. [2] Ben Hardekopf and Calvin Lin. The ant and the grasshopper: fast and accu-
  5. rate pointer analysis for millions of lines of code. In ACM SIGPLAN Notices,
  6. [3] L William and GR Barbara. Pointer-induced aliasing: a problem taxonomy. In
  7. programming languages, 1991.
  8. [4] Dzintars Avots, Michael Dalton, V Benjamin Livshits, and Monica S Lam. Im-
  9. proving software security with a c pointer analysis. In Proceedings of the 27th
  10. international conference on Software engineering, pages 332{341. ACM, 2005.
  11. ACM, 2010.
  12. PLAN symposium on Principles and Practice of Parallel Programming, pages
  13. [7] Aaftab Munshi et al. The opencl speci cation. Khronos OpenCL Working Group,
  14. on. IEEE, 2013.
  15. program analysis & transformation. In Code Generation and Optimization, 2004.
  16. [14] Gianfranco Bilardi and Keshav Pingali. Algorithms for computing the static
  17. single assignment form. Journal of the ACM (JACM), 50(3):375{425, 2003.
  18. ow-sensitive pointer analysis. In
  19. ACM SIGPLAN Notices, volume 44, pages 226{238. ACM, 2009.
  20. [18] Lars Ole Andersen. Program analysis and specialization for the C programming
  21. [19] Ben Hardekopf and Calvin Lin. Flow-sensitive pointer analysis for millions of
  22. lines of code. In Code Generation and Optimization (CGO), 2011 9th Annual
  23. IEEE/ACM International Symposium on, pages 289{298. IEEE, 2011.
  24. ACM symposium on Principles and practice of parallel programming, pages 277{
  25. volume 42, pages 290{299. ACM, 2007.
  26. Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of
  27. [5] Mario Mendez-Lojo, Augustine Mathew, and Keshav Pingali. Parallel inclusion-
  28. based points-to analysis. In ACM Sigplan Notices, volume 45, pages 428{443.
  29. [6] Mario Mendez-Lojo, Martin Burtscher, and Keshav Pingali. A gpu implementa-
  30. tion of inclusion-based points-to analysis. In Proceedings of the 17th ACM SIG-
  31. 107{116. ACM, 2012.
  32. 1:l1{15, 2009.
  33. [8] Luba Tang. Mclinker - llvm linker for mobile computing. In Code Generation and
  34. Optimization (CGO), 2013 11th Annual IEEE/ACM International Symposium
  35. [9] AMD AMD. Accelerated parallel processing: Opencl programming guide. URL
  36. http://developer. amd. com/sdks/AMDAPPSDK/documentation, 2011.
  37. [10] Aaftab Munshi, Benedict Gaster, Timothy G Mattson, and Dan Ginsburg.
  38. OpenCL programming guide. Pearson Education, 2011.
  39. [11] Benedict Gaster, Lee Howes, David R Kaeli, Perhaad Mistry, and Dana Schaa.
  40. Heterogeneous Computing with OpenCL: Revised OpenCL 1. Newnes, 2012.
  41. [12] Chris Lattner and Vikram Adve. Llvm: A compilation framework for lifelong
  42. CGO 2004. International Symposium on, pages 75{86. IEEE, 2004.
  43. [13] John Aycock and Nigel Horspool. Simple generation of static single-assignment
  44. form. In Compiler Construction, pages 110{125. Springer, 2000.
  45. [15] Diego Novillo. Design and implementation of tree ssa. In Proceedings of GCC
  46. developers summit, pages 119{130, 2004.
  47. [16] Chris Arthur Lattner. LLVM: An infrastructure for multi-stage optimization.
  48. PhD thesis, University of Illinois, 2002.
  49. [17] Ben Hardekopf and Calvin Lin. Semi-sparse
  50. language. PhD thesis, University of Cophenhagen, 1994.