模拟退火技术一个矩形网状网络的路由

文摘

过程中自动设计印刷电路板(pcb),后阶段细胞放置路由。另一方面,路由过程是一个很困难的问题,甚至最简单的路由问题,由一组两脚网是np完全的。在本研究中,我们的路由区域是第一个完全嵌合制服一系列广场细胞。路由问题的最终目标是实现完全自动路由以最小的任何手动干预的必要性。因此,需要建立最短路径的所有连接。而古典Dijkstra算法保证找到最短路径为一个网络,每个路由净之后会形成障碍的路径。这将添加路由后网和复杂性使其超过最优路由路径或有时不可能完成。今天的顺序通常路由启发式方法适用于进一步完善解决方案。通过这个过程,所有网将在不同的路线以便提高路由的质量。正因为如此,我们的动机是应用模拟退火,metaheuristic方法之一我们的路由模型序列产生更好的候选人。

1。介绍

在电子设计自动化(EDA)、布线或简单地称为路由是最重要的步骤之一,在超大规模集成电路的设计集成电路和机器人路径规划。每一对的连接销(有时称为终端或节点)的电路必须满足设计规则。高质量的路由会给一个伟大的对芯片性能的影响。由于它的重要性和普及应用,研究人员发现高这个问题,正在研究的兴趣广泛提高最优性和效率。最优路由应该提供最低的成本,最短的距离,或者最低的运行时间。

假设我们有一个网络列表,列表中的每个净处理由一对元素。这个处理元素有时也称为节点,处理节点,或销的文学。为针的数量,会有最多网路由。然而,在真正的问题,大多数时候,连接通常是小于的数量网因为有时一些针不分配给被连接到任何其他别针。但是我们限制自己网的最大数量并提出一个方法来实现100%路由而满足路由需求。

然而,它几乎是不可能的网在一层特别是路由很大。在本文中,我们的目标是提出一个方法来减少层矩形网状网络同时满足路由需求。为了做到这一点,我们需要在每一层的连接数量最大化,因此重要的是要让每个净最短路由。路由的复杂性区域是有界的处理器数量的限制和能量,这能量水平高度取决于网表。

路由问题是一个有趣的话题,引起了研究人员的广泛的研究。在此领域的一些问题已经解决(包括提供deadlock-free路由方案1),obstacle-aware净长度约束路由问题[2),并为每个净最长路径和障碍的存在(3]。大多数路由算法在这个领域是李的扩展的算法(4- - - - - -6]。尽管它保证要尽可能找到最小成本路径如果它存在,它的搜索基于波传播性质是缓慢的。因此,我们提出另一个动机是基于随机优化的路由算法使用模拟退火技术和迪杰斯特拉算法解决最短路径问题的一部分。我们提出的路由算法可以应用于任何尺寸的问题。

本文组织如下。部分2问题和讨论我们的路由布局模型。部分3解释了使用迪杰斯特拉最短路径问题的算法和模拟退火技术的实现问题。模拟工作和整个章节中讨论的结果4。本文总结与结论部分5。

2。问题陈述

路由在印刷电路板(PCB)是一个确定的过程和处方路径之间的各种电子元件,以建立一个给定的源点和目标之间的联系。路由在现代芯片是一个很困难的问题,甚至最简单的路由问题,由一组两脚网是np完备性(7]。

在这个问题上,我们的路由区域被认为是均匀分成广场的细胞,每个细胞都包含别针。除非另有规定,被认为是1。专注于布线,我们应当承担针已指定的位置。这个过程如图1。

假设我们有一组由两脚网的路由需求,在那里与和分别是源和目标别针。这个路由问题的最终目标是减少层数需要执行完整的路由。为了做到这一点,我们首先寻求互连结构的最大数量的网每一层(s)同时最小化整个地区的交通拥堵。这个问题的目标函数可以定义为

最小化能量水平也是目标之一。为了计算路由的能量水平地区,我们只是替换与,所以能量函数 在哪里序列(也可以称为迭代次数)。

完成这个网状网络布线应遵守设计规则,满足必要的条件如下。(我)考虑 (2)为每一个,必须有一个连接。(3)所有路径可以交叉,但不应该互相重叠。(iv)每个连接将使用的通信链接,没有特定的方向。这允许一个更简单的路由配置,尽管它降低自由在路由。

由于其重要性的行业,我们的动机是产生显著的方法来执行最优路由。图2说明的概念结构矩形网格模型。

这个网格模型的主要功能介绍如下。(我)我们定义随着网络的大小。为模型中,我们为每个针在第一行指定一个ID,分别以左上角为1和4的右上角。类似地,每个销的ID在最后一行,分别以左下角为13,右下角为16。因此,每个销网络中会有一个惟一的ID。(2)剩下针可以相互通信,右,向上或向下的方向,只要道路并不重叠。(3)每个连接独立于其他连接。(iv)每个针只能属于一个净。(v)只有一个销能在给定subbu日志数据。这个操作是按顺序执行的,高度依赖于网络订购。因此,早些时候连接块后的路径。(vi)为了简单起见,每个链接网络举行一个值为1的重量。

3所示。路由模型

最短路径问题是我们研究工作的组件之一。基本上,这个问题寻求解决这个问题:如何处理程序被连接到处理器以这样一种方式,它的最小距离旅行?大多数现在的原型最短路径问题实际上是旅行推销员问题(TSP)。在TSP,销售员需要执行一个完整的旅行从一个点开始,通过每个车站只有一次,回到起点同时最小化旅行的距离。

3.1。最短路径的过程

在我们的问题,重要的是要有所有针连接以来最短的方式减少了路由区域的能量水平是我们的目标之一。通过这种方式,我们可以提供更大的路由空间剩余路由网,从而最大限度地发挥每一层上的连续网数量。提出了最短路径算法在文学如Dijkstra算法的算法,解决了单一问题[8]。然而,所有的权重图应给予积极的价值。否则,它将导致无环图中大部分时间无法提供正确的最短路径。更夫和福特生产Bellman算法提高Dijkstra算法不足的工作负权值(9,10]。Floyd-Warshall算法解决所有成对的最短路径,并使用矩阵更新所有的路径值(11,12]。我们决定使用迪杰斯特拉算法作为工具来解决最短路径问题由于以下几个原因。(我)我们的连通图的形式是矩形数组将不会使用负值作为它的重量。(2)我们只需要找到一个路径连接处理器和在一个时间;因此Floyd-Washall的算法可能不合适。

迪杰斯特拉算法的,假设我们有一个连接或无向图,在那里所有顶点的集合和吗在每条边的重量代表成本或时间。该算法通过求解子问题工作搜索源顶点之间的路径,所有相邻顶点。迪杰斯特拉算法首先将初始值分配给图中的每个节点并一步一步提高。

3.2。启发式改进

传统上,路由在矩形数组可以按顺序或并行执行。顺序路由可能是最简单的策略,必须选择特定的网络订购和路由网根据订单一个接一个。在这个研究中,我们应用顺序路由方法。因此,路由解决方案的质量将极大地依赖于净命令和任务找到这样的命令已经被证明是np难(13]。虽然迪杰斯特拉算法保证找到最短路径为一个网络,每个路由净之后会形成障碍的路径。这将添加路由后网和复杂性使其路由超过最优路径或有时不可能完成。今天的顺序通常路由启发式方法适用于开展撕碎,变更流程进一步细化解决方案。在这个过程中,一些网的连接将被删除,然后重新路由在不同以提高路由的质量。正因为如此,我们的动机是应用模拟退火,metaheuristic方法之一我们的路由模型序列产生更好的候选人。

3.2.1之上。模拟退火的路由算法

在这个研究中,提出了一种启发式方法称为模拟退火生产优质的网上订购。它是一种概率统计方法,由大都市等人第一次模拟,柯克帕特里克et al。14,15]。这个算法现在已经成为一个非常有用的工具在解决各种各样的组合优化问题。

该方法理论的动机在固体退火。模拟退火一词来源于大致类似的物理过程的加热,然后慢慢冷却的物质来获得强大的晶体结构(14]。在这项研究中使用的参数,如下。(1)初始排列。(2)初始温度。这么高的温度是允许几乎所有潜在的社区解决方案。(3)最终温度。当温度达到零或接近于零,接受的概率也将接近零,几乎没有机会接受糟糕的举措。(4)温度下降规则。温度衰减将几何衰减目前的温度和是以前的迭代温度。在[6),经验表明,最好的合适的值应该是。如果值设置太小,系统将迅速降温,可能包含困局部最小值。如果值设置得太大,冷却过程需要较长的时间,系统将运行更多的迭代,直到它到达停止标准。因此,这里我们选择。(5)行动是基于成对交换两个随机网。(6)只有一个解决方案是选为邻近的解决方案。(7)停止条件。

在仿真过程中,温度会逐渐降低,直到系统“冻结”,不再发生变化。在每个温度,模拟必须进行足够长时间的系统达到稳定状态或热平衡。这种方法避免了被困在局部最小值通过接受有时艰苦的举措。这种接受是由使用Boltzman概率: 在哪里是当前解决方案之间的成本差异,前一个吗是当前温度。对于一个给定的退火温度的时间表,我们的模拟退火算法实现如下。(1)确定一个初始序列为所有路由网,叫道。集。(2)Dijkstra算法的算法来计算每个网络的最短路径。为每一个分配到每一个节点的距离值:将它设置为零初始节点和所有其他节点到正无穷。(3)所有节点标记为未浏览。初始节点设置为电流。当前节点,考虑所有既邻国,并计算其试探性的距离。比较新计算初步距离当前分配值和分配较小的一个。(4)当我们做考虑当前节点的所有邻居,当前节点标记为访问。访问节点永远不会又检查了一遍。(5)如果被标记为访问,然后计算。如果是没有达到,因此发生了堵塞。放弃净并继续下一个。重复这个过程每净。(6)计算初始能量,使用(2)。计算成功的路由网的数量,。这个序列标记为“接受”。(7)从,生成新的序列随机交换任意两个不同的元素。(8)集重复步骤2 - 5。评估新序列的新能源,和新。(9)如果,继续步骤13所示。(10)如果,拒绝序列,重复步骤7。(11)如果计算能量变化,。如果,继续步骤13所示。否则,进入步骤12。(12)应用玻耳兹曼的概率。如果,在那里13日,去一步。否则,拒绝移动和重复步骤7。(13)接受候选序列作为当前解决方案,集和。使用减少参数,、更新计数器和参数的温度。集重复步骤7。如果迭代或时代的总数小于,在那里是指定的数字控制运行的迭代的数量,去第七步。否则,停止。

4所示。仿真结果

通过目标函数(1),我们想说明方程是如何工作的。假设我们有一个路由区域的大小和净需求如下: 表1说明了数量的计算(成功路由网在特定的顺序)。

例如,假设我们有一个路由区域的大小和净需求如下: 表2说明了这个过程。在第二个迭代,是交换生产序列,,,,。通过这个序列,屏蔽网的数量减少;这样的数量即使增加也增加。然而,随着过程的持续的价值会逐渐被降低到一个最佳的和可接受的结果。

请注意,反映了线的总长度需要执行在PCB布线和路由的复杂性/拥挤的地区。我们的算法实现了使用Microsoft Visual c++ 2010 (16)和一个英特尔Core2双核2.00 GHz CPU机器上运行3 GB内存。我们首先测试了仿真程序的大小问题16针和随机8网路由。图在图3总结了过程。我们的算法改进的最大数量6网8在早在迭代6号和没有获得最好的结果。因此,对于这个问题,这六个网将在第一层路由和剩下的两个网第二层实现完整的路由。

图4显示所有可接受的能级之间的改善和最低能级移动记录是这需要从整体布局路由大约只有70.83%。通过接受一些艰苦的行动基于Boltzman的概率,减少拥挤的路由布局已经生成。

此外,我们的项目已经测试一个更大的数据集64针和32网网络的大小。从图在图5的最大数量匹配或连接后才得到迭代数24时。这是由于大量的网和复杂的路由需求。因此,当大,程序允许进一步迭代。因为我们的程序需要不到一秒在每个迭代生成解决方案,允许程序继续长时间并不影响计算时间。

记得,我们的目标是最大化同时最小化能量水平的连接数量。然而,此举产生的最大连接总是接受,忽视了它的能量水平。但是,如果当前的价值不是最优,它将逐渐减少到可以接受的一个项目仍在继续。如图6,最低能级记录在是。

然后重复退火过程中发现最大匹配在第二层剩余10网。图7显示最大数量的在每个迭代中获得。我们可以看到,该算法能够路线所有剩余10网8日迭代。因此,只需要两层来执行完整的路由这各自的要求。

接受的明确结果几个最差条件结果移动到一个较低的能级,这是总结在图8。

图9说明了每一层整个线路轨道。两层以不到60%的路由。因此,第一次和第二次地板上的拥堵水平是平衡的。因此,降低成本和开销,从电气来看,每一层都拥有完全相同的传热和性能得到了改进。这表明,我们的算法适用于采用变成一个真正的问题。

我们的算法能产生大量的连接各种网络大小减少拥堵水平整个地区。因此,它表明,此法适用于采用真正的问题。

5。结论

本文描述了一个基本的路由模型通常使用矩形阵列作为路由的布局。这可以建模为路由图,在那里代表一个节点和代表节点之间的网格边界或边界和。在本文中,我们提出一个方法来最大化的连接数量网格组成的网状连接处理数组元素(PEs)网的数量。注意,每个网将按顺序发送。因此,一旦网络路由,它将阻止后路径,这将增加更多的复杂性,将剩余的网。为了克服这个问题,基于智能启发式算法使用退火技术建造产生更好的网络订购,进一步细化序列。我们注入经典最短路径法算法作为工具来提供每个网络的最短路线。我们的仿真结果表明,算法能够减少层数为一个完整的PCB路由先最大化在每一层的连接数量。我们还提供一个低能量水平在整个路由布局通过所有网最短路由。结果还表明,接受一些艰苦的运动与Boltzman的概率会导致一个更好的结果,这是我们的启发式算法是如何工作的。为进一步研究,我们想做一些修改和改进在网上订购。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

作者要感谢教育部奖学金给马来西亚,马来西亚各种大学支持本研究在数量04 h43投票。

引用

1. x段和j·吴Deadlock-free路由方案不规则网格拓扑区域的国有石油公司,”电脑杂志,8卷,不。1,新,2013页。视图:出版商的网站|谷歌学术搜索
2. J.-T。燕和z。陈,“Obstacle-aware length-matching总线路由”程序的物理设计国际研讨会(ISPD 11)ACM,页61 - 67年,圣芭芭拉分校,加州,美国,2011年3月。视图:出版商的网站|谷歌学术搜索
3. y金台,j . Ming-Ching和c . Zhi-Wei”Obstacle-aware最长路径在路由网格,使用矩形模式绕道”第15届亚洲和南太平洋学报》设计自动化会议(ASP-DAC 10)2010年1月,页287 - 292。视图:出版商的网站|谷歌学术搜索
4. c . y . Lee,”一个算法及其应用程序的路径连接,”愤怒的交易在电子计算机上,10卷,第365 - 346页,1961年。视图:谷歌学术搜索|MathSciNet
5. n .摩尼”启发式路由算法的电路布局设计,“IEE诉讼:电脑和数码技术,卷147,不。2,59 - 64年,2000页。视图:出版商的网站|谷歌学术搜索
6. 杨绍明。关铭林,研究。许,F.-S。混合路由,“蔡IEEE计算机辅助设计的集成电路和系统,9卷,不。2、151 - 157年,1990页。视图:出版商的网站|谷歌学术搜索
7. l . t . Wang y . w . Chang和k . t .程电子设计自动化:合成、验证和测试爱思唯尔,波士顿,质量,美国,2009年。
8. e·w·迪杰斯特拉”,注意在连接图,两个问题”Numerische Mathematik1卷,第271 - 269页,1959年。视图:出版商的网站|谷歌学术搜索|MathSciNet
9. r·贝尔曼“路由问题,”季度的应用数学》16卷,第90 - 87页,1958年。视图:谷歌学术搜索|MathSciNet
10. l·r·福特Jr .)“网络流理论,”纸p - 923,兰德公司,圣莫尼卡,加利福尼亚州,美国,1956年。视图:谷歌学术搜索
11. r·w·弗洛伊德“97年算法:最短路径,”ACM的通信,5卷,不。6,345年,页1962。视图:谷歌学术搜索
12. 沃肖尔,”布尔矩阵的定理,计算机协会的杂志上卷。9日,11 - 12,1962页。视图:出版商的网站|谷歌学术搜索|MathSciNet
13. l·c·亚伯”订购自动布线的连接,”IEEE计算机,21卷,不。11日,第1233 - 1227页,1972年。视图:出版商的网站|谷歌学术搜索
14. n .大都市a . w . Rosenbluth m . n . Rosenbluth a . h .出纳员和e .出纳员”状态方程计算通过快速计算机器,”《物理化学》杂志上,21卷,不。6,1087 - 1092年,1953页。视图:出版商的网站|谷歌学术搜索
15. s .柯克帕特里克j . Gelatt和m . p . Vecchi“由模拟退火优化”科学,卷220,不。4598年,第680 - 671页,1983年。视图:出版商的网站|谷歌学术搜索|MathSciNet
16. 美国Salleh、a . y . Zomaya和s . a . Bakar使用Visual c++计算的数值方法美国新泽西州霍博肯市Wiley-Interscience, 2008。视图:MathSciNet

版权

版权©2014 Noraziah Adzhar和Shaharuddin Salleh。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。