一种综合型FPGA布局算法

FPGA的快速发展对EDA软件提出了更高的要求,布局是EDA流程中重要的一环。现有的FPGA布局算法单独应用于解决布局问题时或需要耗费太长时间,或不能给出质量较高的解。提出一种改进的综合型算法以解决FPGA布局问题,它结合了二次线性规划算法和模拟退火算法并做出相应改进,使得算法可以在较短的时间内给出质量较高的布局结果。     

基于线性规划的最小扰动标准单元合法化算法

在传统的标准单元总体布局完成之后,一个很重要的步骤是消除标准单元之间的重叠,即合法化过程.文章以对总体布局结果的最小扰动为优化目标,考虑标准单元布局合理位置的约束,通过采用线性规划建模求解,有效地解决了布局合法化问题.与启发式算法相比,该模型从理论上给出了对布局造成最小扰动的最优解.实验表明,该合法化算法在ISPD02的例子中基于mPL6的总体布局能够比Fastplace3.0的合法化结果有平均3.8%的线长减少.     

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

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

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

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

一个求无向网络最大流的算法

从对通路的选后堵塞观点出发，给出了若干定理，从而构造了一对点之间的最大流算法，并讨论了算法的复杂度。     

解线性及二次型规划问题增广的神经网络

本文提出了一个解线性及二次型规划问题的神经网络模型，证明了该网络是全局稳定于平衡点，而平衡点就是线性及二次型规划问题的解，该网络的优点是能够实时获得问题的精确解，且可以同时获得带等式不式约束的对偶问题解，该网络易于电路实现。     

计算机通信网最大流算法的分析和实现

应用网论分析了计算机通信网的最大流，采用ＴＵＲＢＯＣ语言编程实现了基本算法。应用面向对象的程序设计方法，为用户提供交互式图形界面的系统框架，从而可以直观地在显示屏上求得给定网络图任一对节点间的最大流值和流向。     

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

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

超图的最大流算法及其连通性测试

在经典的网络流理论的基础上,给出了超图的最大流和多终端最大流的有效算法。首次提出了表征超连通性的两个基本定理,给出了确定超图连通度的有效算法。文中算法及应用实例均编程上机试算,结果是令人满意的。文章最后提出了一些可供继续研究的相关课题。     

基于移动节点二次部署的WSN栅栏新型强化方法

无线传感器网络栅栏覆盖在入侵检测方面发挥着重要作用,如何构建顽健的栅栏是重点研究问题.针对栅栏初始部署后,随着节点能量的消耗,部分节点过早死亡,从而导致栅栏中存在较多薄弱点的问题,提出了一种利用移动节点二次部署来强化栅栏的方法.该方法采用基于集合的最大流算法计算能强化薄弱点的数量,并根据薄弱情况部署和调度可移动节点来强化栅栏,经过强化后的栅栏具有更好的性能,解决了栅栏薄弱点强化问题.仿真实验表明,该算法能有效强化栅栏,延长栅栏的生存时间,且算法复杂度也比较低.     

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

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

一种新的基于最大流的无线Mesh网络信道分配算法

在无线Mesh网络中,为节点配置多接口多信道MAC协议成为提高网络性能、扩大网络容量的有效手段之一。有效的信道分配策略在多信道无线Mesh网络中显得尤为重要。本文提出一种基于最大流的信道分配算法。该算法通过最大流计算网络中可达到的最大吞吐量,以此作为网络负载标准进行信道分配,将降低整个网络的总体干扰作为目标函数进行优化。仿真结果表明,即使在网络负载较重的情况下,算法仍能保持较好的性能。     

A New Timing-Driven Placement Algorithm Based on Table-Lookup Delay Model

An algorithm is presented for obtaining placements of cell-based very large scale integrated circuits, subject to timing constraints based on table-lookup model. A new timing delay model based on some delay tables of fabricators is first simplified and deduced; then it is formulated as a constrained programming problem using the new timing delay model. The approach combines the well-known quadratic placement with bottom-up clustering, as well as the slicing partitioning strategy, which has been tested on a set of sample circuits from industry and the results obtained show that it is very promising.     

A New Timing-Driven Placement Algorithm Based on Table-Lookup Delay Model

There have been extensive studies on timing-driven placement in recent years.Theapproaches toward this problem fall into two main categories:net-based and path-based.In a typical net-based one,potential critical paths and acceptable d...     

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

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

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

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

基于 VPR的 FPGA 布局算法的改进

通过在原模拟退火算法中加入回火过程对原算法进行优化,同时,减小内循环次数用于弥补回火导致的布局时间增量。回火过程用于寻找“被遗漏”的最优解。结果表明新算法利于跳出局部最优“陷阱”,进一步搜索最优解,具体体现在改进后的算法不但能够保证布局质量,而且缩减了布局时间,同时,布线时间与电路关键路径延时得到不同程度的改善。     

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

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

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

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