Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-11-05
2003-07-15
Garbowski, Leigh M. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06594808
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates to computer-aided design (CAD) and, more particularly, to regularity extraction in the design of integrated circuits.
2. Background Art
In high-performance custom integrated circuit designs, designers take advantage of the high degree of regularity often present in circuits to generate efficient layouts in terms of area and performance as well as to reduce the design effort. Datapath circuits perform various arithmetic and multiplexing operations on wide buses. Such circuits have a very high degree of regularity. The design effort can be reduced by identifying or extracting regularity in circuits, thus improving the productivity of designers. Currently, however, datapath circuits in general-purpose microprocessors are designed almost entirely by hand. Existing CAD tools can not extract and utilize regularity to the extent necessary for competitive designs.
Various techniques for extraction of functional regularity have been proposed in the literature. For example, D. S. Rao et al., “On clustering for maximal regularity extraction,” IEEE Trans. on CAD of Integrated Circuits and Systems, Vol. 12, No. 8 (August. 1993), pp. 1198-1208, describes a string matching algorithm to find all instances of user-specified templates in the circuit, and then heuristically choose a subset of the set of templates to cover the circuit. The final cover is sensitive to the templates provided by the designer. M. R. Corazao et al., “Performance optimization using template mapping for datapath-intensive high-level synthesis,” IEEE Trans. on CAD of Integrated Circuits and Systems, Vol. 15, No. 8 (August 1996), pp. 877-887, also assumes that a template library is provided, but claims to generate all complete as well as partial instances of a given template in the circuit. Another approach described in R. X. T. Nijssen et. al., “Regular layout generation of logically optimized datapaths,” Proc. Int'l Symp. on Physical Design, (1997), pp. 42-47, involves choosing small logic components, such as latches, as templates, and then growing them to obtain bigger templates. This approach is highly dependent on the initial choice of templates.
Various techniques for extraction of structural regularity have also been proposed in the literature. For example, G. Odawara et al., “Partitioning and Placement Technique for CMOS Gate Arrays,” IEEE Trans. on CAD, Vol. 6, No. 3 (May 1987), pp. 355-363, presents a methodology to identify structural regularity in highly-regular datapaths. Odawara's method chooses latches driven by the same control signals as initial templates, and uses them to grow larger templates. Odawara's approach identifies one-dimensional regularity in terms of bit-slices of the datapath. Other approaches by R. X. T. Nijssen et al, “Regular Layout Generation of Logically Optimized Datapaths,” Proc. Int's Symp. on Physical Design, (1997) pp. 42-47, and S. R. Arikati et al., “A Signature Based Approach to Regularity Extraction,” Proc. Int'l Conf. on CAD, (Nov. 1997), pp. 542-545, extend Odawara's methodology to identify bit slices as well as stages of datapath circuits. However, these structural methods are not sufficient for circuits with a mix of datapath and control logic.
In the approaches in the above-listed articles opportunities for regularity extraction are missed. Furthermore, there is a need for a regularity extraction approach which would speed up technology mapping and layout generation of datapath circuits without comprising the final design quality.
Accordingly, there is a need for techniques for systematic regularity extraction.
SUMMARY
In some embodiments, the invention includes a computerized method for identifying structural regularity in a logic design. The method includes receiving a plurality of templates covering the logic design, receiving one or more control signals for the logic design, and receiving one or more databus identifiers for the logic design. The method generates a first vector for the logic design through computer automated operations to combine at least one instance of one of the plurality of templates based on the control signals, the databus identifiers and connectivity of the logic design.
REFERENCES:
patent: 5652874 (1997-07-01), Upson et al.
patent: 5737237 (1998-04-01), Tanaka et al.
patent: 5838583 (1998-11-01), Varadarajan et al.
patent: 5898595 (1999-04-01), Bair et al.
patent: 5910898 (1999-06-01), Johannsen
patent: 5926398 (1999-07-01), Nakamura
patent: 5930499 (1999-07-01), Chen et al.
patent: 5991524 (1999-11-01), Belkhale et al.
patent: 6066178 (2000-05-01), Bair
patent: 6148433 (2000-11-01), Chowdhary et al.
patent: 6189131 (2001-02-01), Graef et al.
patent: 6230303 (2001-05-01), Dave
patent: 6237129 (2001-05-01), Patterson et al.
Chowdhary, A., et al., “Extraction of Functional Regularity in Datapath Circuits”,IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 18, 1279-1296, (Sep. 1999).
Rao, D., et al., “An Approach to Scheduling and Allocation Using Regularity Extraction”,IEEE, 557-531, (1993).
Chowdhary, Amit., et al., “Extraction of Functional Regularity in Datapath Circuits”,IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 18, No. 9, Sep. 1999, XP-002191876, 1279-1296.
Arikati, S.R., et al., “A Signature Based Approach to Regularity Extraction”,Proceedings IEEE International Conference on CAD, 542-545, (Nov. 1997).
Chowdhary, A., et al., “A General Approach for Regularity Extraction in Datapath Circuits”,ICCAD, (Nov. 1998).
Chowdhary, A., et al., “Technology Mapping for Field-Programmable Gate Arrays Using Integer Programming”,Proceedings IEEE International Conference on CAD, 346-352, (Nov. 1995).
Corazao, M.R., et al., “Performance Optimization Using Template Mapping for Datapath-Intensive High-Level Synthesis”,IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, 8, 877-888, (Aug. 1996).
Detjens, E., et al., “Technology Mapping in MIS”,Proceedings IEEE International Conference on CAD, 116-119, (1987).
Dobberpuhl, D.W., “Circuits and Technology for Digital's StrongARM and Alpha Microprocessors”,Proceedings Seventeenth Conference on Advanced Research in VLSI, 2-11, (Sep. 15-16 1997).
Gupta, R.K., et al., “Using a Programming Language for Digital System Design”,IEEE Design&Test of Computers, 72-80, (Apr. 1997).
Hansen, M.C., et al., “High-Level Test Generation using Physically-Induced Faults”,13th IEEE VLSI Test Symposium, 20-28, (May 1995).
Hirsch, M., et al., “Automatically Extracting Structure from a Logical Design”,Proceedings IEEE International Conference on CAD, 456-459, (Nov. 1988).
Keutzer, K., “DAGON: Technology Binding and Local Optimization by DAG Matching”,Proceedings 24th Design Automation Conference, 341-347, (Jun. 1987).
Li, J., et al., “HDL Code Restructuring Using Timed Decision Tables”,Proceedings of the Sixth International Workshop on Hardware/Software Codesign, 131-135, (Mar. 1998).
Nijssen, R., et al., “GreyHound: A Methodology for Utilizing Datapath Regularity in Standard Design Flows”,Integration, the VLSI Journal 25, 111-135, (1998).
Nijssen, R., et al., “Regular Layout Generation of Logically Optimized Datapaths”,Proceedings International Symposium on Physical Design, 42-47, (1997).
Odawara, G., et al., “Partitioning and Placement Technique for CMOS Gate Arrays”,IEEE Transactions on Computer-Aided Design, vol. CAD-6, 3, 355-363, (May 1987).
Rabaey, J.M., et al., “Fast Prototyping of Datapath-Intensive Architectures”,IEEE Design&Test of Computers, 40-51, (Jun. 1991).
Rao, D.S., et al., “On Clustering for Maximal Regularity Extraction”,IEEE Transactions on Computer-Aided Design of Integrated Circuts and Systems, vol. 12, 8, 1198-1208, (Aug. 1993).
Yalcin, H., et al., “An Approximate Timing Analysis Method for Datapath Circuits”,Proceedings IEEE International Conference on CAD, 114-118, (Nov. 1996).
Chowdhary Amit
Gupta Rajesh
Kale Sudhakar
Saripella Phani
Sehgal Naresh K.
Garbowski Leigh M.
Schwegman Lundberg Woessner & Kluth P.A.
LandOfFree
Structural regularity extraction and floorplanning in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Structural regularity extraction and floorplanning in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Structural regularity extraction and floorplanning in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3100815