M-hopping 方法：一個有效的不規則相依迴圈排程方式

Abstract

一般而言，任何巢狀迴圈都能藉由同步 (synchronization) 機制維持迴圈相依 (iteration dependence) 的正確性，進而達到平行化的目的。這些同步機制可以結合迴圈排程方法 (loop scheduling scheme)，以維護迴圈的正確執行順序，同時平均分配各處理器 (processors) 的工作量。於本篇論文中，我們提出一個新的不規則相依迴圈 (non-uniform dependence loop) 排程方法，稱為 M-hopping 方法 (M-hopping method)，以便在多處理器系統(multiprocessor system) 上有效排程不規則相依迴圈。此方法的主要精神是動態釋放已滿足相依限制的 iterations，同時更新可平行化的 iterations 個數。由於此特性，我們的方法能在執行時間有效彰顯平行度。所依據的原理為迴圈中最小相依距離 (minimum dependence distance)，藉此求出調整可平行化 iterations 個數所需之相關資訊。初步評估結果顯示，若巢狀迴圈繼承豐富的平行度，我們的方法可以在不介入明顯的同步負載下，動態開發平行度。因此，M-hopping方法優於大部份現有的不規則迴圈排程方法約 20.29%。

In general, any nested loop can be parallelized due to dependence constraints among iterations can be preserved through synchronization. Synchronization mechanisms can be combined with loop scheduling scheme to form a uniform framework. Meanwhile, correct execution order and balance workload distribution will be achieved. In this thesis, we propose a new scheduling scheme, called M-hopping method, to schedule non-uniform dependence doubly nested loop on multiprocessor system. To initialize a set of hopping information, our approach is based on the concept of minimum dependence distance. During runtime, hopping information will be used to adjust the number of parallelizable iterations. According to our experimental results, if loops carry sufficient parallelism, our propose method will reliably exploit parallelism, and outperform most of the existing non-uniform dependence loop scheduling schemes by 20.29% in average.