Retiming and Clock Skew Scheduling for High-Performance VLSI Design

Abstract

Retiming is an architectural-level transformation that can improve the performance of synchronous digital circuits by relocating their registers. Over the years, significant progress has been made in the design of efficient retiming algorithms for improving operating speed. However, all retiming algorithms with polynomial worst-case runtimes focus exclusively on setup timing constraints and ignore the issue of hold violations. Furthermore, little is known about the effectiveness of retiming when combined with the adjustment of clock skews.

In this talk, I will present new results in retiming and clock skew scheduling. First, I will describe the first ever polynomial-time algorithm for retiming under both setup and hold constraints. After highlighting the challenges associated with retiming in the presence of long and short paths constraints, I will present an integer monotonic program for the problem and give a very simple algorithm for solving it in polynomially many steps.

The second part of my talk will focus on the problem of simultaneous retiming and clock skew scheduling with a target clock period and a specified tolerance to delay varations. For this problem, I will present a mixed-integer program for maximizing tolerance to delay variations under setup and hold constraints. I will also discuss preliminary experimental results from the application of our techniques on benchmark circuits. Our experiments show that the combination of retiming and clock skew scheduling can significantly improve circuit tolerance to delay variations.

The work on clock skew scheduling is in collaboration with Xun Liu and Eby Friedman (U. Rochester).

Other publications of Prof. Papaefthymiou can be found here.