IEICE TRANSACTIONS on Fundamentals
A Fast Algorithm for Crosspoint Assignment under Crosstalk Constraints with Shielding Effects
Summary :
This paper presents a novel algorithm for crosspoint assignment (CPA) that takes into consideration crosstalk noise and shielding effects in deep sub-micron design. We introduce a conditional constraint which is imposed on a sensitive net-pair to detach one net from the other or to put another insensitive net between them for shielding. We provide two algorithms which can handle the conditional constraint: One is based on an ILP, which outputs an exact optimum solution. The other is a fast heuristics whose time complexity is O(n2 log n), where n is the number of pins. In experiments, we tested these algorithms for industrial examples. The results showed that the conditional constraint for shielding released algorithms from a tight space of feasible assignments. Our heuristics ran quickly and attained near optimum solutions.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.12 pp.3258-3264
- Publication Date
- 2004/12/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
- Category
- Physical Design
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
Keiji KIDA, Xiaoke ZHU, Changwen ZHUANG, Yasuhiro TAKASHIMA, Shigetoshi NAKATAKE, "A Fast Algorithm for Crosspoint Assignment under Crosstalk Constraints with Shielding Effects" in IEICE TRANSACTIONS on Fundamentals,
vol. E87-A, no. 12, pp. 3258-3264, December 2004, doi: .
Abstract: This paper presents a novel algorithm for crosspoint assignment (CPA) that takes into consideration crosstalk noise and shielding effects in deep sub-micron design. We introduce a conditional constraint which is imposed on a sensitive net-pair to detach one net from the other or to put another insensitive net between them for shielding. We provide two algorithms which can handle the conditional constraint: One is based on an ILP, which outputs an exact optimum solution. The other is a fast heuristics whose time complexity is O(n2 log n), where n is the number of pins. In experiments, we tested these algorithms for industrial examples. The results showed that the conditional constraint for shielding released algorithms from a tight space of feasible assignments. Our heuristics ran quickly and attained near optimum solutions.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e87-a_12_3258/_p
Copy
@ARTICLE{e87-a_12_3258,
author={Keiji KIDA, Xiaoke ZHU, Changwen ZHUANG, Yasuhiro TAKASHIMA, Shigetoshi NAKATAKE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Fast Algorithm for Crosspoint Assignment under Crosstalk Constraints with Shielding Effects},
year={2004},
volume={E87-A},
number={12},
pages={3258-3264},
abstract={This paper presents a novel algorithm for crosspoint assignment (CPA) that takes into consideration crosstalk noise and shielding effects in deep sub-micron design. We introduce a conditional constraint which is imposed on a sensitive net-pair to detach one net from the other or to put another insensitive net between them for shielding. We provide two algorithms which can handle the conditional constraint: One is based on an ILP, which outputs an exact optimum solution. The other is a fast heuristics whose time complexity is O(n2 log n), where n is the number of pins. In experiments, we tested these algorithms for industrial examples. The results showed that the conditional constraint for shielding released algorithms from a tight space of feasible assignments. Our heuristics ran quickly and attained near optimum solutions.},
keywords={},
doi={},
ISSN={},
month={December},}
Copy
TY - JOUR
TI - A Fast Algorithm for Crosspoint Assignment under Crosstalk Constraints with Shielding Effects
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 3258
EP - 3264
AU - Keiji KIDA
AU - Xiaoke ZHU
AU - Changwen ZHUANG
AU - Yasuhiro TAKASHIMA
AU - Shigetoshi NAKATAKE
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E87-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2004
AB - This paper presents a novel algorithm for crosspoint assignment (CPA) that takes into consideration crosstalk noise and shielding effects in deep sub-micron design. We introduce a conditional constraint which is imposed on a sensitive net-pair to detach one net from the other or to put another insensitive net between them for shielding. We provide two algorithms which can handle the conditional constraint: One is based on an ILP, which outputs an exact optimum solution. The other is a fast heuristics whose time complexity is O(n2 log n), where n is the number of pins. In experiments, we tested these algorithms for industrial examples. The results showed that the conditional constraint for shielding released algorithms from a tight space of feasible assignments. Our heuristics ran quickly and attained near optimum solutions.
ER -
English
