文摘
作为一个最重要的复杂的网络路由问题在超大规模集成电路(VLSI),总线路由已成为更具挑战性当目睹先进技术节点进入深纳米时代,因为所有的总线位需要相同的路由路由拓扑中。特别是,非均匀路由跟踪配置和障碍带来最大的困难保持相同的所有总线拓扑位。在本文中,我们首先提出一个跟踪处理非均匀路由跟踪技术统一配置与障碍。然后,我们制定topology-aware单总线路由作为unsplittable流问题(UFP),这是集成到一个negotiation-based全球路由确定所需的路由区域为每个公共汽车。topology-aware跟踪的任务是提出将轨道分配给每一段公交车的指导下全球路由的结果。最后,详细的提出了路由方案每个总线连接的部分。我们评估我们的路由结果与基准套件2018 CAD的比赛。与前三的最先进的方法相比,实验结果表明,我们的算法达到最好的总分在指定的时间限制。
1。介绍
随着先进技术的节点进入深纳米时代,路由变得更加具有挑战性,因为大规模的增长巨大的规模超大规模集成电路(VLSI) (1]。之间的路由问题,总线路由吸引大多数研究兴趣和遇到了新的挑战:(1)所有部分在每个总线必须与相同的路由拓扑路由;(2)非均匀和复杂的路由跟踪配置;(3)我们需要处理的障碍。特别是约束根据所有属于同一总线位必须遵循同样的路由拓扑路由使前面的路由器不适用当前topology-matching总线路由。
之前的总线路由主要关注印刷电路板(PCB)设计。例如,田和渡边2)被认为是总线delay-matching约束的路由,以满足一些时间规范。燕和黄3和Zhang et al。4]length-matching总线处理路由的电线长度相同的总线上的所有网在指定范围内。然而,这些作品被认为是维持相同的约束所有部分在同一总线拓扑。因此,需要开发一个有效和高效topology-matching总线路由算法。
根据以前的标准,位在总线被认为具有相同的拓扑如果满足以下四个条件:(1)所有位具有相同数量的电线。(2)所有电线追踪层位有相同的所有测序。(3)所有电线追踪从所有位路线朝着同一个方向。(4)在每个段(一个段是一组连接不同的相同的比特序列当追踪从一组销形状),不同位的电线保持相同或相反的顺序,顺序从针形状。
图1(一)演示了一个总线进行成功具有相同的拓扑结构。假设我们开始跟踪的电线销左边的形状,如这个图所示,所有电线追踪所有位都有相同的方向(向右,向下,向右、职责)和同一层测序(L1、L2和L1)。此外,在所有领域(seg1、seg2 seg3),不同位的电线保持相同的顺序或倒序针形状的顺序。
(一)
(b)
路由跟踪旨在帮助路由器符合各种设计要求和帮助掩盖着色,在先进的技术是必不可少的节点(5]。每个路由跟踪都有宽度限制,只有线宽度不允许有大于约束路由在跑道上。自不同的路由要求公共汽车可能不同(例如,不同的线宽度和不同线间距),路由跟踪配置可能不均匀。例如,图1 (b)显示5个跟踪可分为两种类型(蓝色和绿色,resp)基于宽度约束。蓝色的痕迹有更大的宽度约束和覆盖整个设计从下到上,而绿色轨道宽度约束较小,只有封面设计的一部分。特别是,路由跟踪可以相互重叠,分布不均匀。这种非均匀路由跟踪配置对总线路由构成巨大的挑战。
障碍等电路元件和电力通过使总线路由更具挑战性。由于这些障碍是分散在某些层,是不可能找到连续可路由区域如果总线位不允许他们中的一些人之间的路线。
由于高路由的复杂性问题,路由过程通常分为全球路由跟踪任务,和详细的路由。在全球路由、路由区域分为粗粒度的网格细胞(称为g-cells),和粗糙的路由区域确定为每个网络通过g-cells之间的连接。接下来,跟踪任务分配路由追踪iroutes从全球路由中提取结果。最后,详细的路由发现每个网络连接的路径iroute和固定针并完成最终的路由。
在本文中,我们提出一个有效的算法来解决topology-matching总线路由问题考虑障碍和非均匀跟踪配置。我们工作的主要贡献总结如下:(我)跟踪处理技术提出了统一的非均匀路由跟踪配置的障碍。(2)我们制定topology-aware单总线路由作为unsplittable流问题(UFP),这是集成到一个negotiation-based全球路由确定所需的路由区域为每个公共汽车。(3)全球路由结果的指导下,topology-aware跟踪的任务是提出将跟踪分配给每一段的巴士,大大减少了维护的难度相同的路由拓扑在随后的步骤。(iv)详细路由方案提出了考虑为所有总线位路由拓扑连接每个总线的片段。(v)实验结果表明,我们建议的总线路由算法是有效的。与CAD的前三队比赛在总线上Obstacle-Aware赛道ICCAD路由5),我们的算法可以达到最好的总分在指定的时间内。
本文的其余部分组织如下。部分2首先介绍了总线路由优先指标,然后给出了问题的陈述。第三节细节我们的巴士路由算法。第四节提供了实验结果。最后,结论是第五节。
2。预赛
在本节中,我们首先介绍了总线路由选择度量考虑在2018 CAD比赛ICCAD [5),然后制定topology-matching总线路由问题。
2.1。总线路由选择度量
成功路由的巴士,导线长度等指标,段的数量,每一段的宽度和间距的侵犯是用来测量总线路由质量在比赛中(5]。我们详细介绍这四个指标如下。
2.1.1。线的长度
线长度是一个基本的路由质量的指标。长导线长度通常意味着更大的延迟和更大的能源消耗6];因此路由器将减少线的长度。总线的电线长度计算,总结了钢丝长度的位,并采取迂回将导致线长度的增加。
2.1.2。段数
因为每层都有一个优先路由方向(水平或垂直),使用段表明,更多的通过。然而,通过不良是由于他们的负面影响信号完整性,延迟,路由区,制造业产量(6]。因此,理想的总线路由器应该段的数量最小化。
2.1.3。段的宽度
如果一段的方向是水平的,那么段的宽度的定义 - - - - - -最上面的线的坐标减去 - - - - - -协调最下的线的部分;相反,如果一个线段的方向是垂直的,之间的计算 - - - - - -协调的最右边的和最左边的线5]。段的宽度越小,相应的公共汽车更紧凑。
2.1.4。间距违反
每一层有一个间隔约束指定之间应保持的最小距离的路由路径,设计边界,障碍,和其他路由连接层。间距违反将导致额外的惩罚的评价分数。
图2公交优先路由度量显示了一个示例,图2(一个)了下路由的结果有更长的线长度、大量的段,段和一个更大的宽度,而图2 (b)提供所需的解决方案,因为它的导线长度和数量的片段被最小化,段的宽度也小。
(一)
(b)
2.2。问题陈述
我们给出如下:(1)设计路由层 。每一层有一个路由方向和间隔约束。路由方向是垂直或水平,间距约束指定的最小距离应保持输出路由路径和设计之间的边界,障碍,和其他路由连接层。(2)一套路由追踪 。每个跟踪是由一条线在一层宽度约束 。每个轨道的方向总是一样的路由方向层轨道,和宽度约束要求只有电线宽度小于或等于宽度约束可以路由在跑道上。(3)一组障碍 ,这是分散在特定的层。(4)一套公共汽车 。每个总线由位,所有位都有销形状和宽度约束( )表明总线的路由路径在层宽度等于宽度约束。
topology-matching总线路由的目的是为了实现尽可能多的成功路由巴士,和下面的指标也应同时最小化:(1)总导线长度的公交车;(2)段的数量;(3)每个总线(即的紧密性。段的宽度);(4)违反间距的数量。
总线是路由成功如果满足以下三个硬约束:(1)路由路径的每一点一点连接的所有销形状和不重叠与其他的路径。(2)赛道上的电线都是在不违反铁轨的宽度约束和障碍不重叠。(3)所有相同的比特路由拓扑。
3所示。我们的算法
我们的算法的总体流程总结在图3,主要包括四个部分:(1)预处理,全球路由(2),(3)跟踪任务,和(4)详细路由。
预处理阶段结合非均匀路由跟踪配置支持高效的查询与障碍,简化后续路由操作。在全球路由阶段,我们制定topology-aware单总线路由UFP和集成到一个negotiation-based全球路由确定所需的路由区域为每个公共汽车。可以减少后续步骤的复杂性限制搜索空间的区域被全球路由阶段。全球路由的指导下结果,跟踪任务阶段分配跟踪每一段公交车,大大减少了维护的难度相同的路由拓扑在随后的步骤。最后,详细路由阶段每个总线的连接段,获得最终的路由的结果。我们将细节下面这四个主要部分。
3.1。预处理
在本节中,我们对输入数据执行一些预处理来简化后续路由操作。自非均匀路由跟踪配置和障碍使总线路由更加复杂,我们首先提出一个跟踪处理技术统一跟踪配置,同时考虑障碍。具体地说,我们对待每一个路由跟踪均匀覆盖整个设计从上到下(或从左到右),并且每个跟踪有一组间隔记录的子轨迹。此外,如果两个轨道的中心线重合,我们将减少或删除的使用间隔宽度较小的跟踪。
图4显示了三个非均匀路由追踪和一个障碍。在图中,我们把这三个轨道覆盖整个设计从上到下,和跟踪 , ,和间隔使用的套吗 , ,和 ,分别。的时间间隔占领的障碍,和间隔 不受相应的跟踪。此外,由于轨道的中心线和重叠和跟踪宽度较小,我们更新的间隔使用的轨道通过删除间隔 。然后使用间隔设置的追踪最后是空的,因此电线可以通过直接从跟踪跟踪 。
此外,我们采用最小生成树算法将每个multipin位分解成一组两脚位和确定首选方向(垂直或水平)每个销。也就是说,如果同一销形状在不同的物理位置横向分布,然后针形状的首选方向设置为垂直的;相比之下,如果相同的物理位置销形状在不同的垂直分布,然后针形状的首选方向是水平的。销的首选方向所需的方向的线连接到销。例如,所有六个别针的首选方向图1(一)是水平的,因为相同的物理位置销在不同位垂直分布形状。
3.2。全球路由
确定所需的路由区域为每个总线和减少后续详细路由的复杂性,我们制定topology-aware单总线路由UFP和集成到一个negotiation-based全球路由方案。我们的全球路由方案的三个主要步骤阐述如下。
3.2.1之上。网格图施工
在全球路由阶段,每个路由层划分为一组全球细胞(g-cells)如图5(一个),可以构造相应的网格图如图5 (b)。在网格图,每个顶点代表g-cell和每个路由优势代表相邻g-cells之间的边界,通过和任何两个相邻层连接。此外,在每个路由图的边缘5 (b)显示的容量优势,对应的路由追踪的数量可以包含在边缘。由于直接解决3 d全球路由问题是费时,我们进一步项目多层设计到二维平面上,然后生产图 构造。
(一)
(b)
此外,每个销对应于一个g-cell。如果两个别针的两位在同一个g-cells,然后我们暂时把两位。通过这种方式,我们可以在每个总线大大减少碎片的数量在全球路由、全球路由阶段和运行时将减少。把图5(一个)为例。有两位在一辆公共汽车和每一位有两个别针。两针两位在同一个g-cells,我们把两个比特位,和需求(消费的歌曲数量)合并中的每个路由线是2。
3.2.2。初始解代
太多的弯曲的路由路径不仅增加通过的数量,导致路由质量差,但也使它更难以维护相同的路由拓扑由于段的数量的增加。因此,我们限制弯曲的数量在这个最初的解决方案生成步骤。位可以分为两种类型基于针的首选方向。图6(一)显示四位来自不同的针公交车使用相同的优先方向,和路径连接每个点都有偶数个弯曲。相反,三位来自不同的针巴士如图6 (b)垂直的优先方向,道路连接的两针每一位有奇数个弯曲。进一步,因为我们设置为每个销易磁化方向,有点最多有一个路径与一个或零弯曲,而我们只需要确定( )弯曲点依次获得路径弯曲。
(一)
(b)
在这一步中,弯曲的路径连接的数量每一位仅限于四个。对于每一个巴士,让代表的需求 , 表示路径的设置 ,和代表的路径相同的路由拓扑在 。注意,在全球路由拓扑确保(1)所有位具有相同数量的电线和(2)所有电线追踪从所有位路线朝着同一个方向,而暂时忽略导线的相对顺序不同的碎片。此外,对于每一个 ,我们有一个非负变量和重量与它相关联的。重量的路径是所有的边的权重的和路径,和边缘的重量吗被定义为 在哪里代表的总和的要求通过和边的容量吗 。为每条边 ,的需求被初始化为0,一旦总线路由更新成功。重量急剧减少的需求趋于能力但在强度不足和过剩部分增长缓慢。
我们确定订单路由拓扑根据弯曲的数量和重量的路径 。小数量的弯曲有更高的优先级。对于每一个巴士,我们尝试总线拓扑的一个接一个,直到总线发送成功。此外,我们引入一个新的变量为每一位 ,在哪里 ,,让是一份 。然后,全球的总线拓扑路由问题可以作为UFP制定如下:
制定UFP的目标是最大化可路由的碎片的数量,和所有选择路径的总重量是尽可能大(即。,交通拥堵是尽可能小的)。第一行的约束确保最多每一点,选择一条路径和第二行约束的限制部分的总需求,可以通过每条边。将会增加如果所有总线的拓扑路由失败。总线是成功路由如果所有的公共汽车都成功路由(即, )。一旦成功地击败一辆公共汽车,我们更新的需求和重量的每条边下一辆公车,然后处理。
基于UFP的组合算法(7),算法1提供了一个算法的问题(1)。让 和最小(最大)能力和边缘 最小/最大需求/重量在所有总线位。在1号线,我们第一个分区的碎片分成两个不相交的集和 。 包含的比特 ,剩下的部分 。为每一位和一个给定的路径的位 ,我们采用 在[7)测量体重增加相对于增加负载的需求。我们设置了下界和上界在在第3行。在第6行位的顺序排序,然后我们处理比特一个接一个地为每一位选择路径在7 - 11行。在第8行表示边缘的相对负荷路由后位 。
|
算法的时间复杂度1是 ,在哪里一辆公共汽车和碎片的数量的边的数量相同的路径,路由拓扑公共汽车。从算法的细节,我们可以看到1,1号线要求时间,6号线需要 ,和8 - 9行需要时间。此外,由于循环的数量在2号线和4号线是常数,在第7行循环的数量 。因此,算法1需要 每个总线。
定理1。算法1是一个UFP的近似算法。
证明。考虑一个最优解路由部分 。为每一个 ,让被选择的路线在最优的解决方案。的总重量 或 至少是 。表示,由和它的指数 ,,让 是最高的,这样 。让 和 是集高和低质量的路线 。根据的定义 ,我们有 ,的不平等是真的因为一个最佳解决方案不能溢出的优势。因此,我们有 。此外,由于 对于每一个 ,根据(7),我们有 。通过结合两个不等式,我们得到 。
3.2.3。撕碎和路由
撕碎和路由是一个基本的路由技术,通常结合谈判技巧。的negotiation-based撕碎,重新路由广泛用于全球路由(8,9)、跟踪任务(10),和详细的路由(11)和已被证明是有效的和有效的提高路由质量。
在每个撕碎和变更迭代,我们首先确定和马克有溢出边的一组公共汽车或过度的路由成本(方程(9)需要被重新路由。重路由的公交车不溢出,但过多的路由成本不仅可以降低路由成本也释放路由资源为其他溢出的公交车。然后,标志着公共汽车是基于分数降序排序定义如下: 在哪里 中定义的路由成本方程(9),表示溢出边缘通过公共汽车的数量在前面的迭代是一个用户定义的参数设置为是哪一个 。
此外,基于历史成本函数为每个路由边缘在[8)采用,它被定义为 在哪里线的长度是成本,是历史成本,是目前的违约成本, 表示的拥堵成本优势 ,和是通过成本。边缘的重量是设置为 ,我们重新路由的总线,解决问题(2)。
我们重复撕碎,重新路由过程,直到没有溢出边缘或过度的路由成本或达到最大迭代次数。因为我们重新路由的总线,解决UFP (2)和所需的运行时 ,撕碎,需要重新路由阶段 ,在哪里公交车的总数需要撕毁和路线。
获得一个2 d全球路由解决方案后,我们扩展层赋值方法12)投影平面的地图解决方案最初的多层。注意,在每一段的巴士,我们确保电线不同的比特分配给相同的层。
3.3。跟踪任务
在获得所需的路由区域为每个总线在全球路由阶段,我们提出一个topology-aware追踪任务在本节将跟踪分配给每一段公交车的指导下全球路由的结果。在这个跟踪作业阶段,我们把数组的行或列中的所有g-cells路由层作为面板,和每个直导线,通过一个或多个g-cells被视为一个iroute。
3.3.1。初始跟踪任务
因为所有部分在每个总线需要相同的路由路由拓扑中,我们处理巴士一个接一个来分配每个段的跟踪。对于每个总线,每一部分由一组iroutes不同的比特从源代码时,有相同的序列跟踪销销。
为了保持iroutes在每一段的相对顺序,我们最初的跟踪任务为每个部分如下。首先,我们每个段的iroutes在相同的顺序或倒序的碎片。这两个订单测试,因为每个订单的结果可能不同,最好的结果了。基于顺序,对于每个iroute,我们收集板的有效跟踪和计算的成本分配iroute每个有效跟踪。跟踪是有效的,如果轨道的宽度约束大于或等于iroute的线宽。最后,我们选择一个有效的跟踪以最低的成本,以适应iroute。
分配iroute的成本函数的跟踪被定义为 在哪里 是分配的总成本跟踪对iroute , 线的长度是成本, 成本是重叠的, 阻塞成本区间, 是紧性成本, ,和是用户定义的常量设置为0.2,1000年,分别和1。
线长度的定义采用成本从工作10]。因为路由追踪可能不均匀,甚至重叠,重叠的成本iroute被分配给一个追踪修改工作(10],它不仅取决于轨道的重叠iroutes重叠的iroutes还在其他痕迹。此外,因为一些跟踪可能仅覆盖部分设计,阻塞成本区间是阻塞成本的总和中定义(10)和iroute的长度这不是在轨道上。根据2018年的CAD比赛ICCAD [5),所有位的电线在一辆公共汽车应该尽可能紧凑。因此,我们定义密实度成本使每个总线更紧凑,储备更多的自由空间对其他公共汽车。
图7说明了密实度计算成本。我们假设不失一般性,面板是水平的。每个总线的第一和最后一段,因为iroutes最终需要被连接到相应的针在详细路由阶段,密实度成本设置为iroute之间的垂直距离和相应的销。例如,图7(一)显示了巴士的第一部分,销和iroute属于第一位销和iroute属于第二位。iroute的密实度成本在跟踪 , ,和是0, ,和 ,分别和密实度iroute成本在跟踪 , ,和是 , ,分别和0。
(一)
(b)
(c)
剩下的部分在公共汽车上,不需要连接销,iroutes的密实度成本相关的iroutes比特分配的顺序。如果我们处理iroute之前iroute在图7 (b),成本的密实度之间的垂直距离是每个iroute iroute和面板的上边界。相反,如果我们处理之前 ,然后每个iroute成本的密实度之间的垂直距离iroute和面板的下边界。此外,如果一段的iroutes分布在多个面板如图7 (c),密实度的每个iroute成本最低的小组之间的垂直距离是iroute和面板的上边界的紧性成本最高的面板中的每个iroute iroute之间的垂直距离和面板的下边界,和成本的密实度iroute其他面板是0。
3.3.2。撕碎,再赋值
在最初的跟踪任务,iroutes之间可能会有重叠。因此,我们扩展negotiation-based跟踪分配工作(10)尽量减少重叠和电线长度,同时保持iroutes在每一段的相对顺序。
重新分配的成本函数被定义为 在哪里 ,和 在方程(一样的定义5), 是历史成本的工作10]。用户定义的参数 ,和是用来平衡成本组件。这两个和初始化为1,逐步下降到0.1随着迭代的增加,然后呢0.1初始化,逐步增加到1随着迭代的增加。除此之外,是一个非常大的常数和设置为1。通过对这些参数的控制,我们可以用更少的电线长度减少重叠和密实度的成本在早期的迭代中,将更多的注意力放在减少重叠在后期迭代。
为了保持相同的所有总线拓扑位,我们总是保持的相对顺序iroutes在撕碎的每一部分和分配阶段。然而,重新分配一个iroute同时保持的相对顺序iroutes段可能陷入局部最优,因为解决方案空间是有限的,我们可能总是选择同一组iroutes或总是试图分配一个iroute少量的痕迹。因此,在每次迭代中,我们可能会撕毁并重新分配多个iroutes减少陷入局部最优的概率。具体来说,当一个iroute没有其他追踪,可以分配给这些跟踪已经被这iroute打了几次,我们还将撕毁和重新分配的一些iroutes iroute相邻。重新分配一个iroute的时间复杂度在每一次迭代是轨道的数目在面板iroute所在地。因为我们可以撕碎并重新分配多个iroutes同时减少陷入局部最优的概率,如果我们处理同时iroutes,时间复杂度 。然而,由于不是太大(数十到数百),我们准备好了吗3,这个阶段的运行时间主要取决于iroutes的数量需要重新分配。
例如,假设iroute在图7 (c)需要重新分配。以来的相对顺序不同比特的iroutes段应该保持,iroute只能iroute之间放置和iroute 。也就是说,如果iroute不是重新分配到另一个轨道,然后iroute不能重新分配。因此,我们iroutes撕碎和 ,然后iroutes和可以重新分配到跟踪和 ,分别。
3.4。详细的路由
跟踪任务之后,我们需要连接的组件每一位获得最终的路由的结果。有些组件是一个销或iroute钻头。算法2给我们详细的框架路由。在第3行,为了保持相同的路由拓扑所有总线位和荣誉全球路由的结果,每个位排序的组件根据全球路由路径的跟踪订单从源汇销销,然后我们只需要连接相邻组件的每一位。
|
||||||||||||||||||||||||||||||||||||
在4号线,我们采用l型(13],z字形[13],3-bend路由(14连接相邻组件,因为它是容易控制相同的所有总线拓扑位和非常有效的利用这些预定义的模式路由。之后,我们使用两级negotiation-based撕碎,路由在分裂到8 - 16个。行迭代提高解决方案的质量和在第8行显示的最大迭代数的第一阶段和第二阶段撕碎和变更,分别。在第一阶段,我们把每两个相邻组件有重叠的连接和路由通过路由模式,同时保持相同的路由拓扑。每一次迭代后,我们增加的历史成本的重叠区间轨道重叠电线的数量。因此,跟踪的历史成本更高,往往有较少的机会路由,和部分替代路线被迫使用其他痕迹。最后,大多数需要使用这个跟踪最终会使用它。
因为有限的搜索空间模式路由和只允许撕毁和路由相邻组件在第一阶段撕碎和路由,可以减少线重叠是否删除一些限制。在第二阶段中,我们使用算法(15搜索路径和允许的路径以外的全球路由指南。此外,我们还允许一些iroutes提取跟踪作业阶段被移除,从而增加路由的自由。例如,如果我们删除第二个组成部分,那么我们必须找到一个路径连接第一组件和第三个组件。有点路线的一部分时,我们检查是否其他的总线拓扑结构是一样的。如果没有,我们将调整其他基于路径的路由路径的。我们重复撕碎,重新路由过程,直到所有的公交车都发送成功或达到最大迭代次数。
最后,我们构造一个冲突图中每个总线被认为是一个顶点,和每条边代表两辆公共汽车之间的冲突。我们反复rip总线(顶点)最大的程度及其相关的边缘,直到没有冲突的边缘图,和最终的路由的结果。
4所示。实验结果
评估我们提出汽车路由算法,我们实现了我们的算法的c++编程语言和测试的基准(包括隐藏的情况下)的2018 CAD比赛在总线上Obstacle-Aware赛道ICCAD路由5]。表1列出了基准统计,“#层,”“#轨道,”“#障碍,”“#公共汽车,”“#,”和“#销”给层的总数量,跟踪,障碍,巴士,位,分别和固定针。
在比赛中得分函数(5]采用总线路由的质量评估结果,由路由成本 ,间距违反处罚 ,和失败的路由点球 。也就是说,
三个部分的得分函数计算如下: 在哪里 有五个权重参数给定的输入数据,以及这些参数的值可能会有所不同从不同的基准。为每一个巴士 ,线的长度成本 ,部分成本 ,和密实度成本定义如下:
理想情况下,如果一辆公共汽车路由的最低线长度( )和最小数量的部分( )和所有路由段宽度接近下限( ),然后路由成本接近完美的路由总线 。
实验结果前三的球队2018 CAD比赛ICCAD [5和我们的表中列出2。算法运行在Linux工作站和一个2.40 GHz Intel Xeon处理器和64 GB的内存,和前三队的比赛的结果由比赛组织者提供。因为不能使用前三队的二进制文件对我们来说,我们不报告他们的运行时。然而,在指定的时间为每一个测试用例是根据比赛(一个小时5),我们的项目将被杀死,如果运行时超过指定的时间。
在表2列“首先”、“第二名”,“第三位,”和“我们的”给相应的路由结果生成的,第二名,第三名的比赛5我们的算法,分别。最新的评估脚本(eval_1.0-a8)提供的比赛(5)是用于获得路由成本” ,“间隔违反处罚” ,“失败”路由点球 ,“分数” 。“这可以从表2所有的公共汽车都成功路由算法的测试用例 , , ,和 。尤其是平均算法优于前三队9%,124%,357%,最后的成绩,分别。实验结果表明,我们建议的总线路由算法是有效的。
5。结论
在本文中,我们提出了一个有效的算法来解决topology-aware总线路由问题考虑非均匀跟踪配置和障碍的存在。我们首先提出了一种跟踪处理非均匀路由跟踪技术统一配置与障碍。然后,我们制定单总线作为UFP topology-aware路由问题,这是集成到一个negotiation-based全球路由问题确定所需的路由区域为每个公共汽车。此外,我们提出了一个topology-aware跟踪分配方法分配跟踪每一段公交车的指导关于全球路由的结果。最后,详细的路由方案已经提交给每个总线的连接部分。我们评估我们的路由结果ICCAD基准套件。与最先进的方法相比,实验结果表明,我们提出的方法在指定的时间内达到最好的总分。
数据可用性
在这项研究中使用的数据可以通过访问http://iccad-contest.org/2018/problems.html。
的利益冲突
作者宣称没有利益冲突。
确认
这项工作是支持的基础研究基金为中央大学拨款2242021 k30031下的中国,国家重点研究和开发项目的中国2018 yfb22022704格兰特,国家科学基金会中国(61977017和61977017号),和优秀青年创新团队项目下的山东大学2020 kjn008格兰特。