An efficient routing tree construction algorithm with buffer insertion, wire sizing and obstacle considerations

Abstract

<p>In this thesis, we present a fast algorithm to construct a performance driven routing tree with simultaneous buffer insertion and wire sizing in the presence of wire and buffer obstacles. Recently several algorithms like Ptree, Stree, Sptree, and graph-RTBW have been published addressing the routing tree construction problem. But all these algorithms are slow and not scalable. Here we present an algorithm which is fast and scalable with problem size. The main idea of algorithm is to specify some important high-level features of the whole routing tree so that it can be broken down into several components. We apply stochastic search to find the best specification. Since we need very few high-level features to evaluate a routing tree, the size of stochastic search space is small which can be searched in very less time. The solutions for the components are either pre-generated and stored in lookup tables, or generated by extremely fast algorithms whenever needed. Since, the solutions of the components can be constructed efficiently, we can construct and evaluate the whole routing tree efficiently for each specification. Experimental results show that, for trees of moderate size, our algorithm is at least several hundred times faster than the recently proposed algorithms, Sptree and graph-RTBW, with not much difference in delay and resource consumption.</p>