We consider non-uniform wire-sizing for general routing trees under the Elmore delay model. Three minimization objectives are studied: 1) total weighted sink-delay; 2) total area subject to sink-delay bounds; and 3) maximum sink-delay. We first present an algorithm NWSA-wd for minimizing total weighted sink-delays based on iteratively applying the wire-sizing formula in . We show that NWSA-wd always converges to an optimal wire-sizing solution. Based on NWSA-wd and the Lagrangian relaxation technique, we obtained two algorithms NWSA-db and NWSA-md which can optimally solve the other two minimization objectives. Experimental results show that our algorithms are efficient both in terms of runtime and storage. For example, NWSA-wd, with linear runtime and storage, can solve a 6201-wire-segment routing-tree problem using about 1.5-second runtime and 1.3-MB memory on an IBM RS/6000 workstation.
|Original language||English (US)|
|Number of pages||6|
|Journal||IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers|
|State||Published - Dec 1 1996|
|Event||Proceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design - San Jose, CA, USA|
Duration: Nov 10 1996 → Nov 14 1996
ASJC Scopus subject areas