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

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.