- 作者: 楊朝棟; 曾憲雄; 莊孫文; 莊正得; 時文中
- 作者服務機構: 行政院國家科學委員會太空計畫室籌備處; 國立交通大學資訊科學系
- 中文摘要: 為了使平行編譯器能獲得更高的平行度,我們提出一個基於知識庫技術的平行化模式。此基於知識庫方法整合了目前現有的資料相依性測試法、迴圈轉換法與迥圈排程法,用以找出最佳的演算法來解決迴圈平行化問題。三個分別叫做K-Test、KPLT與KPLS的知識庫系統,都是利用表格擷取式的分析與屬性擇序表的方法來建構知識庫,並整合於平行編譯器中。這些知識庫系統會依照迴圈的特性和系統資訊加以分析,利用現有的資料相依性測試法、迴圈轉換演算法或迴圈排程法,推理一個最適合的資料相依性測試法、迴圈轉換演算法或迴圈排程法,使得轉換後的迴圈能提供更高的平行度並節省執行所費的時問。實驗的結果也展現出此種新模式可使迴圈的平行化達到不錯的效果。此一研究,整合在我們已發展的可移植式平行編譯(PFPC)中,來提昇編譯器產生有效率的執行碼。而本論文的研究成果,對未來發展高性能平行編譯器,在學術或實用上都可提供重要的參考。
- 英文摘要: In this paper, we concentrate on three fundamental phases,data dependence testing, parallel looptransformation, and parallel loop scheduling, of loop parallelization in parallelizing compilers runningon multiprocessor systems.A new model exploiting loop parallelization using knowledge-based techniquesis proposed. The knowledge-based approach integrates existing data dependence tests, loop transformationsand loop schedules to make good use of their abilities in extracting more parallelism. Three rule-basedsystems, called the K-Test, Knowledge-based Parallel Loop Scheduling (KPLS)and Knowledge-basedParallel Loop Transformation (KPLT), are then-developed by means of repertory grid analysis and anattribute ordering table to construct the knowledge base, respectively.These systems can choose anappropriate test, transform and schedule, and then apply the resulting methods to perform loop parallelizationand obtain a high speedup rate. For example, the KPLT system can choose appropriate loop transformationsto reorder the execution of statements and loop iterations for parallelization. Unlike previous researchesthat used the one-pass approach, we introduce the idea of multi-pass,which can be used to find moreparallelism of loops.Experimental results show that our new model can achieve higher speedup onparallelizing compilers. Furthermore, for system maintenance and extensibility, our approach is obviouslysuperior to others.
- 中文關鍵字: parallelizing compilers; data dependence testing; parallel loop scheduling; parallel loop transformation; knowledge-based technique; rule-based system; repertory grid analysis; multiproceddor systems
- 英文關鍵字: --