在排列圖及區間圖上一些問題的平行演算法設計及分析

The Designs and Analyses of Parallel Algorithms for Some Problems on Permutation and Interval Graphs

賴有得(Yue-Der Lai)

指導教授 ： 林順喜

國立臺灣師範大學/教育學院/資訊教育學系/碩士(1999年)

摘要

摘 要
在排列圖及區間圖上一些問題的平行演算法設計及分析
具有可重組態匯流排系統之處理器陣列 (Processor Arrays with Reconfigurable Bus Systems，簡稱PARBS) 為一種平行處理的計算模型，它具有一個處理器陣列和一個可重組態匯流排系統。在此模型中，我們可以動態地調整所有處理器的組態，進而將整個處理器陣列切割成不同的子網路，在子網路上我們可以做快速的資料傳輸動作，於是便有許多研究者在此平行計算模型上發展平行演算法，以解決許多複雜的問題。
在本篇論文中，我們設計出利用O(p)個處理器的一維PARBS在O(n/p + log p)的時間內計算出前置最大值、後置最小值和前置和的演算法。另外，我們也發展出一個可以在O(n/p)的時間內利用O(p)個處理器來過濾一個非遞減數列中的重覆資料演算法。
在排列圖上，我們發展出連通測試、尋找連通元件、尋找切點和尋找擴張樹的演算法；在區間圖上，我們發展出連通測試、尋找連通元件、尋找切點、尋找橋接線和尋找擴張樹的演算法。這些問題均可以在O(n/p + log p)的時間內，利用O(p)個處理器的一維PARBS來解決。上述的所有演算法，當p = O(n/log n)時，整個演算法的計算成本均可以達到成本最佳化。
關鍵字：可重組態匯流排系統之處理器陣列、成本最佳化演算法、前置最大值、後置最小值、前置和、過濾非遞減數列重覆資料、排列圖、區間圖、連通測試問題、連通元件問題、切點問題、橋接線問題、擴張樹問題

關鍵字

可重組態匯流排系統之處理器陣列 ； 成本最佳化演算法 ； 前置最大值 ； 後置最小值 ； 前置和 ； 過濾非遞減數列重覆資料 ； 排列圖 ； 區間圖

並列摘要

ABSTRACT
The Designs and Analyses of Parallel Algorithms for Some
Problems on Permutation and Interval Graphs
A processor array with reconfigurable bus system (abbreviated to PARBS) is a parallel computation model that consists of processor array and a reconfigurable bus system. In this model, we can dynamically setup the configurations of all processors in order to form different sub-buses in the processor array. In a sub-bus, the data can be broadcasted in fixed units of time. There are a lot of researchers that develop parallel algorithms on this computation model in order to solve many complicated problems.
In this thesis, we propose algorithms for computing prefix maxima, suffix minima and prefix sum in O(n/p+log p) time on a 1D PARBS with O(p) processors. We also design an algorithm to filter out duplicate data in a nondecreasing sequence in O(n/p) time on a 1D PARBS with O(p) processors.
In addition, we develop algorithms for finding all connected components, articulation points, and a spanning tree of a permutation graph. We also develop algorithms for finding all connected components, articulation points, bridges, and a spanning tree of an interval graph. These algorithms take O(n/p + log p) time on a 1D PARBS with O(p) processors. If p = O(n/log n), they all become cost optimal.
Keyword: PARBS (Processor Arrays with Reconfigurable Bus Systems), cost optimal algorithm, prefix maxima, suffix minima, prefix sum, filter out duplicate data, permutation graph, interval graph, connectivity test problem, connected component problem, articulation point problem, bridge problem, spanning tree problem.

並列關鍵字

PARBS (Processor Arrays with Reconfigurable Bus Systems) ； cost optimal algorithm ； prefix maxima ； suffix minima ； prefix sum ； filter out duplicate data ； permutation graph ； interval graph

參考文獻

[1] Akl, S. G., Parallel computation - Models and Methods, Prentice-Hall Inc.,New Jersey, (1997).

[3] Atallah, M. J., and Kosaraju, S. R., "Graph problems on a mesh-connected processor array," Journal of the Association for Computing Machinery, vol. 31, no. 3, pp. 649-667, (1984).

[4] Bodlaender, H., Kloks, T., and Kratsch, D., "Treewidth and pathwidth of permutation graphs," SIAM Journal on Discrete Mathematics, vol. 8, no. 4, pp. 606-616, (1996).

[5] Chao, H. S., Hsu, F. R., and Lee, R. C. T., "An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs," Information Processing Letters, vol. 61, no. 6, pp. 311-316, (1997).

[6] Chen, Y. W., Horng, S. J., Kao, T. W., Tsai, H. R., and Tsai, S. S., "Parallel connectivity algorithms on permutation graphs," Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, pp. 97-104, (1994).