System and method for determining a plurality of clock delay...

Details System and method for determining a plurality of clock delay... System and method for determining a plurality of clock delay...

2005-08-02

2005-08-02

Lee, Thomas (Department: 2115)

Electrical computers and digital processing systems: support

Digital data processing system initialization or configuration

C713S100000, C716S030000

Reexamination Certificate

active

06925555

ABSTRACT:
A method determines a plurality of clock delay values. Each delay value is associated with a delay element on a clock line leading to a clock sink in a synchronous circuit. The method determines an initial set of delay values and executes an optimization algorithm, beginning with the initial set of delay values, to arrive at a set of delay values that at least approximately meets an criteria while satisfying timing constraints associated with selected pairs of logically connected clock sinks. In a preferred form, the optimization algorithm is a genetic algorithm or a gradient descent algorithm. The genetic algorithm involves selecting parent sets of delay values, crossing over so as to produce a child set of delay values, mutating the child set of delay values, evaluating how well the child set of delay values meets the criteria, and conditionally discarding the child set on the basis of the evaluating step. The gradient descent algorithm involves perturbing the initial set of delay values, evaluating how well the perturbed set of delay values meets the criteria, and conditionally discarding the perturbed set on the basis of the evaluating step. If the perturbed set is not discarded, then the gradient descent algorithm adjusts the values of the perturbed set in the same direction relative to the corresponding values in the initial set.

REFERENCES:
patent: 5570045 (1996-10-01), Erdal et al.
patent: 5758130 (1998-05-01), Dhuey
patent: 5849610 (1998-12-01), Zhu
patent: 6075832 (2000-06-01), Geannopoulos et al.
patent: 6553338 (2003-04-01), Buch et al.
patent: 6559701 (2003-05-01), Dillon
patent: 6625787 (2003-09-01), Baxter et al.
Westhead et al, A comparison of heuristic search algorithms for molecular docking, 1997, Journal of Computer-Aided Molecular Design, vol. 11, pp. 209-228.
SNU Dept. of Computer Engineering, Artificial Intelligence Cource, 1999.
http://web.archive.org/web/20010224045751/http://www.doc.ic.ac.uk/˜nd/surprise_96/journal/vol4/tcw2/report.html , Genetic Algorithms, Feb. 24, 2001.
Liu, X. et al., “ Maximizing Performance by Retiming and Clock Skew Scheduling”, Design Automotation Conference, 1999, pp. 231-236.
Papaefthymiou, M. et al., “ Retiming and Clock Scheduling for High-Performance Synchronous Circuits”, 10 pages, date unknown.
Kourtev, I. et al., “ Timing Optimization Through Clock Skew Scheduling”, Kluw er Academic Publishers, 2000, pp. 1-194.

Affiliated with

Also associated with

Rating

System and method for determining a plurality of clock delay... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and method for determining a plurality of clock delay..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for determining a plurality of clock delay... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3515734