一种改善中转距离的方法及装置与流程

1.本技术涉及芯片设计领域，尤其涉及一种改善中转距离的方法及装置。


背景技术：

2.芯片在投产之前，可以使用fpga(field programmable gate array，现场可编程门阵列)原型验证系统对用户芯片设计进行逻辑验证。随着技术的快速发展，用户芯片设计的电路规模也越来越大，单颗fpga已无法容纳全部用户设计，所以必须把用户芯片设计分割为多个部分，将各个部分分配至不同的fpga上，由多个fpga组成原型验证系统，一起协同工作以达到验证用户芯片设计的目的。
3.在多个fpga组成的原型验证系统中，在对电路之间的连线(即net，可在网表中定义)进行路由之后，会发现某些连线借助了中间fpga的中转进行连接，中转所经过的中间fpga的个数即为中转距离。
4.发明人在实现本技术方案的过程中发现，当用户芯片设计被分为多个部分后，有些被切割开的电路之间的信号需要通过fpga之间的物理互连线进行跨fpga连接，而fpga之间的互连线长度相比于fpga内部电路连线的长度要大得多，所以fpga之间的互连线所产生的信号延迟也大得多，而对于中转连接来讲，由于路径中要跨过一个或更多个fpga，若信号的中转距离过长，则所带来的延时时间也就越长，最终影响系统的时序效果，因此可以说最大中转距离是影响系统工作频率的一个重要因素。
5.在工程实际中，分割完成后常常会出现很多中转距离过大的路径，严重影响了系统的工作频率，造成系统性能提升困难。在现有技术中，解决方案通常为重新进行分割，从而规避原有那些中转距离过大的路径。然而重新进行分割不但需要花费时间，而且分割后还有可能在其他地方又出现新的中转距离过长的路径。


技术实现要素：

6.本技术提供一种改善中转距离的方法及装置，以解决既不需要重新分割又可改善最大中转距离的问题。
7.根据本技术实施例的第一方面，提供一种改善中转距离的方法，用于由多个fpga组成的原型验证系统，该方法包括：
8.在分割结果中定位产生最大中转距离的线路；
9.根据该线路及该线路上的驱动节点和负载节点形成电路生成树，其中生成树以驱动节点为根节点s、以负载节点为叶子节点；
10.计算每个叶子节点的中转效率，选出中转效率最低的叶子节点d；
11.在叶子节点d和根节点s之间添加一条按照叶子节点d的最优路径进行连接的连线，并去除因添加连线而形成的环；
12.在分割结果中重复以上步骤，直至达到预设结束条件。
13.可选的，计算每个叶子节点的中转效率，包括：
14.获取叶子节点到根节点s的实际距离；
15.获取叶子节点到根节点s的最优距离；
16.将实际距离与最优距离的比值作为叶子节点的中转效率。
17.可选的，获取叶子节点到根节点s的实际距离，包括：
18.根据分割结果中的实际连接关系，获取叶子节点到根节点s实际所经过的fpga的数量，将该数量作为叶子节点到根节点s的实际距离。
19.可选的，获取叶子节点到根节点s的最优距离，包括：
20.根据分割结果中的实际连接关系建立地图g；
21.在地图g中，初始化每个叶子节点i到根节点s的距离distance(i,s)＝地图g中所有边的长度总和；
22.遍历g中的每一条边n：分别获取边n两端的节点va、vb到根节点s的距离distance(va,s)、distance(vb,s)，其中以distance(vb,s)为较大者；比较distance(va,s)+e(a,b)与distance(vb,s)的大小，其中e(a,b)为边n的长度，如果distance(va,s)+e(a,b)更小则更新distance(vb,s)的值为distance(va,s)+e(a,b)，并记录vb的前驱节点为va；
23.根据对前驱节点的记录获取每个叶子节点到根节点s的最优路径，再根据每个叶子节点到根节点s的最优路径获取每个叶子节点到根节点s的最优距离。
24.可选的，去除因添加连线而形成的环，包括：
25.计算环上的每个叶子节点在环的两个方向上的中转距离d_clockwise和d_anticlockwise；
26.确定节点c，其中节点c为环上绝对值|d_clockwise-d_anticlockwise|最大的节点；
27.在节点c的d_clockwise和d_anticlockwise中的较大者所对应的方向上删除节点c的邻居连线以去除环。
28.可选的，预设结束条件包括：
29.分割结果中的最大中转距离不能再下降，或者，重复的次数达到指定数量。
30.可选的，该方法还包括：
31.在每次修改分割结果后，计算修改后生成树的大小与最小生成树的比值，其中生成树的大小为该线路所经过的所有fpga的数量总和；
32.判断比值是否超过预设值α；
33.如果超过预设值，则触发预设操作。
34.根据本技术实施例的第二方面，提供一种改善中转距离的装置，用于由多个fpga组成的原型验证系统，该装置包括：
35.定位单元，用于在分割结果中定位产生最大中转距离的线路；
36.生成树单元，用于根据该线路及该线路上的驱动节点和负载节点形成电路生成树，其中生成树以驱动节点为根节点s、以负载节点为叶子节点；
37.中转效率计算单元，用于计算每个叶子节点的中转效率，选出中转效率最低的叶子节点d；
38.修改单元，用于在叶子节点d和根节点s之间添加一条按照叶子节点d的最优路径进行连接的连线，并去除因添加连线而形成的环；
39.控制单元，用于重复触发以上单元，直至达到预设结束条件。
40.可选的，中转效率计算单元在计算每个叶子节点的中转效率时，具体用于：
41.获取叶子节点到根节点s的实际距离；
42.获取叶子节点到根节点s的最优距离；
43.将实际距离与最优距离的比值作为叶子节点的中转效率。
44.可选的，中转效率计算单元在获取叶子节点到根节点s的实际距离时，具体用于：
45.根据分割结果中的实际连接关系，获取叶子节点到根节点s实际所经过的fpga的数量，将该数量作为叶子节点到根节点s的实际距离。
46.可选的，中转效率计算单元在获取叶子节点到根节点s的最优距离时，具体用于：
47.根据分割结果中的实际连接关系建立地图g；
48.在地图g中，初始化每个叶子节点i到根节点s的距离distance(i,s)＝地图g中所有边的长度总和；
49.遍历g中的每一条边n：分别获取边n两端的节点va、vb到根节点s的距离distance(va,s)、distance(vb,s)，其中以distance(vb,s)为较大者；比较distance(va,s)+e(a,b)与distance(vb,s)的大小，其中e(a,b)为边n的长度，如果distance(va,s)+e(a,b)更小则更新distance(vb,s)的值为distance(va,s)+e(a,b)，并记录vb的前驱节点为va；
50.根据对前驱节点的记录获取每个叶子节点到根节点s的最优路径，再根据每个叶子节点到根节点s的最优路径获取每个叶子节点到根节点s的最优距离。
51.可选的，修改单元在去除因添加连线而形成的环时，具体用于：
52.计算环上的每个叶子节点在环的两个方向上的中转距离d_clockwise和d_anticlockwise；
53.确定节点c，其中节点c为环上绝对值|d_clockwise-d_anticlockwise|最大的节点；
54.在节点c的d_clockwise和d_anticlockwise中的较大者所对应的方向上删除节点c的邻居连线以去除环。
55.可选的，预设结束条件包括：
56.分割结果中的最大中转距离不能再下降，或者，重复的次数达到指定数量。
57.可选的，该装置还包括：
58.检查单元，用于在每次修改分割结果后，计算修改后生成树的大小与最小生成树的比值，其中生成树的大小为该线路所经过的所有fpga的数量总和；判断比值是否超过预设值α；如果超过预设值，则触发预设操作。
59.本技术实施例提供的技术方案可以包括以下有益效果：
60.在本技术实施例中，先定位产生最大中转距离的线路，然后根据该线路及该线路上的驱动节点和负载节点形成电路生成树，再计算生成树每个叶子节点的中转效率，选出中转效率最低的叶子节点d，然后在叶子节点d和根节点s之间添加一条按照叶子节点d的最优路径进行连接的连线，并去除因添加连线而形成的环，从而完成一次对分割结果的修改。
61.本技术在分割结果的基础上对中转距离过大的线路进行了局部改善与调整，缩短其最大中转距离，从而提升了系统时序性能，相比于重新分割、布线的做法，本技术的方案不需要重新进行分割，可以更加快速的实施，节约了时间，而且还避免了因重新分割布线而
在其他地方又出现中转距离过长的问题。
62.应当理解的是，以上的一般描述和后文的细节描述仅是示例性和解释性的，并不能限制本技术。
附图说明
63.为了更清楚地说明本技术实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，对于本领域普通技术人员而言，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。此外，这些介绍并不构成对实施例的限定，附图中具有相同参考数字标号的元件表示为类似的元件，除非有特别申明，附图中的图不构成比例限制。
64.图1是中转原理示意图；
65.图2是本技术实施例提供的一种改善中转距离的方法的示意性流程图；
66.图3是本技术实施例中电路生成树示意图；
67.图4为本技术实施例中路径改善示意图；
68.图5是本技术实施例中去除因添加连线而形成的环的示意性流程图；
69.图6是本技术实施例中防止过多增加连线数量的示意性流程图；
70.图7是本技术实施例提供的一种改善中转距离的装置的示意图。
具体实施方式
71.下面将结合本技术实施例中的附图，对本技术实施例中的技术方案进行详细描述。当涉及附图时，除非另有说明，否则不同附图中的相同数字表示相同或相似的要素。显然，以下所描述的实施例仅仅是本技术的一部分实施例，而不是全部的实施例，或者说以下示例性实施例中所描述的实施方式并不代表与本技术相一致的所有实施方式。基于本技术中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本技术保护的范围。
72.当本技术实施例的说明书、权利要求书及上述附图中若出现术语“第一”、“第二”、“第三”等时，是用于区别不同对象，而不是用于限定特定顺序。在本技术实施例中，“示例性的”或者“例如”等词用于表示作例子、例证或说明。本技术实施例中被描述为“示例性的”或者“例如”等的任何实施例或设计方案不应被解释为比其它实施例或设计方案更优选或更具优势。确切而言，使用“示例性的”或者“例如”等词旨在以具体方式呈现相关概念。
73.为了便于理解，下面先对本技术实施例涉及的中转等概念进行介绍。
74.在原型验证系统中，当用户芯片设计被分割到多个fpga之后，通过对电路之间的连线(net)进行路由，可以发现某些连线借助了中间fpga的中转进行连接，这个中转路径的选择和调整即为本技术方案的重点内容。
75.图1是中转(hop)原理示意图。假设用户芯片设计中存在一局部电路连接关系，如图1的右侧所示，节点代表电路模块，连线代表电路线路，其中s节点为驱动节点，a、b、c为负载节点，也即s节点输出信号通过图中带箭头的net传递给a、b、c节点，此带箭头的连线即为超边，相比于图中普通的边，一条超边可以连接大于等于两个节点。假设该局部电路在分割后节点被分配至不同的fpga上，如图1中的左侧所示，可见并非任意两颗fpga都有直接互连
线相连，有些fpga之间有连接，而有些没有，由此形成的连接关系可以称之为连接关系约束，也叫互联约束。在互联约束下，从s节点出发的信号必须经过中间fpga的中转，路由到目标节点a、b、c上。故路由就是信号在互联约束的条件下从驱动节点到负载节点寻找路径的过程，也即中转的过程，而中转所经过的中间fpga的个数称为中转距离。
76.发明人在工程实际中发现，最大中转距离是一个影响系统工作频率的重要因素，如果信号中转距离过长，则所需要的延时时间也就越长，最终影响系统的时序效果。现有分割结果常常会出现很多中转距离过长的路由路径，造成系统性能提升困难。因此发明人希望能够找到一种方案，在分割结果的基础上改善、调整分割结果中的最大中转距离，而不需要重新进行分割，从而节约时间，另外还可以避免因重新分割而可能造成其他区域中又出现中转距离过长路径的问题。
77.图2是本技术实施例提供的一种改善中转距离的方法的示意性流程图。该方法可以用于由多个fpga组成的原型验证系统。
78.参考图2所示，该方法可以包括：
79.在步骤s201中，在分割结果中定位产生最大中转距离的线路。
80.在步骤s202中，根据该线路及该线路上的驱动节点和负载节点形成电路生成树，其中生成树以驱动节点为根节点s、以负载节点为叶子节点。
81.也即在分割结果中定位产生最大中转距离的net，作为示例可参考图3所示，图3是本技术实施例中电路生成树示意图，该net与net上的驱动节点和负载节点形成了电路生成树，该生成树以唯一一个驱动节点为根节点s，以负载节点为叶子节点(即图3中的a、b、c、d、e)。另外该图中虚化了组网结构，是为了表明图中有些fpga之间存在互连线连接，有些fpga之间不存在直接互连线，但可以通过其他fpga中转连接。原型验证系统中的fpga组成的图是连通图，即不存在孤立的fpga。图中的云朵代表中转经过的路径，云朵中的fpga的数量和连接方式支持中转，而无需规定具体结构和连接方式，以显示本实施例中的方法所具有的通用性。
82.在步骤s203中，计算每个叶子节点的中转效率，选出中转效率最低的叶子节点d。
83.因为本技术致力于改善中转距离，所以需要找到中转效率最低的叶子节点d，以此入手。而对于具体如何定义、计算叶子节点的中转效率，本实施例并不进行限制，本领域技术人员可以根据不同需求\不同场景而自行选择、设计，可以在此处使用的这些选择和设计都没有背离本技术的精神和保护范围。
84.在步骤s204中，在叶子节点d和根节点s之间添加一条按照叶子节点d的最优路径进行连接的连线，并去除因添加连线而形成的环。
85.该步骤s204即修改中转路径的步骤。以图3为例，易知叶子节点d到根节点s的最优路径显然应该是将d与s直接相连，可参考图4所示，图4为本技术实施例中路径改善示意图，与原net(即图3)相比，图4中在叶子节点d和根节点s之间添加了一条按照叶子节点d的最优路径进行连接的连线(即连线d-s)。
86.而由于增加了这条连线，此时电路生成树中新出现了一个环(即s-b-c-e-d-s)。需要去除因添加连线而形成的环。
87.作为示例，参考图5所示，在本实施例或本技术其他某些实施例中，去除因添加连线而形成的环，具体可以包括：
88.在步骤s501中，计算环上的每个叶子节点在环的两个方向上的中转距离d_clockwise和d_anticlockwise。
89.在步骤s502中，确定节点c，其中节点c为环上绝对值|d_clockwise-d_anticlockwise|最大的节点。
90.在步骤s503中，在节点c的d_clockwise和d_anticlockwise中的较大者所对应的方向上删除节点c的邻居连线以去除环。
91.仍以图4为例，遍历环上所有叶子节点b、c、e、d，计算其中每个叶子节点按照环的两个方向上(即顺时针方向、逆时针方向)的中转距离d_clockwise和d_anticlockwise，取绝对值|d_clockwise-d_anticlockwise|最大的节点，假设在图4中是节点c，则在其上述两个距离中最大的方向上删除邻居连线，如图4中连线b-c变为了虚线，即代表删除了连线b-c。
92.在步骤s205中，在分割结果中重复以上s201～s204步骤，直至达到预设结束条件。
93.经过步骤s201～步骤s204处理后，原先的分割结果被修改，即原先产生最大中转距离的net被修改，不再是最大中转距离，而原先产生次长中转距离的net就成为了产生最大中转距离的net，因此需要重复以上步骤s201～步骤s204，继续处理当前产生最大中转距离的net，循环下去直至达到预设结束条件。
94.对于预设结束条件，本实施例并不进行限制，本领域技术人员可以根据不同需求\不同场景而自行选择、设计，可以在此处使用的这些选择和设计都没有背离本技术的精神和保护范围。
95.作为示例，在本实施例或本技术其他某些实施例中，预设结束条件具体可以包括：
96.分割结果中的最大中转距离不能再下降，或者，重复的次数达到指定数量。
97.另外，作为进一步优化，在改善中转距离的过程中，最好不要使改善后的电路生成树的规模扩大很多，也即在每次修改路线的步骤(如步骤s204)后可以计算一下修改后生成树的大小与最小生成树的比值，该比值不能超过预设值α(α》1)。其中，生成树的大小即为net经过的所有fpga的数量总和，而最小生成树使用现有技术计算即可。
98.因此，参考图6所示，在本实施例或本技术其他某些实施例中，该方法还可以包括：
99.在步骤s601中，在每次修改分割结果后，计算修改后生成树的大小与最小生成树的比值，其中生成树的大小为该线路所经过的所有fpga的数量总和。
100.在步骤s602中，判断比值是否超过预设值α。
101.在步骤s603中，如果超过预设值，则触发预设操作。例如预设操作可以是发出警告等操作。
102.下面再对叶子节点的中转效率做进一步举例说明。
103.在本实施例或本技术其他某些实施例中，计算每个叶子节点的中转效率，具体可以包括：
104.获取叶子节点到根节点s的实际距离；
105.获取叶子节点到根节点s的最优距离；
106.将实际距离与最优距离的比值作为叶子节点的中转效率。
107.叶子节点的中转效率即route_efficiency，有：
108.route_efficiency＝real_distance/optimal_distance
109.其中，real_distance为叶子节点的实际距离，作为示例，获取叶子节点到根节点s的实际距离，具体可以包括：
110.根据分割结果中的实际连接关系，获取叶子节点到根节点s实际所经过的fpga的数量，将该数量作为叶子节点到根节点s的实际距离。
111.换句话说，叶子节点的实际距离就是叶子节点到根节点的按照net路径中间经过的实际fpga数量。以图3为例，假设a到b需要经过m颗fpga，b到s需要经过n颗fpga，加上b这一颗fpga，那么a的real_distance为m+n+1。
112.optimal_distance为叶子节点的最优距离，可以通过计算最优路径(即optimal_route_path)得到。
113.作为示例，在本实施例或本技术其他某些实施例中，获取叶子节点到根节点s的最优距离，具体可以包括：
114.根据分割结果中的实际连接关系建立地图g；
115.在地图g中，初始化每个叶子节点i到根节点s的距离distance(i,s)＝地图g中所有边的长度总和；
116.遍历g中的每一条边n：分别获取边n两端的节点va、vb到根节点s的距离distance(va,s)、distance(vb,s)，其中以distance(vb,s)为较大者；比较distance(va,s)+e(a,b)与distance(vb,s)的大小，其中e(a,b)为边n的长度，如果distance(va,s)+e(a,b)更小则更新distance(vb,s)的值为distance(va,s)+e(a,b)，并记录vb的前驱节点为va；
117.根据对前驱节点的记录获取每个叶子节点到根节点s的最优路径，再根据每个叶子节点到根节点s的最优路径获取每个叶子节点到根节点s的最优距离。
118.下面进一步进行说明：
119.1)按照分割后组网中fpga的连接关系建立地图g，fpga为节点，fpga之间的连线为边，叶子节点所在的fpga为目的节点，根节点s所在的fpga为起始节点s。假设地图g中一共有n个节点(v1,v2,v3
…
,vn)。
120.2)初始化每个节点i到起始节点s的距离distance(i,s)＝地图g中所有边的长度总和(i≠s)，其中s节点到它自己的距离初始化为0，即distance(s,s)＝0。
121.3)假设地图g中存在m条边，遍历g中的每一条边，也即以下步骤4)重复执行m次后进入步骤5)。
122.4)假设当前遍历的是边n，则获得该边n的两端节点，假设为va和vb，并获得此时的distance(va,s)和distance(vb,s)。比较distance(va,s)和distance(vb,s)的大小，不失一般性，假设较大者为distance(vb,s)。
123.比较distance(va,s)+e(a,b)与distance(vb,s)的大小，其中e(a,b)为边n的长度大小。如果distance(vb,s)更小，则结束本次步骤4)；如果distance(va,s)+e(a,b)更小，则更新distance(vb,s)的值为distance(va,s)+e(a,b)，并记录vb的前驱节点为va，结束本次步骤4)；如果出现等于的情况，则直接结束本次步骤4)。
124.5)此时步骤4)执行了m次，地图g中所有边被遍历了一遍，根据前驱节点的记录，可以逆向递归得知节点的前驱节点，前驱节点的前驱节点
…
，直到s节点，这样所有上述前驱节点及其连线组成了最优路径。这样便可以得到每个叶子节点到根节点s的最优路径，再根据每个叶子节点到根节点s的最优路径便可获得每个叶子节点到根节点s的最优距离。
125.在本实施例中，先定位产生最大中转距离的线路，然后根据该线路及该线路上的驱动节点和负载节点形成电路生成树，再计算生成树每个叶子节点的中转效率，选出中转效率最低的叶子节点d，然后在叶子节点d和根节点s之间添加一条按照叶子节点d的最优路径进行连接的连线，并去除因添加连线而形成的环，从而完成一次对分割结果的修改。本技术在分割结果的基础上对中转距离过大的线路进行了局部改善与调整，缩短其最大中转距离，从而提升了系统时序性能，相比于重新分割、布线的做法，本技术的方案不需要重新进行分割，可以更加快速的实施，节约了时间，而且还避免了因重新分割布线而在其他地方又出现中转距离过长的问题。
126.下述为本技术装置实施例，可以用于执行本技术方法实施例。对于本技术装置实施例中未披露的细节，请参照本技术方法实施例。
127.图7是本技术实施例提供的一种改善中转距离的装置的示意图。该装置可用于由多个fpga组成的原型验证系统。
128.参考图7所示，该装置可以包括：
129.定位单元701，用于在分割结果中定位产生最大中转距离的线路；
130.生成树单元702，用于根据该线路及该线路上的驱动节点和负载节点形成电路生成树，其中生成树以驱动节点为根节点s、以负载节点为叶子节点；
131.中转效率计算单元703，用于计算每个叶子节点的中转效率，选出中转效率最低的叶子节点d；
132.修改单元704，用于在叶子节点d和根节点s之间添加一条按照叶子节点d的最优路径进行连接的连线，并去除因添加连线而形成的环；
133.控制单元705，用于重复触发以上单元，直至达到预设结束条件。
134.作为示例，在本实施例或本技术其他某些实施例中，中转效率计算单元在计算每个叶子节点的中转效率时，具体用于：
135.获取叶子节点到根节点s的实际距离；
136.获取叶子节点到根节点s的最优距离；
137.将实际距离与最优距离的比值作为叶子节点的中转效率。
138.作为示例，在本实施例或本技术其他某些实施例中，中转效率计算单元在获取叶子节点到根节点s的实际距离时，具体用于：
139.根据分割结果中的实际连接关系，获取叶子节点到根节点s实际所经过的fpga的数量，将该数量作为叶子节点到根节点s的实际距离。
140.作为示例，在本实施例或本技术其他某些实施例中，中转效率计算单元在获取叶子节点到根节点s的最优距离时，具体用于：
141.根据分割结果中的实际连接关系建立地图g；
142.在地图g中，初始化每个叶子节点i到根节点s的距离distance(i,s)＝地图g中所有边的长度总和；
143.遍历g中的每一条边n：分别获取边n两端的节点va、vb到根节点s的距离distance(va,s)、distance(vb,s)，其中以distance(vb,s)为较大者；比较distance(va,s)+e(a,b)与distance(vb,s)的大小，其中e(a,b)为边n的长度，如果distance(va,s)+e(a,b)更小则更新distance(vb,s)的值为distance(va,s)+e(a,b)，并记录vb的前驱节点为va；
144.根据对前驱节点的记录获取每个叶子节点到根节点s的最优路径，再根据每个叶子节点到根节点s的最优路径获取每个叶子节点到根节点s的最优距离。
145.作为示例，在本实施例或本技术其他某些实施例中，修改单元在去除因添加连线而形成的环时，具体用于：
146.计算环上的每个叶子节点在环的两个方向上的中转距离d_clockwise和d_anticlockwise；
147.确定节点c，其中节点c为环上绝对值|d_clockwise-d_anticlockwise|最大的节点；
148.在节点c的d_clockwise和d_anticlockwise中的较大者所对应的方向上删除节点c的邻居连线以去除环。
149.作为示例，在本实施例或本技术其他某些实施例中，预设结束条件包括：
150.分割结果中的最大中转距离不能再下降，或者，重复的次数达到指定数量。
151.作为示例，在本实施例或本技术其他某些实施例中，该装置还可以包括：
152.检查单元，用于在每次修改分割结果后，计算修改后生成树的大小与最小生成树的比值，其中生成树的大小为该线路所经过的所有fpga的数量总和；判断比值是否超过预设值α；如果超过预设值，则触发预设操作。
153.关于上述实施例中的装置，其中各个单元\模块执行操作的具体方式已经在相关方法的实施例中进行了详细描述，此处不再赘述。在本技术中，上述单元\模块的名字对单元\模块本身不构成限定，在实际实现中，这些单元\模块可以以其他名称出现，只要各个单元\模块的功能和本技术类似，皆属于本技术权利要求及其等同技术的范围之内。
154.在本实施例中，先定位产生最大中转距离的线路，然后根据该线路及该线路上的驱动节点和负载节点形成电路生成树，再计算生成树每个叶子节点的中转效率，选出中转效率最低的叶子节点d，然后在叶子节点d和根节点s之间添加一条按照叶子节点d的最优路径进行连接的连线，并去除因添加连线而形成的环，从而完成一次对分割结果的修改。本技术在分割结果的基础上对中转距离过大的线路进行了局部改善与调整，缩短其最大中转距离，从而提升了系统时序性能，相比于重新分割、布线的做法，本技术的方案不需要重新进行分割，可以更加快速的实施，节约了时间，而且还避免了因重新分割布线而在其他地方又出现中转距离过长的问题。
155.以上所述，仅是本技术的较佳实施例而已，并非对本技术作任何形式上的限制，虽然本技术已以较佳实施例揭露如上，然而并非用以限定本技术，任何熟悉本专业的技术人员，在不脱离本技术技术方案范围内，当可利用上述揭示的技术内容做出些许更动或修饰为等同变化的等效实施例，但凡是未脱离本技术技术方案内容，依据本技术技术方案的技术实质，在本技术技术方案的精神和原则之内，对以上实施例所作的任何简单的修改、等同替换与改进等，均仍属于本技术技术方案的保护范围之内。
156.本领域技术人员在考虑说明书及实践这里公开的方案后，将容易想到本技术的其它实施方案。本技术旨在涵盖本技术的任何变型、用途或者适应性变化，这些变型、用途或者适应性变化遵循本技术的一般性原理并包括本技术未公开的本技术领域中的公知常识或惯用技术手段。说明书和实施例仅被视为示例性的，本技术的真正范围和精神由所附的权利要求指出。
157.应当理解的是，本技术并不局限于上面已经描述并在附图中示出的精确结构，并且可以在不脱离其范围进行各种修改和改变。本技术的范围仅由所附的权利要求来限制。

技术特征：
1.一种改善中转距离的方法，其特征在于，所述方法用于由多个fpga组成的原型验证系统，所述方法包括：在分割结果中定位产生最大中转距离的线路；根据所述线路及所述线路上的驱动节点和负载节点形成电路生成树，其中所述生成树以驱动节点为根节点s、以负载节点为叶子节点；计算每个叶子节点的中转效率，选出中转效率最低的叶子节点d；在所述叶子节点d和根节点s之间添加一条按照所述叶子节点d的最优路径进行连接的连线，并去除因添加所述连线而形成的环；在所述分割结果中重复以上步骤，直至达到预设结束条件。2.根据权利要求1所述的方法，其特征在于，计算每个叶子节点的中转效率，包括：获取叶子节点到根节点s的实际距离；获取叶子节点到根节点s的最优距离；将所述实际距离与所述最优距离的比值作为叶子节点的中转效率。3.根据权利要求2所述的方法，其特征在于，获取叶子节点到根节点s的实际距离，包括：根据所述分割结果中的实际连接关系，获取叶子节点到根节点s实际所经过的fpga的数量，将所述数量作为叶子节点到根节点s的实际距离。4.根据权利要求2所述的方法，其特征在于，获取叶子节点到根节点s的最优距离，包括：根据所述分割结果中的实际连接关系建立地图g；在所述地图g中，初始化每个叶子节点i到根节点s的距离distance(i,s)＝地图g中所有边的长度总和；遍历g中的每一条边n：分别获取边n两端的节点va、vb到根节点s的距离distance(va,s)、distance(vb,s)，其中以distance(vb,s)为较大者；比较distance(va,s)+e(a,b)与distance(vb,s)的大小，其中e(a,b)为边n的长度，如果distance(va,s)+e(a,b)更小则更新distance(vb,s)的值为distance(va,s)+e(a,b)，并记录vb的前驱节点为va；根据对前驱节点的记录获取每个叶子节点到根节点s的最优路径，再根据每个叶子节点到根节点s的最优路径获取每个叶子节点到根节点s的最优距离。5.根据权利要求1所述的方法，其特征在于，去除因添加所述连线而形成的环，包括：计算所述环上的每个叶子节点在环的两个方向上的中转距离d_clockwise和d_anticlockwise；确定节点c，其中节点c为所述环上绝对值|d_clockwise-d_anticlockwise|最大的节点；在所述节点c的d_clockwise和d_anticlockwise中的较大者所对应的方向上删除所述节点c的邻居连线以去除所述环。6.根据权利要求1所述的方法，其特征在于，所述预设结束条件包括：所述分割结果中的最大中转距离不能再下降，或者，重复的次数达到指定数量。7.根据权利要求1所述的方法，其特征在于，所述方法还包括：在每次修改分割结果后，计算修改后生成树的大小与最小生成树的比值，其中所述生
成树的大小为所述线路所经过的所有fpga的数量总和；判断所述比值是否超过预设值α；如果超过所述预设值，则触发预设操作。8.一种改善中转距离的装置，其特征在于，所述装置用于由多个fpga组成的原型验证系统，所述装置包括：定位单元，用于在分割结果中定位产生最大中转距离的线路；生成树单元，用于根据所述线路及所述线路上的驱动节点和负载节点形成电路生成树，其中所述生成树以驱动节点为根节点s、以负载节点为叶子节点；中转效率计算单元，用于计算每个叶子节点的中转效率，选出中转效率最低的叶子节点d；修改单元，用于在所述叶子节点d和根节点s之间添加一条按照所述叶子节点d的最优路径进行连接的连线，并去除因添加所述连线而形成的环；控制单元，用于重复触发以上单元，直至达到预设结束条件。9.根据权利要求8所述的装置，其特征在于，所述中转效率计算单元在计算每个叶子节点的中转效率时，具体用于：获取叶子节点到根节点s的实际距离；获取叶子节点到根节点s的最优距离；将所述实际距离与所述最优距离的比值作为叶子节点的中转效率。10.根据权利要求9所述的装置，其特征在于，所述中转效率计算单元在获取叶子节点到根节点s的实际距离时，具体用于：根据所述分割结果中的实际连接关系，获取叶子节点到根节点s实际所经过的fpga的数量，将所述数量作为叶子节点到根节点s的实际距离。11.根据权利要求9所述的装置，其特征在于，所述中转效率计算单元在获取叶子节点到根节点s的最优距离时，具体用于：根据所述分割结果中的实际连接关系建立地图g；在所述地图g中，初始化每个叶子节点i到根节点s的距离distance(i,s)＝地图g中所有边的长度总和；遍历g中的每一条边n：分别获取边n两端的节点va、vb到根节点s的距离distance(va,s)、distance(vb,s)，其中以distance(vb,s)为较大者；比较distance(va,s)+e(a,b)与distance(vb,s)的大小，其中e(a,b)为边n的长度，如果distance(va,s)+e(a,b)更小则更新distance(vb,s)的值为distance(va,s)+e(a,b)，并记录vb的前驱节点为va；根据对前驱节点的记录获取每个叶子节点到根节点s的最优路径，再根据每个叶子节点到根节点s的最优路径获取每个叶子节点到根节点s的最优距离。12.根据权利要求8所述的装置，其特征在于，所述修改单元在去除因添加所述连线而形成的环时，具体用于：计算所述环上的每个叶子节点在环的两个方向上的中转距离d_clockwise和d_anticlockwise；确定节点c，其中节点c为所述环上绝对值|d_clockwise-d_anticlockwise|最大的节点；
在所述节点c的d_clockwise和d_anticlockwise中的较大者所对应的方向上删除所述节点c的邻居连线以去除所述环。13.根据权利要求8所述的装置，其特征在于，所述预设结束条件包括：所述分割结果中的最大中转距离不能再下降，或者，重复的次数达到指定数量。14.根据权利要求8所述的装置，其特征在于，所述装置还包括：检查单元，用于在每次修改分割结果后，计算修改后生成树的大小与最小生成树的比值，其中所述生成树的大小为所述线路所经过的所有fpga的数量总和；判断所述比值是否超过预设值α；如果超过所述预设值，则触发预设操作。

技术总结
本申请实施例提供了一种改善中转距离的方法及装置，先定位产生最大中转距离的线路，然后根据该线路及该线路上的驱动节点和负载节点形成电路生成树，再计算生成树的每个叶子节点的中转效率，选出中转效率最低的叶子节点d，然后在叶子节点d和根节点s之间添加一条按照叶子节点d的最优路径进行连接的连线，并去除因添加该连线而形成的环，从而完成一次对分割结果的修改。本申请在分割结果基础上对中转距离过大的线路进行了局部改善与调整，缩短其最大中转距离，从而提升了系统时序性能。本申请方案不需要重新进行分割，节约了时间，而且还避免了因重新分割布线而在其他地方可能又会出现中转距离过长的问题。会出现中转距离过长的问题。会出现中转距离过长的问题。


技术研发人员：邵中尉 张吉锋 万鹭 肖慧
受保护的技术使用者：上海思尔芯技术股份有限公司
技术研发日：2023.06.13
技术公布日：2023/9/9