Cluster matching for circuit implementation

Abstract

Provided are a method, article of manufacture, and apparatus for matching candidate clusters to cells in a technology library. An automated design system comprises a computer configured to use second order signatures in generating candidate permutations of each permutation group in a canonical form of the candidate function. The system selects first and second symmetric subgroups, determines a second order signature for the candidate function and the first and second symmetric subgroups, and compares the second order signature to a corresponding second order signature for a library cell function. If the signatures match, the permutation is continued with the first and second symmetric subgroups being included in an intermediate permutation. If not, the system produces no more intermediate permutations beginning with the first and second symmetric subgroups. Further symmetric subgroups are added to the intermediate permutation. For each new symmetric subgroup, the system produces pairings of that symmetric subgroup with each of the symmetric subgroups in the intermediate permutation, and compares the second order signatures of the pairings to corresponding second order signatures in the library function. If at any time any of the second order signatures do not match their corresponding library function signatures, the system produces no more intermediate permutations beginning with the current sequence of the intermediate permutation, and instead removes the new symmetric subgroup and attempts to continue building the previous intermediate permutation. When all symmetric subgroups in the permutation group have been added to the intermediate permutation, the intermediate permutation becomes a candidate permutation.