VLSI电路划分问题的分散搜索算法

电路划分是超大规模集成电路(VLSI)设计自动化中的一个关键阶段,是NP困难的组合优化问题.本文把基于顶点移动的Fiduccia-Mattheyses(FM)算法结合到分散搜索算法框架中,提出了电路划分的分散搜索算法.算法利用FM算法进行局部搜索,利用分散搜索的策略进行全局搜索.为满足该方法对初始解的质量和多样性的要求,采用贪心随机自适应搜索过程(GRASP)和聚类相结合的方法产生初始解.实验结果表明,算法可以求解较大规模的电路划分实例,且与基于多级框架的划分算法hMetis相比,划分的质量有明显的提高.     

一种新的基于晶体管级的电路划分算法

随着VLSI电路规模的不断增加,为实现电路并行仿真所做的电路划分算法的质量显得日益重要。鉴于现有算法未能同时保证均衡的分块间规模和最少的互联信号数目,该文提出了一种新的基于晶体管级的电路划分算法。该算法首先通过一个聚合过程对电路网表进行分割,得到一个比较好的初始分割;然后通过平衡分块间规模差异和进一步优化分块间互连线的数目,最终得到理想的电路划分结果。应用该电路划分算法对工业界的实际电路网表进行测试,结果表明:相比于目前普遍使用的COPART算法,该算法在分块间规模的均衡性方面平均改善了25%,在分块间的互联信号数目方面平均减少了18%。     

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.     

一种VLSI设计到赋权超图的转换系统

本文基于VLSI划分问题的需要,提出了一种VLSI设计到赋权超图转换算法.该算法解决的关键问题是,它读取和遍历Verilog语言描述的树状结构VLSI设计,将其转换为赋权超图并存储为指定的文件存储格式,从而有效地将VLSI划分问题转换为超图划分优化问题.进而,本文给出了VLSI设计到赋权超图的转换系统（VLSI/Hypergraph Converter,VHC）的处理流程图,并在Windows平台下用C＋＋设计实现了VHC系统.实验及分析表明,该系统能正确地将Verilog语言描述的门级CPU测试用例转换为赋权超图,避免了直接在VLSI线网上进行划分,提高了VLSI划分的效率.     

基于细胞神经网络的从阴影恢复形状的新方法

细胞神经网络(CNN)是一种实时处理信号的大规模非线性模拟电路,它的连续时间特点以及局部互连特点使其可以进行并行计算,并且非常适用于超大规模集成电路(VLSI)的实现.本文针对从阴影恢复形状(SFS)问题,提出了一种基于硬件退火CNN的能量函数优化方法,并对该方法进行了详细分析,给出了实例的仿真结果,验证了该方法的有效性.该方法为并行处理算法,具有运算量小、易于大规模VLSI集成实现,且能够克服局部极小等优点,可以使SFS问题得到实时的处理.     

适用于数字电路的通用多块划分算法

本文提出了一个通用数字电路的多块划分的算法。该算法能适用于不同的优化目标函数。我们在基于组迁移算法线模型基础上，在费用函数中引进一个有效的离散罚函数以考虑单元移动的潜在增益，使新算法较原来的Ｆ－Ｍ算法有较大的提高，同时还一定程度上减少了组迁移算法所固的漂移性。     

一种应用于二次布局的有效划分方法

提出了一种基于二次布局的结合MFFC结群和h METIS划分的算法.实验表明:这种方法能得到很好的布局结果,但是运行消耗的时间比较长.为了缩短划分在二次布局中运行的时间,提出了一种改进的结群算法IMF-FC,用它在二次布局中做划分.与前者相比较,这种方法虽然布局质量稍差,但速度更快.     

一种应用于二次布局的有效划分方法

提出了一种基于二次布局的结合MFFC结群和hMETIS划分的算法.实验表明:这种方法能得到很好的布局结果,但是运行消耗的时间比较长.为了缩短划分在二次布局中运行的时间,提出了一种改进的结群算法IMFFC,用它在二次布局中做划分.与前者相比较,这种方法虽然布局质量稍差,但速度更快.     

An iterative approach to VLSI circuit lifetime estimation

In this paper, the problem of VLSI circuit lifetime estimation is discussed. It is shown that lifetime determination is equivalent to finding the smallest zero of a continuous non-differentiable function for a specific circuit realization. An iterative multiple cubic spline approximation algorithm is proposed to determine the lifetime. Application in VLSI circuit analysis is given, in which the degradation resulting from the hot electron effects are considered. The results show that our proposed approach is efficient.     

BiCMOS dynamic minimum circuit using a parallel comparison algorithm for fuzzy controllers

A BiCMOS dynamic minimum circuit using a parallel comparison algorithm for the VLSI implementation of fuzzy controllers is presented. Using BiCMOS dynamic circuits and a parallel comparison algorithm a four 4-bit-input minimum circuit, designed based on a 2 mu m BiCMOS technology shows a 7.4 ns comparison time, which is a *3 improvement in speed as compared with the CMOS circuit. In addition, this circuit has an expansion capability for realising large-scale minimum circuits.<>     

Automatic layout synthesis of analog ICs using circuit recognition and constraint analysis techniques

A systematic method for automatic layout synthesis of analog integrated circuit modules is presented. This method uses analog circuit recognition and critical net analysis techniques to derive proper layout constraints for analog circuit performance optimization. These layout constraints are analyzed and prioritized according to the recognized analog circuit topologies and classified net sensitivities. The weighted constraints are then used to drive the physical layout generation process to obtain a high-quality custom circuit layout. An efficient, constraint-driven analog floorplanning technique based on a zone-sensitivity partitioning algorithm is specially developed to generate a slicing floorplan incorporating the layout constraints. This layout synthesis approach has three key advantages. First, it can produce a satisfactory analog circuit performance with negligible degradation due to the layout-introduced parasitic effects. Second, it allows a complete automation for netlist-to-layout synthesis so that the layout tool can be used by VLSI system designers. Finally, this method is quite general and can be applied to handle a wide variety of analog circuits. Experimental results in CMOS operational amplifiers and a comparator are presented.     

Built-in test for complex digital integrated circuits

A method for testing the logic function of complex digital integrated circuits is presented. The extra hardware needed is kept minimal by functional conversion of already existing components (e.g., registers). The feasibility of the proposed method is demonstrated by results from both hardware simulation and logic simulation. The method is based on an adapted version of signature analysis, and on circuit partitioning (the structure of VLSI circuits is assumed to be inherently modular).     

集成电路的模块生成与选择算法

借鉴软件设计中的思想,采用模块化技术是提高大规模集成电路的设计能力和系统芯片开发效率的重要手段.文章首先对现有的模块生成算法进行了全面的分析,在此基础上提出了一新的模块生成算法,此算法可生成一个电路系统的顶点数小于m的所有模块,并且对电路系统以及模块的结构没有限制.本文还提出了一个模块选择算法,此算法可以在满足一定要求的前提下选择一部分模块覆盖整个电路,同时还对算法进行了实验分析.     

Partitioning-based decoupling capacitor budgeting via sequence of linear programming

In this paper, we propose an efficient algorithm to reduce the voltage noises for on-chip power/ground (P/G) networks of VLSI. The new method is based on the sequence of linear programming (SLP) as the optimization engine, and partitioning scheme for dealing with large-sized circuits. We show that by directly optimizing the decoupling capacitor (decap) areas as the objective function and using the time-domain adjoint method, SLP can deliver much better quality in terms of decap budget than existing methods based on the merged time-domain adjoint method. The partitioning strategy further improves the scalability of the proposed algorithm and makes it efficient for larger circuits. The resulting algorithm is general enough for any P/G network. Experimental results demonstrate the advantage of the proposed method over existing state-of-the-art methods in terms of solution quality at a mild computation cost increase.     

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²).     

一种基于伪LRU的新型共享Cache划分机制

本文提出了一种基于伪LRU方法的新型共享Cache动态划分策略PLRU-SCP.本文提出的划分策略在分析电路中给出了基于二叉树的新型分析方法,在划分电路中使用了一种非遍历的划分算法.并提出了一种新型共享Cache结构.本文提出的新型划分策略比基于LRU方法的不划分共享Cache策略和效用最优的划分策略的性能分别提高了11.05%和8.66%.     

3D human posture segmentation by spectral clustering with surface normal constraint

In this paper, we propose a new algorithm for partitioning human posture represented by 3D point clouds sampled from the surface of human body. The algorithm is formed as a constrained extension of the recently developed segmentation method, spectral clustering (SC). Two folds of merits are offered by the algorithm: (1) as a nonlinear method, it is able to deal with the situation that data (point cloud) are sampled from a manifold (the surface of human body) rather than the embedded entire 3D space; (2) by using constraints, it facilitates the integration of multiple similarities for human posture partitioning, and it also helps to reduce the limitations of spectral clustering. We show that the constrained spectral clustering (CSC) still can be solved by generalized eigen-decomposition. Experimental results confirm the effectiveness of the proposed algorithm.     

基于采样的大规模图聚类分析算法

针对当前聚类方法（例如经典的GN算法）计算复杂度过高、难以适用于大规模图的聚类问题，本文首先对大规模图的采样算法展开研究，提出了能够有效保持原始图聚类结构的图采样算法（Clustering-structure Representative Sampling，CRS），它能在采样图中产生高质量的聚类代表点，并根据相应的扩张准则进行采样扩张.此采样算法能够很好地保持原始图的内在聚类结构.其次，提出快速的整体样本聚类推断（Population Clustering Inference，PCI）算法，它利用采样子图的聚类标签对整体图的聚类结构进行推断.实验结果表明本文算法对大规模图数据具有较高的聚类质量和处理效率，能够很好地完成大规模图的聚类任务.     

基于划分的力矢量布局算法

提出了一个全新的基于划分的力矢量布局算法．针对大规模集成电路的布局问题，采用基于并行结群技术的递归划分方法进行分解解决，并结合改进的力矢量算法对划分所得的子电路进行迭代布局优化．通过对MCNC标准单元测试电路的实验，与FengShui布局工具相比，该布局算法在花费稍长一点的时间内获得了平均减少12%布局总线长度的良好效果．