A Fast Algorithm for Crosspoint Assignment under Crosstalk Constraints with Shielding Effects

Keiji KIDA; Xiaoke ZHU; Changwen ZHUANG; Yasuhiro TAKASHIMA; Shigetoshi NAKATAKE

A Fast Algorithm for Crosspoint Assignment under Crosstalk Constraints with Shielding Effects

Keiji KIDA, Xiaoke ZHU, Changwen ZHUANG, Yasuhiro TAKASHIMA, Shigetoshi NAKATAKE

Full Text Views

0

Cite this

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(n² 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

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(n² 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(n² 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(n² 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 -