A Fast Algorithm for Crosspoint Assignment under Crosstalk Constraints with Shielding Effects(Physical Design)(<Special Section>VLSI Design and CAD Algorithms)
スポンサーリンク
概要
- 論文の詳細を見る
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^2 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.
- 社団法人電子情報通信学会の論文
- 2004-12-01
著者
-
Takashima Yasuhiro
The Department Of Information And Media The University Of Kitakyushu
-
Takashima Yasuhiro
The Department Of Electrical And Electronic Engineering Tokyo Institute Of Technology
-
Kida Keiji
Research And Development Division Jedat Innovation Inc.:dept. Of Information And Media Sciences The
-
Nakatake S
The Department Of Information And Media The University Of Kitakyushu
-
ZHU Xiaoke
Research and Development Division, Jedat Innovation Inc.
-
TAKASHIMA Yasuhiro
Dept. of Information and Media Sciences, The University of Kitakyushu
-
NAKATAKE Shigetoshi
Dept. of Information and Media Sciences, The University of Kitakyushu
-
ZHUANG Changwen
Research and Development Division, Jedat Innovation Inc.
-
Takashima Youichi
The Department Of Information And Media The University Of Kitakyushu
-
Zhu Xiaoke
Research And Development Division Jedat Innovation Inc.
-
Zhuang Changwen
Research And Development Division Jedat Innovation Inc.
-
Nakatake Shigetoshi
Department Of Information And Media Engineering The University Of Kitakyushu
関連論文
- Incremental Buffer Insertion and Module Resizing Algorithm Using Geometric Programming
- The Oct-Touched Tile : A New Architecture for Shape-Based Routing( Analog Circuit Techniques and Related Topics)
- A Device-Level Placement with Schema Based Clusters in Analog IC Layouts(Analog Layout)(VLSI Design and CAD Algorithms)
- A Fast Algorithm for Crosspoint Assignment under Crosstalk Constraints with Shielding Effects(Physical Design)(VLSI Design and CAD Algorithms)
- Abstraction and Optimization of Consistent Floorplanning with Pillar Block Constraints(Floorplan)(VLSI Design and CAD Algorithms)
- The 3D-Packing by Meta Data Structure and Packing Heuristics(Special Section on Discrete Mathematics and Its Applications)
- A Performance-Driven Circuit Bipartitioning Method Considering Time-Multiplexed I/Os(Discrete Mathematics and Its Applications)
- Optimal Time-Multiplexing in Inter-FPGA Connections for Accelerating Multi-FPGA Prototyping Systems
- Digital Watermarking Technique for Motion Pictures Based on Quantization(Special Section on Cryptography and Information Security)
- Improved Digital Watermark Robustness against Translation and / or Cropping of an Image Area(Special Section on Cryptography and Information Security)
- Recovery from Marked Altered Consciousness in a Patient with Adult-onset Type II Citrullinemia Diagnosed by DNA Analysis and Treated with a Living Related Partial Liver Transplantation
- Assignment of Intervals to Parallel Tracks with Minimum Total Cross-Talk
- Routability of FPGAs with Extremal Switch-Block Structures(Special Section on Discrete Mathematics and Its Applications)
- A transistor-level symmetrical layout generation method for analog device (VLSI設計技術)