Proceedings - ACM IEEE Design Automation Conference · 2007 · 28 citations · 9 references
EngineeringComputer EngineeringComputer ScienceComputer ArchitectureDesign OptimizationSchedulingClock Distribution NetworksClock ManagementDelay ModelingTiming AnalysisTiming ClosureTiming ModelingClock Skew MinimizationClock Skew OptimizationLower Bound ComputationPolynomial Time ComplexityTiming Optimization
The combination of clock skew scheduling and delay insertion may lead to further clock period reduction. Although some previous works can minimize the clock period, they only heuristically reduce the required inserted delay. However, since the delay insertion is an ECO (engineering change order) process, minimizing the required inserted delay is very important for the design closure, In this paper, we present a linear program to formally formulate the simultaneous application of clock skew scheduling and delay insertion. Our objective is not only to achieve the lower bound of the clock period, but also to achieve the lower bound of required inserted delay. Compared with previous works, our paper has the following two significant contributions: (1) our approach is the first work that guarantees solving this problem optimally; and (2) our paper is the first proof of showing that the time complexity of this problem is polynomial.
9
A new polynomial-time algorithm for linear programming
Narendra Karmarkar · COMBINATORICA · 1984 · 4.8K citations
J.P. Fishburn · IEEE Transactions on Computers · 1990 · 520 citations
Engineering, Computer Engineering, Electrical Engineering +17
Cycle time and slack optimization for VLSI-chips
Christoph Albrecht, B. Korte, Jürgen Schietke et al. · 1999 · 50 citations
Engineering, Computer Engineering, Electrical Engineering +17