Constant-Time Algorithms for the Channel Assignment Problem on Processor Arrays With Reconfigurable Bus Systems

Shun Shii Lin*

*此作品的通信作者

研究成果: 雜誌貢獻期刊論文同行評審

3 引文 斯高帕斯(Scopus)

摘要

In this paper, we present an ()(l) time algorithm to solve the minimum coloring problem defined on a set of intervals, which is also called the channel assignment problem. This problem has not been solved in O(1) time before, even on the idealistic CRCW PRAM model. For large-sized problems, it is desirable to have fast hardware solutions. Our algorithm is based on the processor arrays with a reconfigurable bus system (abbreviated to PARBS) that consists of a processor array and a reconfigurable bus system. In order to solve this problem with constant time complexity, we first transform the “left-edge” channel assignment algorithm to the parenthesis-matching problem. Based on this novel scheme, we are able to explore constant-time parallel algorithms to solve the minimum coloring problem for n intervals, which is also called the channel assignment problem, on a PARBS with ()(n2) processors.

原文英語
頁(從 - 到)884-890
頁數7
期刊IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
13
發行號7
DOIs
出版狀態已發佈 - 1994 7月

ASJC Scopus subject areas

  • 軟體
  • 電腦繪圖與電腦輔助設計
  • 電氣與電子工程

指紋

深入研究「Constant-Time Algorithms for the Channel Assignment Problem on Processor Arrays With Reconfigurable Bus Systems」主題。共同形成了獨特的指紋。

引用此