| Presentation | 2003/11/21 A Fast Algorithm for Crosspoint Assignment under Crosstalk Constraints with Shielding Effect Keiji KIDA, Xiaoke ZHU, Changwen ZHUANG, Yashuhiro TAKASHIMA, Shigetoshi NAKATAKE, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we present a fast algorithm for Crosspoint Assignment that takes into consideration crosstalk noise and shielding effects in deep sub-micron design. In our formulation, for crosspoint assignment problem (deciding a position where a global routing tree crosses a global routing cell boundary), we introduce {d, 1}-pitch constraint that takes into consideration crosstalk with shielding effects. Under the constraints, an integer linear programming based algorithm can output an exact optimum solution if there exists a, feasible solution. But, the integer linear programming based algorithm can not be applied to the typical routing system for the large scale design because it takes much calculating time. Therefore, we provide a fast heuristic algorithm for this problem. In experiments, we tested integer linear programming based algorithm and heuristic algorithm for industrial examples, and demonstrated that our heuristics ran quickly and attained near optimum solutions. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | crosspoint assign / crosstalk / shielding effect |
| Paper # | VLD2003-99 |
| Date of Issue |
| Conference Information | |
| Committee | VLD |
|---|---|
| Conference Date | 2003/11/21(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | VLSI Design Technologies (VLD) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Fast Algorithm for Crosspoint Assignment under Crosstalk Constraints with Shielding Effect |
| Sub Title (in English) | |
| Keyword(1) | crosspoint assign |
| Keyword(2) | crosstalk |
| Keyword(3) | shielding effect |
| 1st Author's Name | Keiji KIDA |
| 1st Author's Affiliation | Systems Development Department, SII EDA Technologies Inc.:Faculty of Environmental Engineering, The University of Kitakyushu() |
| 2nd Author's Name | Xiaoke ZHU |
| 2nd Author's Affiliation | Systems Development Department, SII EDA Technologies Inc. |
| 3rd Author's Name | Changwen ZHUANG |
| 3rd Author's Affiliation | Systems Development Department, SII EDA Technologies Inc. |
| 4th Author's Name | Yashuhiro TAKASHIMA |
| 4th Author's Affiliation | Faculty of Environmental Engineering, The University of Kitakyushu |
| 5th Author's Name | Shigetoshi NAKATAKE |
| 5th Author's Affiliation | Faculty of Environmental Engineering, The University of Kitakyushu |
| Date | 2003/11/21 |
| Paper # | VLD2003-99 |
| Volume (vol) | vol.103 |
| Number (no) | 476 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |