Non-tree Wire Sizing Using Symbolic Moment Calculator

As the feature size of the chip in Integrated Circuit (IC) scales down rapidly, the interconnect delay has exceeded the gate delay and become a dominant factor of the overall delay on the chip. Interconnect has become the current design focus in the integrated circuit design practice. There is tremendous research on this topic in the past twenty years, including interconnect modeling, analysis, optimization, manufacturing, etc. Since the circuits become more and more complex, we need to model interconnect as a non-tree circuit. But due to the complicate structure of the non-tree, the traditional methods of analyzing and optimizing the tree structure circuits can not be directly applied to non-tree circuits. New approaches to handle the non-tree circuits urgently needed to be explored.This paper first introduces the recently proposed symbolic moment calculator (SMC), it utilizes the sharing property of the Binary Decision Diagram and put forward a hybrid data structure to represent the moment computation process. This method can get the moment and its symbolic derivatives very quickly. Then we proposed a novel non-tree wire sizing algorithm based on the symbolic moment calculation, the proposed algorithm can efficiently handle very large scale non-tree circuit due to taking fully usage of the SMC. Meanwhile, we also implement a non-tree wire sizing algorithm based on decomposition, which first decompose the non-tree into trees, then do wire sizing of the tree circuits. After analyzing and comparing the optimization results of the two algorithms, we find that the symbolic moment based wire sizing algorithm outperforms the latter one and can make much improvement on the overall performance of the non-tree circuits.