Local searching techniques for technology mapping

Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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).

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFUS-PAI-O-4009029

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.