摘要

技术摘要（来自于incoPat）

分类号

专利历程

其他著录项

权利要求

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，直至达到所述预设条件，得到所述第一优化结果。