半导体工业的迅速发展给集成电路的计算机辅助设计(CAD)带来了很多挑战：一方面,随着特征尺寸的不断缩小,工艺偏差的影响日益严重,使得电路设计时,需要考虑可实现性、成品率等因素。现有的电路优化方法,如时钟偏差规划,需要做进一步的研究和改进。另一方面,随着电路规模的指数级增大,其对计算机辅助设计算法的性能提出了越来越高的要求,这导致许多集成电路优化的问题,需要研究新的求解方法,以满足超大规模集成电路的需求。作为强大的时序优化技术之一,时钟偏差规划通过有意地给触发器分配不同的时钟延时(触发时间),来优化电路的性能。传统的时钟偏差规划可转化为网络流中的最小环比问题,并采用高效的算法求解。在实际电路设计中,触发器的时钟延时最终要通过时钟网络中的互连线和额外的缓冲器来实现。传统时钟偏差规划可能需要大量不同的时钟延时,这导致两个潜在的问题：一个是时钟网络中缓冲器的大量增加导致不可接受的面积和功耗开销,另一个是,在工艺偏差的影响日益严重的情况下,同时精准地实现大量不同的时钟延时变得越来越难。最终,传统时钟偏差规划在工业界的应用受到了很大限制。多域时钟偏差规划技术提出,在优化电路性能的同时,将触发器分配到若干个时钟域内,这巧妙地解决了时钟网络的可靠实现问题。然而,离散时钟域的引人,使得问题的复杂度变为NP-complete,无法采用传统的方法求解。现有的算法要么在时间复杂度上太高,要么在计算精度上无法让人满意,亟需研究高效的求解算法。本论文围绕多域时钟偏差规划问题的有效算法进行了深入的研究。首先,本论文提出了一种多域时钟偏差规划问题的快速算法,主要贡献有：·首次提出,通过略微施加更多约束,将问题转换为一种近似的、可解的混合整数线性规划(MILP)问题。这种转化的优势在于,能够从全局的角度来考虑时钟域分配,并且一次性最优地求解。·针对转换后的MILP问题,研究该问题的特殊性后,提出了一种广义Howard’s算法来有效地求解。·提出了一种增量式的面向关键环的时钟域分配改良算法,以继续改进结果。·为了进一步提高多域时钟偏差规划算法的性能,提出了一种图剪接算法,可以用于对时序约束图进行预处理,从而有效地降低输入规模。实验结果证明,所提出的快速算法具有接近最优解的精度,在ISCAS89基准电路上的93次测试中,有88次(=94.6%)获得了最优解,同时在性能上比现有算法有至少一个数量级的提升。对于图剪接算法,实验结果也验证了其有效性,应用于快速算法后,使后者在性能上有1.43X-4.76X的进一步提升(平均2.66X)。随后,针对多域时钟偏差规划问题,为了能够获得理论上保证的最优解,我们还提出了一种精确算法,主要贡献有：·提出了基于分支定界的算法,来搜索最优的时钟域分配方案。·提出了三种有效的分支策略,来提高搜索效率,包括最小裕量优先分支的策略、基于负路径的分支限制策略以及最小代价优先处理的策略。·采用了有效的定界算法,其中快速算法被用来作为计算下界的子程序。实验结果验证了该算法的精确性和有效性。例如,在ISCAS89基准测试电路上,精确算法均在3.15秒内获得了最优解。快速算法和精确算法循序渐进地解决了多域时钟偏差规划的计算问题,为其在工业界的广泛应用提供了有效的求解方法。工艺偏差影响的不仅是时钟网络中的延时,同时对电路本身也有广泛的影响。随着工艺偏差规划影响日益严重,电路延时的不确定性增加,最终导致时序成品率的问题。因此,如何设计时钟延时以优化成品率,也是时钟偏差规划技术中的关键问题。通用的成品率驱动时钟偏差规划,结合当前分析电路延时普遍采用的统计时序分析方法,能够精确地考虑路径延时在工艺偏差下的统计分布,因而在优化成品率上有天然的优势。本论文围绕此问题展开研究,主要贡献有：·在理论上明确地指出了其广义网络流问题的特殊性。·提出了高效的广义网络流算法来求解,包括广义Howard’s算法(V2)和改进的广义最小平衡算法。实验结果验证了算法的高效性。相比已有算法,所提出的算法在性能上有显著的优势,尤其是在大电路上,最高有157.55X的加速。