Abstract
由於電子技術的進步神速, 各種平行計算機結構紛紛被提出,其中, 網狀 連結計算機 (MESH-CONNECTED COMPUTERS) 由於其架構簡單而有規則, 至 今仍受到相當重視, 然而由於其結構所導致之直徑太大, 使其在長距離通 訊上之效率較差, 對於一些含長距離通訊之應用, 採用網狀連結計算機, 並不適合。 因此, 許多研究均在探討如何加強其處理機間之連結架構以 改進其缺點。在這些研究當中, 一種很有效率的方法便是在網狀連結方式 以外加入具有廣播功能的巴士 (Broadcasting Bus) 。本篇論文便是探討 在具有廣播功能的網狀連結計算機上的平行演算法之設計。本篇論文探討 在網狀連結計算機上的平行演算法之設計,包括: 二組網狀連結計算機 (2-MCCs) 及具有可重組巴士的網狀連結計算機 (Reconfigurable Meshes)。在 2-MCCs 上, 我們使用方形的 2-MCCS 針對多重搜尋問題 (MULTIPLE SEARCH PROBLEM) 設計快速而有效率的平行演算法。 RECONFIGURABLE MESHES 最大的特點在於其負責連結處理單元的可重組巴 士系統, 可重組巴士為一種可動態地調整處理單元間連結組態的廣播巴 士, 因此我們可以根據問題本身的通訊需求, 動態地調整組態以達到最有 效率的處理機連結。在 RECONFIGURABLE MESHES 上,我們首先將針對多重 搜尋問題設計一快速而有效率的平行演算法, 其次我們將針對區間圖形 (INTERVAL GRAPH)上的關節點 (ARTICULATION POINT) 和橋接 (BRIDGE) 設計一種在 RECONFIGURABLE MESHES 上可快速執行的方法。第三個欲探 討之問題為凸殼計算 (CONVEXITY OMPUTATION)上的直徑 (DIAMETER) 及 最小方形面積 (SMALLEST-AREA ENCLOSING RECTANGLE) 兩個問題, 我們 提出一種在 RECONFIGURABLE MESHES 可快速執行的方法。這個演算法是 目前為止處理時間複雜度 (TIME COMPLEXITY) 最少的平行演算法。 In this thesis, we will discuss the design of parallel algorithms on mesh-connected architectures, including mesh- connected computers(MCCs)and mesh-connected computers with reconfigurable bus system(Reconfigurable Meshes). On the pure mesh-connected computers, it will be first shown that multiple search problem can be solved in $O(n^{1/2})$ time on the $n^{1/2 }\times n^{1/2}$ mesh-connected computers. Then, on the mesh- connected computers with reconfigurable bus system, parallel computation will be studied. A reconfigurable mesh consists a mesh-connected processor array superimposed with a reconfigurable bus system whose configuration can be dynamically changed. First, an constant time algorithm for solving the multiple search problem with n data and m queries$( m\leq n)$ is designed on an $n^{1/2}\times n^{1/2}\times n^{1/2 }$ 3-dimensional reconfigurable mesh. Next, we propose a constant time algorithm for finding bridges and articulation points of an interval graph with n intervals on an $n\times n$ 2-dimensional reconfigurable mesh. Finally, we will propose a novel strategy to compute the diameter of an n-vertex convex polygon. Accordingly, an $O(\log \log n)$ time algorithm is achieved on an $n^{1/2}\times n^{1/2}\times n$ reconfigurable mesh. In addition, we will also show that the smallest-area rectangle enclosing an n-vertex convex polygon can be computed in $O(\log\log n)$ time by adopting three-dimensional reconfigurable meshes of size $O(n^{2})$.