Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2005-02-08
2005-02-08
Thompson, A. M. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06854098
ABSTRACT:
Some embodiments of the invention provide a method for pre-tabulating sub-networks. This method (1) generates a sub-network that performs a function, (2) generates a parameter based on this function, and (3) stores the sub-network in a storage structure based on the generated parameter. In some embodiments, the generated sub-network has several circuit elements. Also, in some embodiments, the generated sub-network performs a set of two or more functions. Some embodiments store each generated sub-network in an encoded manner. Some embodiments provide a method for producing a circuit description of a design. This method (1) selects a candidate sub-network from the design, (2) identifies an output function performed by the sub-network, (3) based on the identified output function, identifies a replacement sub-network from a storage structure that stores replacement sub-networks, and (4) replaces the selected candidate sub-network with the identified replacement sub-network in certain conditions. In some embodiments, this method is performed to map a design to a particular technology library. Some embodiments provide a data storage structure that stores a plurality of sub-networks based on parameters derived from the output functions of the sub-networks.
REFERENCES:
patent: 4703435 (1987-10-01), Darringer et al.
patent: 5003487 (1991-03-01), Drumm et al.
patent: 5311442 (1994-05-01), Fukushima
patent: 5519630 (1996-05-01), Nishiyama et al.
patent: 5521835 (1996-05-01), Trimberger
patent: 5526276 (1996-06-01), Cox et al.
patent: 5537330 (1996-07-01), Damiano et al.
patent: 5537341 (1996-07-01), Rose et al.
patent: 5610829 (1997-03-01), Trimberger
patent: 5649165 (1997-07-01), Jain et al.
patent: 5668732 (1997-09-01), Khouja et al.
patent: 5696694 (1997-12-01), Khouja et al.
patent: 5696974 (1997-12-01), Agrawal et al.
patent: 5574441 (1998-05-01), Tokunoh et al.
patent: 5752000 (1998-05-01), McGeer et al.
patent: 5787010 (1998-07-01), Schaefer et al.
patent: 5892678 (1999-04-01), Tokunoh et al.
patent: 5903466 (1999-05-01), Beausang et al.
patent: 5991524 (1999-11-01), Belkhale et al.
patent: 6023566 (2000-02-01), Belkhale et al.
patent: 6035107 (2000-03-01), Kuehlmann et al.
patent: 6080204 (2000-06-01), Mendel
patent: 6086626 (2000-07-01), Jain et al.
patent: 6102964 (2000-08-01), Tse et al.
patent: 6134705 (2000-10-01), Pedersen et al.
patent: 6216252 (2001-04-01), Dangelo et al.
patent: 6298472 (2001-10-01), Phillips et al.
patent: 6301687 (2001-10-01), Jain et al.
patent: 6301696 (2001-10-01), Lien et al.
patent: 6311317 (2001-10-01), Khoche et al.
patent: 6334205 (2001-12-01), Iyer et al.
patent: 6336208 (2002-01-01), Mohan et al.
patent: 6389586 (2002-05-01), McElvain
patent: 6397170 (2002-05-01), Dean et al.
patent: 6421818 (2002-07-01), Dupenloup et al.
patent: 6446240 (2002-09-01), Iyer et al.
patent: 6453447 (2002-09-01), Gardner et al.
patent: 6470478 (2002-10-01), Bargh et al.
patent: 6470486 (2002-10-01), Knapp
patent: 6473884 (2002-10-01), Ganai et al.
patent: 6490717 (2002-12-01), Pedersen et al.
patent: 6496972 (2002-12-01), Segal
patent: 6519609 (2003-02-01), Touzet
patent: 6519754 (2003-02-01), McElvain et al.
patent: 6523156 (2003-02-01), Cirit
patent: 6539536 (2003-03-01), Singh et al.
patent: 6543037 (2003-04-01), Limqueco et al.
patent: 6546539 (2003-04-01), Lu et al.
patent: 6546541 (2003-04-01), Petranovic et al.
patent: 6574779 (2003-06-01), Allen et al.
patent: 6618835 (2003-09-01), Garlapati et al.
patent: 20010013113 (2001-08-01), Matsunaga
patent: 20020157063 (2002-10-01), Besson
patent: 20020178432 (2002-11-01), Kim et al.
patent: 20030145288 (2003-07-01), Wang et al.
NN78055443, “Automatic Remap”, IBM Technical Disclosure Bulletin, vol. 20, No. 12, May 1978, pp. 5443-5444 (5 pages).*
NN9411291, “Design of Portable Library using Parameterized Cells”, IBM Technical Disclosure Bulletin, vol. 37, No. 11, pp. 291-292 (4 pages).*
Markovic et al., “FPGA to ASIC Conversion Design Methodology with the Support for Fast Retargeting to Different CMOS Implementation Technologies”, Proceedings of 2000 22nd International Conference on Microelectronics, vol. 2, May 14, 2000, pp. 703-706.*
Tamiya, Y., “Delay Estimation for Technology Independent Synthesis”, 1997 Proceedings of the ASP-DAC '97, Asia and South Pacific Design Automation Conference, Jan. 28, 1997, pp. 31-36.*
Ruiz et al., “Design and Prototyping of DSP Custom Circuits Based on a Library of Arithmetic Components”, vol. 1, 9 Nov. 1997, pp. 191-196.*
Krishnamoorthy et al., Boolean Matching of Sequential Elements, Proceedings of the 31st annual conference on Design automation conference, pp. 691-697, Jun. 06-10, 1994, San Diego, California, United States.
Yi, J. H. et al., Technology Mapping for Storage Elements Based on BDD matching, Proceedings of the 40thMidwest Symposium on Circuits and Systems, pp. 1099-1022, vol. 2, Aug. 1997.
U.S. Appl. No. 10/062,017, filed Jan. 31, 2002, Steven Teig & Asmus Hetzel.
U.S. Appl. No. 10/061,459, filed Jan. 31, 2002, Steven Teig & Asmuz Hetzel.
U.S. Appl. No. 10/062,014, filed Jan. 31, 2002, Steven Teig & Asmus Hetzel.
U.S. Appl. No. 10/062,044, filed Jan. 31, 2002, Steven Teig & Asmuz Hetzel.
U.S. Appl. No. 10/066,264, filed Jan. 31, 2002, Steven Teig & Asmus Hetzel.
U.S. Appl. No. 10/066,188, filed Jan. 31, 2002, Steven Teig & Asmus Hetzel.
U.S. Appl. No. 10/062,992, filed Jan. 31, 2002, Steven Teig & Asmus Hetzel.
U.S. Appl. No. 10/061,474, filed Jan. 31, 2002, Steven Teig & Asmus Hetzel.
U.S. Appl. No. 10/061,719, filed Jan. 31, 2002, Steven Teig & Asmus Hetzel.
U.S. Appl. No. 10/066,456, filed Jan. 31, 2002, Steven Teig & Asmus Hetzel.
U.S. Appl. No. 10/062,047, filed Jan. 31, 2002, Steven Teig & Asmuz Hetzel.
Crastes, M. et al., A Technology Mapping Method Based on Perfect and Semi-Perfect Matchings, Design Automation Conference, 1991, 28thACM/IEEE, Jun. 17-21, 1991, pp. 93-98.
Devadas, S. et al., Synthesis and Optimization for robustly delay-fault testable combinational logic circuits, Design Automation Conference, 1990, 27thACM/IEEE, Jun. 24-28, 1990, pp. 221-227.
D. Jongeneel, R. Otten, Y. Watanabe and R. K. Brayton, Area and Search Space Control for Technology Mapping, 37thDesign Automation Conference, 86-91, 2000.
Henrik Reif Andersen, An Introduction to Binary Decision Diagrams, Oct. 1997 (minor revisions Apr. 1998), 36 pp.
Jerry Burch and David Long, Efficient Boolean Function Matching, Proc. ICCAD, 1992, 408-411.
John Fishburn, A Depth-Decreasing Heuristic for Combinational Logic; or How to Convert Ripple-Carry Adder into a Carry-Lookhead Adder of Anything In-Between, Proceedings of the 27thDesign Automation Conference, 361-364, 1990.
Kamal Chaudhary and Massoud Pedram, A Near Optimal Algorithm for Technology Mapping Minimizing Area under Delay Constraints, Proceedings of the 29thDesign Automation Conference, 492-498, 1992.
Kurt Keutzer, DAGON: Technology Binding and Local Optimization by DAG Matching, Proceedings of the 24thDesign Automation Conference, 341-347, 1987.
Randal Bryant, Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams, CMU CS Tech Report CMU-CS-92-160.
Uwe Hinsberger and Reiner Kolla, Boolean Matching for Large Libraries, Proceedings of the 35thDesign Automation Conference, 206-211. Jun. 1998.
Yuji Kukimoto, Robert K. Brayton, and Prashant Sawkar. Delay-Optimal Technology Mapping by DAG Covering, Dept. of Electrical Engineering and Computer Science, University of California, Berkeley, Strategic CAD Laboratories, Intel Corp., Oct. 1997.
Zbigniew J. Czech, et al., An Optimal Algorithm for Generating Minimal Perfect Hashing Functions. Information Processing Letters. 43(5): 257-264, Oct. 1992.
Hetzel Asmus
Teig Steven
Cadence Design Systems Inc.
Flattler Johansen & Adeli LLP
Kik Phallaka
Thompson A. M.
LandOfFree
Method and apparatus for performing technology mapping does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for performing technology mapping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing technology mapping will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3513199