## Abstract

The authors study the problem of shifting vias to obtain more compactable two-layer channel routing solutions. Let S be a grid-based two-layer channel routing solution. Let v_{c} be the number of grid points on column c that are occupied by vias. Let w_{c} be the number of grid points on column c that are occupied by horizontal wires. They define the height of a column c to be the quantity h_{c}=Av_{c}+Bw_{c}+C, where A, B, C are some design rule dependent constants. A column is said to be critical if it is a column with maximum height. Let H_{S} be the height of the critical column(s) in S. In general, H_{S} is a good measure of the channel height after compaction. They show that the problem of shifting vias to minimize H_{S} can be solved optimally in polynomial time. The complexity of the optimal via-shifting algorithm is O(WL(V+L)log^{2}(V+L)) where W, L, and V are the number of tracks in S, the number of columns in S, and the number of vias in S, respectively.

Original language | English |
---|---|

Title of host publication | Proceedings of the European Design Automation Conference, EDAC 1990 |

Publisher | IEEE |

Pages | 186-190 |

Number of pages | 5 |

ISBN (Print) | 0818620242, 9780818620249 |

DOIs | |

Publication status | Published - Mar 1990 |

Event | 1990 European Design Automation Conference, EDAC 1990 - Glasgow, United Kingdom Duration: 12 Mar 1990 → 15 Mar 1990 https://ieeexplore.ieee.org/xpl/conhome/273/proceeding |

### Publication series

Name | Proceedings of the European Design Automation Conference, EDAC |
---|

### Conference

Conference | 1990 European Design Automation Conference, EDAC 1990 |
---|---|

Country/Territory | United Kingdom |

City | Glasgow |

Period | 12/03/90 → 15/03/90 |

Internet address |

## Scopus Subject Areas

- Hardware and Architecture
- Electrical and Electronic Engineering
- Control and Optimization
- Modelling and Simulation