可重組態架構上之有向圖平行演算法

Parallel Digraph Algorithms on Reconfigurable Architectures

潘典台(Tien-Tai Pan)

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/博士(2011年)

摘要

在過去的30年中，可重組態架構所具有的超高速計算能力，吸引許多研究者與科學家投入該領域，它們是具有強大能力的平行計算模型，但是有些類型的計算問題並沒有被完整地研究清楚，例如：有向圖問題。有方向性的可重組態架構是針對有向圖問題特別開發出來的可重組態架構，這些有方向性的可重組態架構是一種理想化的機器，且只用來處理有向圖問題。在本論文中，我們將嘗試以新的方法並使用無方向性的可重組態架構去處理有向圖問題。
根據我們所知在本研究之前，有二種方法可以在可重組態架構上處理有向圖問題：第一種方法是基於與計算模型無關的矩陣乘法，它被用來解決代數路徑問題，例如遞移閉包、任兩端點間最短路徑、與最小擴張樹等問題，其所使用的計算模型為無方向性的可重組態架構；第二種方法則是使用有方向性的可重組態架構，例如有方向性的可重組態格狀網路、有方向性的可重組態匯流排之處理器陣列，來解決特定的有向圖問題。基於第二種方法的演算法必須利用有方向性的可重組態架構之特定能力才能正確無誤地處理問題，這能力就是它們能夠在匯流排的每一段落控制資料的流向。
在本論文中我們提出第三種解決方案，它是基於那些無方向性的可重組態架構上去解決有向圖問題，例如有向的遞移閉包問題可以在三維n* n* n的可重組態格狀網路用O(log d(D))的時間解決該問題，其中d(D)是有向圖D的直徑，基於有向的遞移閉包演算法的相同設計概念，我們可以解決下列的有向圖問題：強連接圖、強連接元件、環狀圖檢查、樹的建構、任兩端點之最短距離、單源最短距離、直徑、拓樸排序等問題，這些演算法價恰恰證明了這第三種解決方案的威力，因此我們認為這個在無方向性的可重組態架構上有向圖問題解決方案是有相當價值，而這將對超高速計算與即時運算等領域有所貢獻。

關鍵字

可重組態架構 ； 可重組態格狀網路 ； 遞移閉包 ； 強連接元件 ； 任兩頂點對之最短距離 ； 單源最短距離 ； 拓樸排序 ； 有向圖問題

並列摘要

Reconfigurable architectures have attracted many researchers and scientists for their high performance computing for the past three decades. They are very powerful parallel computation models, but some types of problems have not been studied completely, for example, the digraph problems. The directional reconfigurable architectures are developed especially for digraph problems, they are idealistic machines for handling such problems. In this dissertation, we focus on digraph problems by using non-directional reconfigurable architectures and try to solve them by a new approach.
Before this study, to our best knowledge, there are two approaches to solve digraph problems on reconfigurable architectures. The first one is on the basis of matrix multiplication which is independent of computation models.
It was used to solve the algebraic path problems (APP), for example, transitive closure (TC), all-pairs shortest path (APSP), the minimum spanning tree (MST), on non-directional reconfigurable architectures. The second approach uses directional reconfigurable architectures, such as directional reconfigurable mesh (DR-Mesh) and complete directional processor arrays with reconfigurable bus systems (CD-PARBS), to solve specified digraph problems. The algorithms of the second approach specifically use the capability of the directional reconfigurable architectures which can control the data flow in each segment of a bus.
In this dissertation, the third approach on non-directional reconfigurable architectures will be proposed to solve many digraph problems. For example, the transitive closure problem can be solved in $O(log ,d(D))$ time on a three-dimensional (3-D) $n! imes!n! imes!n$ reconfigurable mesh (R-Mesh), where $d(D)$ is the diameter of digraph $D$. Based on the same idea used in the transitive closure algorithm, we can solve the following digraph problems: strongly connected graph, strongly connected component (SCC), cyclic digraph checking, tree construction, all-pairs shortest distance, single source shortest distance, diameter, topological sort (TS). These algorithms show the power of the third approach. So we believe this approach is valuable to digraph problems on non-reconfigurable architectures for the high performance computing and time-critical applications.

並列關鍵字

reconfigurable architectures ； reconfigurable mesh (R-Mesh) ； transitive closure (TC) ； strongly connected component (SCC) ； all-pairs shortest distance ； single source shortest distance ； topological sort (TS) ； digraph problems

參考文獻

[2] G. Estrin, “Organization of computer systems: the fixed plus variable structure computer,” in Proc. Western Joint Computer Conf. 1960, Western Joint Computer Conference.

[3] G. Estrin, “Reconfigurable computer origins: the ucla fixed-plus-variable (f+v) structure computer,” IEEE Ann. Hist. Comput., vol. 24, pp. 3–9, 2002.

[4] Y. Ben-Asher, D. Peleg, R. Ramaswami, and A. Schuster, “The power of reconfiguration,” Lecture Notes in Computer Science, vol. 510, pp. 139–150, 1991.

[5] K. Nakano, “A bibliography of published papers on dynamically reconfigurable architectures,” Parallel Processing Letters, vol. 5, pp. 111–124, 1995.

[7] R. Vaidyanathan and J. L. Trahan, Dynamic reconfiguration architectures and algorithms, Kluwer, New York, 2004.