一個有效不規則相依迴圈計算與資料分解方法之研製

Abstract

由於遠端記憶體存取(Remote memory access)時間遠大於區域記憶體存取(Local memory access)。因此，我們利用計算分解與資料分解之架構計算出迴圈中計算(iteration)與陣列資料之相關性。並採用廣域資料分析，對整個程序中之迴圈進行陣列資料分析，促使陣列資料分解型態一致，以減少資料重組溝通。同時利用迴圈交換方法，促使迴圈中之計算對陣列資料之存取順序能符合資料之區域性。最後，經由資料型態之分析決定出最後之區塊或循環分配方式，將具有相關性之計算與資料分配到同一個處理器和其區域記憶體中。初步評估結果顯示，當陣列之下標函數之變數較為複雜時，本方法能經由計算與資料分解之分配方式，降低遠端資料存取順序。而當迴圈之計算順序會破壞陣列資料之區域性時，本方法會利用迴圈交換方式，使其存取順序滿足資料之區域性，進而降阺遠端存取次數。因此，將此方法搭配不規則相依迴圈靜態排程方式，確可減少迴圈中遠端存取之次數。

In distributed shared memory multiprocessors, local memory access are much faster than remote access. For the sake of reducing remote communication, the array elements in programs must be precisely distributed to local memory for parallel execution. In this thesis, we have developed an efficient computation and data decomposition method to reduce interprocessor communication. Firstly, computation and data decomposition are mapped onto virtual processors, and the data decomposition pattern is analyzed to minimize the cost of data reorganization communication. By using the data decomposition pattern, the mapping of virtual processors to physical processor is determined. According to our experimental results, for non-uniform dependence loops, which have complex array subscripts and data access order has no data locality, they can be executed with less iterprocessor communication overhead on the distributed shared memory multiprocessors system if our method is applied.