DISTRIBUTION DEPENDENT CLUSTERING IN BUFFER INSERTION OF HIGH FANOUT NETS

Methods and apparatus are disclosed for inserting buffers into the design of an integrated circuit with a high fanout net. If a net has a ramptime violation, all of the driven elements in the net are clustered in such a manner that the total load (capacitance) of the driver decreases. Clustering is based upon a two-dimensional partitioning approach together with three proposed heuristics (expand, shrink and merge), which iteratively partitions the placement regions of the net such that the number of buffers to be inserted and the level of inserted buffer tree are minimized. After clustering, one buffer is inserted for each cluster created in the clustering operation. Each of the inserted buffers drives its corresponding cluster. The buffers that are inserted will not have any ramptime violation, which ensures converge of the buffer insertion scheme. Therefore, each insertion of a level of buffers reduces the overall ramptime of the net. After insertion of a level of buffers, the ramptime of the net is checked once again. If it is still not acceptable, the aforementioned clustering and insertion are repeated and the above cycle is iterated until there is no ramptime violation. During the first iteration of clustering and buffer insertion, the original circuit elements are clustered. After the first iteration of clustering and buffer insertion, the driven elements that are clustered are the buffers that were inserted in the previous iteration. In this manner, levels of buffers may be inserted into the net.