一种L型通道布线算法

近年来,通道布线问题引起了人们广泛的重视。但至今研究L型通道布线的文章很少。本文提出了一种以减少信号网冲突数为主要目标的L型通道布线算法。该算法从一种总体的考虑出发,把L型通道分解为两个相关的四边通道进行布线,提高了布线成功率。     

BPGR积木块自动布局和总体布线系统

超大规模集成电路(VLSI)的积木块布局布线是一个非常复杂的问题.本文介绍了我们自行研制的VLSI 积木块布局和总体布线系统BPGR.该系统包括积木划分、布局优化、通道划分、总体布线、交互式布局布线调整等过程.BPGR系统能最有效地利用芯片资源和最大限度地提高芯片性能·编程和实验证明,BPGR系统是VLSI 积木块布局布线设计的有效工具.     

基于自由分层的通道区布线算法

本文在分析线网之间关系的基础上提出了自由分层条件下的通道区布线模型:同层限制图 Gs,相交图 Gi。基于这一模型,分析了二层布线条件下对线网分层和布线序的基本限制,导出了分层的基本原则。在此基础上,分析了线网可 overlap 的性质和条件,从总体分析的思想出发,提出了直接以完成布线通道区所需面积最小化为目标的分层布线算法。实验结果表明,通道区布线面积和通孔的数目比基于横竖分层的布线算法有较大减少,对于Deutsch's difficult example,该算法获得18个 track 解。     

超大规模集成电路成功布线的策略

该文对超大规模集成电路 (VLSI)的成功布线给出一些策略。运用这些策略可以确定通道区最优布线 ,避免出现“开关盒”问题 ,还可以预知成功布线的可实现性 ,保证在通道区扩张阶段需要重新布线的通道区数目最少。这些策略均以图论为基础 ,对VLSI布图设计具有一定的理论和实用意义。     

一种以改变目标为策略的改进型三层通道布线算法

本文提出了一种改进型的三层通道布线算法——以改变目标为策略的三层通道布线算法.根据不同的布线问题,分别采用不同的布线方法,即首先从分析布线问题的最大垂直限制链长和最大通道密度出发,当以完成布线所需的通道数为最小作为目标时,采用HVH的三层通道布线算法;当以缩短最大垂直限制链长为目标时,采用HVH_m的布线算法.因此,它综合了曲干布线和直干布线两方面的优点,即不仅充分利用了通道区的空间,而且又一定程度地限制了导通孔数的增加.本算法已用FORTRAN语言编程实现,对引文中已发表的若干布线实例,都获得了较满意的结果.     

实现印制板最佳自动布线的一个有效途径

本文先对一类特殊网络集合给出了最佳排序算法,及确定布线所能达到的最小通道占用数的定理。进而给出普遍的网络集合可以用最小通道占用数T_0进行布线的充分必要条件,及相应的排序算法:在网络集合中划出若干个宏子集,根据上述充分必要条件,给宏子集中的网络排次序。从而保证布线结果为最佳,即布线占用的通道数最小。最后从图论角度,对所得到的结果做简单解释。     

基于Hopfield神经网络模型的通道布线算法

本文探讨了用Hopfield神经网络模型解决通道布线问题的一种新算法。算法描述了Hopfield模型与通道布线问题的映射方法和网络能量函数的构造方法,在能量函数中既考虑了合法解约束项,又考虑了优化解约束项,从而提高了布线质量。本文的意义还在于它证明了用Hopfield网络求解通道布线问题是可行的,有效的。     

一个具有最小串扰的多层通道集成电路布线算法

提出一种多层通道布线算法.采用动态规划思想逐层进行布线,使当前层面上的串扰达到最小,并将不能在当前层面连接的管脚对"沉积"到下一层,产生多层通道布线解.     

通孔最小化的三层不规则边界通道布线

提出了一种以连通孔和布线区域最小化为目标的三层不规则边界通道布线算法。算法将通道边界的凹陷区域看成固定障碍,利用填充和压缩方法,使线网绕过障碍,实现互连。算法已用PASCAL语言编程,并在XT/286机上实现。结果表明,该算法不仅使通孔数减少,而且由于利用了各凹陷区域之间的面积进行布线,通道宽度也相应减小。     

MCM布线中v4R算法的改进方法

对多芯片组件的布线方法提出了一种新的方法,以MCM布线中的四通孔算法（v4R）为基础,针对其易对图的拓扑结构信息丢失的缺陷,通过引入最小斯坦纳树（Minimum Steiner Tree,MST）,减少总布线层数,使总布线长度缩短,减小延迟,以达到总体布线结果优化。此外,针对v4R算法自动布线结果不均匀的缺点,引入预分配层进行手动预布线,使最后MCM总布线层数减少,软件模拟表明,改进算法有效利用了整个布线空间,在电特性方面使整体延时减小。     

解决布线过程中通道消失分解、合并问题的一种方法

在 VLSI 积木块布图设计模式中,模块的移动会引起通道图发生变化,影响布线的进行。本文给出了一种布线方法,用此方法可保证:任给一个通道图,只要其 T 形约束图中无约束环,无论模块在布线过程中怎样平行移动,均可按照通道图正常布线。此方法已成功地应用在我们研制的 VLSI 版图 CAD 系统中。本文从理论上给予证明,并给出应用实例。     

时延驱动的门阵和标准单元布图系统——Tiger

Ｔｉｇｅｒ可以完成从布局到详细布线的整个布图全过程。在整个布图过程中，根据ＲＣ延迟模型计算所有连线的延迟，并把整个芯片的时延最小作为优化目标。在Ｔｉｇｅｒ系统中，应用了性能驱动的布局和总体布线算法、ＤＲＡＦＴ通道布线算法和基于垂直通道模型的走线道分配算法。实验结果表明，Ｔｉｇｅｒ的布图速度要比ＴｉｍｂｅｒＷｏｌｆ６．０快很多。它在保证芯片性能的同时，其芯片面积与ＴｉｍｂｅｒＷｏｌｆ差不多。     

一层半模式的宏单元阵列版图自动设计及验证系统MALS

本文提出的 ＭＡＬＳ系统，针对一层半模式门阵的特点，以线网均匀分配为主要目标 的布局和总体布线算法以及分区、定序、预测和并行横向的通道布线算法，提高了布图 的成功率。系统还提供了多种方式可进行人工干预的交互环境及布图正确性验证手段。 已用ＭＡＬＳ设计了若干芯片，表明该系统是有效的。     

Congestion-Driven Multilevel Full-Chip Routing Framework

A W-shaped multilevel full-chip routing framework using W-shaped optimization flow is used to find the final routing solution. The W-shaped flow consists of two sequential V-shaped optimization flows. The first V-shaped flow optimizes the global routing solution. The probabilistic congestion prediction technique is used to guide the global routing decision to find the routing solution that evenly distributes the nets. Then, the second V-shaped flow improves the quality of the routing result. Tests on a set of commonly used benchmark circuits and comparisons with other multilevel routing systems show that the routability, total wire length, total number of vias, and the runtime are all improved.     

一种连通孔最小化的布线算法

提出了一种先分层、后布线的减少连通孔的布线算法，该算法的主要思想是从总体上考虑布线的，即先从总体上考虑连通孔最小化，再行布线比传统的布线方法更为紧凑和有效，最后通过实例验证了该算法，并给出了计算结果     

一种Mesh路由缓存机制及其仿真

对于无线Mesh网络中的MGMP路由协议,在信道切换过程中,Mesh节点数据报文可能会因找不到路由或数据拥塞而导致数据丢失。为了解决MGMP路由协议在路由策略和数据拥塞方面存在的问题和不足,提出一种MGMP路由协议报文缓存机制,详细论述了MGMP路由缓存机制思想及其具体实现过程。同时,对这种带缓存的MGMP路由机制进行了NS-2仿真测试和性能分析。实验结果表明:这种支持报文缓存的MGMP路由协议,能够更好地适应信道动态调整,从而提高了Mesh网络的整体性能。     

多信道无线网状网的多信道多径路由实现

基于优化链路状态路由(OSLR)协议,提出了一种改进的路由算法,能在多信道无线网状网中进行多信道多径路由.仿真实验结果表明,与单径路由方案相比,有效地减少了信道切换次数,从而降低了总体端到端延时.     

多速率ad hoc网络的信道忙感知路由协议

为了适应时变的信道条件并获得更好的信道利用率,IEEE 802.11支持多种数据传输速率,但是传统的无线ad hoc网络路由协议不能充分利用多速率,严重制约了网络吞吐量.文章在分析无线媒介接入竞争和冲突退避情况的基础上,提出了一个信道忙感知路由协议(简称CBAR协议);通过跨层设计,利用信道忙率衡量信道的繁忙程度,结合...