一种新的无网格拆线重布算法

结合无网格布线的特点,提出一种新的无网格拆线重布算法.该算法显式地表示并动态更新线网所属区域的拥挤程度.在拆线重布进行待布线网的路径搜索时,每个扩展节点中增加拆除线网周边的拥挤权重,从而将待布线网的路径搜索过程和拆除线网的选择过程统一起来,有效地提高了被拆除线网重新布通的可能性.该算法利用改进的二叉区间树有效组织中间数据,降低计算的复杂度.实验结果表明,该算法能有效消除布线顺序对布线结果的影响,提高布通率,且算法运行速度较快.     

一个基于层次式PB角钩链结构的区域布线器

提出一个新的基于层次式PB角钩链结构的多层无网格布线器.该布线器基于PB层次式角勾链数据结构和网块扩展算法,使用朝向目标的加速策略提高算法的运行速度,并使用改进的二叉区间树管理算法的中间数据.还提出了基于拥挤度的无网格拆线重布算法.通过显式记录每个线网段周边的拥挤状况,并将其结合到网块扩展的费用当中,使拆除线网的选择和待布线网的路径搜索统一起来.实验结果表明,该布线器能有效地提高布通率,且算法运行速度较快.     

一个基于层次式PB角钩链结构的区域布线器

提出一个新的基于层次式 PB角钩链结构的多层无网格布线器 .该布线器基于 PB层次式角勾链数据结构和网块扩展算法 ,使用朝向目标的加速策略提高算法的运行速度 ,并使用改进的二叉区间树管理算法的中间数据 .还提出了基于拥挤度的无网格拆线重布算法 .通过显式记录每个线网段周边的拥挤状况 ,并将其结合到网块扩展的费用当中 ,使拆除线网的选择和待布线网的路径搜索统一起来 .实验结果表明 ,该布线器能有效地提高布通率 ,且算法运行速度较快     

结合改进A*算法与拆线重布的有序逃逸布线

逃逸布线是印刷电路板设计的一个重要组成部分.针对并行逃逸布线的方法用于较大规模电路板布线时速度慢且结果不够好的问题,该文提出一种结合改进A*算法与拆线重布的有序逃逸布线方法.首先,通过代价预估函数确定引脚的布线顺序,使用改进A*算法初始化有序逃逸布线.接着,优化同长度布线路径,调整拥挤区域布线路径.最后,使用A*算法和广度优先搜索进行拆线重布.实验结果表明,该方法对给出的所有测试用例都实现了100％的逃逸,得到有序逃逸路径的可行解非常接近最优解,CPU时间比布尔可满足性问题(SAT)算法与最小费用多商品流(MMCF)算法平均减少分别约为95.6％,?97.8％,总体线长也接近最优.提出的方法能够明显减少寻找可行解的时间,提高布线质量.     

结合改进A*算法与拆线重布的有序逃逸布线

逃逸布线是印刷电路板设计的一个重要组成部分。针对并行逃逸布线的方法用于较大规模电路板布线时速度慢且结果不够好的问题,该文提出一种结合改进A*算法与拆线重布的有序逃逸布线方法。首先,通过代价预估函数确定引脚的布线顺序,使用改进A*算法初始化有序逃逸布线。接着,优化同长度布线路径,调整拥挤区域布线路径。最后,使用A*算法和广度优先搜索进行拆线重布。实验结果表明,该方法对给出的所有测试用例都实现了100%的逃逸,得到有序逃逸路径的可行解非常接近最优解,CPU时间比布尔可满足性问题(SAT)算法与最小费用多商品流(MMCF)算法平均减少分别约为95.6%, 97.8%,总体线长也接近最优。提出的方法能够明显减少寻找可行解的时间,提高布线质量。     

SERR:基于模拟进化技术的性能驱动总体布线算法

本文结合ＢＢＬ布图模式，以提高整个芯片的时间性能为目标，提出了关于总体布线的基于模拟进化（ＳＥ）技术的拆线与重布线算法（简称为ＳＥＲＲ算法）．ＳＥＲＲ算法对传统的顺序布线算法进行了改进，运用概率准则选择线网进行拆除与重布，具有绕开局部优化点、得到全局优化解的能力．实验证明，ＳＥＲＲ算法能够较好地达到优化整个芯片的连线延时性能的目标     

一种用于FPGA的新型混合布线算法

布尔可满足性是计算机科学中最基础的问题之一,已经出现了包括著名的基于查找的SAT算法在内的各种算法.对于传统的一次布通一条线网的方法,基于布尔可满足性的算法有着独特的优点,例如:同步线网嵌入及可布通性确定.然而基于SAT的布线法在可扩展性方面有很大缺陷.而另一方面,几何查找布线算法即使具有广泛的拆线重布线的能力,但当北一个问题具有严格的布线约束条件时,它在布线方案收敛方面存在很大困难.文章提出了将一种布尔可满足性算法与VPR430相结合的新型、有效的混合布线算法.试验结果表明与相应的纯几何布线算法相比,这种算法在运行时间上有了极大的改善(减少了29%),并且对布线整体方案无不良影响.     

Full-Chip Scalable Routing Framework Considering Congestion and Performance

提出一个全新的全芯片可控布线系统框架,同时考虑布线拥挤度和芯片性能.为了在总体布线和详细布线之间架起桥梁,该框架把总体布线和详细布线集成起来,交互进行,每完成一个线网的布线,都及时对布线资源进行更新,由此可以得到精确的资源估计结果,有利于指导后续总体布线决策.该系统框架的主要特征包括快速的基于模式的和基于外框约束下最短路算法的总体布线器、基于迷宫算法的拥挤度驱动的详细布线器以及在两个布线器之间很好的交互性.在该布线系统框架中,为了优化电路性能,在布线中关键线网被赋予更高的优先级.同时,为了优化不同的布线目标,可以采用不同的线网排序策略.该布线系统框架在一套公用的测试电路上完成测试,并与之前提出的多级布线系统框架进行比较,实验结果表明,文中提出的布线系统框架在电路性能、布通率和运行时间方面都取得了很大改进.     

考虑拥挤度和性能的全芯片可控布线系统框架

提出一个全新的全芯片可控布线系统框架,同时考虑布线拥挤度和芯片性能.为了在总体布线和详细布线之间架起桥梁,该框架把总体布线和详细布线集成起来,交互进行,每完成一个线网的布线,都及时对布线资源进行更新,由此可以得到精确的资源估计结果,有利于指导后续总体布线决策.该系统框架的主要特征包括快速的基于模式的和基于外框约束下最短路算法的总体布线器、基于迷宫算法的拥挤度驱动的详细布线器以及在两个布线器之间很好的交互性.在该布线系统框架中,为了优化电路性能,在布线中关键线网被赋予更高的优先级.同时,为了优化不同的布线目标,可以采用不同的线网排序策略.该布线系统框架在一套公用的测试电路上完成测试,并与之前提出的多级布线系统框架进行比较,实验结果表明,文中提出的布线系统框架在电路性能、布通率和运行时间方面都取得了很大改进.     

一种基于层次式FPGA的扩展布线算法

实现了一种基于Virtex架构的FPGA芯片,测试其单长线及直连开关连通情况的布线算法;巧妙地利用了FPGA结构层次化这一特点,采用轮回行布线整体扩展的方法进行布线,布线过程中,利用整体分组、多点布线、综合评优等多套策略,有效降低了后期资源冲突几率和回退率,极大地提高了布线质量和布线效率;拆除重布的过程又采用部分而非整体拆除的机制,大大减少了拆线数量,显著提高了运行速度;实验结果表明,本算法具有布线效率高、单长线资源覆盖率高、故障定位准确率高等优势.