Back to results
US 2007/0186199 A1Published application
Heuristic clustering of circuit elements in a circuit design
AssigneeInternational Business Machines Corporation
InventorsMark Fredrickson, Glen Handlogten, Chad McBride
Life of this patent
Estimating the term…
Abstract
An apparatus, program product and method utilize heuristic clustering to generate assignments of circuit elements to clusters or groups to optimize a desired spatial locality metric. For example, circuit elements such as scan-enabled latches may be assigned to individual scan chains using heuristic clustering to optimize the layout of the scan chains in a scan architecture for a circuit design.
Claims25
A method of clustering circuit elements in a circuit design, the method comprising:
- grouping a plurality of circuit elements in a circuit design into a plurality of size balanced clusters;
- and
- heuristically optimizing a spatial locality metric for the plurality of circuit elements by iteratively:
- performing a swap of circuit elements between clusters among the plurality of clusters;
- recalculating the spatial locality metric after performing the swap;
- and
- selectively discarding the swap based upon the recalculated spatial locality metric.
4 more elements
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 heuristically optimizing a spatial locality metric for the plurality of circuit elements, wherein the program code is configured to heuristically optimize the spatial locality metric by iteratively performing a swap of circuit elements between clusters among the plurality of clusters, recalculating the spatial locality metric after performing the swap, and selectively discarding the swap based upon the recalculated spatial locality metric.
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 heuristically optimizing a spatial locality metric for the plurality of circuit elements, wherein the program code is configured to heuristically optimize the spatial locality metric by iteratively performing a swap of circuit elements between clusters among the plurality of clusters, recalculating the spatial locality metric after performing the swap, and selectively discarding the swap based upon the recalculated spatial locality metric;
- and
- a computer readable medium bearing the program code.
Dependencies are inferred from the claim text.