Patent
1997-04-14
1999-11-23
Stamber, Eric W.
39550018, G06F 1750
Patent
active
059915242
ABSTRACT:
Provided are a method, article of manufacture, and apparatus for identifying candidate clusters for matching to cells in a technology library. An automated design system comprises a computer configured to extract a portion of a circuit, levelize it, select a first node, identify the realizable clusters at the inputs of the first node, and combine the first node with realizable clusters at the inputs to produce candidate clusters. A dummy cluster is used at each input to represent using the input as a fanin. The system takes the cross product of the sets, and the first node is merged with each element of the cross product to produce a set of candidate clusters. The candidate clusters are then checked for realizability by comparing them to cells in the technology library, which includes dummy cells to facilitate mapping to large cells in the technology library. A set of realizable clusters is produced for the first node. The system applies the same process to successive nodes in the levelized circuit, including in the intermediate set the sets of realizable clusters for preceding nodes.
REFERENCES:
patent: 5500808 (1996-03-01), Wang
patent: 5521835 (1996-05-01), Trimberger
patent: 5526276 (1996-06-01), Cox et al.
patent: 5801957 (1998-09-01), Lehman et al.
Karayiannis et al. ("A new approach for clustering network modules for delay minimization", IEEE Proceedings of the 1995 International Symposium and Workshop on Systems Engineering of Computer Based Systems, pp. 325-332, Mar. 6, 1995).
Bahar et al. ("Boolean techniques for low power driven re-synthesis", IEEE/ACM International Conference on Computer-Aided Design, Nov. 5, 1995, pp. 428-432.
Kanecko et al. ("Concurrent cell generation and mapping for CMOS logic circuits", Proceedings of the ASP-DAC '97 Asia and South Pacific Design Automation Conference, Jan. 28, 1997, pp. 247-252).
De Micheli et al. ("Technology mapping of digital circuits", Proceedings of the 5th Annual European Computer Conference on Advanced Computer Technology, Reliable Systems and Applications, May 13, 1991, pp. 580-586).
Liem et al. ("A constructive matching algorithm for cell generator based technology mapping", IEEE International Symposium on Circuits and Systems, vol. 6, May 3, 1992).
Ortiz et al. ("Technology mapping algorithms for NORA dynamic logic circuits", Proceedings of 4th European Conference on Design Automation, Feb. 22, 1993, pp. 310-314).
G. Hachtel and F. Somenzi, "Logic Synthesis and Verification Algorithms", Kluwer Academic Publishers, 1996.
G. De Micheli, "Systhesis and Optimization of Digital Circuit", McGraw-Hill, Inc., 1994.
J. Mohnke and S. 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.
R. Bryant, "Graph-Based Algorithms for Boolean Function Manipulation", IEEE Transactions on Computers, vol. C-35, No. 8 p. 670, Aug. 1986.
I. Pomeranz and S. Reddy, "on Diagnosis and Correction of Design Errors", IEEE/ACM International Conference on Computer-Aided Design, Nov. 7-11, 1993.
Y. Lai, S. Sastry, and M. Pedram, "Boollean 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.
E. Clarke, et al., "Spectral Transforms for Large Boolean Functions with Applications to Technology Mapping", 30th Design Automation Conference, Jun. 14-18, 1993, Dallas, Texas.
F. Mailhot and G. De Micheli, "Technology Mapping Using Boolean Matching and Don't Care Sets", Proceedings of the European Conference on Design Automation, 1990, p. 212-216.
Belkhale Krishna
Roy Sumit
Varma Devadas
Cadence Design Systems
Glenn Michael A.
Kik Phallaka
Stamber Eric W.
LandOfFree
Cluster determination 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 determination for circuit implementation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cluster determination for circuit implementation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1232230