Trading propensity-based clustering of circuit elements in a circuit design

Abstract

An apparatus and program product utilize a clustering algorithm based upon trading propensity to generate assignments of circuit elements to clusters or groups to optimize a spatial distribution of the plurality of clusters. For example, trading propensity-based clustering may be used to assign circuit elements such as scan-enabled latches to individual scan chains to optimize the layout of the scan chains in a scan architecture for an integrated circuit design.

1 . An apparatus, comprising:
 a processor; and   program code configured to execute on the processor to cluster circuit elements in a circuit design by grouping a plurality of circuit elements in a circuit design into a plurality of size balanced clusters and optimizing a spatial distribution of the plurality of clusters, wherein the program code is configured to optimize the spatial distribution of the plurality of clusters by iteratively selecting first and second clusters, determining a trading propensity metric for each circuit element grouped into each of the first and second clusters, selecting a first selected circuit element from the first cluster and a second selected circuit element from the second cluster based upon the determined trading propensity metrics of at least a portion of the plurality of circuit elements, and trading the first and second selected circuit elements between the first and second clusters.   
   
   
       2 . The apparatus of  claim 1 , wherein each of the plurality of circuit elements comprises a latch, and wherein each cluster is associated with a scan chain or a clock control tree. 
   
   
       3 . The apparatus of  claim 1 , selecting first and second clusters includes selecting the first and second clusters based upon a relative need of at least one cluster. 
   
   
       4 . The apparatus of  claim 1 , wherein each cluster is associated with a desired centroid, and wherein the trading propensity metric for a circuit element is based at least in part upon a distance from such circuit element to the desired centroid of a cluster. 
   
   
       5 . The apparatus of  claim 4 , wherein the trading propensity metric for each circuit element grouped into the first cluster is calculated using the formula:
   TP=(D 1 −D 2 )(D 1 +D 2 )(LC)/SC   
     where D 1  is the distance from the desired centroid of the first cluster to such circuit element, D 2  is the distance from the desired centroid of the second cluster to such circuit element, LC is a latch count for such circuit element, and SC is a scaling constant. 
   
   
       6 . The apparatus of  claim 1 , wherein the program code is configured to optimize the spatial distribution further by sorting circuit elements in each of the first and second clusters into respective first and second sorted lists based upon the trading propensity metrics, and wherein selecting the first and second circuit elements includes selecting the first and second circuit elements respectively from the first and second sorted lists. 
   
   
       7 . The apparatus of  claim 6 , wherein the program code is configured to optimize the spatial distribution further by, after trading the first and second circuit elements, removing the first and second elements from the first and second sorted lists, selecting third and fourth circuit elements respectively from the first and second sorted lists based upon their respective trading propensity metrics and trading the third and fourth circuit elements between the first and second clusters. 
   
   
       8 . The apparatus of  claim 1 , wherein the first circuit element includes at least one latch, wherein the second circuit element includes more than one latch, and the program code is configured to select the first and second circuit elements by:
 adding the first circuit element to a first trade group;   adding the second circuit element to a second trade group; and   adding at least one additional circuit element to at least one of the first and second trade groups to maintain a balance between the number of latches in each of the first and second trade groups, wherein trading the first and second circuit elements includes assigning each circuit element in the first trade group to the second cluster and assigning each circuit element in the second trade group to the first cluster.   
   
   
       9 . A program product, comprising:
 program code configured to cluster circuit elements in a circuit design by grouping a plurality of circuit elements in a circuit design into a plurality of size balanced clusters and optimizing a spatial distribution of the plurality of clusters, wherein the program code is configured to optimize the spatial distribution of the plurality of clusters by iteratively selecting first and second clusters, determining a trading propensity metric for each circuit element grouped into each of the first and second clusters, selecting a first selected circuit element from the first cluster and a second selected circuit element from the second cluster based upon the determined trading propensity metrics of at least a portion of the plurality of circuit elements, and trading the first and second selected circuit elements between the first and second clusters; and   a computer readable medium bearing the program code.