Lagrangian Relaxation Based Gate Sizing With Clock Skew Scheduling - A Fast and Effective Approach

Speaker : Prof. Chris Chu (Iowa State University)

Date : 2019/03/22 (Fri.)

Time : 13:20

Location :R615, Delta Bldg.  

Host : Prof. Wai-Kei Mak

Abstract

This seminar presents a fast and effective approach for circuit power minimization by combining clock skew scheduling with gate sizing. Gate sizing has been established as the state-of-the-art approach to minimize power. However, with tight timing constraints, gate sizing has limited potential to reduce power. By adjusting the arrival times of clock signals (clock skew scheduling), the timing constraints can be relaxed that facilitates more power reduction. Our approach for simultaneous gate sizing and clock skew scheduling is based on the popular Lagrangian relaxation (LR) technique and has two advantages over previous LR-based approaches. First, we deal with a realistic discrete gate sizing formulation with table lookup delay models rather than a simplified continuous formulation with convex delay models. Second, to update the Lagrange multipliers, we introduce a very fast projection heuristic instead of solving a min-cost flow problem. The experimental results show that our approach saves 5.3% more power and is 70x faster than the previous min-cost flow based approach. Compared to gate sizing alone with the state-of-the-art LR gate sizer, our approach with skew scheduling saves 19.7% more power with a small runtime penalty.

This seminar also provides a brief highlight of the graduate program at Iowa State University. Students aspiring to study in the US are particularly encouraged to come.

---------------------------