Buffer insertion to reduce wirelength in vlsi circuits

Abstract

Wirelength in a net of an integrated circuit design is reduced by forming clusters of sinks to be interconnected, inserting a buffer at each cluster, and providing branch connections between clusters by connecting a sink of one cluster to a buffer of another cluster, to create a buffer tree spanning all sinks. The buffers are inserted at a point on a respective bounding box of a cluster that is closest to a source for the net. A sink that provides a branch connection to the buffer of another cluster is the closest sink to that buffer (except for those sinks in the cluster). Clusters may be formed by examining different pairs of the sinks with different bounding boxes, and identifying one of the pairs whose bounding box has a lowest half-perimeter as the best pair for clustering.

1 .- 6 . (canceled) 
   
   
       7 . A computer system comprising:
 one or more processors which process program instructions;   a memory device connected to said one or more processors; and   program instructions residing in said memory device which when executed by said one or more processors perform a method for reducing wirelength in a net of an integrated circuit design by identifying a plurality of sinks in the net to be interconnected with a source, forming two or more clusters of the sinks wherein the forming of the clusters includes removing an overlap between two of the clusters by determining which of a plurality of horizontal cuts between sinks of the overlapping clusters and a plurality of vertical cuts between sinks of the overlapping clusters provides an optimum partition, inserting buffers at selected clusters, connecting buffers at selected clusters to sinks in respective clusters, connecting the source to at least a first buffer in a first one of the clusters, and connecting a first one of the sinks in the first cluster to at least a second one of the buffers in a second one of the clusters to create a buffer tree from the source to the sinks wherein the connection between the first sink and the second buffer is the shortest distance from the second buffer to any sink outside of the second cluster.   
   
   
       8 . The computer system of  claim 7  wherein a given one of the buffers is inserted at a point on a bounding box of a respective one of the clusters that is closest to the source. 
   
   
       9 . The computer system of  claim 7  wherein said program instructions further establish a threshold value for a wiring parameter of the net, and determine that the wiring parameter of the net exceeds the threshold value. 
   
   
       10 . (canceled) 
   
   
       11 . (canceled) 
   
   
       12 . The computer system of  claim 7  wherein a given cluster is formed by:
 examining different pairs of the sinks which define respective bounding boxes;   identifying one of the pairs whose bounding box has a lowest half-perimeter as the best pair for clustering; and   merging the best pair of sinks to form one of the clusters.   
   
   
       13 . A computer program product comprising:
 a computer-readable medium; and   program instructions residing in said medium which when executed by a computer, perform a method for reducing wirelength in a net of an integrated circuit design by identifying a plurality of sinks in the net to be interconnected with a source, forming two or more clusters of the sinks wherein the forming of the clusters includes removing an overlap between two of the clusters by determining which of a plurality of horizontal cuts between sinks of the overlapping clusters and a plurality of vertical cuts between sinks of the overlapping clusters provides an optimum partition, inserting buffers at selected clusters, connecting buffers at selected clusters to sinks in respective clusters, connecting the source to at least a first buffer in a first one of the clusters, and connecting a first one of the sinks in the first cluster to at least a second one of the buffers in a second one of the clusters to create a buffer tree from the source to the sinks wherein the connection between the first sink and the second buffer is the shortest distance from the second buffer to any sink outside of the second cluster.   
   
   
       14 . The computer program product of  claim 13  wherein a given one of the buffers is inserted at a point on a bounding box of a respective one of the clusters that is closest to the source. 
   
   
       15 . The computer program product of  claim 13  wherein said program instructions further establish a threshold value for a wiring parameter of the net, and determine that the wiring parameter of the net exceeds the threshold value. 
   
   
       16 . (canceled) 
   
   
       17 . (canceled) 
   
   
       18 . The computer program product of  claim 13  wherein a given cluster is formed by:
 examining different pairs of the sinks which define respective bounding boxes;   identifying one of the pairs whose bounding box has a lowest half-perimeter as the best pair for clustering; and   merging the best pair of sinks to form one of the clusters.