Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2006-06-13
2006-06-13
Whitmore, Stacy A. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
07062729
ABSTRACT:
A method (300) and system (500) for optimizing a circuit layout based on layout constraints (308) and objectives (312). The method includes solving a linear program so as to obtain a rational solution whose variables are either whole or half integer. The tight constraints and objectives involving variables whose solution are a half integer are reduced to a 2-SAT problem, which is analyzed to determine its satisfiability. If the 2-SAT problem is not satisfiable, one or more objectives are removed so as to make the 2-SAT problem satisfiable. Any half-integer results of the linear program are rounded according to the truth assignment that satisfies the 2-SAT problem. The rounded results are used to create the circuit layout.
REFERENCES:
patent: 5258919 (1993-11-01), Yamanouchi et al.
patent: 5794242 (1998-08-01), Green et al.
patent: 6031984 (2000-02-01), Walser
patent: 6189132 (2001-02-01), Heng et al.
patent: 6539345 (2003-03-01), Jones et al.
patent: 6816825 (2004-11-01), Ashar et al.
Alexey Lvov, Fook-Luen Heng, “A graph based simplex method for the integer minimum perturbation problem with sum and difference constraints.” Proceedings of the GLSVLSI-2004 ACM Symposium, Boston, MA, Apr. 2004, pp. 67-72.
Random 2-SAT and Unsatisfiabilityby Yann Verhoeven; ACM Information Processing Letters 72, Nov. 1999; pp. 119-123, Elsevier Science.
A Linear-Time Algorithm For Testing The Trust of Certain Quantified Boolean Formulas, by Bengt Aspvall, Michael F. Plass and Robert Endre Tarjan; Information processing Letters, vol. 8, No. 3, Mar. 1979, pp. 121-123, 195.
Gray Michael S.
Hibbeler Jason D.
Tellez Gustavo E.
Walker Robert F.
Downs Rachlin & Martin PLLC
International Business Machines - Corporation
Tat Binh
Whitmore Stacy A.
LandOfFree
Method and system for obtaining a feasible integer solution... 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 system for obtaining a feasible integer solution..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for obtaining a feasible integer solution... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3706264