在多處理機系統上設計並製作一個平行編譯器

Abstract

本篇論文是著重在設計並製作一個有效率且精確的平行編譯器來有效地擷 取迴圈之平行度，使多處機系統的執行能達到高速度。首先，我們從解析 Parafrase-2編譯器的技術來作為發展編譯器的基礎。Parafrase-2主要目 標在探測平行編譯器的程式轉換行為，我們介紹此編譯器的純量分析、資 料相依性分析、平行化分析、以及其他相關分析的邏輯觀點，同時也提出 一些有關於可改進Parafrase-2的觀點。接著在本文中，我們提出一個基 於多引線作業系統上的平行編譯器模式，此模式中的迴圈平行化分析即是 使用Parafrase-2。然後我們將此模式一般化以用來建構其他語言的平行 編譯器。基於上述的模式，我們設計並製作出能在AcerAltos 10000系統 上使用多引線作業系統的一個具迴圈切割能力且可移植之平行編譯器，叫 做 PFPC。迴圈若能以平行或部份平行的形式執行，如DOALL或DOACROSS迴 圈，則程式的執行效率可因而提昇。在本文中我們提出一個實用平行迴圈 偵測器(PPD)，用來取代Parafrase-2的角色，PPD是結合I test與ZIV test做陣列索引測試，能從循序程式中偵測DOALL及 DOACROSS迴圈。此外 ，如果偵測出程式中有DOACROSS迴圈，則做同步協調的最佳化。為了使編 譯器能獲得更高的平行度，我們也提出一個基於知識庫技術的平行化模式 。此基於知識庫方法整合了目前現有的資料相依性測試法與迴圈排程法， 用以找出最佳的演算法來解決迴圈平行化問題。兩個叫做K-Test與KPLS的 知識庫系統，都是利用表格擷取式的分析與屬性擇序表的方法來建構知識 庫，並整合於平行編譯器。實驗的結果展現此編譯器可使迴圈的執行達到 高的加速性。最後，我們更提出一個基於偵測與執行二階段法的執行時迴 圈平行化法。此偵測階段是利用建構DEF-USE表來偵測出迴圈中複雜的間 接陣列參考，此偵測階段可以完全被平行化以加速找出要執行的波前數。 實驗的結果也展現出此方法可使迴圈在執行時的平行化達到不錯的效果。 This dissertation describes the design and implementation of an efficient and precise parallelizing compiler to parallelize loops and achieve high speedup rates on multiprocessor systems. In this thesis, Parafrase-2 is first discussed for designing efficient parallelizing compiler. Parafrase-2 is a existing parallelizing compiler which aims at exploring program transformation. The logical views of scalar analysis, data dependence analyses, and parallelization analysis passes along with their relevant relations between passes are then presented. A model of FORTRAN parallelizing compiler on multithreading OSF/1 is also proposed in this thesis. The model uses Parafrase-2 for data dependence analysis. The model is then generalized for construction of corresponding parallelizing compilers for other computer languages. Based upon this model, we designed and implemented a portable FORTRAN parallelizing compiler (PFPC) with loop partitioning for the AcerAltos 10000 multiprocessor system running OSF/1. As we know, the execution efficiency of a loop can be enhanced if the loop is executed in parallel or partially parallel, like a DOALL or DOACROSS loop. This thesis also reports on the practical parallel loop detector (PPD) that is implemented in PFPC to replace the role of Parafrase-2 on finding the parallelism in loops. The PPD can extract the potential DOALL and DOACROSS loops in a program by invoking a combination of the ZIV test and the I test for verifying array subscripts. Moreover, if DOACROSS loops are available, an optimization of synchronization statements are made. Experimental results show that PPD is more reliable and accurate than previous approaches. In addition, a new model by using knowledge-based techniques is proposed to exploit more loop parallelisms in this thesis. The knowledge-based approach integrates existing data dependence tests and loop scheduling algorithms to make good use of their ability to extract loop parallelisms.