布局优化方法及布局优化系统

摘要

本发明提供了一种布局优化方法，包括对电路进行时序分析，从时序器件中提取时序关键器件，将所述时序关键器件按照时序裕量进行排序，选取一个所述时序关键器件，计算偏差值，判断所述偏差值大于偏差阈值，进行位置优化处理，按照所述排序依次选取所述时序关键器件，直至完成所有所述时序关键器件的所述位置优化处理。所述偏差值大于偏差阈值，按照所述排序依次选取所述时序关键器件进行位置优化处理，使所有所述时序关键器件的位置都得到优化，避免了所述时序关键器件之间的相互影响，减少了所述时序关键器件的时延，提高了时序优化效果。本发明还提供了一种用于实现所述布局优化方法的布局优化系统。

权利要求

1.一种布局优化方法，其特征在于，包括以下步骤：

S1：对电路进行时序分析；

S2：对m个时序器件按照时序裕量进行排序，取前n个所述时序器件为时序关键器件，并将所述时序关键器件按照所述时序裕量进行排序，所述m为大于1的自然数，所述n为大于1的自然数，且所述n占所述m的0.5％至1.5％；

S3：从n个时序关键器件中选取一个所述时序关键器件，计算所述时序关键器件基于所述时序关键器件所在路径的偏差值，所述偏差值为所述时序关键器件的位置与所述路径上所述时序关键器件的扇入器件和扇出器件连线之间的距离；

S4：判断所述偏差值大于偏差阈值时，则对所述时序关键器件进行位置优化处理；

S5：重复执行所述步骤S3和所述步骤S4，按照所述排序依次选取所述时序关键器件，直至完成所有所述时序关键器件的所述位置优化处理。

2.根据权利要求1所述的布局优化方法，其特征在于，所述步骤S4中，当所述偏差值小于等于所述偏差阈值时，则执行所述步骤S3选取下一个所述时序关键器件。

3.根据权利要求1所述的布局优化方法，其特征在于，所述位置优化处理包括：S21：提取所述时序关键器件的扇入集合，计算所述时序关键器件的最小实际到达时间弧；

S22：提取所述时序关键器件的扇出集合，计算所述时序关键器件的最大要求到达时间弧；

S23：根据所述最小实际到达时间弧和所述最大要求到达时间弧，计算所述时序关键器件的时序最佳区域和时序最佳区域的边框；

S24：在所述边框内进行遍历，选取所述时序关键器件的最佳布局位置；

S25：计算所述时序关键器件在所述最佳布局位置的时序裕量和原始位置的时序裕量；

S26：将所述最佳布局位置的时序裕量和所述原始位置的时序裕量进行对比，判断是否还原所述时序关键器件的位置。

4.根据权利要求3所述的布局优化方法，其特征在于，所述步骤S26中，当所述最佳布局位置的时序裕量小于所述原始位置的时序裕量，则将所述时序关键器件固定在所述最佳布局位置。

5.根据权利要求3所述的布局优化方法，其特征在于，所述步骤S26中，当所述最佳布局位置的时序裕量大于等于所述原始位置的时序裕量，则将所述时序关键器件还原到所述原始位置。

6.根据权利要求3所述的布局优化方法，其特征在于，所述最小实际到达时间弧为第一位置的集合，所述第一位置为使实际到达时间最小的所述时序关键器件的位置。

7.根据权利要求3所述的布局优化方法，其特征在于，所述最大要求到达时间弧为第二位置的集合，所述第二位置为使要求到达时间最大的所述时序关键器件的位置。

8.根据权利要求3所述的布局优化方法，其特征在于，所述时序最佳区域为第三位置的集合，所述第三位置为使所述时序裕量最大的所述时序关键器件的位置。

9.一种布局优化系统，其特征在于，所述布局优化系统用于实现权利要求1-8中任意一项所述的布局优化方法，所述布局优化系统包括时序分析模块、排序模块、选择模块、计算模块、判断模块和处理模块，所述时序分析模块用于对电路进行时序分析，所述排序模块用于对所述时序关键器件进行排序，所述选择模块用于提取所述时序关键器件的集合和所述时序关键器件，所述计算模块用于计算所述时序裕量和所述偏差，所述判断模块用于将所述偏差和所述偏差阈值进行对比，所述处理模块用于对所述时序关键器件进行位置优化处理。

说明书

布局优化方法及布局优化系统

技术领域

[0001] 本发明涉及集成电路技术领域，尤其涉及一种布局优化方法及布局优化系统。

背景技术

[0002] 集成电路的时序驱动的全局布局方法，通常采用线网加权等间接的方法来优化布局的芯片时序质量，因此全局布局后芯片时序仍然有相当大的优化空间。

[0003] 公开号为US07072815B1的美国发明专利申请的公开了一种优化布局后的构件再定位方法，其中的优化布局方法中只考虑单个时序关键路径上器件旧位置和新位置，没有考虑器件的新位置对其它通过该器件的时序关键路径的影响，因此在选择器件的新位置时，需要采用时序分析来检测器件新位置是否会造成其它时序关键路径的时序恶化，从而增加了时序分析的工作量，降低运行效率，另外，在选择器件的优化位置时，优化位置的选择错误也会影响到整体时序优化所能达到的效果。

[0004] 因此，有必要提供一种新型的布局优化方法以解决现有技术中存在的上述问题。

发明内容

[0005] 本发明的目的在于提供一种布局优化方法及布局优化系统，避免位置优化对其它时序关键器件的影响，提高时序优化效果。

[0006] 为实现上述目的，本发明的所述布局优化方法，包括以下步骤：

[0007] S1：对电路进行时序分析；

[0008] S2：从m个时序器件中提取n个时序关键器件，并将所述时序关键器件按照时序裕量进行排序，所述m为大于1的自然数，所述n为大于1的自然数；

[0009] S3：从n个时序关键器件中选取一个所述时序关键器件，计算所述时序关键器件基于所述时序关键器件所在路径的偏差值；

[0010] S4：判断所述偏差值大于偏差阈值时，则对所述时序关键器件进行位置优化处理；

[0011] S5：重复执行所述步骤S3和所述步骤S4，按照所述排序依次选取所述时序关键器件，直至完成所有所述时序关键器件的所述位置优化处理。

[0012] 本发明的有益效果在于：计算所述时序关键器件的偏差值，所述偏差值大于偏差阈值，按照所述排序依次选取所述时序关键器件进行位置优化处理，使所有所述时序关键器件的位置都得到优化，避免了所述时序关键器件之间的相互影响，减少了所述时序关键器件的时延，提高了时序优化效果。

[0013] 进一步优选地，所述步骤S4中，当所述偏差值小于等于所述偏差阈值时，则执行所述步骤S3选取下一个所述时序关键器件，其有益效果在于：只优化需要位置优化处理的所述时序关键器件，提高优化效率。

[0014] 优选地，对m个所述时序器件按照所述时序裕量进行排序，取前n个所述时序器件为所述时序关键器件，所述n占所述m的0.5％至1.5％。

[0015] 优选地，所述偏差阈值为所有所述时序器件平均长度的十倍。

[0016] 优选地，所述位置优化处理包括：

[0017] S21：提取所述时序关键器件的扇入集合，计算所述时序关键器件的最小实际到达时间弧；

[0018] S22：提取所述时序关键器件的扇出集合，计算所述时序关键器件的最大要求到达时间弧；

[0019] S23：根据所述最小实际到达时间弧和所述最大要求到达时间弧，计算所述时序关键器件的时序最佳区域和时序最佳区域的边框；

[0020] S24：在所述边框内进行遍历，选取所述时序关键器件的最佳布局位置；

[0021] S25：计算所述时序关键器件在所述最佳布局位置的时序裕量和原始位置的时序裕量；

[0022] S26：将所述最佳布局位置的时序裕量和所述原始位置的时序裕量进行对比，判断是否还原所述时序关键器件的位置，其有益效果在于：根据所述最小实际到达时间弧和所述最大要求到达时间弧，计算所述时序关键器件的时序最佳区域和时序最佳区域的边框，在所述边框内选取所述时序关键器件的最佳布局位置，不会对其它所述时序关键器件和路径在成影响，从而不会出现时序下降的可能，提高了时序优化的质量。

[0023] 进一步优选地，所述步骤S26中，当所述最佳布局位置的时序裕量小于所述原始位置的时序裕量，则将所述时序关键器件固定在所述最佳布局位置。

[0024] 进一步优选地，所述步骤S26中，当所述最佳布局位置的时序裕量大于等于所述原始位置的时序裕量，则将所述时序关键器件还原到所述原始位置。

[0025] 进一步优选地，所述最小实际到达时间弧为第一位置的集合，所述第一位置为使实际到达时间最小的所述时序关键器件的位置。

[0026] 进一步优选地，所述最大要求到达时间弧为第二位置的集合，所述第二位置为使要求到达时间最大的所述时序关键器件的位置。

[0027] 进一步优选地，所述时序最佳区域为第三位置的集合，所述第三位置为使所述时序裕量最大的所述时序关键器件的位置。

[0028] 本发明还提供了一种用于实现所述布局优化方法的布局优化系统，所述布局优化系统包括时序分析模块、排序模块、选择模块、计算模块、判断模块和处理模块，所述时序分析模块用于对电路进行时序分析，所述排序模块用于对所述时序关键器件进行排序，所述选择模块用于提取所述时序关键器件的集合和所述时序关键器件，所述计算模块用于计算所述时序裕量和所述偏差，所述判断模块用于将所述偏差和所述偏差阈值进行对比，所述处理模块用于对所述时序关键器件进行位置优化处理。

[0029] 本发明的布局优化系统的有益效果在于：通过所述计算模块计算所述时序裕量，再通过所述排序模块将所述时序关键器件进行排序，通过所述选择模块依次选取所述时序关键器件，通过所述计算模块计算出所述时序关键器件的偏差值，所述判断模块对所述时序关键器件的偏差值进行判断后，所述判断模块判断对所述时序关键器件进行所述位置优化处理，所述处理模块则对所述时序关键器件进行位置优化处理，能对所有所述时序关键器件进行时序优化，排序后依次进行所述位置优化，减少所述时序关键器件相互之间的影响，提高时序优化质量。

附图说明

[0030] 图1为本发明布局优化方法的流程图；

[0031] 图2为本发明布局优化系统的结构框图；

[0032] 图3为本发明的一些实施例的最小实际到达时间的示意图；

[0033] 图4a为本发明的一些实施例的所述时序最佳区域的一种位置示意图；

[0034] 图4b为本发明的一些实施例的所述时序最佳区域的另一种位置示意图；

[0035] 图5a为本发明一些实施例的曼哈顿弧的一种位置示意图；

[0036] 图5b为本发明一些实施例的曼哈顿弧的另一种位置示意图；

[0037] 图5c为本发明一些实施例的曼哈顿弧的又一种位置示意图。

具体实施方式

[0038] 为使本发明的目的、技术方案和优点更加清楚，下面将结合本发明的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明的一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。除非另外定义，此处使用的技术术语或者科学术语应当为本发明所属领域内具有一般技能的人士所理解的通常意义。本文中使用的“包括”等类似的词语意指出现该词前面的元件或者物件涵盖出现在该词后面列举的元件或者物件及其等同，而不排除其他元件或者物件。

[0039] 针对现有技术存在的问题，本发明的实施例提供了一种布局优化方法，参照图1，所述布局优化方法包括：

[0040] S1：对电路进行时序分析；

[0041] S2：从m个时序器件中提取n个时序关键器件，并将所述时序关键器件按照时序裕量进行排序，所述m为大于1的自然数，所述n为大于1的自然数；

[0042] S3：从n个时序关键器件中选取一个所述时序关键器件，计算所述时序关键器件基于所述时序关键器件所在路径的偏差值；

[0043] S4：判断所述偏差值大于偏差阈值时，则对所述时序关键器件进行位置优化处理；

[0044] S5：重复执行所述步骤S3和所述步骤S4，按照所述排序依次选取所述时序关键器件，直至完成所有所述时序关键器件的所述位置优化处理。

[0045] 本发明的一些优选实施例中，所述步骤S2中，从m个时序器件中提取n个时序关键器件，并将所述时序关键器件按照时序裕量从小到大进行排序，所述m为大于1的自然数，所述n为大于1的自然数。

[0046] 本发明的一些优选实施例中，所述步骤S5中，重复执行所述步骤S3和所述步骤S4，按照所述时序裕量从小到大的顺序依次选取所述时序关键器件，直至完成所有所述时序关键器件的所述位置优化处理。

[0047] 本发明的一些实施例中，所述步骤S4中，当所述偏差值小于等于所述偏差阈值时，则执行所述步骤S3选取下一个所述时序关键器件。

[0048] 本发明的一些实施例中，对m个所述时序器件按照所述时序裕量进行排序，取前n个所述时序器件为所述时序关键器件，所述n占所述m的0.5％至1.5％。优选地，对m个所述时序器件按照所述时序裕量从小到大进行排序，取前n个所述时序器件为所述时序关键器件，所述n占所述m的1％。

[0049] 本发明的一些实施例中，所述电路中共m个所述时序器件。

[0050] 本发明的一些实施例中，所述偏差阈值为所有所述时序器件平均长度的十倍。

[0051] 本发明的一些实施例中，所述位置优化处理包括：

[0052] S21：提取所述时序关键器件的扇入集合，计算所述时序关键器件的最小实际到达时间弧；

[0053] S22：提取所述时序关键器件的扇出集合，计算所述时序关键器件的最大要求到达时间弧；

[0054] S23：根据所述最小实际到达时间弧和所述最大要求到达时间弧，计算所述时序关键器件的时序最佳区域和时序最佳区域的边框；

[0055] S24：在所述边框内进行遍历，选取所述时序关键器件的最佳布局位置；

[0056] S25：计算所述时序关键器件在所述最佳布局位置的时序裕量和原始位置的时序裕量；

[0057] S26：将所述最佳布局位置的时序裕量和所述原始位置的时序裕量进行对比，判断是否还原所述时序关键器件的位置。

[0058] 本发明的一些实施例中，所述步骤S26中，当所述最佳布局位置的时序裕量小于所述原始位置的时序裕量，则将所述时序关键器件固定在所述最佳布局位置。

[0059] 本发明的一些实施例中，所述步骤S26中，当所述最佳布局位置的时序裕量大于等于所述原始位置的时序裕量，则将所述时序关键器件还原到所述原始位置。

[0060] 本发明的一些实施例中，所述最小实际到达时间弧为第一位置的集合，所述第一位置为使实际到达时间最小的所述时序关键器件的位置。

[0061] 本发明的一些实施例中，所述最大要求到达时间弧为第二位置的集合，所述第二位置为使要求到达时间最大的所述时序关键器件的位置。

[0062] 本发明的一些实施例中，所述时序最佳区域为第三位置的集合，所述第三位置为使所述时序裕量最大的所述时序关键器件的位置。

[0063] 图2为本发明一些实施例的所述布局优化系统的结构框图。参照图2，所述布局优化系统包括时序分析模块1、排序模块2、选择模块3、计算模块4、判断模块5和处理模块6，所述时序分析模块1用于对电路进行时序分析，所述排序模块2用于对所述时序关键器件进行排序，所述选择模块3用于提取所述时序关键器件的集合和所述时序关键器件，所述计算模块4用于计算所述时序裕量和所述偏差，所述判断模块5用于将所述偏差和所述偏差阈值进行对比，所述处理模块6用于对所述时序关键器件进行位置优化处理。

[0064] 本发明的一些实施例中，所述电路中，传递信号给所述时序关键器件的器件为所述时序关键器件的扇入器件，接收所述时序关键器件传输信号的器件为所述时序关键器件的扇出器件。

[0065] 本发明的一些实施例中，所述偏差值为所述时序关键器件的位置与所述路径上所述时序关键器件的扇入器件和扇出器件连线之间的距离。

[0066] 本发明的一些实施例中，计算所述偏差值的具体步骤为：依次计算所述时序关键器件的扇入器件和所述时序关键器件之间的曼哈顿距离、所述时序关键器件和所述时序关键器件的扇出器件之间的曼哈顿距离、所述时序关键器件的扇入器件和所述时序关键器件的扇出器件之间的曼哈顿距离；根据所述时序关键器件的扇入器件和所述时序关键器件之间的曼哈顿距离、所述时序关键器件和所述时序关键器件的扇出器件之间的曼哈顿距离、所述时序关键器件的扇入器件和所述时序关键器件的扇出器件之间的曼哈顿距离得到所述偏差值。

[0067] 本发明的一些实施例中，所述时序关键器件的扇入器件和所述时序关键器件之间的曼哈顿距离加所述时序关键器件和所述时序关键器件的扇出器件之间的曼哈顿距离得到第一结果；所述第一结果减所述时序关键器件的扇入器件和所述时序关键器件的扇出器件之间的曼哈顿距离得到所述偏差值。

[0068] 本发明的一些具体实施例中，计算所述偏差值的公式为dev(v)＝dist(s,v)+dist(v,t)-dist(s,t)，其中，所述v为所述时序关键器件，所述s为所述v的扇入器件，所述t为所述v的扇出器件，所述dev(v)为所述v的偏差值，所述dist(s,v)为所述s和所述v之间的曼哈顿距离，所述dist(v,t)为所述v和所述t之间的曼哈顿距离，所述dist(s,t)为所述s和所述t之间的曼哈顿距离。

[0069] 本发明的一些实施例中，计算所述时序关键器件的实际到达时间的具体步骤为：计算所述时序关键器件的单个扇入节点的实际到达时间；再计算所述单个扇入节点和所述时序关键器件之间的曼哈顿距离；对所述单个扇入节点和所述时序关键器件之间的曼哈顿距离进行修订，得到修订曼哈顿距离；根据所述时序关键器件的单个扇入节点的实际到达时间和所述修订曼哈顿距离得到单个扇入节点的实际到达时间；依次求取所述时序关键器件所有所述单个扇入节点的实际到达时间；取所有所述单个扇入节点的实际到达时间中的最大值为所述时序关键器件的实际到达时间。

[0070] 本发明的一些具体实施例中，定义所述最小实际到达时间弧为K(F)，F＝{Fi}，其中，F为所述时序关键器件的所有扇入节点的集合，F＝{Fi}，因为所述最小实际到达时间弧为所述第一位置的集合，Fi表示所述第一位置的物理意义，用函数K(F)表示所述最小实际到达时间弧。

[0071] 本发明的一些具体实施例中，计算所述时序关键器件的实际到达时间的公式为AAT(v)＝max{AAT(Fi)+delay(Fi,v)},其中，Fi∈F，在对布局结果进行时序分析时，对连线采用线性时延模型，因此忽略信号通过所述时序关键器件的延时，将忽略信号通过所述时序关键器件的延时假设为常数，且不影响所述最小实际到达时间弧的计算和相关分析，则得到公式AAT(v)＝max{AAT(Fi)+τ×dist(Fi,v)},Fi∈F，所述v为所述时序关键器件，所述τ为常数，所述Fi为所述v的一个扇入节点，所述AAT(v)为所述v的实际到达时间，所述AAT(Fi)为所述v的扇入时间，所述dist(Fi,v)为所述Fi和所述v之间的曼哈顿距离。

[0072] 图3为本发明的一些实施例的最小实际到达时间的示意图。参照图3，所述时序关键器件具有两个扇入节点，所述两个扇入节点分为第一扇入节点31和第二扇入节点32，定义所述第一扇入节点31为F1，所述第二扇入节点32为F2，信号到达所述F1的时间为AAT(F1)，AAT(F1)＝1，信号到达所述F2的时间为AAT(F2)，AAT(F2)＝3，所述第一扇入节点31和所述第二扇入节点32之间的距离对应的连线延时为6，所述最小实际到达时间弧为一条与水平线成45度的线段33，信号从所述第一扇入节点31到达所述线段33的连线延时时间为4，信号从所述第二扇入节点32到达所述线段33的连线延时时间为2，当所述时序关键器件在所述最小实际到达时间弧上某个位置时，AAT(v)＝5，5为最小值。

[0073] 本发明的一些实施例中，计算新的最小实际到达时间弧的步骤为：依次遍历所述时序关键器件的所有扇入节点，更新所述时序关键器件的最小实际到达时间弧和信号到达所述时序关键器件的最小实际到达时间弧的实际到达时间；对所有所述扇入节点中的第一个扇入节点进行初始化，所述最小实际到达时间弧等于所述第一个扇入节；所述所有扇入节点排除所述第一个扇入节点，得到剩余扇入节点；选取单个剩余扇入节点，计算所述单个剩余扇入节点和最小实际到达时间弧之间的距离，并根据修订后的所述距离、所述实际到达时间和所述单个剩余扇入节点的实际到达时间，得到所述最小实际到达时间弧到达所述新的最小实际到达时间弧的第一距离和所述单个剩余扇入节点到达所述新的最小实际到达时间弧的第二距离；根据所述最小实际到达时间弧和所述单个节点构建范围图形，得到单个最小实际到达时间弧；求取根据所有单个剩余节点得到的所述单个最小实际到达时间弧，进行处理后得到所述新的最小实际到达时间弧。

[0074] 本发明的一些具体实施例中，计算新的最小实际到达时间弧的具体步骤为：依次遍历所述所有扇入节点的集合，更新所述最小实际到达时间弧和信号到达所述最小实际到达时间弧中位置的实际到达时间，所述实际到达时间为AAT(K(F))；对所述所有扇入节点的集合中的第一个节点行初始化处理，所述第一个节点为F1，得到K(F)＝F1，所以AAT(K(F))＝AAT(F1)；所述所有扇入节点的集合中除去所述第一个节点得到剩余扇入节点集合，所述剩余扇入节点集合为Fa，计算所述剩余扇入节点集合和所述最小实际到达时间弧之间的距离，所述距离为d。

[0075] τ为常数，当τ与d的乘积大于所述最小实际到达时间弧的实际到达时间减所述剩余扇入节点集合的实际到达时间的绝对值时，所述最小实际到达时间弧的实际到达时间减所述剩余扇入节点集合的实际到达时间得到第三结果，τ与d的乘积为第四结果，所述第三结果加所述第四结果得到第五结果，2与τ的乘积为第六结果，所述第五结果除以所述第六结果得到第一距离，d减去所述第一距离，得到第二距离；

[0076] 当τ与d的乘积小于所述最小实际到达时间弧的实际到达时间减所述剩余扇入节点集合的实际到达时间的绝对值，且所述最小实际到达时间弧的实际到达时间大于所述剩余扇入节点集合的实际到达时间时，第一距离为0，所述最小实际到达时间弧的实际到达时间减所述剩余扇入节点集合的实际到达时间得到第七结果，所述第七结果除以τ得到所述第二距离；

[0077] 当τ与d乘积小于所述最小实际到达时间弧的实际到达时间减所述剩余扇入节点集合的实际到达时间的绝对值，且所述最小实际到达时间弧的实际到达时间小于所述剩余扇入节点集合的实际到达时间时，第二距离为0，所述剩余扇入节点集合的实际到达时间减所述最小实际到达时间弧的实际到达时间得到第八结果，所述第八结果除以τ得到所述第一距离；

[0078] 所述第一距离为d1，所述第二距离为d2；构建以所述最小实际到达时间弧为对边中心点连线上的线段，距所述最小实际到达时间弧的距离为d1，与水平线呈45度角倾斜的第一正方形，构建以所述剩余扇入节点集合为中心点，一个角离所述中心点的距离为d2，与水平线呈45度角的第二正方形，所述第一正方形和所述第二正方形相互重叠的部分是一个曼哈顿弧，所述曼哈顿弧为所述新的最小实际到达时间弧。

[0079] 图5a为本发明一些实施例的曼哈顿弧的一种位置示意图。图中所述第一正方形51和所述第二正方形52与水平线59呈45度角，线段53与所述水平线呈45度角，所述第一正方形51和所述第二正方形52部分边相重叠，所述第一正方形51内的所述线段53为所述最小实际到达时间弧，所述最小实际到达时间弧右端点54和所述第一正方形51第一右端角55的距离为d1，所述第二正方形内的黑点56为所述剩余扇入节点集合，所述黑点56和所述第二正方形52第二右端角57的距离为d2，所述第一正方形51和所述第二正方形52重叠部位为所述曼哈顿弧58。

[0080] 图5b为本发明一些实施例的曼哈顿弧的另一种位置示意图。图中所述第二正方形52与水平线59呈45度角，线段53与所述水平线59呈45度角，所述第二正方形52内的黑点56为所述剩余扇入节点集合，与所述第二正方形52右上边交叉连接的线段53为所述最小实际到达时间弧，与所述线段53位于所述第二正方形52内部且重叠的部分为所述曼哈顿弧58。

[0081] 图5c为本发明一些实施例的所述曼哈顿弧的又一种位置示意图。图中所述第一正方形51与水平线59呈45度角，线段53与所述水平线59呈45度角，所述第一正方形51内部的线段53为最小实际到达时间弧，所述第一正方形51内部的黑点56为所述剩余扇入节点集合，所述曼哈顿弧(图中未标出)与所述黑点54重合。

[0082] 本发明的一些实施例中，定义所述最大要求到达时间弧为K(S)，S＝{Si}，所述S为所述时序关键器件的所有扇出节点的集合，因为所述最大要求到达时间弧为所述第二位置的集合，所述Si表示所述第二位置的物理意义，用函数K(F)表示所述最大要求到达时间弧。

[0083] 本发明的一些实施例中，所述最大要求到达时间弧在物理意义上所形成的形状情况与所述最小实际到达时间弧相同。

[0084] 本发明的一些实施例中，计算所述时序关键器件的要求到达时间的步骤与计算所述时序关键器件的实际到达时间步骤相同，其区别在于，计算所述要求到达时间基于所述扇出节点的集合，且结果中取最小值，计算所述时序关键器件的实际到达时间基于所述扇入节点的集合，且结果中取最大值。

[0085] 本发明的一些具体实施例中，计算所述时序关键器件的要求到达时间的公式为RAT(v)＝min{RAT(Si)+τ×dist(v,Si)}，其中，所述v为所述时序关键器件，所述τ为常数，所述Fi为所述v的一个扇入节点，所述Si为所述v的一个扇出节点，所述RAT(v)为所述v的要求到达时间，所述RAT(Si)为所述v的扇出时间，所述dist(v,Si)为所述v与所述Si之间的曼哈顿距离。

[0086] 本发明的一些实施例中，计算新的最大要求到达时间弧与计算新的最小实际到达时间弧的方法相同，其区别在于，所述新的最小实际到达时间弧基于所述时序关键器件的扇入节点的集合计算得出，所述新的最大要求到达时间弧基于所述时序关键器件的扇出节点的集合计算得出。

[0087] 本发明的一些具体实施例中，计算所述新的最大要求到达时间弧的具体步骤为：依次遍历所述所有扇出节点的集合，更新所述最大要求到达时间弧和信号到达所述最大要求到达时间弧中位置的所述要求到达时间，所述要求到达时间为RAT(K(S))；对所述所有扇出节点的集合中的第一个节点行初始化处理，所述第一个节点为S1，得到K(S)＝S1，所以RAT(K(S))＝RAT(S1)；所述所有扇出节点的集合中除去所述第一个节点得到剩余扇出节点集合，所述剩余扇出节点集合为Sa，计算所述剩余扇出节点集合和所述最大要求到达时间弧之间的距离，所述距离为e；

[0088] τ为常数，当τ与e的乘积大于所述最大要求到达时间弧的要求达到时间减所述Sa的要求达到时间的绝对值时，所述最大要求到达时间弧的要求达到时间减所述Sa的要求达到时间得到第三结果，τ与e乘积为第四结果，所述第三结果加所述第四结果得到第五结果，2与τ的乘积为第六结果，所述第五结果除以所述第六结果得到第三距离，e减去所述第三距离，得到第四距离；

[0089] 当τ与e的乘积小于所述最大要求到达时间弧的要求达到时间减所述剩余节点集合的要求达到时间的绝对值，且所述最大要求到达时间弧的要求达到时间大于所述剩余节点集合的要求达到时间时，第三距离为0，所述最大要求到达时间弧的要求达到时间减所述剩余节点集合的要求达到时间得到第七结果，所述第七结果除以τ得到所述第四距离；

[0090] 当τ与e的乘积小于所述最大要求到达时间弧的要求达到时间减所述剩余节点集合的要求达到时间的绝对值，且所述最大要求到达时间弧的要求达到时间小于所述剩余节点集合的要求达到时间时，第四距离为0，所述剩余节点集合的要求达到时间减所述最大要求到达时间弧的要求达到时间得到第八结果，所述第八结果除以τ得到所述第三距离；

[0091] 所述第三距离为e1，所述第四距离为e2；构建以所述最大要求到达时间弧为中心线，距所述中心线的距离为e1，呈45度角倾斜的第一正方形，构建以所述剩余扇出节点集合为中心点，距所述中心点的距离为e2，呈45度角倾斜的第二正方形，所述第一正方形和所述第二正方形相互重叠的部分是一个曼哈顿弧，所述曼哈顿弧为所述新的最大要求到达时间弧。

[0092] 本发明的一些实施例中，计算所述时序裕量的具体步骤为：计算所述时序关键器件的要求达到时间；计算所述时序关键器件的实际到达时间；所述时序关键器件的要求达到时间减所述时序关键器件的实际到达时间得到所述时序裕量。

[0093] 本发明的一些具体实施例中，定义所述时序关键器件的所述时序最佳区域为Z，所述时序最佳区域为使所述时序关键器件的时序裕量最大的位置的集合，所述时序关键器件的时序裕量计算公式为slack(v)＝RAT(v)-AAT(v)，所述v为所述时序关键器件，所述slack(v)为所述v的时序裕量，所述RAT(v)为所述v的要求到达时间，所述AAT(v)为所述v的实际到达时间。

[0094] 本发明的一些实施例中，所述时序关键器件位于所述最小实际到达时间弧和所述最大要求到达时间弧所包围的所述时序最佳区域内时，所述时序关键器件和所述最小实际到达时间弧之间的曼哈顿距离加上所述时序关键器件和所述最大要求到达时间弧之间的曼哈顿距离之和最小，同时所述时序裕量最大。

[0095] 图4a为本发明的一些实施例的所述时序最佳区域的一种位置示意图。参照图4a，所述最小实际到达时间弧41和所述最大要求到达时间弧42相互平行，所述最小实际到达时间弧41和所述最大要求到达时间弧42包围的区域为所述时序最佳区域43，虚线矩形为所述时序最佳区域的边框44。

[0096] 图4b为本发明的一些实施例的所述时序最佳区域的另一种位置示意图。参照图4b，所述最小实际到达时间弧41和所述最大要求到达时间弧42相互垂直，所述最小实际到达时间弧和所述最大要求到达时间弧包围的区域为所述时序最佳区域43，虚线矩形为所述时序最佳区域的边框44。

[0097] 本发明的一些实施例中，计算基于所述最小实际到达时间弧和所述最大要求到达时间弧的所述时序最佳区域的边框的具体步骤为：计算所述最小实际到达时间弧和所述最大要求到达时间弧之间的最小距离；去掉所述最小实际到达时间弧中到达所述最大要求到达时间弧的距离大于所述最小距离的部分，去掉所述最大要求到达时间弧中到达所述最小实际到达时间弧的距离大于所述最小距离的部分；计算包围所述最小实际到达时间弧的边框和所述最大要求到达时间弧的边框的边框，即为所述时序最佳区域的边框。

[0098] 本发明的一些实施例中，选取所述时序关键器件的新布局位置的具体步骤为：计算出所述时序最佳区域的边框后，遍历所述时序最佳区域的边框中的所有位置；选取所述时序最佳区域的边框中没有被器件占用的位置；从所述没有被器件占用的位置中，选取到所述最小实际到达时间弧和所述最大要求到达时间弧距离之和最小的位置；从所述距离之和最小的位置中，选取到所述时序关键器件所在路径两个始终点所构成的边框距离最小的位置，所述距离最小的位置为最佳位置，所述最佳位置作为所述时序关键器件的新布局位置。

[0099] 虽然在上文中详细说明了本发明的实施方式，但是对于本领域的技术人员来说显而易见的是，能够对这些实施方式进行各种修改和变化。但是，应理解，这种修改和变化都属于权利要求书中所述的本发明的范围和精神之内。而且，在此说明的本发明可有其它的实施方式，并且可通过多种方式实施或实现。