林順喜2014-10-272014-10-271995-06-??http://rportal.lib.ntnu.edu.tw/handle/20.500.12235/17481在本論文中，我們提出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.影像元件面積及周長計算模型影像處理平行處理可重組態匯流排系統Area and perimeter of image componentsComputation modelImage processingParallel processingReconfigurable bus system