可重組態匯流排系統之處理器陣列上求影像元件面積及周長的常數時間演算法

作者:林順喜(國立臺灣師範大學資訊教育研究所)

摘要：

在本論文中，我們提出O（1）時間的演算法，以求出一n*n影像每一個元件的面積及周長。此問題以前從沒有在O（1）時間內被解決過，即使是在即理想的CRCW PRAM計算模型上。就大型的問題而言，我們需要快速的硬體方案。我們的演算法乃使用可重組態匯流排系統之處理器陣列（簡稱PARBS），它含有一處理器陣列以及一可重組態匯流排系統。為了能以常數時間之複雜度解決此問題，我們先利用inerative-PARBS的設計觀念〔13〕，類似循序程式語言中的FOR迴圈，使處理中的資料能夠迴繞數次（固定次數），我們可將之視為一種硬體的副程式。根據這種特別的架構，我們得以在PARBS發展出常數時間的平行演算法。以下是我們所得到的心結果：
(1)一具有p個元件之n*n影像每一個元件的面積，可在一含有O(p*n^2+ε)個處理器之PARBS上，以O（1）時間球出，此處ε＞o。
(2)一具有p個元件之n*n影像每一個元件的周長，可在一含有O(max{n,p}*n^2+ε)個處理器之PARBS上，以O（1）時間求出，此處ε＞o。

關鍵詞：影像元件面積及周長、計算模型、影像處理、平行處理、可重組態匯流排系統

《詳全文》

Constant-Time Algorithms for the Area and Perimeter of Image Components on Processor Arrays with Reconfigurable Bus Systems

Author: Shun-Shii Lin(Department of Information and Computer Education, National Taiwan Normal University)

Abstract：

In this paper, we present O(l) time algorithms to determine the area and the perimeter of each component of an n*n image. This problem has not been solved in O(l) time before, even in the idealistic CRCW PRAM model. For large-sized problems, it is desirable to have fast hardware solutions. Our algorithms are based on the proces-sor arrays with a reconfigurable bus system (abbreviated as PARBS) that consists of a processor array and a reconfigurable bus system. In order to solve this problem with constant time complexity, we first propose the concept of iterative-PARBS [13], which is similar to the FOR-loop construct in sequential programming languages. The iterative-PARBS is a building block in which the processing data can be routed through itself several times. We can think of it as a "hardware subroutine". Based on this novel scheme, we are able to explore constant-time parallel algorithms on PARBS. The fol-lowing new results are derived in this study:
(1)The area of each component of an n*n image with p components can be computed in O(l) time on a PARBS with O(p*n^2+ε) processors for any fixed ε >0.
(2)The perimeter of each component of an n*n image with p components can be com-puted in O(l) time on a PARBS with O(max{n,p}*n^2+ε) processors for any fixed ε >0.

Keywords：Area and perimeter of image components, computation model, image processing, parallel processing, reconfigurable bus system