An Improved Algorithm for the Net Assignment Problem

Takao ONO; Tomio HIRATA

An Improved Algorithm for the Net Assignment Problem

Takao ONO, Tomio HIRATA

Full Text Views

0

Share
Cite this

Summary :

In this paper, we consider the net assignment problem in the logic emulation system. This problem is also known as the board-level-routing problem. There are field programmable logic arrays (FPGAs) and crossbars on an emulator board. Each FPGA is connected to each crossbar. Connection requests between FPGAs are called nets, and FPGAs are interconnected through crossbars. We are required to assign each net to the suitable crossbar. This problem is known to be NP-complete in general. A polynomial time algorithm is known for a certain restricted case, in which we treat only 2-terminal nets. In this paper we propose a new polynomial time algorithm for this case.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1161-1165

Publication Date: 2001/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Takao ONO, Tomio HIRATA, "An Improved Algorithm for the Net Assignment Problem" in IEICE TRANSACTIONS on Fundamentals, vol. E84-A, no. 5, pp. 1161-1165, May 2001, doi: .
Abstract: In this paper, we consider the net assignment problem in the logic emulation system. This problem is also known as the board-level-routing problem. There are field programmable logic arrays (FPGAs) and crossbars on an emulator board. Each FPGA is connected to each crossbar. Connection requests between FPGAs are called nets, and FPGAs are interconnected through crossbars. We are required to assign each net to the suitable crossbar. This problem is known to be NP-complete in general. A polynomial time algorithm is known for a certain restricted case, in which we treat only 2-terminal nets. In this paper we propose a new polynomial time algorithm for this case.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e84-a_5_1161/_p

Copy

@ARTICLE{e84-a_5_1161,
author={Takao ONO, Tomio HIRATA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Improved Algorithm for the Net Assignment Problem},
year={2001},
volume={E84-A},
number={5},
pages={1161-1165},
abstract={In this paper, we consider the net assignment problem in the logic emulation system. This problem is also known as the board-level-routing problem. There are field programmable logic arrays (FPGAs) and crossbars on an emulator board. Each FPGA is connected to each crossbar. Connection requests between FPGAs are called nets, and FPGAs are interconnected through crossbars. We are required to assign each net to the suitable crossbar. This problem is known to be NP-complete in general. A polynomial time algorithm is known for a certain restricted case, in which we treat only 2-terminal nets. In this paper we propose a new polynomial time algorithm for this case.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - An Improved Algorithm for the Net Assignment Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1161
EP - 1165
AU - Takao ONO
AU - Tomio HIRATA
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E84-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2001
AB - In this paper, we consider the net assignment problem in the logic emulation system. This problem is also known as the board-level-routing problem. There are field programmable logic arrays (FPGAs) and crossbars on an emulator board. Each FPGA is connected to each crossbar. Connection requests between FPGAs are called nets, and FPGAs are interconnected through crossbars. We are required to assign each net to the suitable crossbar. This problem is known to be NP-complete in general. A polynomial time algorithm is known for a certain restricted case, in which we treat only 2-terminal nets. In this paper we propose a new polynomial time algorithm for this case.
ER -