實用型平行迴圈偵測器之設計

Abstract

眾所周知，平行迴圈的偵測在平行編譯器的設計上扮演著相當重要的角色 。一個迴圈若能以平行或部份平行的型態執行，如 DOALL 或 DOACROSS 迴圈，則程式的執行效率可因此而提昇。由於這個理由，我們需要一個前 端處理器來將一個循序性程式轉譯成其對應的提示性平行碼。雖然伊利諾 大學曾發展了一個類似的工具 Parafrase-2，我們仍希望開發一個新的工 具，期能提供更高的精確度並綴補改正 Parafrase-2 的謬誤。在本篇論 文中，我們提出一個能同時開發傳統程式中潛在的 DOALL 及 DOACROSS 迴圈的方法。此外，如果偵測出有 DOACROSS 迴圈，則做最佳化的同步協 調。在我們的方法中將利用 I test 做陣列索引測試，因為其精確度比 GCD test 與 Banerjee test 的組合來得高。我們亦設計了一個實現我們 的理念之工具 PPD以進行實驗。實驗結果顯示 PPD 在可靠度與精確度方 面都要比 Parafrase-2 來得好。 It is well-known that the detection of parallel loops plays a significant role while designing a parallelizing compiler, and that if a loop can be executed in parallel or partial parallel, like a DOALL or DOACROSS loop, the execution efficiency of the program is promoted. For this reason, we need a front-end which translates a serial program into its prompted parallel code. Although there is a resembling tool, Parafrase-2 which was developed at the University of Illinois, we still want to explore a new one which offers more accuracy and makes up the suspicion of Parafrase-2. In this thesis, we propose a method which exploits the potential DOALL and DOACROSS loops of traditional programs in a time. Furthermore, if DOACROSS loops are available, the optimized synchronization is made. Since the I test is more accurate than the combination of the GCD and Banerjee tests, it is invoked in our method for array subscripts testing. We also designed a tool, PPD, which realizes our opinion for experiments. The experimental results show that PPD is more reliable and accurate than Parafrase-2.