Abstract
We study in this thesis the problem of adaptive routing tree reconstruction with simultaneous flip-flop and buffer insertion, where a routing tree is given for considering flip-flop and buffer insertion with blockage avoidance and net segments of the tree are adaptively re-routed such that the clock period of the resultant registered-buffered tree is met and the latency is as small as possible. Our focus is to find alternative registered-buffered paths between each internal node inside a blockage and its parent node. To this end, we modify an existing registered-buffered path construction algorithm to find a set of irredundant registered-buffered paths (instead of just a single path). All the paths are found within a bounding region containing both the internal node and the parent node. The size of the routing grid graph imposed on the bounding region is scalable for considering tradeoff between CPU time and solution quality. Our approach can be also easily extended to handle several other problems, such as a latency constrained problem and a buffer insertion only problem. We conduct experiments to compare our approaches with two existing algorithms, the MiLa and GiLa algorithms. In comparison to the MiLa algorithm, our approach is able to find a solution with the same latency (for about half of the test cases) or even better latency (for the remaining test cases) and the same wirelnegth, while the buffer/flip-flop usage and CPU time are comparable or acceptable. In comparison to the GiLa algorithm, our approach is able to find a feasible solution for each test case while the Gila algorithm fails to do so for several test cases.