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 . A method of reducing wirelength in a net of an integrated circuit design, comprising:
 identifying a plurality of sinks in the net to be interconnected with a source;   forming two or more clusters of the sinks;   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.   
   
   
       2 . The method of  claim 1  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. 
   
   
       3 . The method of  claim 1  further comprising:
 establishing a threshold value for a wiring parameter of the net; and   determining that the wiring parameter of the net exceeds the threshold value.   
   
   
       4 . The method of  claim 1  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. 
   
   
       5 . The method of  claim 1  wherein the first sink is closest to the second buffer out of all sinks except those in the second cluster. 
   
   
       6 . The method of  claim 1  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.   
   
   
       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 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, 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.   
   
   
       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 . The computer system of  claim 7  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. 
   
   
       11 . The computer system of  claim 7  wherein the first sink is closest to the second buffer out of all sinks except those in the second cluster. 
   
   
       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 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, 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.   
   
   
       14 . The computer system 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 system 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 . The computer system of  claim 13  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. 
   
   
       17 . The computer system of  claim 13  wherein the first sink is closest to the second buffer out of all sinks except those in the second cluster. 
   
   
       18 . The computer system 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.