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 from previous approaches in that we derive an explicit area/delay trade-off curve. We achieve this goal by limiting the solution space to the set of topologies induced by a permutation on the sinks of the net. This constraint allows efficient identification of optimal solutions while still providing a rich solution space. We also incorporate simultaneous wire sizing. Our technique consistently produces topologies equalling the performance of previous approaches with substantially less area overhead.