LSI/VLSI的任意元胞K行安置的算法

本文提出一种适用于LSI/VLSI任意元胞布局的K行安置的算法。当矩形单元的拓朴位置确定后,每个单元有横放、竖放两个态共有2n个态。在K行安置时,从这2n个态中选出包络矩形面积最小的问题,可归结为求n个态中的包络矩形面积最小,所以是很有效的算法。可以和结群法混合使用;在一定条件下,还可以直接用于准BBL布局。     

An algorithm ofk-line location for BBL in LSI/VLSI

In this paper, aK-line location algorithm for building block cells in LSI/VLSI is presented. When the relative positions of rectangular cells are given, there are 2 states according to the two orientations of a cell. It is proved that to find the optimum solution from the 2^N states can be reduced to calculate theN states inK-line algorithm. So the algorithm is shown very effective and can be used with association for cluster method in BBL placement. Under certain conditions, this method can also be used to pesudo BBL placement directly.     

基于BSG的时延驱动布局

本文采用BSG (bounded slicing grid) 结构对时延驱动 (timing driven) 或称为性能驱动 (performance driven)布局问题进行了研究和实现,此算法是一种Non-slicing的面向路径的时延优化BBL (Building Block Layout),算法思路简洁,易于实现,实验效果令人满意。     

基于BSG模型的BBL布局

布局是VLSI物理设计的关键步骤之一.对于一般的BBL布局,一个基本问题是如何对布局问题的解进行有效的表示,文献[1]提出了BSG模型并对non-slicing结构的BBL布局进行了成功的表示.文章对BSG模型进行了研究和实现,并在用模拟退火算法实现过程中进行了搜索策略的改进,得到了较好的实验结果.     

混合模拟退火算法解决VLSI布局问题

VLSI布局问题是集成电路物理设计过程中的关键步骤，它直接影响整个设计的成败。Slicing结构是一种简单而高效的布局表示方法，采用正则波兰表达式编码，将模拟退火与禁忌搜索算法结合形成了一种以模拟退火算法为基础的混合算法进行求解，用MCNC benchmarks进行实验，结果表明：文章提出的混合算法比模拟退火算法在求解效率和质量上都有较大的提高。     

具有多目标形状选择的布局方法

本文简述具有多目标形状选择的布局算法,包括结群树的形成、多目标形状的产生及目标函数的选择、布局过程简介以及本算法思想对BBL布局的贡献。文章同时给出本算法对benchmark,工业界及我们选用的实例的运行结果,并和美国U.C.Berkeley的BEAR系统进行了比较。结果表明,本算法无论在质量上或是在速度上,都是令人满意的。本布局系统已于1989年12月在国家攻关项目PANDA系统上,用C语言编程,在SUN、HP、GPX、VAX等机器上实现。     

Placement algorithm for the optimal synthesized design of CMOS logic cells

A systematic placement algorithm is described for the design of CMOS logic cells. Unlike the other placement algorithms that apply only to NAND/NOR circuits or that are very time consuming, the proposed algorithm applies to any kind of CMOS circuit, and has no restriction as to the NAND/NOR circuits. Furthercmore, it applies to both planar and non-planar circuits. In addition, since a very efficient graph-theoretic approach is used as a constructive algorithm which generates a near optimal initial placement combined with an iterative approach by simulated annealing, an optimum result can be obtained in less time. The layout style of a transistor chain is used which, in conjunction with the optimal synthesized design approach using switching network logic, constitutes a systematic method for the design automation of high-speed VLSI circuits.     

标准单元模式下的一种快速增量式布局算法

增量式布局是适应高性能设计要求的一种新的布局模式 .它针对电路更改 ,局部地调整单元位置 ,重新获得合理的布局 .本文提出了一种标准单元模式下的快速增量布局算法 .算法采用单元行划分的方法处理布局约束 ,然后将布局调整归结为单元依次插入单元行的问题 ,并构造了一个数学规划求解最佳的插入方案 .同时提出了复杂度为O(n)的双对角线搜索法求解这个特殊的数学规划 .实际电路测试表明算法高效而稳定 ,比简单的启发式算法快十倍 ,并使布局修改减少 2 0 %以上     

大规模混合模式初始详细布局算法

以大规模混合模式布局问题为背景 ,提出了有效的初始详细布局算法 .在大规模混合模式布局问题中 ,由于受到计算复杂性的限制 ,有效的初始布局算法显得非常重要 .该算法采用网络流方法来满足行容量约束 ,采用线性布局策略解决单元重叠问题 .同时 ,为解决大规模设计问题 ,整体上采用分治策略和简化策略 ,有效地控制问题的规模 ,以时间开销的少量增加换取线长的明显改善 .实验结果表明该算法能够取得比较好的效果 ,平均比 PAFL O算法有 1 6 %的线长改善 ,而 CPU计算时间只有少量增加     

大规模混合模式初始详细布局算法

以大规模混合模式布局问题为背景,提出了有效的初始详细布局算法.在大规模混合模式布局问题中,由于受到计算复杂性的限制,有效的初始布局算法显得非常重要.该算法采用网络流方法来满足行容量约束,采用线性布局策略解决单元重叠问题.同时,为解决大规模设计问题,整体上采用分治策略和简化策略,有效地控制问题的规模,以时间开销的少量增加换取线长的明显改善.实验结果表明该算法能够取得比较好的效果,平均比PAFLO算法有16%的线长改善,而CPU计算时间只有少量增加.     

Hybrid genetic-paired-permutation algorithm for improved VLSI placement

This paper addresses Very large-scale integration (VLSI) placement optimization, which is important because of the rapid development of VLSI design technologies. The goal of this study is to develop a hybrid algorithm for VLSI placement. The proposed algorithm includes a sequential combination of a genetic algorithm and an evolutionary algorithm. It is commonly known that local search algorithms, such as random forest, hill climbing, and variable neighborhoods, can be effectively applied to NP-hard problem-solving. They provide improved solutions, which are obtained after a global search. The scientific novelty of this research is based on the development of systems, principles, and methods for creating a hybrid (combined) placement algorithm. The principal difference in the proposed algorithm is that it obtains a set of alternative solutions in parallel and then selects the best one. Nonstandard genetic operators, based on problem knowledge, are used in the proposed algorithm. An investigational study shows an objective-function improvement of 13%. The time complexity of the hybrid placement algorithm is O(N²).     

Optimization-based placement algorithm for BiCMOS leaf cellgeneration

We present a transistor placement algorithm for the automatic layout synthesis of logic and interface cells comprised of a mixture of MOS and bipolar devices. Our algorithm is applicable to BiCMOS logic cells, ECL logic cells as well as TTL, CMOS and ECL compatible input/output (I/O) cells. The transistor placement problem is transformed into a layout floorplan design problem with a mixture of rigid and flexible modules. A constructive “branch-and-bound” algorithm is used to minimize the area of synthesized circuits subject to pre-placement constraints. Experimental results indicate that the algorithm can produce efficient placements under fixed-height constraints. The design space exploration mechanism can be controlled by the user so as to apportion computing resources judiciously     

Optimizing Data Placement of Loops for Energy Minimization with Multiple Types of Memories

Strict real-time processing and energy efficiency are required by high-performance Digital Signal Processing (DSP) applications. Scratch-Pad Memory (SPM), a software-controlled on-chip memory with small area and low energy consumption, has been widely used in many DSP systems. Various data placement algorithms are proposed to effectively manage data on SPMs. However, none of them can provide optimal solution of data placement problem for array data in loops. In this paper, we study the problem of how to optimally place array data in loops to multiple types of memory units such that the energy and time costs of memory accesses can be minimized. We design a dynamic programming algorithm, Iterational Optimal Data Placement (IODP), to solve data placement problem for loops for processor architectures with multiple types of memory units. According to the experimental results, the IODP algorithm reduced the energy consumption by 20.04 % and 8.98 % compared with a random memory placement method and a greedy algorithm, respectively. It also reduced the memory access time by 19.01 % and 8.62 % compared with a random memory placement method and a greedy approach.     

An efficient heuristic force directed placement algorithm based on partitioning

An efficient heuristic force directed placement algorithm based on partitioning is proposed for very large-scale circuits. Our heuristic force directed approach provides a more efficient cell location adjustment scheme for iterative placement optimization than the force directed relaxation (FDR) method. We apply hierarchical partitioning based on a new parallel clustering technique to decompose circuit into several level sub-circuits. During the partitioning phase, a similar technique to ‘terminal propagation’ was introduced so as to maintain the external connections that affect cell adjustment in sub-circuit. In these lowest level sub-circuits, the heuristic force directed algorithm is used to perform iterative placement optimization. Then each pair of sub-circuits resulted from bisection combine into a larger one, in which cells are located as the best placement state of either sub-circuits. The bottom-up combination is done successively until back to the original circuit, and at each combination level the heuristic force directed placement algorithm is used to further improve the placement quality. A set of MCNC (Microelectronics Centre of North-Carolina) standard cell benchmarks is experimented and results show that our placement algorithm produces on average of 12% lower total wire length than that of Feng Shui with a little longer CPU time.     

Two-Phase Fine-Grain Sleep Transistor Insertion Technique in Leakage Critical Circuits

Sleep transistor (ST) insertion is a valuable leakage reduction technique in circuit standby mode. Fine-grain sleep transistor insertion (FGSTI) makes it easier to guarantee circuit functionality and improve circuit noise margins. In this paper, we introduce a novel two-phase FGSTI technique which consists of ST placement and ST sizing. These two phases are formally modeled using mixed integer linear programming (MILP) models. When the circuit timing relaxation is not large enough to assign ST everywhere, leakage feedback (LF) gates, which are used to avoid floating states, induce large area and dynamic power overhead. An extended multi-object ST placement model is further proposed to reduce the leakage current and the LF gate number simultaneously. Finally, heuristic algorithms are developed to speed up the ST placement phase. Our experimental results on the ISCAS'85 benchmarks reveal that: 1) the two-phase FGSTI technique achieves better results than the simultaneous ST placement and sizing method; 2) when the circuit timing relaxation varies from 0% to 5%, the multi-object ST placement model can achieve on average 4 $times$-9 $times$ LF gate number reduction, while the leakage difference is only about 8% of original circuit leakage; 3) our heuristic algorithm is 1000 $times$ faster than the MILP method within an acceptable loss of accuracy.      

一种动态密度和约束的四边布线程序

本文介绍一种新的四边通道布线器(DDCR),该布线器基于启发式原则提出,并应用动态布线密度和约束图完成线网定序和连线段选择。DDCR是H/V方式布线,该程序由C语言写成,运行于VAX11/780VMS下,可与BBL2布图系统配套使用,通过对许多例子试验,其效果是满意的。     

Design and Analysis of Circular Microstrip Patch Antenna for White Space TV Band Application

The wide range of wireless sensor network applications has made it an interesting subject for many studies. One area of research is the controlled node placement in which the location of nodes is not random but predetermined. Controlled node placement can be very effective when either the price of the sensor nodes is high or the sensor coverage is of a specific type and it is necessary to provide special characteristics such as coverage, lifetime, reliability, delay, efficiency or other performance aspects of a wireless sensor network by using the minimum number of nodes. Since node placement algorithms are NP-Hard problems, and characteristics of a network are often in conflict with each other, the use of multi-objective evolutionary optimization algorithms in controlled node placement can be helpful. Previous research on node placement has assumed a uniform pattern of events, but this study shows if the pattern of events in the environment under investigation is geographically dependent, the results may lose their effectiveness drastically. In this study, a controlled node placement algorithm is proposed that aims to increase network lifetime and improve sensor coverage and radio communication, assuming that the event pattern is not uniform and has a geographical dependency. The proposed placement algorithm can be used for the initial placement or, for repairing a segmented network over time. In this study, multi-objective evolutionary optimization algorithms based on decomposition (MOEA/D) have been used, and the performance results have been compared with other node placement methods through simulation under different conditions.

     

一种新的标准单元增量式布局算法

提出了一种新的增量式布局方法W-ECOP来满足快速调整布局方案的要求.与以前的以单元为中心的算法不同,算法基于单元行划分来进行单元的插入和位置调整,在此过程中使对原布局方案的影响最小,并且尽可能优化线长.一组从美国工业界的测试例子表明,该算法运行速度快,调整后的布局效果好.     

基于核心生长-力矢量算法的门阵列布局

结合核心生长和力矢量算法的思想,构成核心生长-力矢量(CGFD)算法来实现门阵列模式布局.其中,先利用核心生长将核心单元安置在布局的中心位置,再分别以核心单元为中心,在它们周围放置与之联系紧密的次核心单元,依次类推以减少连线长度;同时运用力矢量法,计算单元之间的拉力,使所受合力最小,从而较大地改善布局结果.实验表明,此算法可行,且对于门阵列布局问题性能优越.