时钟扭斜规划（clock skew scheduling）是同步时序电路的一种优化手段。它通过控制时钟信号到达不同触发器的传播时间，实现提升芯片工作频率的目的。长期以来，它一直在全定制设计如高性能处理器中被应用，近来，也被应用到基于标准单元的设计流程中。　　 随着制造工艺的发展，设计规模不断扩大，时钟扭斜规划运行时间较长的缺点，使得满足芯片上市时间需求变得困难。随着CAD工具的发展，尤其是综合工具的优化算法的进步，时钟扭斜规划作为一个点工具被集成到流程中所能获得的优化效果有限。为了解决这些问题，本文提出了新的算法以降低时钟扭斜规划的时间复杂度，并且给出了更加合理的在业界标准流程中应用时钟扭斜规划的方法。其主要创新点和贡献包括：　　 1.提出一种近似线性时间（near linear time）复杂度的时钟扭斜规划算法。同传统的基于参数化最短路径（parameterized shortest path）算法的时钟扭斜规划算法一样，该算法支持增量式延迟提取。它通过用整数来描述延迟的大小，并且限制对时钟延迟的调整步进至少为一，以引入少量误差为代价，有效地降低了算法的复杂度。对于真实电路而言，其时间复杂度是线性的；同时其迭代次数具有经验性的上限值，这有助于降低增量式延迟提取的时间复杂度。　　 2.提出一种近似线性时间复杂度的增量式延迟提取算法。在上述的时钟扭斜规划算法中，当新的节点被加入关键子图时，时序分析引擎只需快速找到由该节点扇出的裕量最小的非关键边的延迟即可，而不必得到全部扇出边的延迟。根据这一特点，设计了新的增量式延迟提取算法。该算法为网表图中的中间节点维护一系列参数以提升时序分析的速度。每次在时钟扭斜规划算法改变时钟延迟后，只需增量式地对少数节点更新参数即可，因此运行时间被大大降低了。实验表明，结合使用上述两种算法，可以将大规模设计的时钟扭斜规划时间缩短约一个数量级。　　 3.提出一种针对上述时钟扭斜规划算法和增量式延迟提取算法的扩展，对时钟延迟进行双向调整。传统上支持增量式延迟提取的时钟扭斜规划算法仅仅增加时钟延迟而不减小时钟延迟，这往往会造成时钟树综合工具实现时钟扭斜规划的代价较高。通过对上述两种算法进行扩展，可以使它们交替地以增加和减小时钟延迟的方式来进行时钟扭斜规划，以减小时钟树的实现代价。用最新的支持有益时钟扭斜的时钟树综合算法测试扭斜方案所增加的实现代价，实验结果表明双向调整时钟延迟和单向调整相对于零扭斜时钟树都增加了布线代价，但前者所增加的线长要少3.5％到17.2％。　　 4.在基于Synopsys公司的EDA工具的物理实现流程中，有效地集成了时钟扭斜规划算法。传统的物理实现流程中，综合工具和时钟扭斜规划工具之间缺乏交互，导致优化效果有限。为了提高时钟扭斜规划在业界标准的物理实现流程中的实用性，在实现流程中增加反标和重优化的迭代，并且在为时钟扭斜规划进行电路建模时加入对门控单元的考虑。实验表明，相对于传统的流程，改进后的流程可以进一步降低时钟周期达7.7％至15.5％。　　 5.为了在反标和重优化的流程中辅助综合工具进行面积优化，提出一种新的时钟扭斜规划算法。不同于传统算法中平均分配裕量的策略，该算法以延迟图中边的面积优化潜力为权重，按权重为关键环中的边分配裕量。实验结果表明，相对于平均分配裕量的算法，该算法对面积的减小要高0.3％到5.9％。