IEICE TRANSACTIONS on Fundamentals
An Algorithm to Position Fictitious Terminals on Borders of Divided Routing Areas
Summary :
A parallel detailed router based on the area division is one of important tools to overcome the increase of CPU time required for routing of a very large multilayer SOG. In order to conduct routing in each divided area independently, fictitious terminals are introduced on the border of each divided area, and routes connected to the fictitious terminals are concatenated to complete the final detailed routes. In this paper, we consider a problem how to position such fictitious terminals on borders, so as to make each detailed routing in a divided area easy. We formulate this problem as a minimum cost assignment problem, and propose an iterative improvement algorithm. We also give some experimental results which indicate the effectiveness of the algorithm.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.11 pp.2424-2430
- Publication Date
- 1999/11/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Atsushi KAMOSHIDA, Shuji TSUKIYAMA, "An Algorithm to Position Fictitious Terminals on Borders of Divided Routing Areas" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 11, pp. 2424-2430, November 1999, doi: .
Abstract: A parallel detailed router based on the area division is one of important tools to overcome the increase of CPU time required for routing of a very large multilayer SOG. In order to conduct routing in each divided area independently, fictitious terminals are introduced on the border of each divided area, and routes connected to the fictitious terminals are concatenated to complete the final detailed routes. In this paper, we consider a problem how to position such fictitious terminals on borders, so as to make each detailed routing in a divided area easy. We formulate this problem as a minimum cost assignment problem, and propose an iterative improvement algorithm. We also give some experimental results which indicate the effectiveness of the algorithm.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_11_2424/_p
Copy
@ARTICLE{e82-a_11_2424,
author={Atsushi KAMOSHIDA, Shuji TSUKIYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Algorithm to Position Fictitious Terminals on Borders of Divided Routing Areas},
year={1999},
volume={E82-A},
number={11},
pages={2424-2430},
abstract={A parallel detailed router based on the area division is one of important tools to overcome the increase of CPU time required for routing of a very large multilayer SOG. In order to conduct routing in each divided area independently, fictitious terminals are introduced on the border of each divided area, and routes connected to the fictitious terminals are concatenated to complete the final detailed routes. In this paper, we consider a problem how to position such fictitious terminals on borders, so as to make each detailed routing in a divided area easy. We formulate this problem as a minimum cost assignment problem, and propose an iterative improvement algorithm. We also give some experimental results which indicate the effectiveness of the algorithm.},
keywords={},
doi={},
ISSN={},
month={November},}
Copy
TY - JOUR
TI - An Algorithm to Position Fictitious Terminals on Borders of Divided Routing Areas
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2424
EP - 2430
AU - Atsushi KAMOSHIDA
AU - Shuji TSUKIYAMA
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 1999
AB - A parallel detailed router based on the area division is one of important tools to overcome the increase of CPU time required for routing of a very large multilayer SOG. In order to conduct routing in each divided area independently, fictitious terminals are introduced on the border of each divided area, and routes connected to the fictitious terminals are concatenated to complete the final detailed routes. In this paper, we consider a problem how to position such fictitious terminals on borders, so as to make each detailed routing in a divided area easy. We formulate this problem as a minimum cost assignment problem, and propose an iterative improvement algorithm. We also give some experimental results which indicate the effectiveness of the algorithm.
ER -
English
