基於知識庫的迴圈資料相依性測試

Abstract

多處理機架構日趨普遍，致使傳統的編譯方法不足以應付．為了善用潛在 的平行度，許多平行編譯技術應運而生．雖然這些方法未必適用於所有狀 況，但是它們各有所長．這促使我們研究以知識庫的方式整合這些技術的 可行性．我們首先針對平行編譯器中的一個重要階段－資料相依性分析－ 加以探討．本文提出一個方法試圖整合現有的測試法．簡言之，它先詢問 知識庫，以決定要採用何種測試，然後應用這種測試來偵測資料相依性． 我們進一步發展了一個稱為K-test的規則庫系統來驗證這個構想．模擬結 果顯示K-test在真實和虛構的輸入例子都能表現相當高的精確度．就軟體 維護而言，我們的做法明顯較傳統方式便利．因此我們正嘗試將這個構想 擴充應用到整個平行編譯的領域． More and more popular multiprocessor architectures have made traditional compiling methodology insufficient. For this reason, various parallelizing compiling techniques have been developed to exploit the potential parallelism. Although none of the new methods is suitable for all input cases, each has its own advantages over other ones. This motivates us to study the feasibility of integrating these techniques by knowledge- based approaches. In this thesis, we concentrate on the fundamental phase, data dependence analysis, in parallelizing compilers. We propose a new approach which integrates existing tests and makes good use of their advantages. This approach chooses an appropriate test by knowledge-based methodology, and then applies the resulting test to detect data dependence on loops. A rule-based system, called the K test, is developed by repertory grid analysis to construct the knowledge base. Simulation results show that the K test gives relatively exact solutions in both practical and contrived cases; furthermore, as for system maintenance and extendibility, our approach is obviously superior to others. Therefore, we are trying to extend the knowledge-based approach to the whole field of parallelizing compiling.