可重組態格狀網路上有向圖問題之常數時間演算法

Constant-time Algorithms for Some Digraph Problems on RMESH

楊惠玲(HUI-LING YEO)

指導教授 ： 林順喜

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

摘要

具有方向性的可重組態格狀網路(Directed Reconfigurable Mesh，簡稱DRM)為一種平行處理的計算模型，一個三維具有方向性的DRM包含一個nxnxn處理器的立體形陣列和一個可重組態的匯流排系統。在此三維的DRM模型中，每個處理器都有六個方向的通訊埠，每個方向的通訊埠有輸入資料的輸入埠(input port)和輸出資料的輸出埠(output port)。我們可以任意動態重組所有處理器的組態，進而將處理器陣列切割成數個不同的獨立子網路，在子網路中我們可以做快速的資料傳輸與計算，於是便有研究者藉由這個平行模型，發展出更有效率或常數時間的平行演算法，以解決許多具有平行性和方向性的複雜問題。
在本篇論文中，我們首先提出了一個嶄新的、針對有向圖形上的遞移包矩陣演算法。我們的演算法可以在O(1)時間內利用O(nxnxn)個處理器在三維的DRM模型上完成計算。此外，再藉由這個常數時間遞移包矩陣演算法以及有向圖的特性，我們可以解決其他有向圖形上的問題，包括有向圖的緊密連通測試、尋找緊密連通元件、拓撲排序、以及無迴圈有向圖的單一端點最短單位路徑，這些問題均可在O(1)時間內，利用O(nxnxn)個處理器在三維的DRM模型上完成演算法的計算。

關鍵字

具有方向性的可重組態格狀網路 ； 有向圖形 ； 無迴圈有向圖 ； 常數時間演算法 ； 遞移包矩陣 ； 緊密連通 ； 緊密連通元件 ； 拓撲排序

並列摘要

A directed reconfigurable mesh(abbreviated to DRM) is a parallel computation model, which consists of a 3-dimensional array with n^3 processors and a reconfigurable bus system. In this 3-D model, each processor has six direction’s switches and there is one input port and one output port for each direction. We can dynamically setup the configurations of all processors in order to form different and independent sub-buses in the processor array. In each sub-buses the data can be broadcasted in fixed units of time. There are a lot of researchers that develop efficient or constant-time algorithms based on this parallel computation model in order to solve many complicated problems.
In this thesis, we propose a new O(1)-time algorithm for computing the transitive closure of digraph. Our algorithm is designed on a 3-dimensional nxnxn DRM, where n is the number of vertices in the graph. Using the O(1)-time transitive closure algorithms and the properties of digraph, we are able to develop many other related digraph algorithms that take O(1) time on a 3-dimensional nxnxn DRM. These problems include strongly connected component testing, finding the strongly connected component, topological sort, and the single source shortest path of acyclic digraph.

並列關鍵字

directed reconfigurable mesh(DRM) ； directed graph ； acyclic digraph ； constant-time algorithm ； transitive closure ； strongly connected component testing ； strongly connected component ； topological sort

參考文獻

【4】Chen, G. H., Wang, B. F. and Lu, C. J., “On the Parallel Computation of the Algebraic Path Problem,” IEEE Transactions on Parallel and Distributed Systems, Vol. 3, No. 2, pp. 251-256(1992).

【2】Bertossi, A. A. and Mei, A., “Constant Time Dynamic Programming on Directed Reconfigurable Networks,” IEEE Transactions on Parallel and Distributed Systems. Vol. 11, No. 6, pp. 529-536(July 2000).

【3】Chen, D. Z. and Lee, D. T., “Solving the All-Pair Shortest Path Problem on Interval and Circular-Arc Graphs,” Parallel Processing Symposium, 1994. Proceedings., Eighth International, pp.224 –228(1994).

【6】Das, S. K. and Deo, N., “Divide-and-Conquer-Based Optimal Parallel Algorithms for Some Graph Problems on EREW PRAM Model,” IEEE Transactions on circuits and systems. Vol. 35, no. 3, pp. 312-322(March 1988).

【7】Dey, S. and Srimani, P. K., “Fast Parallel Algorithm for All-Pairs Shortest Path Problem and its VLSI implementation,” IEE proceedings, Vol. 136, Pt. E, No. 2, pp. 85-89(1989).