Please use this identifier to cite or link to this item: http://rportal.lib.ntnu.edu.tw:80/handle/77345300/17481
Title: Constant-Time Algorithms for the Area and Perimeter of Image Components on Processor Arrays with Reconfigurable Bus Systems
Other Titles: 可重組態匯流排系統之處理器陣列上求影像元件面積及周長的常數時間演算法
Authors: 林順喜
Issue Date: Jun-1995
Publisher: 國立臺灣師範大學研究發展處
Office of Research and Development
Abstract: 在本論文中,我們提出0(1時間的演算法,以求出一n*n影像每一個元件的面積及周長。此問題以前從沒有在0(1)時間內被解決過,即使是在極理想的 CRCWPRAM計算模型上。就大型的問題而言,我們需要快速的硬體方案。我們的演算法乃使用可重組態匯流排系統之處理器陣列(簡稱PARES),它含有一處理器陣列以及一可重組態匯流排系統。為了能以常數時間之複雜度解決此問題,我們先利用Iterative-PARES的設計觀念[13),類似循序程式語言中的FOR迴圈,使處理中的資料能夠迴繞數次(固定次數),我們可將之視為一種硬體的副程式。根據這種特別的架構,我們得以在PARES上發展出常數時間的平行演算法。
In this paper, we present 0(1) time algorithms to determine the area and theperimeter of each component of an n*n image. This problem has not been solved inO(1) 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 processor arrays with a reconfigurable bus system (abbreviated as PARES) that consists of aprocessor array and a reconfigurable bus system. In order to solve this problem withconstant time complexity, we first propose the concept of iterative- PARBS [13], which issimilar to the FOR-loop construct in sequential programming languages. The iterativePARBS is a building block in which the processing data can be routed through itselfseveral times. We can think of it as a "hardware subroutine". Based on this novelscheme, we are able to explore constant-time parallel algorithms on PARBS. The following 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(1) time on a PARBS with 0(p*n2+ε ) processors for any fixed ε >0.(3) The perimeter of each component of an n*n image with p components can be computed in 0(1) time on a PARBS with0( maxn,p*n2+ε ) processors for any fixedε >0.
URI: http://rportal.lib.ntnu.edu.tw//handle/77345300/17481
Other Identifiers: 9D63E0CB-CA87-3436-DE36-563EBCCB6088
Appears in Collections:師大學報

Files in This Item:
File SizeFormat 
ntnulib_ja_L0801_0040_135.pdf639.71 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.