一种采用规划方法的宏模块布局算法

提出一种基于非线性规划的宏模块布局算法。该算法将布局问题归纳为一个非线性规划问题，考虑了引脚的实际位置并使用取向向量来描述模块的取向,可以在确定模块位置的同时也确定模块的取向；同时使用交替求解的策略有效地简化了问题的求解。实验结果表明文中算法快速有效。     

生成最优单毛坯条带T型布局方式的精确算法

为解决大规模矩形件布局问题,提出一个生成单毛坯条带T型布局方式的精确算法。该算法不仅可在合理时间内取得好的优化结果,而且在满足实际下料工艺的同时化简了切割工艺。该算法首先确定最优单毛坯条带,然后通过求解一维背包问题确定单毛坯条带在级中的布局方式和级在段中的最优布局方式,最后选择两个最优段生成布局方式。通过文献中的63道基准测题,将该算法与5种著名算法(经典两阶段、普通T型、同质块两阶段、普通布局算法和启发式算法TABU500)进行了比较。实验结果表明,该算法在计算时间和材料利用率两方面都有效。     

基于位矩阵编码实现模拟集成电路模块布局的遗传算法

提出了一种新的实现模拟集成电路模块布局的遗传算法，其位矩阵编码法提高了算法的搜索效率；模块的滑行处理使绝对布局问题转变成相对布局问题，极大地减小了搜索状态空间而不降低精度；复制过程中个体间的相似性检查避免了算法的早熟收敛；目标函数覆盖了模拟集成电路的特殊要求；正交实验的方法用来研究算法参数，其最优取值由另一个衍化遗传算法确定，多种电路的测试结果表明，该算法性能优于传统的模拟退火算法，布局结果与手工布局相仿，设计效率得到显著提高。     

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

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

结合垂直通孔分配的层次式三维混合布局算法

采用层次式方法,分而治之,减小了电路的设计规模,非常适用于大规模的混合模式布局,并且在布局阶段结合了垂直通孔的分配问题.布局阶段的通孔分配问题不仅使得三维布局问题得以简化,而且为布线做好了准备,减少了后面的调整,是布线阶段垂直通孔分配问题的良好指导.提出了2种垂直通孔分配算法:比较精确的匈牙利近似算法;比较快速的邻域搜索方法.将这2种算法与层次式三维混合模式布局流程紧密结合,有效地解决了三维混合模式布局问题.     

块RAM与标准单元的混合模式布局算法

针对块RAM和标准CLB单元的电路布局问题,提出了一个新的混合模式布局算法。在标准单元采用模拟退火方式的前提下,对块RAM的布局进行算法改进。不但兼顾了块RAM的布局方式,也兼顾了原有的算法。     

生成最优同形块两阶段布局方式的确定型算法

为解决大规模二维布局问题,提出一种生成同形块两阶段布局方式的确定型算法。首先通过动态规划确定最优同形块;然后求解背包问题确定同形块在同形级中的布局方式和同形级在同形段中的最优布局方式;最后选择两个同形段生成最优同形块布局方式。通过43道基准测题,将该算法与经典两阶段和三块算法进行比较。实验结果表明,该算法不仅能满足剪切工艺,在计算时间和板材利用率上优于以上算法,而且能在合理时间内取得好的优化结果。     

一种基于约束的布局求解算法

在研究现有布局求解的基础上，提出了一个基于约束的布局求解算法，该算法借助机构分析与综合中有关自由度分析的概念，在两个层次上进行布局求解，即在高层次上对层布局顺序进行规划，而在较低层次上进行具体的数值定位，通过两层次上交替进行求解最终求得布局结果。     

面向异质结构的可重构任务在线布局算法

基于同质结构模型的可重构任务布局算法和内部资源多样的可重构器件不相适应,不利于实际运用.针对BlockRAM等静态单元在器件上的分布对硬件任务存在位置约束的问题,建立了异质结构的器件和硬件任务模型,并提出一种基于相对任务覆盖度的在线布局算法.通过为布局任务等待队列设立滑动窗口,根据窗内任务集合对器件空闲单元的相对任务覆盖度选择当前任务的放置位置,兼顾后续任务的布局需求,从而提高了整体布局效率.实验结果表明,该算法能取得较低的任务平均等待时间和较高的器件利用率,优于First Fit算法.     

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

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

分级的混合模式布局算法

针对混合模式的布局问题提出一种分级的自动布局算法.所谓混合模式就是标准单元和宏模块相结合的布局模式.该算法在模块级和单元级两个层次上完成布局.在模块级上,首先将所有随机单元划分成若干软模块,然后采用基于序列对(sequence pair,简称SP)的方法完成模块布局;在单元级上,首先对每个软模块内部采用二次规划的布局算法进行布局,然后在全芯片范围内对布局进行改善,最后采用一种基于最小割(min-cut)和枚举相结合的快速详细布局算法完成最终布局.在一组标准单元数和宏模块数不同的电路上对该算法进行了验证,效果是令人满意的.     

Development of a genetic algorithm for component placement sequence optimization in printed circuit board assembly

This paper describes the development and evaluation of a custom application exploring the use of genetic algorithms (GA) to solve a component placement sequencing problem for printed circuit board (PCB) assembly. In the assembly of PCB’s, the component placement process is often the bottleneck, and the equipment to complete component placement is often the largest capital investment. The number of components placed on a PCB can range from few to hundreds. As a result, developing an application to determine an optimal or near-optimal placement sequence can translate into reduced cycle times for the overall assembly process and reduced assembly costs. A custom application was developed to evaluate the effectiveness of using GA’s to solve the component placement sequencing problem. A designed experiment was used to determine the best representation and crossover type, crossover rate, and mutation rate to use in solving a component sequencing problem for a PCB consisting of 10 components being placed on a single-headed placement machine. Three different representations (path, ordinal, and adjacency) and six appropriate crossover types (partially mapped, ordered, cycle, classical, alternating edges, and heuristic) were evaluated at three different mutation rates and at 11 crossover rates. Two algorithm response variables, the total distance traveled by the placement head and the algorithm solution efficiency (measured as number of generations and algorithm solution time) were used to evaluate the different GA applications. The combination of representation and crossover type along with mutation rate were found to be the most significant parameters in the algorithm design. In particular, path representation with order crossover was found to produce the best solution as measured by the total distance traveled as well as the solution generation efficiency. Increasing the mutation rate led to slightly improved solutions in terms of head travel, but also resulted in increased solution time.     

A hybrid genetic algorithm for component sequencing and feeder arrangement

This paper presents a hybrid genetic algorithm to optimize the sequence of component placements on a printed circuit board and the arrangement of component types to feeders simultaneously for a pick-and-place machine with multiple stationary feeders, a fixed board table and a movable placement head. The objective of the problem is to minimize the total traveling distance, or the traveling time, of the placement head. The genetic algorithm developed in the paper hybridizes different search heuristics including the nearest neighbor heuristic, the 2-opt heuristic, and an iterated swap procedure, which is a new improving heuristic. Compared with the results obtained by other researchers, the performance of the hybrid genetic algorithm is superior to others in terms of the distance traveled by the placement head.     

一种面向并行设计规划的快速布局模型与算法

面向并行设计规划的快速布局是高性能计算机概念设计不可缺少的重要手段,布局目标、布局对象、布局结果等方面的特殊性,决定了传统布局方法难以满足并行设计规划需求。针对巨型机概念设计需求,在传统芯片级与系统级布局规划方法基础上,提出一种面向并行设计规划的快速布局模型与算法。该算法是基于有向图分解模型的分级布局算法,将定时驱动布局思想引入结群过程,是集定时驱动布局、基于结群的布局、基于划分的布局和有向图分解为一体的快速布局算法。该算法被成功应用到某巨型机概念设计的并行设计规划过程。     

面向多类型传感器优化布置的结构响应重构

提出了利用逐步消去法(backward sequential algorithm, BSA)、萤火虫算法(firefly algorithm, FA)分别和类卡尔曼滤波算法(excitation identification Kalman filter, EIKF)结合,以结构响应重构为目标,对不同类型传感器同时进行位置优化的方法.通过对萤火虫算法进行二进制编码,使其能够解决传感器优化布置问题;以结构响应重构误差方差平均值为目标,以离散萤火虫算法和逐步消去法为求解方法实现传感器位置的优化;利用预测的状态向量值对激励和感兴趣位置处的结构响应进行重构.用一个二维桁架模型来验证所提出方法的实用性和有效性.数值算例结果表明,利用两种方法得到的优化位置处的测量信息求得的重构激励和响应与理论值能够很好地吻合,对比验证了两种方法的有效性.     

A multi-step standard-cell placement algorithm of optimizing timing and congestion behavior

The timing behavior and congestion behavior are two important goals in the performance-driven standard-cell placement. In this paper, we analyze the relationship between the timing and congestion behavior. We bring up a multi-step placement algorithm to reach the two goals. First, the timing-driven placement algorithm is used to find the global optimal solution. In the second step, the algorithm tries to decrease the maximum congestion while not deteriorating the timing behavior. We have implemented our algorithm and tested it with real circuits. The results show that the maximum delay can decrease by 30% in our timing-driven placement and in the second step the maximum congestion will decrease by 10% while the timing behavior is unchanged.     

VLSI定时驱动布局算法

定时驱动布局算法是改善ＶＬＳＩ性能的重要措施，现有算法主要建立在面向网络和面向通路两种技术之上，仅获得局部最优解．本文以获得全局最优解为目标，从电路逻辑结构和传输延时出发，提出了面向电路最大延时的布局算法．实验表明，本算法是有效的．     

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

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