ABSTRACT
The algorithm performs buffer insertion on a fixed and embedded tree and produces an optimal timing solution under Elmore delay model. In other practical formulations, routing or buffering feasibility is not considered a zero or one property. In addition, algorithm complexity and runtime is a very important practical factor given that hundreds of thousands of nets may need to be buffered within a given CPU time budget. A more robust and predictable approach proposes simultaneous route construction while performing buffer insertion. The chapter presents some of the methods that combine buffer insertion and topology construction. Propagation of candidate solutions through the routing graph is performed using timing-driven maze routing approach with simultaneous buffer insertion. Once the partially embedded topology tree is constructed, many of the known techniques can be used to perform two-pin routing and buffer insertion between the tree nodes.
