Novel binary linear programming for high performance clock mesh synthesis

Abstract

Clock mesh is popular in high performance VLSI design because it is more robust against variations than clock tree at a cost of higher power consumption. In this paper, we propose novel techniques based on binary linear programming for clock mesh synthesis for the first time in the literature. The proposed approach can explore both regular and irregular mesh configurations, adapting to non-uniform load capacitance distribution. Our synthesis consists of two steps: mesh construction to minimize total capacitance and skew, and balanced sink assignment to improve slew/skew characteristics. We first show that mesh construction can be analytically formulated as binary polynomial programming (a class of nonlinear discrete optimization), then apply a compact linearization technique to transform into binary linear programming, significantly reducing computational overhead. Second, our balanced sink assignment enables a sink to tap the least loaded mesh segment (not the nearest one) with another binary linear programming which reduces both slew and skew. Experiments show that our techniques improve the worst skew and total capacitance by 14% and 15% over the state-of-the-art clock mesh algorithm [19] on ISPD09 benchmarks. ©2010 IEEE.