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

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)884-890
Number of pages7
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume13
Issue number7
DOIs
Publication statusPublished - 1994 Jan 1

Fingerprint

Parallel processing systems
Coloring
Parallel algorithms
Hardware

Keywords

  • Complexity
  • channel assignment problem
  • computation model
  • minimum-coloring problem
  • parallel processing
  • processor array
  • reconfigurable bus system

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Cite this

@article{587810ea37794f66b0b414233c4be164,
title = "Constant-Time Algorithms for the Channel Assignment Problem on Processor Arrays With Reconfigurable Bus Systems",
abstract = "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.",
keywords = "Complexity, channel assignment problem, computation model, minimum-coloring problem, parallel processing, processor array, reconfigurable bus system",
author = "Shun-Shii Lin",
year = "1994",
month = "1",
day = "1",
doi = "10.1109/43.293945",
language = "English",
volume = "13",
pages = "884--890",
journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",
issn = "0278-0070",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "7",

}

TY - JOUR

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

AU - Lin, Shun-Shii

PY - 1994/1/1

Y1 - 1994/1/1

N2 - 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.

AB - 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.

KW - Complexity

KW - channel assignment problem

KW - computation model

KW - minimum-coloring problem

KW - parallel processing

KW - processor array

KW - reconfigurable bus system

UR - http://www.scopus.com/inward/record.url?scp=0028461969&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028461969&partnerID=8YFLogxK

U2 - 10.1109/43.293945

DO - 10.1109/43.293945

M3 - Article

AN - SCOPUS:0028461969

VL - 13

SP - 884

EP - 890

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

SN - 0278-0070

IS - 7

ER -