Combining the ant system algorithm and simulated annealing for 3D/2D fixed-outline floorplanning

Three dimensional integrated circuits (3D ICs) can alleviate the problem of interconnection, a critical problem in the nanoscale era, and are also promising for heterogeneous integration. This paper proposes a two-phase method combining the ant system algorithm (AS) and simulated annealing (SA) to handle 3D IC floorplanning with fixed-outline constraints. In the first AS phase, the floorplans are constructed by sequentially packing the block one by one, and the AS is used to explore the appropriate packing order and device layer assignment for the blocks. When packing a block, a proper position including the coordinates and the appropriate layer in the partially constructed floorplan should be chosen from all possible positions. While packing the blocks, a probability layer assignment strategy is proposed to determine the device layer assignment of unpacked blocks. After the AS phase, the SA phase is used to perform further optimization. The proposed method can also be easily applied to 2D floorplanning problems. Compared with the state of the art 3D/2D fixed-outline floorplanner, the experimental results demonstrate the effectiveness of the proposed method.     

利用公共子序列求解固定边框布图问题

提出一种新的固定边框的布图算法．该算法采用SP表示方法,以公共子序列为基础,在随机搜索过程中限定布图宽度的变化,从而使减小芯片面积的目标与固定边框的目标在一定程度上取得一致．与现有的固定边框布图算法相比,文中算法在边框更紧凑、宽长比更大的条件下具有更高的成功率和更短的运行时间．此外,文中算法在布图初始阶段就可以对固定边框的合理性进行评估,避免了因给定的边框不合理而带来的时间上的浪费．     

一种有效的面向软模块的VLSI布图规划算法

随着VLSI设计规模和复杂度的提高,以可复用IP为代表的软模块得到了广泛的应用,针对软模块的布图规划问题随之变得日益重要。基于正则波兰表达式（NPE）表示,提出了一种形状曲线相加算法来处理软模块之间的组合运算,可获得每个布图解下最优的布图实现。通过回溯算法来确定每个模块的位置及形状,并将它们集成到模拟退火算法的流程之内。应用MCNC和GSRC电路对算法进行了测试,结果表明该算法解决软模块的布图规划问题是可行和有效的。     

Fixed-outline floorplanning using robust evolutionary search

Typical floorplanning concerns a series of objectives, such as area, wirelength, and routability, etc., with various aspect ratios of modules in a free-outline regime. However, in a hierarchical design flow for very large ASICs and SoCs, a floorplan can be completely useless for a situation where its outline is dissatisfied. In this paper, we study the fixed-outline floorplanning problem that is more applicable to the hierarchical design style. We develop an efficient algorithm based on robust evolutionary search and achieve substantially improved success rate. We also propose a new approach to handle soft modules to further adjust the generated floorplan to fit into the prescribed chip outline. The effectiveness of our methods is demonstrated on several large cases of MCNC and GSRC benchmarks.     

矩形件优化排样问题的混合遗传算法求解

利用遗传算法结合剩余矩形排样法求解矩形件正交排样问题。通过遗传算法将矩形件正交排样问题转化为一个排列问题,并引入剩余矩形排样算法来惟一确定每一个排列所对应的排样图(即排样方案),两者结合用于求解矩形件排样问题。最后用此混合遗传算法对文献[1]中的两个算例进行了验证,表明了其有效性。     

基于改进最低水平线方法与遗传算法的矩形件排样优化算法

传统的最低水平线方法用于矩形件排样时可能产生较多未被利用的空白区域,造 成不必要的材料浪费。针对此缺陷,在搜索过程中引入启发式判断,实现空白区域的填充处理, 提高板材利用率。在应用遗传算法优化矩形件排样顺序时,在进化过程中采用分阶段设置遗传 算子的方法,改善算法的搜索性能与效果。通过改进最低水平线方法与基于分阶段遗传算子的 遗传算法相结合,共同求解矩形件排样问题。排样测试数据表明,所提出的矩形件排样优化算 法能够有效改善排样效果,提高材料利用率。     

基于改进遗传算法的矩形件优化排样

论文利用遗传算法结合剩余矩形排样法求解矩形件正交排样问题。通过对排样问题已知解信息进行统计分析,并根据分析结果改进原遗传算法判断个体好坏的标准,对父代种群进行了优劣分类,针对不同的分类采用不同的遗传操作,构造出一种改进遗传算法。通过实例验证,该算法得到了排样问题的最优解,说明了其有效性。     

Constraint partitioning in penalty formulations for solving temporal planning problems

In this paper, we study the partitioning of constraints in temporal planning problems formulated as mixed-integer nonlinear programming (MINLP) problems. Constraint partitioning is attractive because it leads to much easier subproblems, where each is a significant relaxation of the original problem. Moreover, each subproblem is very similar to the original problem and can be solved by any existing solver with little or no modification. Constraint partitioning, however, introduces global constraints that may be violated when subproblems are evaluated independently. To reduce the overhead in resolving such global constraints, we develop in this paper new conditions and algorithms for limiting the search space to be backtracked in each subproblem. Using a penalty formulation of a MINLP where the constraint functions of the MINLP are transformed into non-negative functions, we present a necessary and sufficient extended saddle-point condition (ESPC) for constrained local minimization. When the penalties are larger than some thresholds, our theory shows a one-to-one correspondence between a constrained local minimum of the MINLP and an extended saddle point of the penalty function. Hence, one way to find a constrained local minimum is to increase gradually the penalties of those violated constraints and to look for a local minimum of the penalty function using any existing algorithm until a solution to the constrained model is found. Next, we extend the ESPC to constraint-partitioned MINLPs and propose a partition-and-resolve strategy for resolving violated global constraints across subproblems. Using the discrete-space ASPEN and the mixed-space MIPS planners to solve subproblems, we show significant improvements on some planning benchmarks, both in terms of the quality of the plans generated and the execution times to find them.     

A modified simulated annealing algorithm and an excessive area model for floorplanning using fixed-outline constraints

Outline-free floorplanning focuses on area and wirelength reductions, which are usually meaningless, since they can hardly satisfy modern design requirements. We concentrate on a more difficult and useful issue, fixed-outline floorplanning. This issue imposes fixed-outline constraints on the outline-free floorplanning, making the physical design more interesting and challenging. The contributions of this paper are primarily twofold. First, a modified simulated annealing (MSA) algorithm is proposed. In the beginning of the evolutionary process, a new attenuation formula is used to decrease the temperature slowly, to enhance MSA’s global searching capacity. After a period of time, the traditional attenuation formula is employed to decrease the temperature rapidly, to maintain MSA’s local searching capacity. Second, an excessive area model is designed to guide MSA to find feasible solutions readily. This can save much time for refining feasible solutions. Additionally, B*-tree representation is known as a very useful method for characterizing floorplanning. Therefore, it is employed to perform a perturbing operation for MSA. Finally, six groups of benchmark instances with different dead spaces and aspect ratios—circuits n10, n30, n50, n100, n200, and n300—are chosen to demonstrate the efficiency of our proposed method on fixed-outline floorplanning. Compared to several existing methods, the proposed method is more efficient in obtaining desirable objective function values associated with the chip area, wirelength, and fixed-outline constraints.     

A new variable-sized bin packing problem

The problem of BLASTing a genome against a database of DNA sequences to identify potential relationships with other genomes can be divided into subproblems quite naturally. We consider a setting where the problem is distributed to PCs having idle time. This results in a new variant of bin packing, where a rectangle is divided into smaller rectangles that are to be packed in variable-sized bins which arrive on-line. A rectangle fits in a bin, if the sum of its height and width is no more than the size of the bin. The goal is to minimize the total size of the bins used for packing the entire rectangle.     

基于蚁群优化算法求解矩形件排样问题

布局问题来源于生产实际,优秀的布局可以提高原料利用率,降低成本,提高经济效益,对许多行业有重要意义。矩形件优化排样是一类具有NP完全难度的组合优化问题。人工蚁群算法是对蚂蚁群体行为的模拟抽象,该算法具有分布计算、信息正反馈和启发式搜索等特点。本文将蚁群算法和剩余矩形法结合用于解决矩形排样问题,首先用蚁群算法将矩形件排样问题转化为一个排列问题;然后通过剩余矩形排样算法排出每一个排列所对应的排样图;最后用算法对文献[9]中的两个算例进行了验证,表明了其有效性。     

Maximizing the Total Profit of Rectangles Packed into a Rectangle

We consider the following rectangle packing problem. Given a set of rectangles, each of which is associated with a profit, we are requested to pack a subset of the rectangles into a bigger rectangle so that the total profit of rectangles packed is maximized. The rectangles may not overlap. This problem is strongly NP-hard even for packing squares with identical profits. We first present a simple (3 + ε)-approximation algorithm. Then we consider a restricted version of the problem and show a (2 + ε)-approximation algorithm. This restricted problem includes the case where rotation by 90° is allowed (and is possible), and the case of packing squares. We apply a similar technique to the general problem, and get an improved algorithm with a worst-case ratio of at most 5/2 + ε. Finally, we devise a (2 + ε)-approximation algorithm for the general problem.     

带静不平衡约束的正交矩形布局问题的启发式模拟退火算法*

以卫星舱布局为背景,研究一类带静不平衡约束的正交矩形布局问题.借鉴拟物策略,定义矩形与矩形、矩形与圆形容器之间的嵌入度计算公式,将该问题转变为无约束的优化问题.通过将启发式格局更新策略、基于梯度法的局部搜索机制与具有全局优化功能的模拟退火算法相结合,提出一种求解带静不平衡约束的正交矩形布局问题的启发式模拟退火算法.算法中的启发式格局更新策略产生新格局和跳坑,梯度法搜索新格局附近能量更低的格局.另外,在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项,并采用质心平移的方法,使布局系统的静不平衡量达到约束要求.实验表明,文中算法是一种解决带静不平衡约束的正交矩形布局问题的有效算法.     

A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem

The rectangle knapsack packing problem is to pack a number of rectangles into a larger stock sheet such that the total value of packed rectangles is maximized. The paper first presents a fitness strategy, which is used to determine which rectangle is to be first packed into a given position. Based on this fitness strategy, a constructive heuristic algorithm is developed to generate a solution, i.e. a given sequence of rectangles for packing. Then, a greedy strategy is used to search a better solution. At last, a simulated annealing algorithm is introduced to jump out of the local optimal trap of the greedy strategy, to find a further improved solution. Computational results on 221 rectangular packing instances show that the presented algorithm outperforms some previous algorithms on average.     

基于稀疏正则优化的图像复原算法

为提高图像复原的速度,改进图像复原的质量,提出一种新算法。将图像复原表示为一类标准的优化问题,采用交替最小化把该优化问题分解为等价的两个子问题。通过迭代求解这两个子问题,获得图像复原问题的解。在此迭代过程中,引入迭代软阈值法处理图像降噪子问题。实验对不同类型的模糊图像进行了复原,其结果验证了算法的有效性。与多级阈值Landweber(MLTL)算法和快速收缩阈值算法(FISTA)相比,处理相同图像时,所提算法可分别节省28%和71%的时间,同时复原图像的信噪比(SNR)可提高0.7~3.5dB。     

A Best-first Branch-and-bound Algorithm for Orthogonal Rectangular Packing Problems

In this paper we discuss the problem of packing a set of small rectangles (pieces) in an enclosing final rectangle. We present first a best-first branch-and-bound exact algorithm and second a heuristic approach in order to solve exactly and approximately this problem. The performances of the proposed approaches are evaluated on several randomly generated problem instances. Computational results show that the proposed exact algorithm is able to solve small and medium problem instances within reasonable execution time. The derived heuristic performs very well in the sense that it produces high-quality solutions within small computational time.     

一种改进的矩形件优化排样近似算法

分析了传统矩形件优化排样近似算法的主要缺陷，并在此基础上提出了一个改进算法，运用该算法获得了比原算法更好的优化排样结果。     

Use of Genetic Algorithms for Solution of the Rectangle Packing Problem

This paper deals with the problem of packing of rectangles in a given rectangle. Genetic algorithms are proposed for solving the problem. Some details of realization of the approach proposed are given and a high efficiency of the method of genetic algorithms is illustrated by two examples.     

求解二维矩形Packing面积最小化问题的动态归约算法

二维矩形Packing 面积最小化问题(rectangle packing area minimization problem,简称RPAMP)是具有NP难度的高复杂度的布局优化问题,也是大规模集成电路设计中floorplanning 问题的一个核心问题.通过动态构造矩形框的宽和高,将求解一个RPAMP 转化为求解一组二维矩形Packing 判定问题(rectangle packing decision problem,简称RPDP).在求解RPDP 的最大适配度算法的基础上,进一步考虑了当前动作对全局紧凑性的影响,评估了当前动作对局部空间的损害程度,设计了求解RPDP 的最小损害度算法.然后,结合矩形框宽、高的动态构造方法,设计得到求解RPAMP 的最终算法.对15 个相关的RPAMP 算例(包括著名的MCNC 算例和GSRC 算例)进行了测试.更新了其中9 个算例的最好记录,另有2 个与当前的最好记录持平.得到了98.50%的平均填充率,将国内外文献中已见报道的最高平均填充率提高了0.85%.     

Hierarchical congregated ant system for bottom-up VLSI placements

A new perturbation method, called Hierarchical-Congregated Ant System (H-CAS) has been proposed to perform the variable-order bottom-up placement for VLSI. H-CAS exploits the concept of ant colonies, where each ant will generate the perturbation based on differences in dimensions of the VLSI modules in hard modules floorplanning and differences in area of the VLSI modules in soft modules floorplanning. In this paper, it is mathematically proved that the area-based two-dimensional cost function for hard modules floorplanning problem can be reduced to the difference-based one dimensional cost function which avoids local optima problems. Lack of global view is a major drawback in the conventional bottom-up hierarchy, and hence, ants in the H-CAS are made to introduce global information at every level of bottom-up hierarchy. A new relative whitespace formula for bottom-up hierarchy is derived mathematically and the H-CAS embeds it in its unique update formula. The ants in H-CAS are able to communicate among themselves and update the pheromone trails when they reach the destination. Then, the ants will congregate, share their experiences and construct a new pheromone trails that belong to this newly constructed group. The congregation of at least two ants and/or ant consortiums would lead to reduction in subsequent search space and complexity. H-CAS gives the best-so-far near optimal solutions and yields low standard deviations of areas involving 9–600 blocks based on Microelectronics Center of North Carolina (MCNC) and Giga scale Systems Research Center (GSRC) benchmarks. The results obtained establish that H-CAS is a high performance placer in respect of scaling, convergence, precision, stability, and reliability. The above claims are based on the comparisons with the other floorplanning algorithms as depicted graphically.