PCB布线常用技巧

在PCB设计中,布线是完成产品设计的重要步骤,可以说前面的准备工作都是为它而做的,在整个PCB设计中,以布线的设计过程限定最高,技巧最细、工作量最大。PCB布线有单面布线、双面布线及多层布线。布线的方式也有两种:自动布线及交互式布线。在自动布线之前,可以用交互式预先对要求比较严格的线进行布线,输入端与输出端的连线应避免相邻平行,以免产生反射干扰。必要时应加地线隔离,两相邻层的布线要互相垂直,平行则容易产生寄生耦合。自动布线的布通率,依赖于良好的布局,布线规则可以预先设定,包括走线的弯曲次数、导通孔的数目、步进的数目等。一般先进行探索式布线,快速地把短线连通,然后进行迷宫式布线,先把要布的连线进行全局的布线路径     

一种基于通孔数最小化的多层通道布线算法

该文提出了一种基于通孔数量小化的多层通道布线算法，算法采用非预留层模，首先根据线网之间的位置关系利用模拟退火算法将各线网合理地分配到对应的布线层中去，然后利用遗传算法得到相关布线层中线网的最佳布线顺序向量，最的根据得到的顺序向量利用“沉积法”将各线网布于合理的通道上，该算法克服了传统通孔优化算法中原始布线对优化结果的不利影响，使通孔的优化达到很好的效果。     

自动布线方法(上)

本文介绍主要的布线方法及其优缺点,并进行一些分析比较。主要布线方法有:李氏算法、线探索法、单元布线法、迭代法、单层单行布线法、组合布线法、最优通道法、通道布线法、分级布线法、快速迷路法、分支限界布线法等。最后介绍在小型计算机上实现改进的李氏算法的一种方案。用线符代替线号,朝向终点迷路找线。这样可以用较少的内存,缩短布线时间。     

一种自动布线方法：多级线探索法

本文介绍了一种在微机上实现的印制板自动布线方法──多级线探索法及其编程方法。这种方法是基于完备布线算法的概念，通过分析李氏算法和传统线探索法的不足之处而得到的。虽然它也是一种线探索法，但有较传统线探索法更强的探索能力，不需要结合李氏算法而能单独完成布线任务，是一种较理想的算法，通过实验获得了较为满意的效果。     

确定区域详细布线算法

提出了一种确定区域的详细布线算法,它能对不同设计模式进行布线。该算法能适用于任意多层布线情况,并且支持不同布线层具有的不同工艺参数,在构造布线树时,考虑芯片当前的走线拥挤度,使布线比较平均,并加快了算法运行速度、改善了布线质量,在连接两点线网时,构造基于二维迷宫布线结果的分层图,提出了一种对分层图的启发式染色算示来进行布线层分配,大大提高算法布线速度,采用拆线重布的方法来处理布线失败的线网。     

一种自适应多层无网格布线算法

为适应多布线层，采用非均匀网格图模型，引入了一种自适应迭代策略，将多层布线转化为多次两层布线来处理，既能适应任意布线层数，又大大减少了多层迷宫布线的搜索空间；针对非均匀网格图模型的特点，提出了优化的绕障长度的迷宫布线算法。实验数据显示算法具有较快的搜索速度和较好的布线质量。     

一种考虑可制造性的高性能多层布线算法

本文采用改进的“V”字型布线流程,提出了一个考虑可制造性的多层布线算法,通过粗化和细化两个阶段完成布线。粗化阶段进行资源估计,在“V”字型框架的最底层通过多商品流算法获得总体布线的粗略解;细化阶段通过基于图的Steiner树方法细化布线拓扑树。详细布线采用改进的非均匀网格图,通过考虑OPC的迷宫布线算法,提高设计的的可制造性。     

朝向目标的线探索法——用小型计算机实现自动布线

本文提出了一种适合于小型计算机实现的自动布线方法——朝向目标的线探索法。该方法既适用于印制板布线,也可用于集成电路布线,其基本要素是带有预定终点的探索线。方法的特点是线探索针对目标,数据结构合理,所需存储量小,布线速度快。     

考虑总线时序匹配的多策略层分配算法

在总体布线的过程中,层分配阶段通过控制总线线网的层次影响总线的时序匹配效果.为此,提出考虑总线时序匹配的多策略层分配算法.首先基于线网属性的线网优先级策略,针对线网不同属性的特点得到一个兼顾线长和总线偏差的布线顺序;然后基于贪心策略的初始布线策略,每次布线都对正在布线的线网选择当前最短路径,使相同总线内的线网都尽可能等...     

VLSI中高性能X结构多层总体布线器

X结构带来物理设计诸多性能的提高,该结构的引入和多层工艺的普及,使得总体布线算法更复杂.为此,在XGRouter布线器的基础上,本文设计了三种有效的加强策略,包括:1)增加新类型的布线方式;2)粒子群优化(Particle swarm optimization,PSO)算法与基于新布线代价的迷宫布线的结合;3)初始阶段中预布线容量的缩减策略,继而引入了多层布线模型,简化了XGRouter的整数线性规划模型,最终构建了一种高性能的X结构多层总体布线器,称为ML-XGRouter.在标准测试电路的仿真实验结果表明,ML-XGRouter相对其他各类总体布线器,在多层总体布线中最重要的优化目标|溢出数和线长总代价两个指标上均取得最佳.     

基于多层混合结构的IPv6路由表查找算法

针对现有的大多IPv6路由表查找算法采用各种优化手段提高查找性能,却使得路由更新需要重构整个路由表的问题,提出基于多层混合结构的IPv6路由表查找算法。该算法在第一层借鉴最优查找树的优点,把前缀1~16位的不同取值按其在路由表中出现的概率降序存储在线性表中,在第二、三层把前缀的17~32位和33~48位分别用二叉平衡树组织,在第四层把49~64位使用线性表组织。实验结果表明,该算法查找速度快,占用内存少,动态增量更新速度快。     

SSTT: Efficient local search for GSI global routing

In this paper, a novel global routing algorithm is presented for congestion opti-mization based on efficient local search, named SSTT (search space traversing technology). This method manages to traverse the whole search space. A hybrid optimization strategy is adopted,consisting of three optimization sub-strategies: stochastic optimization, deterministic optimiza-tion and local enumeration optimization, to dynamically reconstruct the problem structure. Thus,“transition” can be made from a local minimum point to reach other parts of the search space,traverse the whole search space, and obtain the global (approximate) optimal routing solution.Since any arbitrary initial routing solution can be used as the start point of the search, the initial-ization in SSTT algorithm is greatly simplified. SSTT algorithm has been tested on both MCNC benchmark circuits and industrial circuits, and the experimental results were compared with those of typical existing algorithms. The experimental results show that SSTT algorithm can obtain the global (approximate) optimal routing solution easily and quickly. Moreover, it can meet the needs of practical applications. The SSTT global routing algorithm gives a general-purpose routing solution.     

Genetic algorithm with iterated local search for solving a location-routing problem

This paper deals with a location routing problem with multiple capacitated depots and one uncapacitated vehicle per depot. We seek for new methods to make location and routing decisions simultaneously and efficiently. For that purpose, we describe a genetic algorithm (GA) combined with an iterative local search (ILS). The main idea behind our hybridization is to improve the solutions generated by the GA using a ILS to intensify the search space. Numerical experiments show that our hybrid algorithm improves, for all instances, the best known solutions previously obtained by the tabu search heuristic.     

求解动态需求车辆调度问题的自适应量子遗传算法

针对物流配送过程中存在的动态车辆调度问题,即带载车量约束的实时优化车辆路径问题,提出一种自适应量子遗传算法,用于最小化配送成本.根据搜索点目标函数的变化率,提出一种自适应量子旋转门更新方式,并通过子种群适应度值的变化确定量子旋转角的方向和大小,进而引导种群进化方向,提高算法的全局搜索广泛性;设计了一种变异操作,用于保持自适应量子遗传算法的种群多样性,进而提高算法全局搜索的宽泛性;引入基于两元素搜索原则的局部搜索方法来增强算法的局部优化能力.仿真实验和算法比较验证了所提算法的有效性和优越性.     

混合分散搜索算法求解带容量约束车辆路径问题

设计一种解决带容量约束车辆路径问题的混合分散搜索算法. 在基本分散搜索的基础上, 保留参考集更新策略和组合策略的全局搜索能力. 采用随机插入法作为解的多样性产生方法, 以扩大搜索空间, 避免陷入局部最优.应用简化的变邻域搜索作为改进策略进行局部开发, 引入邻域半径减少策略提高开发效率. 对改进后的新种群实施精英保留策略, 保证算法收敛. 实验结果分析表明, 混合分散搜索算法优于所对比的算法, 寻优能力可靠.

     

基于免疫Memetic算法的网络组播路由优化

为了求得代价最小的网络组播路径,提出了一种基于免疫Memetic算法的优化求解方法。算法充分结合免疫全局搜索和局部搜索机制,设计了适合组播路由问题的各种免疫算子,加快了算法的收敛速度。实验结果表明,该算法在无需备选路径集的情况下,可以较快地找到最优路径,并且算法更加简单。     

基于Tabu搜索的QoS多播路由快速优化算法

QoS多播路由算法的核心问题是建立满足QoS约束的多播树,这就是计算机网络中著名的受约束最小Steiner树问题,是一个NP完全问题.目前已有的启发式算法的时间复杂度大,不能获得最优解.提出了一个基于Tabu搜索的QoS多播路由选择快速优化算法,它选择延迟与带宽约束为QoS参数,利用Tabu搜索的集中性与广泛性并存的优点,在提高搜索速度的同时可以更加接近最优解.仿真结果表明:该算法具有快速、易实施等特点,更加适合在组规模比较大的情况下应用.     

Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem

In this paper, we develop an extended guided tabu search (EGTS) and a new heuristic packing algorithm for the two-dimensional loading vehicle routing problem (2L-CVRP). The 2L-CVRP is a combination of two well-known NP-hard problems, the capacitated vehicle routing problem, and the two-dimensional bin packing problem. It is very difficult to get a good performance solution in practice for these problems. We propose a meta-heuristic methodology EGTS which incorporates theories of tabu search and extended guided local search (EGLS). It has been proved that tabu search is a very good approach for the CVRP, and the guiding mechanism of the EGLS can help tabu search to escape effectively from local optimum. Furthermore, we have modified a collection of packing heuristics by adding a new packing heuristic to solve the loading constraints in 2L-CVRP, in order to improve the cost function significantly. The effectiveness of the proposed algorithm is tested, and proven by extensive computational experiments on benchmark instances.     

基于自适应变异的多目标鸽群优化的无人机目标搜索

无人机在搜索任务中起着关键的作用,它能够在复杂环境中寻找到目标.无人机搜索问题是一个相对复杂的多约束条件下的多目标优化问题.大多数搜索算法不能满足搜索过程中高效率和低功耗的要求.本文所采用的目标搜索方法是一种基于Agent路由和光传感器的解耦滚动时域方法.为了优化目标搜索方法的参数,本文提出一种基于Agent路由和光传感器的自适应变异多目标鸽群优化(AMMOPIO)算法.利用自适应飞行机制可以获得较好的鸽群分布,种群具有多样性和收敛性.利用变异机制简化了鸽群优化算法中的模型,提高了搜索效率.实验仿真结果验证了所提出的AMMOPIO算法在目标搜索问题中的可行性和有效性.