Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2005-04-29
2008-08-26
Dinh, Paul (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
07418690
ABSTRACT:
Local searches are provided for improving technology mapping for programmable logic integrated circuits. A local search algorithm is applied to a solution for mapping logic gates in a netlist to lookup tables (LUTs) on a programmable logic IC. The local search algorithm applies a series of local moves to the solution. At each move, a small change to the LUT mapping is proposed, and the change in cost for that LUT mapping change is computed. If the cost is improved, the change is accepted and the LUT mapping is replaced by the changed LUT mapping. Otherwise, the change in solution is either rejected, or accepted with a probability that depends on the cost change. The cost function can be chosen to represent one or more features of the LUT mapping, such as area, speed, power consumption, or a combination thereof.
REFERENCES:
patent: 7188266 (2007-03-01), Mendel et al.
patent: 2004/0133869 (2004-07-01), Sharma
patent: 2005/0039157 (2005-02-01), Sharma et al.
patent: 2005/0156626 (2005-07-01), Tomar et al.
Hao Li: Low Power Technology Mapping and Performance Driven Placement for FPGAs, Nov. 9, 2004.
Joey Y Lin: Placement Driven Technology mapping for LUT based FPGAs, ACM 2003.
Julien Lamoureux and Steven Wilton: On the Interaction Between Power Aware FPGA CAD Algorithms, ACM 2003.
Altera Patent Application “Timing Driven Synthesis with Area Trade Off”, Filed with the U.S. Patent Office on May 18, 2004, assigned U.S. Appl. No. 10/849,534.
J. Cong, et al., “Simultaneous Depth and Area Minimization in LUT-Based FPGA Mapping”Proceedings of the ACM Interantional Symposium on FPGAS, (Feb. 1995) pp. 68-74.
Francis, R.J., et al., “Chortie-crf: Fast Technology Mapping for Lookup Table-Based FPGAs”ACM/IEEE Design Automation Conference,(Jun. 1991) pp. 613-619.
Kernighan, B.W., et al., “An Efficient Heuristic Procedure for Partitioning Graphs”The Bell System Technical Journal, (Sep. 30, 1969), vol. 49, No. 2, pp. 291-307.
Kirkpatric, S., et al., “Optimization by Simulated Annealing”Science,(May 13, 1983), vol. 220, No. 4598, pp. 671-680.
Aarts et al.,Local Search in Combination Optimization, John Wiley & Sons Ltd., (1st edition, 1997).
Betz et al.,Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, 22-61 (1999).
Altera Corporation
Dinh Paul
Townsend and Townsend / and Crew LLP
LandOfFree
Local searching techniques for 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 Local searching techniques for technology mapping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Local searching techniques for technology mapping will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4009029