一個非連續最佳化數據依賴性測試用來降低原始碼級偵錯之複雜性應用於平行編譯器和向量編譯器之最佳化

A Non-Continuous Optimized Data Dependence Testing for Reducing The Complexity of Source Level Debugging for Parallel Compiler and Vector Compiler Optimizations

翁嘉偉(Chia-Wei, Wong)

指導教授 ： 何善輝

國立臺北大學/電機資訊學院/電機工程研究所/碩士(2013年)

摘要

在平行編譯器進行分析時，必須使用數據依賴性測試來判別某一區段的程式碼是否存在依賴性。近年來，有越來越多學者投入數據依賴性測試相關領域的研究，針對迴圈依賴性測試發展出許多有效率的演算法。一維、二維和三維陣列的參照大約分別佔56%、36%和8%。另外，迴圈正規化讓陣列的參照更加的複雜而且還會產生出用於平行編譯器以及向量編譯器之原始碼級偵錯的困難。
平行編譯器藉由數據依賴性測試在迴圈的迭代之間判定依賴性。判定過程中必須分析註標表示式。陣列參考有可能存在也有可能不存在依賴性。在迴圈中，若平行編譯器找出兩個存取到相同記憶體位址的迭代，那麼該迴圈就會存在依賴性而無法被平行處理。資料依賴性測試可以分為兩大類，分別是精確測試以及非精確測試。精確測試除了可以證明獨立性亦可證明依賴性。另外，非精確測試只能夠用來證明獨立性。
I測試是GCD測試以及Banerjee測試的結合。GCD測試用來檢查是否存在整數解。Banerjee測試用來將迴圈索引變數的邊界納入考慮。GCD測試使用在迴圈依賴性測試上時只能夠證明獨立性。Banerjee測試雖將變數的邊界納入考慮，但它只能夠用來證明一個單一的方程式是無解的，所以使用在迴圈依賴性測試時，它也只能夠證明獨立性。因此對於不變邊界以及一次性增量巢狀迴圈中的一維陣列，I測試能夠用來判定其是否存在依賴性。
I測試的最初設計是用於迴圈索引變數的增量是1的情況，不是1的狀況下，它是不能直接拿來使用的。因為存在非一次性增量迴圈索引變數的巢狀迴圈會出現問題，這樣的迴圈必須經過迴圈正規化將迴圈索引變數的增量轉換成一次。然而，迴圈正規化會對平行編譯器造成許多問題。因此，對於不變邊界還有非一次性增量這樣的一維陣列，一個有效率的最佳化數據依賴性技術是非常重要的。在本篇論文中，我們提出非連續I最佳化測試，用於判別不變邊界以及非一次性增量巢狀迴圈中的一維陣列是否存在整數解。
在論文中，我們建構出從原始I測試修正而來的非連續最佳化數據依賴性測試。它可以直接被應用於非一次性增量以及一維、多維陣列的迴圈而不用經過迴圈正規化的步驟。一維非連續I測試應用於一維陣列。多維非連續I測試應用於多維陣列。在實驗結果中，我們成功的應用非連續I測試來判別非一次性增量的巢狀迴圈是否存在依賴性。使用非連續I測試讓非一次性增量的巢狀迴圈不用經過迴圈正規化的步驟，節省了迴圈正規化所花費的時間。因為不經過迴圈正規化，因此不用修改到程式碼，降低了原始碼偵錯之複雜性，在判定上優於需要使用迴圈正規化的原始I測試。非連續I測試的時間複雜度跟原始I測試的複雜度一樣，均為O(c_3 n^2+c_2 n)。

關鍵字

平行編譯器 ； 資料依賴性測試 ； GCD測試 ； 非一次性增量 ； 迴圈正規化

並列摘要

When a parallel compiler analyzes a program, it must apply data dependence test to determine whether a certain region exists dependence or not. In recent years, there are more and more scholars researched the area of data dependence test and developed many efficient algorithms. One, two and three-dimensional array references approximately account for, respectively, 56, 36 and 8 percent of the examined array references. In the other hand, loop normalization makes array references more complex and creates many difficulties of source level debugging for parallel compilers and vector compilers.
A parallel compiler determines the dependence between loop iterations by data dependence tests. It has to analyze the subscript expression. An array reference may or may not produce dependence. In a loop, if the parallel compiler finds out that there exist two iterations which access the same memory address, then the dependence is existent and cannot be processed by parallel processing. Data Dependence tests can be divided into two categories generally: exact dependence test and in-exact dependence test. Exact dependence tests not only determine dependence but also prove independence.
The I test is a refined combination of the GCD and Banerjee test (Psarris et al. 1993; Psarris et al. 1999). The GCD test is applied in checking whether there is an integer solution (Xiangyun Kong et al. 1991). The Banerjee test is applied in taking the boundaries of loop index variables into account (Xiangyun Kong et al. 1991). The GCD test is only capable of being used to prove independence in data dependence test. The Banerjee test is only able to prove that an equation does not exist any integer solution in the boundaries of iteration variables, it is only capable of being used to prove independence in data dependence test. Therefore, the I test can be used to determine the dependence for one-dimensional arrays with constant bounds and one-increment loop iteration variables.
The normal I test was originally designed for the loop which its index variable increment is 1, that is to say, it can’t be directly applied in non-one-increment nested loop. This kind of nested loop must be converted to one-increment loop by the loop normalization. However, the loop normalization creates many problems. In this paper, we propose the non-continuous I optimization test to determine whether there are integer-valued solutions for one-dimensional arrays with constant bounds and non-one-increment.
In this thesis, we build up the non-continuous optimization data dependence test which is modified from the normal I test. It can be applied in the loops with non-one increment and one-dimensional as well as multi-dimensional arrays directly, without doing the loop normalization. One-dimension non-continuous I test is applied in determining one-dimensional arrays. Multi-dimension non-continuous I test is applied to determine multi-dimensional array. In our experimental simulation, we successfully determined the loop by non-continuous I test. Because of the non-continuous I test, it can directly be used to determine the dependence for one-dimensional as well as multi-dimensional arrays with constant bounds and non-one-increment loop iteration variables without using loop normalization, so we reduce the time of loop normalization. Because it’s unnecessary to modify the code of a program, the complexity of source level debugging for parallel compiler and vector compiler can be reduced, it’s better than the determination of the normal I test which must apply the loop normalization. The time complexity of the non-continuous I test is as the normal I test, they are all O(c_3 n^2+c_2 n).

並列關鍵字

parallel compiler ； data dependence test ； GCD test ； non-one-increment ； loop normalization

參考文獻

Kleanthis Psarris, Xiangyun Kong, David Klappholz, "The direction vector i test," IEEE Transaction on Parallel and Distributed Systems, Vol. 4, No. 11 (1993), pp. 1280?1290.

Uptal Banerjee, Dependence Analysis, Kluwer Academic Publishers, Norwell, Massachusetts, 1997.

Franjo Plavec, "Dependence Testing for Parallelizing Compilers," ECE 1754 Survey Paper (May 2003).

Jia-Hwa Wu and Chih-Ping Chu, “An Exact Data Dependence Testing Method for Quadratic Expressions,” Information Science, Volume 177, Issue 23, 1 December 2007, pp. 5316-5328.

J. Dongarra, M. Furtney, S. Reinhardt and J. Russell, "Parallel Loops ? A test suite for parallelizing compilers: Description and example results," Parallel Computing 17(1991) , pp. 1247?1255.