一种新型宏模块和标准单元的混合模式布局算法

本文针对包含有宏模块和标准单元的超大规模集成电路布局问题, 提出了一个新的混合模式布局算法MMP.该算法综合应用了自底向上的结群策略,数学规划和Slicing划分等技术.MMP算法可以对宏模块和小单元同时求解,算法稳定性好,实用性强,不但求解质量高,而且运算速度快.我们对一组来自工业界的设计实例进行了测试,实验结果表明,MMP是非常实用而高效的.     

标准单元布局中的高效结群算法

本文提出了一个高效的结群算法,用以解决在超大规模条件下标准单元模式集成电路的布局问题.与传统结群算法相比,本算法的特色在于在结群之前,建立和组织了表示所有单元之间连接关系的信息库,使得结群算法具有全局优化性和无冗余计算的特点.本结群算法已应用于二次规划布局过程中.实验结果表明,本算法无论在结群质量和结群速度方面都非常理想,从而成功地解决了超大规模电路的布局问题.     

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

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

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

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

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

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

一种考虑执行延迟最小化和资源约束的改进层划分算法

 本文提出了一种改进的层划分算法.该算法充分考虑了划分块的最小执行延迟和尽可能充分利用可重构资源,能够跟踪层划分算法节点分配过程并进行调整,消除了经典层划分算法不能动态更新就绪节点列表选取节点进行划分的缺陷.实验结果表明,与层划分算法相比,所提出的改进层划分算法在模块数、执行延迟和跨模块间的I/O边数等三个方面均获得了改进.与现有的簇划分、增强静态列表、多目标时域划分、簇层次敏感等四种划分算法相比,新算法能获得最少的执行延迟,并且随着可重构处理单元面积的增大,模块数的均值也是最小的.     

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

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

面向甚大规模集成电路的时延驱动布局方法

本文针对甚大规模集成电路的时延驱动布局问题提出了一个新的解决途径,其策略是将结群技术应用于二次规划布局过程中.结群的作用是可大幅度地降低布局部件的数量.本文设计了一个高效的结群算法CARGO,其优点是具有全局最优性并且运行速度很快.采用了一个基于路径的时延驱动二次规划布局算法对结群后的电路完成布局过程.由于二次规划布局算法能够在很短时间内寻找到全局最优解,故本文的算法更有希望彻底解决甚大规模电路的布局问题.在一组MCMC标准测试电路上对算法进行了测试,得到了满意的结果.     

混合粒子群算法优化神经网络的研究

针对BP神经网络初始权阈值的确定所具有的随机性和各个隐含层神经元数的不确定性,通过利用混合粒子群优化算法来同时优化神经网络的初始权阈值和结构.首先通过混合粒子群优化算法来确定一个较好的搜索空间,然后在这个解空间里再通过BP算法对网络进行训练和学习,搜索出最优的网络结构和权阈值.通过Iris模式分类、Wine模式分类问题和广义异或问题来对该模型进行训练和测试,相比遗传算法等其他算法,该模型可以获得更高的正确识别率,结果表明此方法是可行的.     

微电子学、集成电路

TN4 2005010494一种应用于二次布局的有效划分方法/吕勇强,洪先龙,侯文婷.昊为民,蔡鼓慈(清华大学)“半导体学报一2004,25(3).一272-278提出了一种基于二次布局的结合M FFC结群和hMETIS划分的算法.实验表明:这种方法能得到很好的布局结果,但是运行消耗的时间比较长.为了缩短划分在二次布局中运行的时间.提出了一种改进的结群算法IMFFC,用它在二次布局中做划分.与前者相比较,这种方祛虽然布局质量稍差,但速度更快.图4表3参g(木)TN4 2005010497中、低能离子注人中的剂且效应及模拟方法/施小康,于民,石浩,黄如,张兴(北京大学微电子所)1…     

A New Clustering-Based Partitioning Method for VLSI Mixed-Mode Placement

An efficient partitioning algorithm for mixed-mode placement,extended-MFFC-based partitioning,is presented.It combines the bottom-up clustering and the top-down partitioning together.To do this,designers can not only cluster cells considering logic dependency but also partition them aiming at min-cut.Experimental results show that extended-MFFC-based partitioning performs well in mixed-mode placement with big pre-designed blocks.By comparison with the famous partitioning package HMETIS,this partitioning proves its remarkable function in mixed-mode placement.     

Simulation techniques for mixed analog/digital circuits

The techniques used in the iSPLICE3 simulator for the analysis of mixed analog/digital circuits are described. iSPLICE3 combines circuit, switch-level timing, and logic simulation modes and uses event driven selective-trace techniques. It also uses a hierarchical schematic capture package called iSPI (Simulation Program Interface) for design entry, circuit partitioning, and simulation control. The contributions here include a new DC solution method, a mixed-mode interface modeling technique, and an automatic partitioning approach for MOS logic circuits. The details of these three methods are provided, along with the architecture and transient simulation algorithms used in iSPLICE3. The results of circuit simulations and mixed-mode simulations of a CMOS static RAM, two A/D converters, and a phase-locked loop are presented. These results indicate that iSPLICE3 is between one and two orders of magnitude faster than SPICE2 with negligible loss in accuracy     

Adaptive delay estimation for partitioning-driven PLD placement

This paper describes the application of weighted partitioning techniques to timing-driven placement on a hierarchical programmable logic device. We discuss the nature of placement on these architectures, the details of applying weighted techniques specifically to the programmable logic device (PLD) CAD flow, and introduce the new concept of adaptive delay estimation using phase local to increase performance. Empirical results show that these techniques, in a fully complete system with large industrial designs, give an average 38.5% improvement over the unimproved partitioning-based placement tool. Approximately two-thirds of this benefit is due to our improvements over a straightforward weighted partitioning approach.     

Integrating Physical Constraints in HW-SW Partitioning for Architectures With Partial Dynamic Reconfiguration

Partial dynamic reconfiguration is a key feature of modern reconfigurable architectures such as the Xilinx Virtex series of devices. However, this capability imposes strict placement constraints such that even exact system-level partitioning (and scheduling) formulations are not guaranteed to be physically realizable due to placement infeasibility. We first present an exact approach for hardware-software (HW-SW) partitioning that guarantees correctness of implementation by considering placement implications as an integral aspect of HW-SW partitioning. Our exact approach is based on integer linear programming (ILP) and considers key issues such as configuration prefetch for minimizing schedule length on the target single-context device. Next, we present a physically aware HW-SW partitioning heuristic that simultaneously partitions, schedules, and does linear placement of tasks on such devices. With the exact formulation, we confirm the necessity of physically-aware HW-SW partitioning for the target architecture. We demonstrate that our heuristic generates high-quality schedules by comparing the results with the exact formulation for small tests and with a popular, but placement-uanaware scheduling heuristic for a large set of over a hundred tests. Our final set of experiments is a case study of JPEG encoding-we demonstrate that our focus on physical considerations along with our consideration of multiple task implementation points enables our approach to be easily extended to handle heterogenous architectures (with specialized resources distributed between general purpose programmable logic columns). The execution time of our heuristic is very reasonable-task graphs with hundreds of nodes are processed (partitioned, scheduled, and placed) in a couple of minutes     

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.     

基于存储划分和路径重用的粗粒度可重构结构循环映射算法

目前针对粗粒度可重构结构循环映射的研究主要集中在操作布局和临时数据路由,缺乏考虑数据映射的研究,该文提出一种基于存储划分和路径重用的模调度映射流程。首先进行细粒度的存储划分找到合适的数据映射,提高数据存取的并行性,再用模调度寻找操作布局和临时数据路由,最后利用构建的路由开销模型平衡存储器路由和处理单元路由的使用,引入路径重用策略优化路由资源。实验结果表明,该方法在循环的启动间隔、每周期指令数和执行延迟等方面均具有良好的性能。     

一种新的基于单元扩大的拥挤度驱动的布局算法

描述了一种新的基于单元扩大的拥挤度驱动的布局算法．这个方法用概率估计模型和星型模型来评价线网的走线．使用全局优化和划分交替的算法来进行总体布局．提出了单元的虚拟面积的概念,单元的虚拟面积不仅体现了单元的面积,而且指出了对布线资源的需求．单元的虚拟面积可以由单元的扩大策略来得到．把单元的虚拟面积用到划分过程中,从而减小拥挤度．并且使用了单元移动的策略来进一步减小走线的拥挤．用来自美国公司的一些例子测试了这个算法,结果显示布局的结果在可布性方面有了很大的提高．     

一种新的基于单元扩大的拥挤度驱动的布局算法

描述了一种新的基于单元扩大的拥挤度驱动的布局算法 .这个方法用概率估计模型和星型模型来评价线网的走线 .使用全局优化和划分交替的算法来进行总体布局 .提出了单元的虚拟面积的概念 ,单元的虚拟面积不仅体现了单元的面积 ,而且指出了对布线资源的需求 .单元的虚拟面积可以由单元的扩大策略来得到 .把单元的虚拟面积用到划分过程中 ,从而减小拥挤度 .并且使用了单元移动的策略来进一步减小走线的拥挤 .用来自美国公司的一些例子测试了这个算法 ,结果显示布局的结果在可布性方面有了很大的提高