本发明公布了一种GPU加速计算的集成电路无悲观路径分析方法，包括步骤：电路结构扁平化，电路结构分层预处理，多GPU并行候选路径生成，全局候选路径合并。其中，多GPU并行候选路径生成包括步骤：多GPU任务分配，延迟分组初始化，并行延迟传播，并行渐进候选路径生成，并行局部候选路径预合并。本发明通过引入算法和数据结构的等价变换，在多个GPU上并行地完成无悲观时序分析中的密集计算，实现使用CPU完成多GPU之间的数据和控制调度工作。通过单CPU‑多GPU异构计算模型的协同配合，相比原有CPU算法可得到数十倍的性能提升，大幅降低无悲观路径分析的计算成本，可推广应用于芯片设计自动化技术领域。
1.一种GPU加速计算的集成电路无悲观路径分析方法，其特征是，包括步骤：A.电路结构扁平化，并将数据传送到主GPU；
将集成电路的时钟线网表示为一个有向无环图；有向无环图中的节点表示电路的管脚和转折部分，边表示管脚之间的连接关系；集成电路中的所有寄存器的时钟管脚集合中的节点在有向无环图中的上游节点和边构成集成电路的时钟分发网络，又称时钟树；
对有向无环图进行扁平化，用CSR形式存储的邻接表表示有向无环图中的边关系；构建单CPU‑多GPU异构计算模型，具体是将可用GPU分为一个主GPU和剩余多个从属GPU，并将扁平化的有向无环图数据传送到主GPU；
对扁平化的有向无环图进行逆向拓扑排序，将电路结构中的组合逻辑进行分层，得到分层的部分有向无环图，同时保留寄存器的时钟管脚，并对时钟树进行单独分层，得到分层时钟树，并将分层结果广播到所有从属GPU；
C1)进行多GPU任务分配，将分层时钟树深度对应的计算任务均匀分配给所有GPU；
C2)延迟分组初始化：在每个GPU上分别进行延迟分组初始化，每个GPU依次处理自己分配到的每个深度，将分层时钟树中的所有节点按深度以下的子树进行分组；
C3)并行延迟传播：在每个GPU上分别进行延迟分组初始化，并行延迟传播；
C4)并行渐进候选时序违例路径生成，获得每个GPU上的局部候选时序违例路径列表；
在每个GPU上进行局部候选路径预合并，得到局部计算任务合并后对应的k条局部候选时序违例路径；
从所有从属GPU传送局部候选时序违例路径到主GPU上，并在主GPU上进一步合并获得前k条时序违例最严重的路径，即为路径分析的结果；
通过上述步骤，即可实现GPU加速计算的集成电路无悲观路径分析。
2.如权利要求1所述GPU加速计算的集成电路无悲观路径分析方法，其特征是，步骤A中，所述有向无环图的每条边标记信号传送的最小和最大延迟。
3.如权利要求1所述GPU加速计算的集成电路无悲观路径分析方法，其特征是，步骤A中，传送到主GPU的扁平化的有向无环图数据包括每个节点的起始边索引、终止边索引、是否为寄存器时钟管脚的标记，以及每条边的目标节点、最小延迟、最大延迟信息。
4.如权利要求1所述GPU加速计算的集成电路无悲观路径分析方法，其特征是，步骤B中，对扁平化的有向无环图，在主GPU上设计并行逆向拓扑排序算法，具体是：从出度为零的点出发，并行拓展并移除它们的入边，检查入边的源节点，将出度为零且不为寄存器时钟管脚的节点收集并作为下一次并行拓展的基础；重复此过程，依次将电路结构中的组合逻辑进行分层，得到分层的部分有向无环图；
剩余未分层的有向无环图节点从寄存器时钟管脚节点出发，并行拓展并移除节点的唯一入边，收集出度为零的源节点；重复此过程，对时钟线网进行单独分层，得到分层时钟树；
分层结果包含由组合逻辑构成的分层的部分有向无环图和分层时钟树。
5.如权利要求1所述GPU加速计算的集成电路无悲观路径分析方法，其特征是，步骤C1中，多GPU任务分配方法具体过程如下：设分层时钟树的每层编号分别为0～D‑1，共D个深度，设总GPU个数为N，将D个深度的编号分为N份，每份包含D/N个深度编号，代表一个GPU需要执行和提交的计算任务。
6.如权利要求5所述GPU加速计算的集成电路无悲观路径分析方法，其特征是，步骤C2中，每个GPU依次处理分配到的每个深度d；将分层时钟树中的所有节点按照深度d以下的子树进行分组，过程为：将分层时钟树第d+1层的节点所属分组设置为该节点自己的编号；
从第d+2层开始，并行设置每个节点的组编号为其时钟树上父节点的组编号；
然后处理第d+3层，直到最后一层，得到分层时钟树上每个节点的分组信息；
进行基于分组约束的延迟初始化，根据时钟树边在分层时钟树上的深度，为其设置最小延迟或最大延迟，用于预先消除公共路径悲观量。
7.如权利要求6所述GPU加速计算的集成电路无悲观路径分析方法，其特征是，步骤C3中，具体是在分层的部分有向无环图上逐层完成延迟信息的计算；对于每一层，使用GPU并行完成层内的延迟计算，每一个GPU线程枚举一个节点的入边，计算该节点的延迟信息，包括路径延迟极值、路径延迟第二极值以及对应的延迟来源时钟树节点的分组编号。
8.如权利要求1所述GPU加速计算的集成电路无悲观路径分析方法，其特征是，步骤C4并行渐进候选路径生成的过程，具体是：在每个GPU处，并行从时序分析的所有终点出发，通过延迟信息和分组约束向前查找延迟极值对应的入边，连接成一条路径，即为每个时序分析终点处时序违例最严重的路径；
计算路径的松弛值，对于建立时间传播，计算寄存器的最晚时间约束值，对于保持时间传播，计算寄存器的最早时间约束值，将约束值与路径延迟做差即获得路径的松弛值；所述路径的松弛值与时序违例的程度负相关；
将所有时序分析终点处时序违例最严重的路径按照松弛值由小到大排序，排序使用GPU上的并行归并排序或基数排序算法；
将排序以后的路径列表保留前k条路径并丢弃其余路径，得到第一层渐进候选路径；
使用GPU并行拓展所有第一层渐进候选路径，每个GPU线程枚举一条路径上的所有节点的入边，通过入边扩展出新的路径，新的路径存放在预分配的数组空间中；
所有新的路径构成的列表与第一层渐进候选路径合并后，按照松弛值由小到大排序，保留前k条路径并丢弃其余路径，得到第二层渐进候选路径，其中包含部分第一层渐进候选路径，以及部分由第一层渐进候选路径扩展出的新路径；
再次使用GPU并行拓展第二层渐进候选路径，经过合并、排序、保留操作，获得第三层渐进候选路径，以此类推，直到路径扩展操作不能再扩展出新的路径则停止，得到的k条渐进候选路径即为深度为d的时序违例最严重的k条候选路径。
9.如权利要求8所述GPU加速计算的集成电路无悲观路径分析方法，其特征是，步骤C5并行局部候选路径预合并的过程，具体是：将每个GPU分配到的每个深度d计算出的k条候选路径合并后，按照松弛值由小到大排序，保留前k条路径并丢弃其余路径，作为每个GPU处的局部候选路径；所述合并、排序、保留的过程均在所有GPU上独立并行完成。
10.如权利要求9所述GPU加速计算的集成电路无悲观路径分析方法，其特征是，步骤.全局候选路径合并，具体是从所有从属GPU传送k条局部候选路径到主GPU上，并在主GPU上进一步合并，排序并保留前k条时序违例最严重的路径，即为路径分析的结果。
一种GPU加速计算的集成电路无悲观路径分析方法
技术领域
[0001] 本发明属于集成电路设计自动化技术领域，涉及集成电路静态时序分析技术，具体涉及一种使用CPU‑GPU异构加速计算的集成电路无悲观路径分析方法，在保证获得准确集成电路静态时序分析结果的前提下，提升了集成电路路径分析的效率。
背景技术
[0002] 静态时序分析是芯片设计的重要方法步骤，在这一步骤中，芯片设计自动化软件将会检查设计中的所有路径是否存在时序违例，并按照违例程度顺序报告一系列需要引起注意的路径，这一具体过程也被称为路径分析。存在时序违例的路径会严重影响芯片的运行效率和稳定性，因而在芯片设计自动化的流程中，静态时序分析作为一个核心工具，指导了许多步骤如逻辑综合、布局布线的计算和优化过程。
[0003] 信号在芯片上传播的过程中，会轮流经过线网和门组件构成的时序边，每条时序边都会引入一定的延迟。为了确保芯片设计能够在各种制造和运行条件下正常工作，我们用一个最小值和一个最大值构成的范围来刻画每条时序边的延迟。一条时序路径包含数据通路和时钟通路。对路径的时序违例检查，就是为数据通路部分和时钟通路部分中的时序边选择不同的延迟值，并检查是否会违反寄存器的限制。
[0004] 通常情况下，一条时序路径的数据通路和控制通路存在一段公共部分，这个公共部分使得对时序边选择延迟值的过程变得复杂，因为数据路径和控制路径的延迟选择在公共部分上必须相同。一种方法是忽略这个公共部分的限制，采用简化的模型完成静态时序分析的计算，但是会使得计算出的路径时序违例报告过分悲观，不能准确反映芯片的时序表现。为了消除这种悲观量，必须准确处理公共部分的延迟计算过程，然而这种处理会大幅增加时序分析的计算时间，有学术研究显示，相比不考虑公共部分的静态时序分析实现，准确的、无悲观的路径分析会慢将近100倍。近年来学术界不断出现对无悲观路径分析的改进和算法优化，一定程度上提升了时序分析的效率，但由于这些算法的CPU多线程并行能力的瓶颈，处理超大规模集成电路的分析任务仍然需要10～60分钟。
[0005] 综上所述，现有的无悲观的准确静态时序分析技术具有计算量大、计算效率低、并行能力较差的特点，限制了静态时序分析在芯片设计优化中的应用。
发明内容
[0006] 本发明的目的是提供一种GPU加速计算的集成电路无悲观路径分析方法，以克服上述现有无悲观静态时序分析技术存在的不足。本发明通过将计算负载设计为GPU友好的算法和数据结构，利用单CPU‑多GPU异构计算模型的并行计算和调度能力来处理大规模芯片设计的路径时序验证和悲观量消除问题，在保证获得准确静态时序分析结果的前提下，提升了路径分析方法的执行效率。
[0007] 本发明以无悲观路径分析CPU算法为基础，针对无悲观路径分析中的核心步骤(包括电路结构初始化、分组延迟信息计算、候选路径生成与合并)创新性的引入了算法和数据结构的等价变换，使之适应GPU的计算模型和体系结构，进而能够在多个GPU上并行地完成无悲观时序分析中的密集计算，实现使用CPU完成多GPU之间的数据和控制调度工作。通过单CPU‑多GPU异构计算模型的协同配合，本发明相比原有CPU算法可以得到数十倍的性能提升，大幅降低了无悲观路径分析的计算成本，使之能够在芯片设计自动化流程中得到更大范围的应用。
[0008] 本发明的技术方案是：
[0009] 一种GPU加速计算的集成电路无悲观路径分析方法，包括步骤：电路结构扁平化，电路结构分层预处理，多GPU并行候选路径生成，全局候选路径合并。其中，多GPU并行候选路径生成包括步骤：多GPU任务分配，延迟分组初始化，并行延迟传播，并行渐进候选路径生成，并行局部候选路径预合并。在电路结构扁平化步骤中，将集成电路的时钟线网表示为一个有向无环图，其中节点表示电路的管脚和转折部分，边表示管脚之间的连接关系，对有向无环图进行扁平化，用压缩稀疏行(Compressed Sparse Row,CSR)形式存储的邻接表表示图中的边关系。构建单CPU‑多GPU异构计算模型，具体操作为将可用GPU分为一个主GPU和剩余多个从属GPU，并设总GPU数量为N，并将扁平化的有向无环图数据传送到主GPU。在电路结构分层预处理过程中，对扁平化的有向无环图进行逆向拓扑排序，将电路结构中的组合逻辑进行分层，得到分层的部分有向无环图，同时保留寄存器的时钟管脚，并对时钟线网进行单独分层，得到分层的时钟树，并将分层结果广播到所有从属GPU。在多GPU并行候选路径生成中，进行多GPU任务分配，将分层的时钟树不同层次对应的计算任务均匀分配给所有GPU；在每个GPU上分别进行延迟分组初始化，并行延迟传播，并行渐进候选路径生成，获得每个GPU上的局部候选时序违例路径列表；设静态时序分析的路径需求数目为参数k，在每个GPU上进行局部候选路径预合并，得到局部计算任务合并后对应的k条局部候选时序违例路径，总共N*k条。在全局候选路径合并中，从所有从属GPU传送局部候选时序违例路径到主GPU上，并在主GPU上进一步合并所有的N*k条路径，获得前k条时序违例最严重的路径，即为路径分析的结果。
[0010] 具体包含以下步骤：
[0011] A.电路结构扁平化；
[0012] 将集成电路的时钟线网表示为一个有向无环图，其中节点表示电路的管脚和转折部分，边表示管脚之间的连接关系。每条边标记了信号传送的最小和最大延迟。在给定的集成电路设计中，定义所有寄存器的输入时钟管脚端构成的集合为时钟管脚集合，时钟管脚集合中的节点在有向无环图中的上游节点和边即为集成电路的时钟分发网络，又称时钟树。
[0013] 对有向无环图进行扁平化，用CSR形式存储的邻接表表示图中的边关系。构建单CPU‑多GPU异构计算模型，具体操作为将可用GPU分为一个主GPU和剩余多个从属GPU，并将扁平化的有向无环图数据传送到主GPU。传送的扁平化的有向无环图数据包括每个节点的起始边索引、终止边索引、是否为寄存器时钟管脚的标记，以及每条边的目标节点、最小延迟、最大延迟信息。
[0014] B.电路结构分层预处理
[0015] 对扁平化的有向无环图，在主GPU上设计并行逆向拓扑排序算法，从出度为零的点出发，并行拓展并移除它们的入边，检查入边的源节点，将出度为零且不为寄存器时钟管脚的节点收集并作为下一次并行拓展的基础，重复此过程依次将电路结构中的组合逻辑进行分层，得到分层的部分有向无环图；剩余未分层的有向无环图节点从寄存器时钟管脚节点出发，并行拓展并移除节点的唯一入边，收集出度为零的源节点，重复此过程对时钟线网(时钟树)进行单独分层，得到分层的时钟树。将分层结果(包含由组合逻辑构成的分层的部分有向无环图，以及分层的时钟树)从主GPU广播到所有从属GPU。
[0016] C.多GPU并行候选路径生成
[0017] 进行多GPU任务分配，将分层的时钟树不同层次对应的计算任务均匀分配给所有GPU；在每个GPU上分别进行延迟分组初始化，并行延迟传播，并行渐进候选路径生成，获得每个GPU上的局部候选时序违例路径列表；最后在每个GPU上进行局部候选路径预合并，得到局部计算任务合并后对应的k条局部候选时序违例路径。此步骤包含的五个子步骤分别为多GPU任务分配，延迟分组初始化，并行延迟传播，并行渐进候选路径生成，并行局部候选路径预合并五个子步骤，分别在以下C1,C2,C3,C4,C5中具体介绍。
[0018] C1.多GPU任务分配
[0019] 设分层时钟树的每层编号分别为0～D‑1，共D个深度，设总GPU(含主GPU和从属GPU)个数为N，将D个深度的编号分为N份，每份包含约D/N个深度编号，代表一个GPU需要执行和提交的计算任务。
[0020] C2.延迟分组初始化
[0021] 每个GPU依次处理自己分配到的每个深度d。将分层时钟树中的所有节点按照深度d以下的子树进行分组，过程为：将分层时钟树第d+1层的节点所属分组设置为该节点自己的编号；从第d+2层开始，并行设置每个节点的组编号为其时钟树上父节点的组编号；然后处理第d+3层，直到最后一层，得到分层时钟树上每个节点的分组信息。进行基于分组约束的延迟初始化，根据时钟树边在分层时钟树上的深度，为其设置最小延迟或最大延迟，以预先消除公共路径悲观量。
[0022] C3.并行延迟传播
[0023] 在分层的部分有向无环图上逐层完成延迟信息的计算。对于每一层，使用GPU并行完成层内的延迟计算，每一个GPU线程枚举一个节点的入边，计算该节点的延迟信息，包括路径延迟极值、路径延迟第二极值以及对应的延迟来源时钟树节点的分组编号。
[0024] C4.并行渐进候选路径生成
[0025] 在每个GPU处，并行从时序分析的所有终点出发，通过延迟信息和分组约束向前查找延迟极值对应的入边，连接成一条路径，即为每个时序分析终点处时序违例最严重的路径。计算路径的松弛值(与时序违例的程度负相关)，对于建立时间传播，计算寄存器的最晚时间约束值，对于保持时间传播，计算寄存器的最早时间约束值，将约束值与路径延迟做差获得路径的松弛值。将所有时序分析终点处时序违例最严重的路径按照松弛值由小到大排序，排序使用GPU上的并行归并排序或基数排序算法。将排序以后的路径列表保留前k条路径并丢弃其余路径，得到第一层渐进候选路径。
[0026] 使用GPU并行拓展所有第一层渐进候选路径，每个GPU线程枚举一条路径上的所有节点的入边，通过入边扩展出新的路径，新的路径存放在预分配的数组空间中。所有新的路径构成的列表与第一层渐进候选路径合并后，按照松弛值由小到大排序，保留前k条路径并丢弃其余路径，得到第二层渐进候选路径，其中包含部分第一层渐进候选路径，以及部分由第一层渐进候选路径扩展出的新路径。再次使用GPU并行拓展第二层渐进候选路径，经过合并、排序、保留操作，获得第三层渐进候选路径，以此类推，直到路径扩展操作不能再扩展出新的路径则停止，得到的k条渐进候选路径即为深度为d的时序违例最严重的k条候选路径。
[0027] C5.并行局部候选路径预合并
[0028] 将每个GPU分配到的每个深度d计算出的k条候选路径合并后，按照松弛值由小到大排序，保留前k条路径并丢弃其余路径，作为每个GPU处的局部候选时序违例路径。这一合并、排序、保留的过程在所有GPU上独立并行完成。
[0029] D.全局候选路径合并
[0030] 从所有从属GPU传送k条局部候选时序违例路径到主GPU上，并在主GPU上进一步合并，排序并保留前k条时序违例最严重的路径，即为路径分析的结果。
[0031] 通过上述步骤，即可实现GPU加速计算的集成电路无悲观路径分析。
[0032] 与现有技术相比，本发明的有益效果在于：
[0033] 本发明通过算法和数据结构的等价变换，使用对GPU友好的计算模式完成无悲观路径分析。通过设计GPU上的延迟传播、路径生成、路径合并算法，提升了无悲观路径分析的并行程度。本发明能够调度多个GPU实现进一步的并行计算，并通过局部数据预合并的策略减少在GPU之间的数据传输开销。本发明完成无悲观路径分析的效率整体提升数十倍，节省了集成电路静态时序分析的计算成本，使之能够在芯片设计自动化流程中得到更大范围的应用。
附图说明
[0034] 图1为本发明提供的GPU加速计算的无悲观路径分析方法的流程框图。
[0035] 图2为本发明电路结构示例与电路结构分层预处理示意图；
[0036] 图中CK为芯片的时钟管脚，FF1为1号寄存器，FF2为2号寄存器，D为寄存器输入管脚，Q为寄存器输出管脚，Clk为寄存器时钟管脚，Part.A表示电路的时钟树，Part.B表示电路的组合逻辑构成的部分有向无环图；CTree.L1表示分层时钟树的第1层，以此类推；Logic.L1表示分层的部分有向无环图第1层，以此类推。
[0037] 图3为本发明候选路径生成过程的示意图；
[0038] 图中Path.0表示第一层渐进候选路径中当前正在处理的一条路径，D.1和D.2表示Path.0的两条新的入边，SD.1,SD.2表示Path.0通过D.2扩展出新的一条路径上的两条入边，PT表示具体实现中的路径搜索树。
[0039] 图4为本发明候选路径合并过程的示意图；
[0040] Op.Exp[1]表示对第一层渐进候选路径做扩展得到新的路径的过程；Op.Concat[1]标记表示将第一层渐进候选路径与新路径合并的过程；Op.SortPrune[1]标记表示将所有路径按照松弛值排序后保留前k条的过程。
具体实施方式
[0041] 下面结合附图，通过实施例，进一步阐述本发明。
[0042] 本发明提供一种GPU加速计算的集成电路无悲观路径分析方法，以学术界前沿的无悲观路径分析算法为基础，针对无悲观路径分析中的核心步骤创新性的引入了算法和数据结构的等价变换，使之适应GPU的计算模型和体系结构，进而能够在多个GPU上并行完成无悲观时序分析中的密集计算，降低了无悲观路径分析的计算成本，使之能够在芯片设计自动化流程中得到更大范围的应用。
[0043] 本发明处理无悲观路径分析的方法步骤如图1所示，图1中的实线箭头表示方法步骤的处理顺序关系。方法步骤包括电路结构扁平化，电路结构分层预处理，多GPU并行候选路径生成，全局候选路径合并。其中，多GPU并行候选路径生成步骤又可以细分为五个子步骤，包括多GPU任务分配，延迟分组初始化，并行延迟传播，并行渐进候选路径生成，并行局部候选路径预合并。
[0044] A.电路结构扁平化
[0045] 将集成电路的时钟线网表示为一个有向无环图，如图2左上所示为一个示例时序逻辑电路图，图2右上为其对应的有向无环图，其中节点表示电路的管脚和转折部分，边表示管脚之间的连接关系。每条边标记了信号传送的最小和最大延迟，单位可用ps表示，如10ps/15ps。图中有一个节点的子集带有特殊标记，它们对应着集成电路中的所有寄存器时钟管脚，如图2左上的FF1,FF2两个寄存器组件的Clk管脚，它们在有向无环图中的上游节点和边即为集成电路的时钟分发网络，又称时钟树，即图2左上和右上从时钟树根节点CK到两个Clk管脚的电路部分。
[0046] 对有向无环图进行扁平化，用CSR形式存储的邻接表表示图中的边关系。将可用GPU分为一个主GPU和剩余多个从属GPU，并将扁平化的有向无环图数据传送到主GPU。传送的数据包括每个节点i的起始边索引CSR_Edges_Start[i]、终止边索引CSR_Edges_Start[i+1]、是否为寄存器时钟管脚的标记Is_Clockpin[i]，以及每条边e的目标节点To[e]、最小延迟Delay[e].Min、最大延迟Delay[e].Max信息。
[0047] B.电路结构分层预处理
[0048] 对扁平化的有向无环图，在主GPU上设计并行逆向拓扑排序算法，从出度为零的点出发，并行拓展并移除它们的入边，检查入边的源节点，将出度为零且不为寄存器时钟管脚的节点收集并作为下一次并行拓展的基础，重复此过程依次将电路结构中的组合逻辑进行分层，得到分层的部分有向无环图；剩余未分层的有向无环图节点从寄存器时钟管脚节点出发，并行拓展并移除节点的唯一入边，收集出度为零的源节点，重复此过程对时钟线网进行单独分层，得到分层的时钟树。如图2右上，Part.A表示电路的时钟树，Part.B表示电路的组合逻辑构成的部分有向无环图。以上示例经过分层以后，得到图2下方的分层结果，其中粗虚线右侧为分层的部分有向无环图，分为三层，分别对应图中标记Logic.L1,Logic.L2,Logic.L3，分层结果的特征为：每一层内部没有时序边，所有时序边都从左侧的某层连接到右侧的某层。粗虚线左侧为分层的时钟树，分为两层，分别对应图中标记CTree.L1,CTree.L2，分层结果的特征为：每条边都从一层连接到相邻的下一层。将以上分层结果(包含由组合逻辑构成的分层的部分有向无环图，以及分层的时钟树)从主GPU广播到所有从属GPU。
[0049] C.多GPU并行候选路径生成
[0050] 进行多GPU任务分配，将时钟树深度对应的计算任务均匀分配给所有GPU；在每个GPU上分别进行延迟分组初始化，并行延迟传播，并行渐进候选路径生成，获得每个GPU上的局部候选时序违例路径列表；最后在每个GPU上进行局部候选路径预合并，得到局部计算任务合并后对应的k条局部候选时序违例路径。此步骤包含的五个子步骤分别为多GPU任务分配，延迟分组初始化，并行延迟传播，并行渐进候选路径生成，并行局部候选路径预合并五个子步骤。
[0051] C1.多GPU任务分配
[0052] 设分层时钟树的每层编号分别为0～D‑1，共D个深度，设总GPU(含主GPU和从属GPU)个数为N，将D个深度的编号分为N份，每份包含约D/N个深度编号，代表一个GPU需要执行和提交的计算任务。一种推荐实施方式为：对于编号为i的GPU，分配深度计算任务为d＝i,d＝i+N,d＝i+2N,…,d＝i+ceil((D‑i)/N)*N，其中ceil为向上取整函数。
[0053] C2.延迟分组初始化
[0054] 每个GPU依次处理自己分配到的每个深度d。将分层时钟树中的所有节点按照深度d以下的子树进行分组，过程为：将分层时钟树第d+1层的节点所属分组设置为该节点自己的编号；从第d+2层开始，并行设置每个节点的组编号为其时钟树上父节点的组编号；然后处理第d+3层，直到最后一层，得到分层时钟树上每个节点的分组信息。进行基于分组约束的延迟初始化，根据时钟树边在分层时钟树上的深度，为其设置最小延迟或最大延迟，以预先消除公共路径悲观量。此部分的伪代码可以表示为：
[0055]
[0056]
[0057] C3.并行延迟传播
[0058] 在分层的部分有向无环图上逐层完成延迟信息的计算。对于每一层，使用GPU并行完成层内的延迟计算，每一个GPU线程枚举一个节点的入边，计算该节点的延迟信息，包括路径延迟极值、路径延迟第二极值以及对应的延迟来源时钟树节点的分组编号。此部分的伪代码可以表示为：
[0059]
[0060] C4.并行渐进候选路径生成
[0061] 在每个GPU处，并行从时序分析的所有终点出发，通过延迟信息和分组约束向前查找延迟极值对应的入边，连接成一条路径，即为每个时序分析终点处时序违例最严重的路径。计算路径的松弛值(与时序违例的程度负相关)，对于建立时间传播，计算寄存器的最晚时间约束值，对于保持时间传播，计算寄存器的最早时间约束值，将约束值与路径延迟做差获得路径的松弛值。将所有时序分析终点处时序违例最严重的路径按照松弛值由小到大排序，排序使用GPU上的并行归并排序或基数排序算法。将排序以后的路径列表保留前k条路径并丢弃其余路径，得到第一层渐进候选路径。
[0062] 使用GPU并行拓展所有第一层渐进候选路径，每个GPU线程枚举一条路径上的所有节点的入边，通过入边扩展出新的路径，过程如图3所示，Path.0表示第一层渐进候选路径中当前正在处理的一条路径，D.1和D.2表示Path.0的两条新的入边，它们与各自左侧的虚线连接起来，即获得了新的路径，其中一条路径在将来还可以通过其上的入边SD.1,SD.2扩展出另外的两条新路径，但并不在此步骤中处理。所有新的路径存放在预分配的数组空间中。所有新的路径构成的列表与第一层渐进候选路径合并后，按照松弛值由小到大排序，保留前k条路径并丢弃其余路径，得到第二层渐进候选路径，其中包含部分第一层渐进候选路径，以及部分由第一层渐进候选路径扩展出的新路径，以上过程如图4所示，Op.Exp[1]标记表示对第一层渐进候选路径做扩展得到新的路径，存放在预分配的数组空间中；Op.Concat[1]标记表示将第一层渐进候选路径与新路径合并放置于内存中；Op.SortPrune[1]标记表示将所有路径按照松弛值排序后，保留到第k条路径为止(即图4中kth所示位置)，并丢弃其余路径(即图4中灰色遮住的路径)，得到的就是第二层渐进候选路径，其中Op.Exp[1],Op.Concat[1],Op.SortPrune[1]均在GPU上运行，Op.SortPrune[1]采用GPU上的并行归并排序或基数排序算法。再次使用GPU并行拓展第二层渐进候选路径，经过合并、排序、保留操作(分别对应图4中的Op.Exp[2],Op.Concat[2],Op.SortPrune[2])，获得第三层渐进候选路径，以此类推，直到路径扩展操作不能再扩展出新的路径则停止，得到的k条渐进候选路径即为深度为d的时序违例最严重的k条候选路径。
[0063] C5.并行局部候选路径预合并
[0064] 将每个GPU分配到的每个深度d计算出的k条候选路径合并后，按照松弛值由小到大排序，保留前k条路径并丢弃其余路径，作为每个GPU处的局部候选时序违例路径。这一合并、排序、保留操作的过程在所有GPU上独立并行完成，其过程参考图4所示的流程。
[0065] D.全局候选路径合并
[0066] 从所有从属GPU传送k条局部候选时序违例路径到主GPU上，并在主GPU上进一步合并，其过程与图4中描述的具体实现类似，排序并保留前k条时序违例最严重的路径，即为路径分析的结果。
[0067] 需要注意的是，公布实施例的目的在于帮助进一步理解本发明，但是本领域的技术人员可以理解：在不脱离本发明及所附权利要求的范围内，各种替换和修改都是可能的。因此，本发明不应局限于实施例所公开的内容，本发明要求保护的范围以权利要求书界定的范围为准。
