逻辑图自动绘制算法

研究讨论了逻辑图的自动布局、布线问题。在布局方面，以减少线交叉为优化目标，对重心布局算法＾⑴进行了几点改进；在布线方面，引入了垂直通道的概念，以减少线交叉和连线总长为优化目标，提出了一种新的布线算法，即求解线交叉最少和连接总长最短的布线算法。     

采用统一建模的拥挤度驱动三维芯片布局算法

三维芯片设计对于提高芯片性能以及减少线长显现了很好的优势,降低连线拥挤度是保证布线成功率和三维芯片实现的关键.为了解决三维芯片布局阶段的拥挤度问题,提出一种拥挤度驱动的三维芯片布局算法.该算法首先对拥挤度单元分布和线长等优化目标进行统一建模,利用二次规划求解单元位置,得到一个单元分布均匀、走线均匀以及线长优化的总体布局;然后利用拥挤度驱动的层分配算法将空间上均匀分布的单元分配到各个芯片层上;最后对各个芯片层进行详细布局,消除重叠,优化拥挤度和线长.实验结果表明,该算法能够改善走线拥挤度约15%,而线长仅有3%的增加.     

宏单元阵列自动布局算法研究

本文研究并实现了一个用于宏单元阵列的自动布局算法。算法分为初始布局及迭代改善两部分，为提高布图成功率，以线网均匀分布为目标。在初始布图中，采用自下而上结群的方式将宏单元分配到各单元行上，再进行行内定位。在改善布局中，通过对单元行内及单元行间的迭代改善，进一步降低了布线密度，优化了初始布局的结果，从而可使布图成功率得到提高。算法已用Ｃ语言实现，并应用于自动布图系统中，实验结果表明了算法的有效性。     

LowTARP:低温交替改善的模拟退火布局算法

在模拟退火算法的基础上,提出一种"低温交替改善"的FPGA布局算法.在模拟退火的低温阶段,该算法不仅交换可配置逻辑单元(CLB)的位置,也改变逻辑单元(LE)所属的CLB,即同时对布局和装箱进行优化,并采用布局的目标函数来衡量装箱的优劣.实验数据表明,采用3种不同的装箱算法的结果作为布局的输入,布线通道宽度与最具代表性的VPR布局算法相比,分别提高21.3%,15.5%和10.7%,而引入的额外计算量不到20%.     

应用于大规模集成电路非线性布局的二元结群算法

针对平面模式下非线性布局算法的设计能力远远跟不上集成电路发展速度的现状,将连接紧密的单元结合作为整体参与布局,提出一种应用于大规模非线性布局的二元结群算法,以减小电路规模和复杂度,进而提高布局算法速度、优化布局算法结果质量.该算法按2个单元之间对内连接度与对外连接度的比值排序,并按比值从大到小对单元进行结群,然后更新网表;如果其中一个单元已经被结群或是它们合并后总面积会大于目标结群面积,则放弃这2个单元的组合.将文中算法嵌入之前实现的平面非线性布局器中,可使运行时间相对于平面模式减少40％,布局结果的质量提高了12％.该布局器详细布局后的结果比当前流行的同样采用结群算法的布局器Capo,FastPlace,Fengshui和mPL5-fast算法分别优化了7％,9％,7％和5％,显示了其有效性和高效性.     

优化线长和拥挤度的增量式布局算法

随着IC技术的发展，降低连线拥挤度已经成为一个保证布线成功率的至关重要的因素．提出一种标准单元增量式布局算法C-ECOP．该算法通过一个新型的布线估计模型来精确估算布局以后的走线情况，利用力驱动的方法进行单元插入和单元推移来消除局部拥挤，同时进一步优化线长．来自美国工业界的测试实例表明，该算法能够很好地消除走线局部拥挤，同时尽量维持原有布局方案的电路性能，并且具有很高的效率．     

基于改进蚁群算法的线缆路径规划技术研究

线缆布线是复杂机电产品设计中的普遍性难题。针对线缆布局设计中存在的效率低、可靠性差等问题,提出了一种基于改进蚁群算法的线缆路径规划方法。采用分段式空间划分方法对待布线空间进行环境建模,同时对布线空间进行栅格化处理,以获取三维布线路径的规划空间。为解决基本蚁群算法在进行路径搜索时路径点容易发散的问题,引入了基于重力规则的蚁群算法路径搜索策略,提高了路径规划的真实度。在仿真实验中,将所提出的方法与基本蚁群算法进行了对比分析,验证了该算法的可行性和有效性。     

DrPlace:基于深度学习的可布线性驱动布局算法

在集成电路物理设计的布局阶段,针对基于深度学习的布局算法结果可布线性较差的问题,在开源的DREAMPlace算法的基础上提出并实现了一种基于深度学习的可布线性驱动布局算法DrPlace.算法模型在总体上设计并实现了布局器的整体框架,集成了基于深度学习的可布线性驱动总体布局、可布线性驱动的合法化和详细布局.总体布局过程中,在目标函数中加入了引脚密度函数,并实现了基于GPU的引脚密度的关键内核.在ISPD2011和DAC 2012布局实例上的实验结果表明,该算法与DREAMPlace相比在可布线性上获得了提升,且在运行时间、线长和可布线性方面均优于传统的可布线性驱动布局算法.     

基于非均匀环境建模与三阶Bezier曲线的平滑路径规划

针对工作于复杂环境下的大型工装,本文提出了一种基于非均匀环境建模与三阶Bezier曲线的平滑路径规划算法,以指导工装的运动.在环境建模方面,利用四叉树建立环境的非均匀模型,能够有效压缩环境信息,提高搜索效率;在路径搜索方面,以非均匀环境模型为基础,提出一种距离启发搜索和信息素混合更新的蚁群算法,能够得到工装的安全可行路径点;在路径平滑方面,基于三阶Bezier曲线,提出能够连接任意位置和任意方向两点的转弯单元的设计方法,利用转弯单元连接路径搜索算法得到的路径点,能够获得满足工装非完整性约束的平滑路径.最后,以大型激光驱动器的靶场环境为对象,对本文算法的有效性和可靠性进行验证,并利用DELMIA平台进一步验证了规划路径的运动平滑性和安全性.     

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

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

随程序规模动态调整的通道优化布线算法

针对常规层次型布图算法在大规模程序中布线混乱的缺点,借鉴Sugiyama层次布局算法,提出了一种随着程序规模动态调整的通道优化布线算法。通过将节点的通道数目与程序规模建立函数关系,以解决现有算法在布图时出现的线路重叠和效率低下的问题;在布图中结合广义张量平衡思想,以减少交叉并实现布图的美观性;并根据调用节点之间的相对位置关系,给出了相应的线路分配和申请策略,实现了布线的有序性。实践证明,该算法能够提高布图效率,有效地减少交叉,实现节点的有序布线和实现简单等优点。     

Top-Down Layout for Hierarchical Custom Design

Champ, a chip floor-plan program, and Alpha, an automatic cell placement and routing system, provide a method for hierarchical custom VLSI design that is highly automated and completely top-down. The system can handle standard cell blocks as well as macro cells such as RAMs, ROMs, PLAs. Champ consists of initial block placement and block packing Designers can execute initial block placement either manually or automatically using a method based on attractive-repulsive forces. Block packing is performed automatically or interactively through the moving and reshaping of blocks, which is done as the chip boundaries are being shrunk. Following the floor-plan design, Alpha automatically executes cell placement and routing. Using Champ/Alpha, only seven mandays are needed to design a 20,000-gate VLSI layout, using a predesigned standard cell library and predesigned macro cells.     

输电网接线图增量自动成图算法

输电线网接线图自动成图算法是一个非常复杂的全局优化问题.它涉及到厂站位置的自动布局和输电线路自动规划两个方面.本文给出了解决该问题的一种具体思路和算法,将该问题划分为3个部分：首先,利用力导向算法对厂站位置进行初始布局,采用模拟退火算法进行迭代计算,通过并发技术实现引力、斥力系数进行选择,得到代价最小的初始厂站初始布局.其次,利用A*算法对输电线路进行线路规划,构建了一个线路走向的代价模型,通过代价模型规范线路走向,得到美观的线路布局.最后,对布局结果评价反馈再布局,将常见的几种布局缺陷通过程序的方式进行消缺,减少人工干预.同时,本文还对历史线路和新增线路做了处理,使得算法可以实现在不改变历史厂站线路布局的情况下,对新增厂站线路进行布局规划.通过实验显示,该方法得到的图形结果满足线路规划美观,布局合理,交叉少,拐角少等优点.     

Probability based dynamic-alternate routing and the corresponding converter placement algorithm in all-optical WDM networks

This paper proposes a new dynamic-alternate routing algorithm and its corresponding converter placement algorithm in order to reduce the connection blocking probability for all-optical WDM networks. The main idea in the proposed dynamic-alternate routing algorithm is to try to route the traffics according to a predefined optimal probability distribution. The problem for finding the optimal probability distribution was shown as a convex optimization problem. The problem can be solved by flow deviation method or other standard optimization techniques. Simulation results show that the proposed routing algorithm yields lower connection blocking probabilities than the previous works. The proposed routing algorithm produces similar traffic pattern as the optimal traffic pattern. The similarity between the traffic pattern produced by the proposed dynamic-alternate routing algorithm and the optimal traffic pattern can be further employed for solving other network designing problems such as converter placement problem. Since the optimal traffic pattern can be easily predicted, the optimal traffic pattern which minimizes the blocked traffic intensity is utilized for finding the locations of wavelength converters. The key idea is to place the wavelength converters at the nodes where they are needed most. Simulations have been performed to study the performance of the proposed wavelength converter placement method. The simulation results have shown that the proposed placement method combined with the proposed probability based dynamic-alternate routing algorithm yields smaller connection blocking probability than the two converter placement methods with their corresponding alternate routing algorithms.     

GHz零时滞时钟树物理布图的虚拟通道布线算法

随着集成电路技术的发展和GHz频率的应用需求，已有的基于线长或RC延迟模型的时钟树布图算法已不能适用．针对GHz频率宏模块中时钟树的平面布图，依据流水线技术，提出一种虚拟通道布线算法；根据时钟树的拓扑结构，分别进行粗略布线和虚拟通道内的布线调整，完成时钟树的平面布线．该算法在开发软件原型ClockStar中得以应用．     

新型电路版图布局布线算法设计

调研了电路自动布局布线技术的国内外研究现状,在此基础上设计了一种面向中等规模电路布局布线算法,主要用于大型版图设计软件的模块测试环节,为用户提供各模块初步的布线布局结果,方便用户高效查找并修正错误点,填补了我国在相关领域的空白.建立了超图模型并转换为图模型,改进了Stoer-Wagner算法并利用该算法和Fiduccia-Mattheyses算法对图进行了基于最小割理论的划分,从而构建出一棵划分树.在这棵树的基础上设计了一种二元相对移动算法来确定各个电路元件的位置,大大降低了布局拥挤度,提高了美观度,对于数百元件的电路均能在0.5s内得出布局结果.基于A*算法在多个方面做了改进,提高了布线速度,对于线路数1000以下的元件能在0.1 s～60 s内得出结果,实现了100％ 布通率以及均匀的布局布线效果.     

Hierarchical spanning tree network design with Nash genetic algorithm

In this paper, we will propose a Nash genetic algorithm (Nash GA) for solving a hierarchical spanning tree network design problem, formulated as a bi-level programming problem. The proposed algorithm can be employed in designing the backbone topology in a hierarchical link-state (LS) routing domain. Because the well-designed backbone topology structure has a great impact on the overall routing performance in a hierarchical LS domain, the importance of this research is evident. The proposed algorithm is to find an optimal configuration of backbone network for backbone provider (BP) and distribution network for internet service provider (ISP), properly meeting two-aspect engineering goals: i.e., average message delay and connection costs. Also, it is assumed that there are the decision makers for BP and the decision makers for ISP join in the decision making process in order to non-cooperatively optimize the own objective function. From the experiment results, we can see clearly that our proposed algorithm can be employed in effectively designing the spanning tree network of hierarchical LS routing domain considering not only engineering aspects but also specific benefits from systematical layout of backbone network.     

Drawing layered graphs with port constraints

Complex software systems are often modeled using data flow diagrams, in which nodes are connected to each other through dedicated connection points called ports. The influence a layout algorithm has on the placement of ports is determined by port constraints defined on the corresponding node.In this paper we present approaches for integrating port constraints into the layer-based approach to graph drawing pioneered by Sugiyama et al. We show how our layout algorithm, called KLay Layered, progresses from relaxed to more restricted port constraint levels as it executes, and how established algorithms for crossing minimization and edge routing can be extended to support port constraints. Compared to the previous layout algorithms supporting ports, our algorithm produces fewer edge crossings and bends and yields pleasing results.We also explain and evaluate how layout algorithms can be kept simple by using the concept of intermediate processors to structure them in a modular way. A case study integrating our layout algorithm into UC Berkeley's Ptolemy tool illustrates how KLay Layered can be integrated into Java-based applications.     

Branch pipe routing based on 3D connection graph and concurrent ant colony optimization algorithm

Pipe routing, in particular branch pipes with multiple terminals, has an important influence on product performance and reliability. This paper develops a new rectilinear branch pipe routing approach for automatic generation of the optimal rectilinear branch pipe routes in constrained spaces. Firstly, this paper presents a new 3D connection graph, which is constructed by extending a new 2D connection graph. The new 2D connection graph is constructed according to five criteria in discrete Manhattan spaces. The 3D connection graph can model the 3D constrained layout space efficiently. The length of pipelines and the number of bends are modeled as the optimal design goal considering the number of branch points and three types of engineering constraints. Three types of engineering constraints are modeled by this 3D graph and potential value. Secondly, a new concurrent Max–Min Ant System optimization algorithm, which adopts concurrent search strategy and dynamic update mechanism, is used to solve Rectilinear Branch Pipe Routing optimization problem. This algorithm can improve the search efficiency in 3D constrained layout space. Numerical comparisons with other current approaches in literatures demonstrate the efficiency and effectiveness of the proposed approach. Finally, a case study of pipe routing for aero-engines is conducted to validate this approach.