微核心作業系統多處理機上系統軟體之研製---子計畫三：一個基於知識庫技術的高效能平行編譯器---在多處理機系統上一個支援執行時期平行化的編譯器(II)

Abstract

在上一年計畫中，我們製作出一個Source Program Behavior Analyzer的雛形即是Practical Parallel Loop Detector用來偵測程式中可以平行化的迴圈。此一Analyzer採用我們於先前研究計畫所製作出的K-Test作為Data DependenceTesting。接著我們使用專家系統的技術來解決平行編譯器上迴圈的排程問題。由於程式中迴圈的特性不一，目前的方法中，沒有一種能夠很有效率的解決排程問題。因此，我們發展一個基於知識庫的平行迴圈排程系統(KPLS)，依照迴圈的特性和資訊加以分析，利用現有的排程演算法，推理一個最適合的排程法，使得排程後的迴圈能在多處理機系統上有效的執行。我們在研究中發現，迴圈在一程式中存在有大量的平行度，為了將此程式平行化，平行編譯器利用靜態資料相依性分析來獲得迴圈的平行度。然而，有些迴圈則無法於編譯時期取得資料相依性的資訊。例如，在稀疏矩陣計算上，陣列述語內通常包含了間接陣列或函式，便無法完成靜態資料相依性分析。故便保守的將程式循序的執行，而犧牲了潛在的平行度。因此，在本計畫中，我們將提出了一個兩階段(偵測階段及執行階段)的執行時期平行化方法於執行時期擷取出迴圈中潛在的平行度。偵測階段經由建立一DEF-USE表而決定出可平行執行的迴圈輪替集合-波前，而此偵測階段本身可以被完全的平行化而減少因決定波前所照成的額外負擔。此外，我們仍然要持續的加強與改進Parallel LoopDetector與KPLS的功能，以期能達到我們預期的成果。以上的研究，將在我們已發展的可移植式平行編譯(PFPC)中實際製作出來，提昇編譯器產生有效率的執行碼。