| Presentation | 2004/11/25 Stochastic Equi-Length Channel Routing with Channel Height Minimization Yukiko KUBO, Hiroshi MIYASHITA, Yoji KAJITANI, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In VLSI system, a set of signals is often required to be propagated within a torelable skew of delays. Though the delay of.a signal on a wire is determined by a complex electrical environment, it is hard to attain this requirement unless all the nets are routed within a certain skew of length from the source to sinks. There exists some equi-length algorithms to solve such a problem and we also propose a constructive algorithm for channel routing. But the length from a source to sinks of the routes obtained by the algorithm becomes long because it does not consider the height of the channel. In this paper, the algorithm that solves the channel height problem keeping the total length minimum is presented. Because our problem includes the difficulty of the original channel routing problem, it is difficult to obtain the best solution exactly. Therefore we propose a stochastic algorithm to modify parts of the routes iteratively. First, a basic algorithm of equidistance channel routing is introduced. Then the routes obtained by it is given as an initial solution and apply modifications iteratively. This modification process is controlled by Simulated Annealing. The proposed algorithm is implemented and applied to random data. The experimental result shows that the algorithm reduces the height of the channel about 30%. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Channel equi-length routing / Horizontal segments / Vertical constraints / Simulated Annealing / Track Assignment |
| Paper # | VLD2004-68,ICD2004-154,DC2004-54 |
| Date of Issue |
| Conference Information | |
| Committee | ICD |
|---|---|
| Conference Date | 2004/11/25(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 | Integrated Circuits and Devices (ICD) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Stochastic Equi-Length Channel Routing with Channel Height Minimization |
| Sub Title (in English) | |
| Keyword(1) | Channel equi-length routing |
| Keyword(2) | Horizontal segments |
| Keyword(3) | Vertical constraints |
| Keyword(4) | Simulated Annealing |
| Keyword(5) | Track Assignment |
| 1st Author's Name | Yukiko KUBO |
| 1st Author's Affiliation | Faculty of Environmental Engineering, The University of Kitakyushu() |
| 2nd Author's Name | Hiroshi MIYASHITA |
| 2nd Author's Affiliation | Faculty of Environmental Engineering, The University of Kitakyushu |
| 3rd Author's Name | Yoji KAJITANI |
| 3rd Author's Affiliation | Faculty of Environmental Engineering, The University of Kitakyushu |
| Date | 2004/11/25 |
| Paper # | VLD2004-68,ICD2004-154,DC2004-54 |
| Volume (vol) | vol.104 |
| Number (no) | 480 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |