使用虛擬計算點方法於相依圖映射至處理機陣列上通道相衝之檢查

Abstract

均勻相依演算法為一類具有凸形計算點集與常數資料相依向量的演算法。 此類演算法經常被表示成具有規律相依結構之相依關係圖。 當使用時空映射法將一均勻相依演算法映射至低維處理機陣列時，為了確保映射的正確性，我們必須檢查是否發生通道相衝。 所謂通道相衝意指有兩個資料元素同時出現在同一處理機間的資料通道上。 過去對於通道相衝之研究，皆只限於探討鄰近互連之處理機陣列模式的通道相衝問題。 在本論文中，我們將探討的對象延伸至允許非鄰近互連之處理機陣列模式，並提出虛擬計算點之觀念來解決不同處理機陣列模式上的通道相衝問題。 基於虛擬計算點之觀念，我們推導出通道相衝發生的充份必要條件，並且進一步將其表示成整數規劃模式。 為了有效率地檢查通道相衝，我們提出了一有系統的檢查程序來列舉這些整數規劃模式之所有整數解。 我們的檢查程序之時間複雜度可證明較過去方法為低。 此外，我們也探討了過去之通道相衝檢查方法與我們方法之間的關係。 我們證明了過去之方法皆屬於我們方法的一個特例。

Uniform dependence algorithms are algorithms whose computation domains are sets of integral points and whose data dependence relations can be characterized by constant dependence vectors. This type of algorithms can be represented by dependence graphs with regular dependence structures. When space-time mapping a uniform dependence algorithm into a lower-dimensional processor array, link conflicts should be checked to ensure the validity of the mapping. Most existing methods of checking link conflicts are restricted to array models that only allow neighboring communications between processors. In this thesis, these array models are generalized so that non-neighboring communications between processors are allowed. We introduce the notion of virtual nodes to unify the problem of checking link conflicts on the different array models. Based on the notion of virtual nodes, necessary and sufficient conditions for checking link conflicts are derived and are further formulated into integer programs. A procedure is proposed to systematically enumerate the integer solutions of the integer programs in order to check link conflicts efficiently. We show that the time complexity of the proposed procedure is less than that of previous methods. In addition, relations between our method and previous methods for checking link conflicts are also studied. We show that all previous methods are special cases of our method.