平行編譯器之新的資料相依性測試

Abstract

資料相依性測試常常用來用確定一個巢狀回路是否能平行化處理。在過去, 曾有多種 常用的資料相依法測試法, 例如: GCD測試法及Banerjee 測試法。而在1990年, Kong 結合上述兩種測試法, 並應用區間的觀念, 提出一個測試巢狀回路是否能平行處理的 資料相依性測試演算法, 稱之為區間測試法(Interval Test) , 它是它時間複雜度為 O (BAN＋n.GCD＋n ) , 而且只能處理區間方程式的係數小於或等於區間上整數點個 數的情況。這篇論文以區間測試法為基礎, 提出二個新的演算法。第一個演算法應用 GCD 測試法的概念, 可以在較少時間複雜度O(BAN＋n•GCD＋n•log2n)下, 求出與區 間測試法同樣精確的答案。第二個演算法則在區間方程式的係數小於或等於區間上整 個演算法則在區間方程式的係數小於或等於區間上整數點個數的情況下, 直接使用第 一個演算法; 而在區間方程式的系數大於區間上整整點個數的情況下, 將測試資料相 依性的問題轉換為計算二度平面中一個平行四邊形內部所含格子點的問題, 它可以在 與區間測試法相同的時間復雜度下求出比區間測試法更精確的結果。