Fast clock skew scheduling based on sparse-graph algorithms

Incorporating timing constraints explicitly imposed by the data and control paths during clock network synthesis can enhance the robustness of the synthesized clock networks. With these constraints, a clock scheduler can be used to guide the synthesis of a clock network by specifying a set of feasible arrival times at the respective sequential elements. Clock scheduling can be either static or dynamic. In static clock scheduling, a clock schedule is first specified; next, a clock network is constructed realizing the prescribed schedule. Clock trees constructed using this approach may consume significant routing resources. In dynamic clock scheduling, the clock tree and clock schedule are both simultaneously constructed and determined, respectively. In earlier studies, the scalability of dynamic clock scheduling, which is essentially a shortest path problem, has been limited. The bottleneck is in finding the shortest paths between different vertices in an incrementally changing weighted graph. In this work, we present two clock schedulers that address the scalability issues by exploiting the sparsity of this weighted graph. Experimental results show that the proposed clock schedulers are one to two orders of magnitude faster compared to a published scheduler in an earlier work. The proposed clock schedulers are scalable, and are tested on a synthesized circuit with 348 710 cells, 57 491 sequential elements, and 496 727 explicit timing constraints.