New performance driven routing techniques with explicit area/delay tradeoff and simultaneous wire sizing

Abstract

We present new algorithms for construction of performance driven Rectilinear Steiner Trees under the Elmore delay model. Our algorithms represent a departure f r om previous approaches in that we derive an explicit area/delay tradeo curve. We achieve this goal by limiting the solution space to the set of topologies induced b y a p ermutation on the sinks of the net. This constraint allows ecient identication of optimal solutions while still providing a rich solution space. We also incorporate simultaneous wire sizing. Our technique consistently p r o duces topologies equalling the performance o f previous approaches with substantially less area overhead.