Cluster matching for circuit implementation

Details Cluster matching for circuit implementation Cluster matching for circuit implementation

1997-04-14

2000-02-08

Teska, Kevin J.

39550008, G06F 1500

Patent

active

060235667

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.

REFERENCES:
patent: 4336468 (1982-05-01), Spillman
patent: 5784636 (1998-07-01), Rupp
patent: 5787010 (1998-07-01), Schaefer
Hatchel and Somenzi, "Logic Synthesis and Verification Algorithms", Kluwer Academic Publishers, 1996.
De Micheli, "Synthesis and Optimization of Digital Circuit", McGraw Hill, Inc. 1994.
Mohnke and Malik, "Limits of Using Signatures for Permutation Independent Boolean Comparison", Proceedings of the ASP-DAC'95/CHDL'95/ VLSI'95 Asia and South Pacific Design Automation Conference, Aug. 29-Sep. 1, 1995.
Bryant, "Graph-Based Algorithms for Boolean Function Manipulation", IEEE Transactions on Computers, vol. C-35,, No. 8 p. 670 Aug. 1986.
Pomeranz and Reddy, "On Diagnosis and Correction of Design Errors" IEEE/ACM International Conference on Computer-Aided Design, NOv. 7-11, 1993.
Lai, Sastry, and Pedram, "Boolean Matching Using Binary Decision Diagrams with Applications to logic Synthesis and Verification", 1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors, Oct. 11-14, 1992.
Clarke et al., Spectral Transforms for Large Boolean Functions with Applications to Technology Mapping, 30.sup.th Design Automation Conference, Jun. 14-18,1993, Dallas, Texas.
Mailhot and De Micheli, "Technology Mapping Using Boolean Matching and Don't Care Sets", Proceedings of the European Conference on Design Automation, 1990, p. 212-216.

Affiliated with

Also associated with

Rating

Cluster matching for circuit implementation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Cluster matching for circuit implementation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cluster matching for circuit implementation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1687228