Synthesis of clock trees with useful skew based on sparse-graph algorithms

In this thesis, an optimization framework is proposed to synthesize clock trees with useful skews. The useful skews facilitate both low resource utilization and robustness to on-chip variations (OCV). First, techniques are proposed to construct useful-skew trees for designs with a single corner and a single mode (SCSM). Next, the framework is extended to handle designs with multiple corners and multiple modes (MCMM). The framework is developed based on incorporating essential quality measures and design constraints into mathematical formulations. The useful skew tree synthesis problem for SCSM designs is approached by developing a fast clock scheduler operating of sparse graphs. Guided by the scheduler, clock trees meeting specified useful skew constraints can be constructed, i.e., if there were no OCV, the timing constraints would be satisfied. To satisfy the constraints under OCV, two main directions are explored. The first direction involves providing safety margins in the skew constraints, combined with lowering the point of divergence in the clock tree for certain sequential elements. The second direction reduces the overall negative impact of OCV by bounding the latency of the constructed clock trees. After an initial tree construction, clock tree optimization (CTO) is employed to remove any remaining timing violations. The CTO process removes violations by inserting detour wires and delay buffers based on a linear programming formulation. Modern designs may have multiple corners and multiple modes. To consider the timing and constraints in each scenario, i.e., each corner and mode combination, a scenario compression technique is proposed. The timing and constraints in each scenario are captured in a separate graph. Next, the separate graphs are compressed into a single graph based on dominating skew constraints and linearization. The compression allows the earlier developed techniques to be directly applied to MCMM designs. Nevertheless, it may be costly to consider the dominating timing constraints for designs with many modes. In this thesis, a mode-reconfigurable clock tree, in which the top-part of the structure is reconfigured based on the active mode, is proposed to handle designs with many modes. This approach allows the constraints of each mode to be considered separately. Finally, the thesis is concluded with the introduction of static bounded useful arrival time constraints. The advantage of static arrival time constraints is that the timing constraints can queried in constant time, which facilitates the exploration of various tree topologies. This can serve as a superior substitute to the fast scheduler presented in the first part of the thesis. In summary, this thesis has proposed mathematical models that provide new insights into the algorithmic foundation for clock network synthesis. The models are used to drive a useful skew clock tree synthesis framework that demonstrates significant performance improvements over results reported in related studies on industry scale circuits. (Abstract shortened by ProQuest.