一种布线和TDM比率快速优化方法

摘要

本发明涉及一种布线和TDM比率快速优化方法，包括：基于M个线网组中引脚的数量，利用第一预设算法或者第二预设算法对FPGA图的所有线网进行布线，得到系统级布线结果，第一预设算法包括DK布线算法和快速MTST算法，第二预设算法包括DK布线算法和基于Dijkstra的布线算法，DK布线算法为基于扩展的Dijkstra和Kruskal的算法，每个线网组包括N条线网；基于系统级布线结果，给每个布线信号分配TDM比率，以使最大线网组的TDM比率最小，得到最终的优化结果，且最终的优化结果满足TDM比率约束。本发明提出的多策略系统级布线方法和TDM比率优化方法能够提高布线和优化效率。

权利要求

1.一种布线和TDM比率快速优化方法，其特征在于，所述布线和TDM比率快速优化方法包括：步骤1、基于M个线网组中引脚的数量，利用第一预设算法或者第二预设算法对FPGA图的所有线网进行布线，得到系统级布线结果，其中，所述第一预设算法包括DK布线算法和快速MTST算法，所述第二预设算法包括DK布线算法和基于Dijkstra的布线算法，所述DK布线算法为基于扩展的Dijkstra和Kruskal的算法，每个线网组包括N条线网，M、N为大于零的自然数；

步骤2、基于所述系统级布线结果，给每个布线信号分配TDM比率，以使最大线网组的TDM比率最小，得到最终的优化结果，且所述最终的优化结果满足TDM比率约束，所述TDM比率约束为最终的TDM比率为偶数和每个通道的TDM使用量小于通道容量；

所述步骤1包括：

判断线网组的引脚数量是否大于其他线网组的引脚数量的预设倍数，若存在一个或者多个线网组的引脚数量大于其他线网组的引脚数量的预设倍数，则将这种线网组作为关键线网组，将其他线网组作为非关键线网组，并利用DK布线算法对所述关键线网组的所有线网进行布线，利用快速MTST算法对所述非关键线网组的所有线网进行布线，得到系统级布线结果，若不存在线网组的引脚数量大于其他线网组的引脚数量的预设倍数，则利用DK布线算法对引脚数量大于预设值的线网进行布线，利用基于Dijkstra的布线算法对引脚数量小于或者等于预设值的线网进行布线，得到系统级布线结果；

所述步骤2包括：

步骤2.1、基于所述系统级布线结果，为所述布线信号分配第一TDM比率，其中，同一通道的布线信号分配相同的第一TDM比率，所述第一TDM比率为通道上的布线信号数量；

步骤2.2、基于所述第一TDM比率，给所述布线信号重新分配第二TDM比率；

步骤2.3、迭代调整所述布线信号的第二TDM比率，直至达到预设条件，得到第一优化结果；

步骤2.4、计算每个通道TDM使用量的余量，所述余量为通道容量与该通道的TDM使用量的差值；

步骤2.5、基于所述第一优化结果，选取通道上处于最大TDM比率的线网组且TDM比率最大的布线信号，根据余量计算该布线信号的TDM比率减少量，并将该布线信号的TDM比率减少该TDM比率减少量，得到该布线信号的最终TDM比率，从而得到作为最终优化结果的第二优化结果，最终TDM比率为整数且为偶数。

2.根据权利要求1所述的布线和TDM比率快速优化方法，其特征在于，所述利用DK布线算法对所述关键线网组的所有线网进行布线，包括：S1.11、利用所述扩展的Dijkstra算法对所述关键线网组的所有线网的所有引脚进行处理，以得到第一最短路径终端森林；

S1.12、提取所述第一最短路径终端森林的所有引脚，形成仅包括所有引脚的第一子图，所述第一子图中的节点为引脚，边为桥边，所述边的权重为所述最短路径终端森林中连接两引脚的边的权重之和；

S1.13、使用所述Kruskal算法处理所述第一子图生成第一最小生成树；

S1.14、将所述第一最小生成树的边展开为最短路径，并去除重复的边，得到所述关键线网组的系统级布线结果。

3.根据权利要求2所述的布线和TDM比率快速优化方法，其特征在于，所述S1.11包括：S1.111、将所述关键线网组的所有线网的所有引脚都作为第一源节点，同时从每个所述第一源节点出发，每次访问距离最近且未被访问过的节点；

S1.112、将所述S1.111访问到的节点加入第一终端树，所述第一终端树的根节点为距离最近的第一源节点；

S1.113、重复所述S1.112，直至所有节点都被遍历过后，完成第一最短路径终端森林的构建，所述第一最短路径终端森林包括所有的第一终端树。

4.根据权利要求1所述的布线和TDM比率快速优化方法，其特征在于，所述利用快速MTST算法对所述非关键线网组的所有线网进行布线，包括：S1.21、将所述非关键线网组的所有线网随机生成若干批次，每个所述批次使用Floyd算法得到FPGA图中每两个FPGA之间的最短路径；

S1.22、基于所述S1.21得到的最短路径构建完全图，其中，所述完全图的节点为线网的引脚，所述完全图的边的权重为最短路径上所有FPGA之间边的权重之和；

S1.23、根据所述完全图生成第二最小生成树；

S1.24、将所述第二最小生成树的边展开为最短路径，并去除重复的边，得到所述非关键线网组的系统级布线结果。

5.根据权利要求1所述的布线和TDM比率快速优化方法，其特征在于，所述利用DK布线算法对引脚数量大于预设值的线网进行布线，包括：S1.31、利用所述扩展的Dijkstra算法对所述引脚数量大于所述预设值的线网的所有引脚进行处理，以得到第二最短路径终端森林；

S1.32、提取所述第二最短路径终端森林的所有引脚，形成仅包括所有引脚的第二子图，所述第二子图中的节点为引脚，边为桥边，所述边的权重为所述第二最短路径终端森林中连接两引脚的边的权重之和；

S1.33、使用所述Kruskal算法处理所述第二子图生成第三最小生成树；

S1.34、将所述第三最小生成树的边展开为最短路径，并去除重复的边，得到所述引脚数量大于所述预设值的线网的系统级布线结果。

6.根据权利要求1所述的布线和TDM比率快速优化方法，其特征在于，所述利用基于Dijkstra的布线算法对引脚数量小于或者等于预设值的线网进行布线，包括：S1.41、获取所述引脚数量小于或者等于所述预设值的线网的所有引脚组成的引脚集；

S1.42、从所述引脚集中随机选取一引脚作为第三源节点，从所述第三源节点出发，使用所述Dijkstra算法寻找到未连接的路径最短的引脚，并进行连接，将所找到的引脚也作为所述第三源节点，若所找到的最短路径中存在非引脚节点，则将最短路径上的所有非引脚节点也当做源节点，并将所找到的引脚从所述引脚集中删除，将最短路径对应的边加入边集；

S1.43、从当前所有的所述第三源节点同时出发，使用所述Dijkstra算法寻找到未连接的路径最短的引脚，并进行连接，将所找到的引脚也作为所述第三源节点，若所找到的最短路径中存在非引脚节点，则将最短路径上的所有非引脚节点也当做源节点，并将所找到的引脚从所述引脚集中删除，将最短路径对应的边加入所述边集；

S1.44、重复所述S1.43，直至所述引脚集中的所有引脚全部删除，得到作为系统级布线结果的最终的边集。

7.根据权利要求1所述的布线和TDM比率快速优化方法，其特征在于，所述步骤2.2包括：步骤2.21、根据所述线网组中所有线网的布线信号的第一TDM比率得到所述线网组的TDM比率；

步骤2.22、选取所述布线信号所处线网组的TDM比率的最大值作为所述布线信号的关键度；

步骤2.23、为所述布线信号重新分配第二TDM比率，所述第二TDM比率为通道上所有布线信号的总关键度和当前布线信号的关键度的比值，所述总关键度为同一通道上所有布线信号的关键度之和。

8.根据权利要求1所述的布线和TDM比率快速优化方法，其特征在于，所述步骤2.3包括：步骤2.31、为每个所述布线信号设置一调整比例，所述调整比例为调整目标值与所述布线信号所在线网组的TDM比率的比值；

步骤2.32、将每个通道的所述布线信号的第二TDM比率调整为第三TDM比率，所述第三TDM比率为所述布线信号的第二TDM比率与所述调整比例的乘积；

步骤2.33、计算每个通道的TDM使用量，若所述通道的TDM使用量大于1，则将该通道的所有所述布线信号的第三TDM比率调整为第四TDM比率，此时，所述第四TDM比率为第三TDM比率的u倍，u为通道的TDM使用量，否则直接将第三TDM比率作为第四TDM比率；

步骤2.34、重复步骤2.31‑步骤2.33，直至达到所述预设条件，得到所述第一优化结果。

说明书

一种布线和TDM比率快速优化方法

技术领域

[0001] 本发明属于集成电路技术领域，涉及一种布线和TDM比率快速优化方法。

背景技术

[0002] FPGA(Field Programmable Gate Array)即现场可编程门列阵。基于多FPGA系统的硬件仿真和原型验证具有容量大，运行速度快等优点，被广泛用于大型电路设计的验证。对于大规模电路设计，需要进行划分，映射到多个FPGA。划分完成后，会出现许多需要在FPGA之间通信的信号。由于硬件结构的限制，并不是所有的FPGA之间都能直接进行互联通信。因此需要根据实际的硬件互联拓扑规划信号的通信路径，即系统级布线。各子电路之间的互联数远远超过了实际FPGA物理连线数量。为了解决互联问题，通常采用TDM(Time‑Division Multiplexing，时分复用技术)技术。TDM技术允许多个信号通过同一个I/O端口在两个FPGA之间通信。TDM比率为需要通信的信号数和通道容量的比值。TDM技术虽然解决了I/O端口数少的问题，但却给系统性能带来了负面影响，降低了设计的整体频率。因此，需要给每个信号安排合适的复用通道，即TDM比率，使得总体系统性能最优。

[0003] 现有方案使用一种斯坦纳树近似算法进行初始系统级布线，随后进行拆线重布线进一步提升解的质量；在进行TDM比率分配时，先将TDM比率松弛为非负实数，使用拉格朗日松弛方法求出最优解，然后将结果合法化，并使用一种快速有效的改善算法进一步提升质量。还有其他方案是将系统级布线问题转化为斯坦纳树问题，并对边采用线性增长的方式进行加权；在TDM比率分配阶段，首先将给布线信号平均分配TDM比率，得到初始解，然后提出一种重分配技术，有效解决线网组之间的TDM比率不平衡问题，同时满足TDM比率约束，最后，设计一种比率感知技术得到更小的目标值。

[0004] 但是，现有方法解决系统级布线问题时，采用单一的方法进行布线，在线网数量多，线网组分布复杂时效率低。在进行TDM比率分配时，采用基于拉格朗日松弛的方法会消耗过多的运行时间，而其他TDM比率优化方法依然有提升空间。总之，目前的方法在综合运行时间和结果质量的总体表现上可以进一步提升。

发明内容

[0005] 为了解决现有技术中存在的上述问题，本发明提供了一种布线和TDM比率快速优化方法。本发明要解决的技术问题通过以下技术方案实现：

[0006] 本发明实施例提供了一种布线和TDM比率快速优化方法，所述布线和TDM比率快速优化方法包括：

[0007] 步骤1、基于M个线网组中引脚的数量，利用第一预设算法或者第二预设算法对FPGA图的所有线网进行布线，得到系统级布线结果，其中，所述第一预设算法包括DK布线算法和快速MTST算法，所述第二预设算法包括DK布线算法和基于Dijkstra的布线算法，所述DK布线算法为基于扩展的Dijkstra和Kruskal的算法，每个线网组包括N条线网，M、N为大于零的自然数；

[0008] 步骤2、基于所述系统级布线结果，给每个布线信号分配TDM比率，以使最大线网组的TDM比率最小，得到最终的优化结果，且所述最终的优化结果满足TDM比率约束，所述TDM比率约束为最终的TDM比率为偶数和每个通道的TDM使用量小于通道容量。

[0009] 在本发明的一个实施例中，所述步骤1包括：

[0010] 判断线网组的引脚数量是否大于其他线网组的引脚数量的预设倍数，若存在一个或者多个线网组的引脚数量大于其他线网组的引脚数量的预设倍数，则将这种线网组作为关键线网组，将其他线网组作为非关键线网组，并利用DK布线算法对所述关键线网组的所有线网进行布线，利用快速MTST算法对所述非关键线网组的所有线网进行布线，得到系统级布线结果，若不存在线网组的引脚数量大于其他线网组的引脚数量的预设倍数，则利用DK布线算法对引脚数量大于预设值的线网进行布线，利用基于Dijkstra的布线算法对引脚数量小于或者等于预设值的线网进行布线，得到系统级布线结果。

[0011] 在本发明的一个实施例中，所述利用DK布线算法对所述关键线网组的所有线网进行布线，包括：

[0012] S1.11、利用所述扩展的Dijkstra算法对所述关键线网组的所有线网的所有引脚进行处理，以得到第一最短路径终端森林；

[0013] S1.12、提取所述第一最短路径终端森林的所有引脚，形成仅包括所有引脚的第一子图，所述第一子图中的节点为引脚，边为桥边，所述边的权重为所述最短路径终端森林中连接两引脚的边的权重之和；

[0014] S1.13、使用所述Kruskal算法处理所述第一子图生成第一最小生成树；

[0015] S1.14、将所述第一最小生成树的边展开为最短路径，并去除重复的边，得到所述关键线网组的系统级布线结果。

[0016] 在本发明的一个实施例中，所述S1.11包括：

[0017] S1.111、将所述关键线网组的所有线网的所有引脚都作为第一源节点，同时从每个所述第一源节点出发，每次访问距离最近且未被访问过的节点；

[0018] S1.112、将所述S1.111访问到的节点加入第一终端树，所述第一终端树的根节点为距离最近的第一源节点；

[0019] S1.113、重复所述S1.112，直至所有节点都被遍历过后，完成第一最短路径终端森林的构建，所述第一最短路径终端森林包括所有的第一终端树。

[0020] 在本发明的一个实施例中，所述利用快速MTST算法对所述非关键线网组的所有线网进行布线，包括：

[0021] S1.21、将所述非关键线网组的所有线网随机生成若干批次，每个所述批次使用Floyd算法得到所述FPGA图中每两个FPGA之间的最短路径；

[0022] S1.22、基于所述S1.21得到的最短路径构建完全图，其中，所述完全图的节点为线网的引脚，所述完全图的边的权重为最短路径上所有FPGA之间边的权重之和；

[0023] S1.23、根据所述完全图生成第二最小生成树；

[0024] S1.24、将所述第二最小生成树的边展开为最短路径，并去除重复的边，得到所述非关键线网组的系统级布线结果。

[0025] 在本发明的一个实施例中，所述利用DK布线算法对引脚数量大于预设值的线网进行布线，包括：

[0026] S1.31、利用所述扩展的Dijkstra算法对所述引脚数量大于所述预设值的线网的所有引脚进行处理，以得到第二最短路径终端森林；

[0027] S1.32、提取所述第二最短路径终端森林的所有引脚，形成仅包括所有引脚的第二子图，所述第二子图中的节点为引脚，边为桥边，所述边的权重为所述第二最短路径终端森林中连接两引脚的边的权重之和；

[0028] S1.33、使用所述Kruskal算法处理所述第二子图生成第三最小生成树；

[0029] S1.34、将所述第三最小生成树的边展开为最短路径，并去除重复的边，得到所述引脚数量大于所述预设值的线网的系统级布线结果。

[0030] 在本发明的一个实施例中，所述利用基于Dijkstra的布线算法对引脚数量小于或者等于预设值的线网进行布线，包括：

[0031] S1.41、获取所述引脚数量小于或者等于所述预设值的线网的所有引脚组成的引脚集；

[0032] S1.42、从所述引脚集中随机选取一引脚作为第三源节点，从所述第三源节点出发，使用所述Dijkstra算法寻找到未连接的路径最短的引脚，并进行连接，将所找到的引脚也作为所述第三源节点，若所找到的最短路径中存在非引脚节点，则将最短路径上的所有非引脚节点也当做源节点，并将所找到的引脚从所述引脚集中删除，将最短路径对应的边加入边集；

[0033] S1.43、从当前所有的所述第三源节点同时出发，使用所述Dijkstra算法寻找到未连接的路径最短的引脚，并进行连接，将所找到的引脚也作为所述第三源节点，若所找到的最短路径中存在非引脚节点，则将最短路径上的所有非引脚节点也当做源节点，并将所找到的引脚从所述引脚集中删除，将最短路径对应的边加入所述边集，其中，非引脚节点为FPGA图中除引脚节点之外的其他节点；

[0034] S1.44、重复所述S1.43，直至所述引脚集中的所有引脚全部删除，得到作为系统级布线结果的最终的边集。

[0035] 在本发明的一个实施例中，所述步骤2包括：

[0036] 步骤2.1、基于所述系统级布线结果，为所述布线信号分配第一TDM比率，其中，同一通道的布线信号分配相同的第一TDM比率，所述第一TDM比率为通道上的布线信号数量；

[0037] 步骤2.2、基于所述第一TDM比率，给所述布线信号重新分配第二TDM比率；

[0038] 步骤2.3、迭代调整所述布线信号的第二TDM比率，直至达到预设条件，得到第一优化结果；

[0039] 步骤2.4、计算每个通道TDM使用量的余量，所述余量为通道容量与该通道的TDM使用量的差值；

[0040] 步骤2.5、基于所述第一优化结果，选取通道上处于最大TDM比率的线网组且TDM比率最大的布线信号，根据余量计算该布线信号的TDM比率减少量，并将该布线信号的TDM比率减少该TDM比率减少量，得到该布线信号的最终TDM比率，从而得到作为最终优化结果的第二优化结果，最终TDM比率为整数且为偶数。

[0041] 在本发明的一个实施例中，所述步骤2.2包括：

[0042] 步骤2.21、根据所述线网组中所有线网的布线信号的第一TDM比率得到所述线网组的TDM比率；

[0043] 步骤2.22、选取所述布线信号所处线网组的TDM比率的最大值作为所述布线信号的关键度；

[0044] 步骤2.23、为所述布线信号重新分配第二TDM比率，所述第二TDM比率为通道上所有布线信号的总关键度和当前布线信号的关键度的比值，所述总关键度为同一通道上所有布线信号的关键度之和。

[0045] 在本发明的一个实施例中，所述步骤2.3包括：

[0046] 步骤2.31、为每个所述布线信号设置一调整比例，所述调整比例为调整目标值与所述布线信号所在线网组的TDM比率的比值；

[0047] 步骤2.32、将每个通道的所述布线信号的第二TDM比率调整为第三TDM比率，所述第三TDM比率为所述布线信号的第二TDM比率与所述调整比例的乘积；

[0048] 步骤2.33、计算每个通道的TDM使用量，若所述通道的TDM使用量大于1，则将该通道的所有所述布线信号的第三TDM比率调整为第四TDM比率，此时，所述第四TDM比率为第三TDM比率的u倍，u为通道的TDM使用量，否则直接将第三TDM比率作为第四TDM比率；

[0049] 步骤2.34、重复步骤2.31‑步骤2.33，直至达到所述预设条件，得到所述第一优化结果。

[0050] 与现有技术相比，本发明的有益效果：

[0051] 本发明提出的多策略系统级布线方法能够根据实际的情况选择不同的布线方法进行布线，相比于现有的布线方法具有更高的效率，并且由于针对不同的情况选用了不同的布线方法，能够快速得到高质量布线结果。

[0052] 本发明提出的TDM比率优化方法基于多策略系统级布线方法进行优化，相比于现有的优化方法具有更快的速度，能够在较短时间内完成优化。

[0053] 通过以下参考附图的详细说明，本发明的其它方面和特征变得明显。但是应当知道，该附图仅仅为解释的目的设计，而不是作为本发明的范围的限定，这是因为其应当参考附加的权利要求。还应当知道，除非另外指出，不必要依比例绘制附图，它们仅仅力图概念地说明此处描述的结构和流程。

附图说明

[0054] 图1为本发明实施例提供的一种系统级布线示意图；

[0055] 图2为本发明实施例提供的一种TDM比率优化示意图；

[0056] 图3为本发明实施例提供的一种布线和TDM比率快速优化方法的流程示意图；

[0057] 图4为本发明实施例提供的一种布线和TDM比率快速优化方法的框架图；

[0058] 图5为本发明实施例提供的一种多策略布线算法决策树的流程图；

[0059] 图6为本发明实施例提供的一种DK布线算法的示意图；

[0060] 图7为本发明实施例提供的一种基于Dijkstra的布线算法的示意图；

[0061] 图8为本发明实施例提供的一种TDM使用量余量的示意图。

具体实施方式

[0062] 下面结合具体实施例对本发明做进一步详细的描述，但本发明的实施方式不限于此。

[0063] 实施例一

[0064] 本发明中用无向有权图G(V,E)表示多FPGA系统，顶点集V表示FPGA的集合，边集E表示所有FPGA之间的连接。每个FPGA对之间的连接被称为FPGA边或者通道，图G(V,E)也被称为FPGA图。在FPGA图中，每条边带有权重，代表互联资源的容量。

[0065] 划分完成后，会出现大量需要在FPGA之间通信的信号，系统级布线就是根据多FPGA系统的硬件互联拓扑，规划信号的走线，使得系统性能最佳。系统级布线示意图如图1所示。在系统级布线问题中，划分阶段超图中被切割的超边转化为线网，超边跨越的每个FPGA被称为线网的引脚。线网组是多条线网的集合，可看做时序关键路径，本发明不对线网组中具体的线网进行限定，本领域人员可以根据不同的使用需要划分哪些线网加入一个线网组中。一条线网可以属于多个线网组。值得注意的是，由于TDM技术的引进，FPGA之间通信的信号数可以克服I/O端口数量的限制，即可以大于通道的容量。

[0066] 系统级布线完成后，线网在FPGA边上的跨越被称为布线信号。对于一条FPGA边，上面会有许多布线信号需要通信，通过TDM比率优化，可进一步提升系统性能。给每个信号赋予不同的TDM比率，意味着选择了不同延时的通道。TDM比率优化示意图如图2所示。信号的TDM比率越小则延时越小，然而不能给所有的信号分配最小的TDM比率，因为这违反了互联容量限制约束。布线信号的TDM使用量为其TDM比率的倒数。FPGA边的TDM使用量为其上所有布线信号的TDM使用量之和。对于每个FPGA边，其使用量不能超过1(将互联容量设定为1)，同时因为硬件实现的原因，TDM比率必须为偶数。线网的TDM比率为其所有布线信号的TDM比率之和。线网组的TDM比率为其组内所有线网的TDM比率之和。最大线网组TDM比率为所有线网组TDM比率的最大值。

[0067] 请参见图3，图3为本发明实施例提供的一种布线和TDM比率快速优化方法的流程示意图，基于上述内容，本发明实施例提供一种布线和TDM比率快速优化方法，该布线和TDM比率快速优化方法对划分后出现在FPGA之间的布线信号进行系统级布线，接着为布线信号分配TDM比率，使得总体性能最优。虽然总体上是两步走的策略，但在进行系统级布线时，也会前瞻性地为后续的TDM比率优化步骤考虑。该布线和TDM比率快速优化方法包括步骤1‑步骤2，其中：

[0068] 步骤1、基于M个线网组中引脚的数量，利用第一预设算法或者第二预设算法对FPGA图的所有线网进行布线，得到系统级布线结果，其中，第一预设算法包括DK布线算法和快速MTST(最小终端生成树)算法，第二预设算法包括DK布线算法和基于Dijkstra(迪克斯特拉算法)的布线算法，DK布线算法为基于扩展的Dijkstra和Kruskal(克鲁斯卡尔算法)的算法，每个线网组包括N条线网，M、N为大于零的自然数。

[0069] 具体地，本实施例对于不同的线网组中引脚的数量使用不同的布线方法，提出了一种多策略布线算法，该算法包含三种各具特点的布线算法(即DK布线算法、基于Dijkstra的布线算法、快速MTST算法)，对不同的场景采用不同的布线方法，在运行速度较快的同时保持较高的质量，其中， DK布线算法在极端情况下的表现：当FPGA图中的节点都为线网的引脚时，FPGA图即为子图，无需构建SPTF，DK布线算法退化为Kruskal算法；在引脚数很少，比如两个时，没有必要去构建SPTF，直接搜索两点之间的最短路径就能解决问题。经过分析发现DK布线算法适合步引脚较多的线网。基于Dijkstra的布线算法在极端情况下的表现：随着线网引脚数的增加，基于Dijkstra的布线算法效率逐渐恶化，当引脚等于FPGA图节点数时，时间复杂度变为 ；当线网的引脚数较少时显然算法效率更高，比如引脚数为
2时，基于Dijkstra的布线算法退化为原始的Dijkstra算法。所以与DK布线算法的特点相反，基于Dijkstra的布线算法在对引脚数较少的线网进行布线时效率较高。快速MTST布线算法相较于原始的斯坦纳问题近似算法，减少了最短路径的更新次数，使得时间复杂度为
 ( 为节点数)的Floyd算法的时间耗费分摊到了多个线网。每个批次的线网数量越多，更新最短路径的频率就越小，速度越快，然而布线质量略有下降。所以适合对不太重要的线网进行快速布线。

[0070] 在本实施例中，请参见图5，步骤1包括：

[0071] 判断线网组的引脚数量是否大于其他线网组的引脚数量的预设倍数，若存在一个或者多个线网组的引脚数量大于其他线网组的引脚数量的预设倍数，则将这种线网组作为关键线网组，将其他线网组作为非关键线网组，并利用DK布线算法对关键线网组的所有线网进行布线，利用快速MTST算法对非关键线网组的所有线网进行布线，得到系统级布线结果，若不存在线网组的引脚数量大于其他线网组的引脚数量的预设倍数，则利用DK布线算法对引脚数量大于预设值的线网进行布线，利用基于Dijkstra的布线算法对引脚数量小于或者等于预设值的线网进行布线，得到系统级布线结果。预设倍数例如为60倍，预设值为FPGA数量的一半，本发明对预设倍数和预设值不做具体限定，本领域技术人员可以根据实际需求进行设定。

[0072] 具体地，本实施例将输入分为两种情况。一种情况是存在一个或者多个线网组，其包含的引脚数远大于其他线网组(如60倍)，这种线网组被称为关键线网组，里面的线网使用DK布线算法进行布线。对于非关键线网组里的线网，使用快速MTST算法完成布线。输入的另一种情况是，所有线网组包含的引脚总数规模相当，对于引脚数较多(大于FPGA数目一半)的线网采用DK布线算法，其他的线网使用基于Dijkstra的布线算法。

[0073] 在一个具体实施例中，利用DK布线算法对所述关键线网组的所有线网进行布线，包括S1.11‑ S1.14：

[0074] S1.11、利用扩展的Dijkstra算法对关键线网组的所有线网的所有引脚进行处理，以得到第一最短路径终端森林。

[0075] 其中，最短路径终端森林由多棵终端树和桥边组成。终端树的根节点为线网的引脚，树上的叶子节点到其根节点的距离比到其他树上根节点的距离近。若某条边连接两棵不同终端树上的节点，则称该条边为桥边。

[0076] 在本实施例中，步骤S1.11包括：

[0077] S1.111、将关键线网组的所有线网的所有引脚都作为第一源节点，同时从每个第一源节点出发，每次访问距离最近且未被访问过的节点。

[0078] S1.112、将步骤S1.111访问到的节点加入第一终端树，第一终端树的根节点为距离最近的第一源节点。

[0079] S1.113、重复步骤S1.112，直至所有节点都被遍历过后，完成第一最短路径终端森林的构建，第一最短路径终端森林包括所有的第一终端树。

[0080] S1.12、提取第一最短路径终端森林的所有引脚，形成仅包括所有引脚的第一子图，第一子图中的节点为引脚，边为桥边，边的权重为最短路径终端森林中连接两引脚的边的权重之和。

[0081] S1.13、使用Kruskal算法处理第一子图生成第一最小生成树。

[0082] S1.14、将第一最小生成树的边展开为最短路径，并去除重复的边，得到关键线网组的系统级布线结果。

[0083] 例如，请参见图6，图中所有的节点和带权重的边构成FPGA图 。假设线网的引脚集 。从线网的所有引脚节点出发，使用扩展的Dijkstra算法构建SPTF(最短路径终端森林)，如图6 (a) 所示，分别为 。
桥边集合为 。注意到边 并不是
桥边，因为节点 和 处在同一棵终端树上。接着构建新的子图，如图6 (b) 所示，节点为线网引脚集合，边的权重为两点最短路径的权重和。接着使用Kruskal算法求解子图的最小生成树，结果如图6(c) 所示。然后将最小生成树的边转化为最短路径，如图6 (d) 所示。边展开的最短路径为 ；边 展开的最短路径为 ；边
展开的最短路径为 。注意到，展开为最短路径后，边 会被计算两次，所
以有必要去除重复的边，得到的边的集合即为该条线网的布线结果。因此，综合上述分析可知，最终的布线结果为： 。

[0084] 在一个具体实施例中，利用快速MTST算法对非关键线网组的所有线网进行布线，包括：

[0085] S1.21、将非关键线网组的所有线网随机生成若干批次，每个批次使用Floyd算法得到FPGA图中每两个FPGA之间的最短路径。

[0086] S1.22、基于S1.21得到的最短路径构建完全图，其中，完全图的节点为线网的引脚，完全图的边的权重为最短路径上所有FPGA之间边的权重之和。

[0087] S1.23、根据完全图生成第二最小生成树，第二最小生成树的生成方法可以采用Prim算法或者Kruskal算法。

[0088] S1.24、将第二最小生成树的边展开为最短路径，并去除重复的边，得到非关键线网组的系统级布线结果。

[0089] 在一个具体实施例中，利用DK布线算法对引脚数量大于预设值的线网进行布线，包括：

[0090] S1.31、利用扩展的Dijkstra算法对引脚数量大于预设值的线网的所有引脚进行处理，以得到第二最短路径终端森林。

[0091] 在本实施例中，步骤S1.31包括：

[0092] S1.311、将引脚数量大于预设值的线网的所有引脚都作为第二源节点，同时从每个第二源节点出发，每次访问距离最近且未被访问过的节点。

[0093] S1.312、将步骤S1.311访问到的节点加入第二终端树，第二终端树的根节点为距离最近的第二源节点。

[0094] S1.313、重复步骤S1.312，直至所有节点都被遍历过后，完成第二最短路径终端森林的构建，第二最短路径终端森林包括所有的第二终端树。

[0095] S1.32、提取第二最短路径终端森林的所有引脚，形成仅包括所有引脚的第二子图，第二子图中的节点为引脚，边为桥边，边的权重为第二最短路径终端森林中连接两引脚的边的权重之和。

[0096] S1.33、使用Kruskal算法处理第二子图生成第三最小生成树。

[0097] S1.34、将第三最小生成树的边展开为最短路径，并去除重复的边，得到引脚数量大于预设值的线网的系统级布线结果。

[0098] 在一个具体实施例中，利用基于Dijkstra的布线算法对引脚数量小于或者等于预设值的线网进行布线，包括：

[0099] 在一个具体实施例中，利用基于Dijkstra的布线算法对引脚数量小于或者等于预设值的线网进行布线，包括：

[0100] S1.41、获取引脚数量小于或者等于预设值的线网的所有引脚组成的引脚集；

[0101] S1.42、从引脚集中随机选取一引脚作为第三源节点，从第三源节点出发，使用Dijkstra算法寻找到未连接的路径最短的引脚，并进行连接，将所找到的引脚也作为第三源节点，若所找到的最短路径中存在非引脚节点，则将最短路径上的所有非引脚节点也当做源节点，并将所找到的引脚从引脚集中删除，将最短路径对应的边加入边集，非引脚节点为除引脚节点外的节点；

[0102] S1.43、从当前所有的第三源节点同时出发，使用Dijkstra算法寻找到未连接的路径最短的引脚，并进行连接，将所找到的引脚也作为第三源节点，若所找到的最短路径中存在非引脚节点，则将最短路径上的所有非引脚节点也当做源节点，并将所找到的引脚从引脚集中删除，将最短路径对应的边加入边集；

[0103] S1.44、重复步骤S1.43，直至引脚集中的所有引脚全部删除，得到作为系统级布线结果的最终的边集。

[0104] 例如，请参见图7，图7中所有的节点和带权重的边构成FPGA图 ，线网的引脚集 。如图7(a) 所示 ，将引脚节点 设置为源节点 ，数组，初始化数组 为 ，将源节点
从引脚集中去除， ，边集 为空集。从源节点出发进行搜索，找到距离最近的引脚节点 ，如图7(b)所示，此时数组 ，数组
，将节点 从引脚集 中去除， ，从数组 回
溯最短路径得到边 并插入边集 ，将节点 设为新的源节点，数组
，初始化数组 。继续搜索找到节点 ，如图7(c)所示，此时数组
，数组 ，将节点 从引脚集 中去
除， ，从数组 回溯最短路径得到边集 并插入边集 ，将
节点 设为新的源节点，数组 ，初始化数组 。继续搜索找
到节点 ，如图7(d)所示，此时数组 ，数组
，从数组 回溯最短路径得到边集 并插
入边集 ，将节点 从引脚集 中去除，引脚集 为空集，线网布线完成，此时结果为。

[0105] 步骤2、基于所述系统级布线结果，给每个布线信号分配TDM比率，以使最大线网组的TDM比率最小，得到最终的优化结果，且所述最终的优化结果满足TDM比率约束，所述TDM比率约束为最终的TDM比率为偶数和每个通道的TDM使用量小于通道容量。

[0106] 具体地，系统级布线完成后，需要给每个布线信号分配TDM比率，使最大线网组的TDM比率最小，同时满足TDM比率约束。

[0107] 在一个具体实施例中，步骤2具体可以包括步骤2.1‑步骤2.5，其中：

[0108] 步骤2.1、基于系统级布线结果，为布线信号分配第一TDM比率，其中，同一通道的布线信号分配相同的第一TDM比率，第一TDM比率为通道上的布线信号数量。

[0109] 步骤2.2、基于第一TDM比率，给布线信号重新分配第三TDM比率。

[0110] 在本实施例中，步骤2.2具体可以包括步骤2.2‑步骤2.23，其中：

[0111] 步骤2.21、根据线网组中所有线网的布线信号的第一TDM比率得到线网组的TDM比率。

[0112] 具体地，线网 的TDM比率 为其所有布线信号的TDM比率之和，即：

[0113]

[0114] 其中，为第i个布线信号的TDM比率。

[0115] 线网组 的TDM比率为其组内所有线网的TDM比率之和，即：

[0116]

[0117] 其中，为线网组 的TDM比率。

[0118] 步骤2.22、选取布线信号所处线网组的TDM比率的最大值作为布线信号的关键度，即选取布线信号所处的所有线网组中最大的TDM比率作为布线信号的关键度。

[0119] 步骤2.23、为布线信号重新分配第二TDM比率，第二TDM比率为通道上所有布线信号的总关键度和当前布线信号的关键度的比值，总关键度为同一通道上所有布线信号的关键度之和。

[0120] 步骤2.3、迭代调整布线信号的第二TDM比率，直至达到预设条件，得到第一优化结果。预设条件例如可以为改善很小或者结果变坏，例如当提升小于千分之一时则说明改善很小，当最大线网组TDM比率变大则说明结果变坏，此时则可以停止迭代。

[0121] 在本实施例中，步骤2.3具体可以包括步骤2.2‑步骤2.23，其中：

[0122] 步骤2.31、为每个布线信号设置一调整比例，调整比例为调整目标值与布线信号所在线网组的TDM比率的比值。

[0123] 具体的，首先会设置一个调整目标值 指导TDM比率调节，理想情况下所有线网组的TDM比率会向这个目标靠近。该调整目标值 小于最大线网组TDM比率 ，而且会随着迭代次数 变化，变化关系为：

[0124]

[0125] 其中， 为参数， 跟 的数量级成正比。最大线网组TDM比率 为所有线网组TDM比率的最大值。

[0126] 步骤2.32、将每个通道的布线信号的第二TDM比率调整为第三TDM比率，所述第三TDM比率为布线信号的第二TDM比率与调整比例的乘积。

[0127] 步骤2.33、计算每个通道的TDM使用量，若通道的TDM使用量大于1，则将该通道的所有布线信号的第三TDM比率调整为第四TDM比率，此时，所述第四TDM比率为第三TDM比率的u倍，即进行合法化，u为通道的TDM使用量，否则直接将所述第三TDM比率作为第四TDM比率。

[0128] 步骤2.34、重复步骤2.31‑步骤2.33，直至达到预设条件，得到第一优化结果。

[0129] 本实施例通过迭代调整信号TDM比率，优化最大线网组TDM比率。通过减小总TDM比率较大的线网组内信号的TDM比率，减小最大线网组TDM比率；增大其他线网组内信号的TDM比率使得结果满足TDM比率约束。多次迭代调整信号比率，直到没有优化空间或优化的余地很小。调整过程中，如果结果违反约束需要进行合法化。

[0130] 步骤2.4、计算每个通道TDM使用量的余量，余量为通道容量与该通道的TDM使用量的差值。

[0131] 步骤2.5、基于第一优化结果，选取通道上处于最大TDM比率的线网组且TDM比率最大的布线信号，根据余量计算该布线信号的TDM比率减少量，并将该布线信号的TDM比率减少该TDM比率减少量，得到该布线信号的最终TDM比率，从而得到作为最终优化结果的第二优化结果，最终TDM比率为整数且为偶数。其中，当减少TDM比率减少量的TDM比率为非整数时，则进行向上取整处理，当所得到的TDM比率为奇数时，则将TDM比率值加1。

[0132] 具体地，经过迭代改善后，解的质量有所提升。然而上一阶段中一些保守的策略使得某些通道的TDM使用量小于1，结果还有提升的空间，同时TDM比率的完全合法化也需要得到保障。合法化时，当TDM比率为奇数时，需要将数值增大为偶数，以及对TDM比率向上取整的操作，使得TDM使用量存在余量。如果充分利用这个余量，TDM比率将会进一步减小。图8展示了利用TDM使用量余量的过程。如图8(a)所示，假设信号的TDM比率为奇数，都为5。如图8(b)所示，需要对其进行合法化，为了满足偶数的约束，同时保证TDM使用量不超过1，可以将TDM比率自动加1，此时TDM使用量为0.833，即存在0.167的余量。如图8(c)所示，将布线信号1的TDM比率从6降为4，新的TDM使用量为0.916。可以看出，通过利用余量，提高了TDM使用量，使TDM比率降低，从而使优化目标得到进一步改善。

[0133] 其中，TDM使用量的余量 是通道容量与当前TDM使用量 的差值。若利用该余量，可使某个信号的TDM使用量增加，这意味着TDM比率的降低，关系式为：

[0134]

[0135] 其中，可以表示为：

[0136]

[0137] 其中，为TDM比率 的减少量。

[0138] 本实施例使用后改善算法充分利用改善空间，进一步优化结果，同时确保结果满足TDM比率约束。经过迭代改善后，解的质量有所提升。然而上一阶段中一些保守的策略使得某些通道的TDM使用率小于1，结果还有提升的空间，同时TDM比率的完全合法化也需要得到保障。合法化时，当比率为奇数时将数值增大为偶数，以及对TDM比率向上取整的操作，使得TDM使用量存在余量。如果充分利用这个余量，TDM比率将会进一步减小。

[0139] 本发明提出的多策略系统级布线方法能够根据实际的情况选择不同的布线方法进行布线，相比于现有的布线方法具有更高的效率，并且由于针对不同的情况选用了不同的不限方法，能够快速得到高质量布线结果。

[0140] 本发明提出的TDM比率优化方法基于多策略系统级布线方法进行优化，相比于现有的优化方法具有更快的速度，能够在较短时间内完成优化。

[0141] 在发明的描述中，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者更多个该特征。在本发明的描述中，“多个”的含义是两个或两个以上，除非另有明确具体的限定。

[0142] 在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特征数据点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特征数据点可以在任何的一个或多个实施例或示例中以合适的方式结合。此外，本领域的技术人员可以将本说明书中描述的不同实施例或示例进行接合和组合。

[0143] 以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换，都应当视为属于本发明的保护范围。