可輔助平行化剖析之編譯器前端架構

Compiler Front-End Framework for Parallelism Profiling

陳鴻奎(Hong-Kuei Chen)

指導教授 ： 陳少傑

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.03150

摘要

當多核處理器(chip multiprocessor)變成處理器的主流時，如何使得程式在多核處理器上能夠更有效率的執行的研究問題顯得更為重要。不幸的是，傳統編譯器注重單核處理器以及循序的執行方式缺乏攫取程式平行的能力。本論文將發展一個可輔助平行化剖析的編譯器前端架構，這個架構提出三個不同的觀點的資訊對平行能力的攫取很大的幫助，這三個觀點分別是：靜態觀點(static view)，動態觀點(dynamic view)，機率觀點(probabilistic view)。
靜態觀點使用程式相依圖(program dependence graph)及中間碼(intermediate representation)於我們的架構以求得程式碼與程式碼之間是否存在可平行執行的關係。動態觀點使用粗糙剖析器(coarse-grained profiler)收集程式執行過程的資訊，其中包含程式熱點(program hot spots)和記憶體存取與時間的關係。機率觀點使用Valgrind剖析器收集快取記憶體失誤比率(cache miss rate)。這些剖析的資訊可以幫助發展應用於多核處理器的嵌入式系統使之更有效率。

關鍵字

編譯器 ； 前端 ； 平行化 ； 粗顆粒剖析 ； 多核

並列摘要

Embedded systems on multi-core are nearly ubiquitous today such as handheld mobile phones and game consoles. When developing embedded systems on multi-cores, we need a profiler to analyze an application and find out whether it can be executed in parallel or which part of it can be executed in parallel, which will help a designer to decide how to use system resources well. In the Thesis, we developed a compiler front-end framework for parallelism profiling. Our proposed framework can extract the information on whether one application can be executed in parallel or not. These information are contributive to developing embedded systems on a multi-core environment.

並列關鍵字

compiler ； front-end ； parallelism ； coarse-grained profiling ； multi-core

參考文獻

[1] M. E. Wolf and M. S. Lam, “A Loop Transformation Theory and an Algorithm to Maximize Parallelism,” IEEE Trans. Parallel Distributed Systems, vol. 2 issue 4, pp. 452-471, Oct. 1991.

[2] K. Kennedy, and K. S. McKinley, “Maximizing Loop Parallelism and Improving Data Locality via Loop Fusion and Distribution,” in Proceedings of the Int. Workshop on Languages and Compilers for Parallel Computing, pp. 301-320, Aug. 1993.

[3] K. G. Kumar, D. Kulkarni, and A. Basu, “Deriving Good transformations for Mapping Nested Loops on Hierarchical Parallel Machines in Polynomial Time,” in Proceedings of the 6th international conference on Supercomputing, pp. 82-92, Jul. 1992.

[5] A. I. Holub, Compiler Design in C, Prentice Hall, Mar. 1990.

[8] D. R. Wallace, “Low level scheduling using the hierarchical task graph,” in Proceedings of the 6th international conference on Supercomputing (ICS), pp. 72-81, Jul. 1992.