Optimal non-uniform wire-sizing under the Elmore delay model

摘要: We consider non-uniform wire-sizing for general routing trees under the Elmore delay model. Three minimization objectives are studied: (1) total weighted sink-delays; (2) area subject to sink-delay bounds; and (3) maximum sink delay. first present an algorithm NWSA-wd minimizing sink-delays based on iteratively applying formula in [1]. show that always converges optimal solution. Based Lagrangian relaxation technique, we obtained two algorithms NWSA-db NWSA-md which can optimally solve other objectives. Experimental results our efficient both terms of runtime storage. For example, NWSA-wd, with linear storage, a 6201-wire segment routing-tree problem using about 1.5-second 1.3-MB memory IBM RS/6000 workstation.