The search functionality is under construction.

Author Search Result

[Author] Keiji KIDA(1hit)

1-1hit
  • A Fast Algorithm for Crosspoint Assignment under Crosstalk Constraints with Shielding Effects

    Keiji KIDA  Xiaoke ZHU  Changwen ZHUANG  Yasuhiro TAKASHIMA  Shigetoshi NAKATAKE  

     
    PAPER-Physical Design

      Vol:
    E87-A No:12
      Page(s):
    3258-3264

    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.