VLSI定量驱动布局算法

定量驱动布局算法是改善ＶＬＳＩ性能的重要措施，现有算法主要建立在面向网络和面向通路两种技术之上，仅获得局部最优解，本文以获得全局最优解为目标，从电路逻辑结构和传输延时出发，提出了面向电路最大延时的布局算法，实验表明，本算法是有效的。     

三维实体布局中改进局部最优解的冲突决策方法

利用博弈论中冲突决策的思想实现了三维实体布局从一个局部最优解向另一个更好的局部最优解跳跃的算法，部分克服了传统算法的主要瓶－局部最优陷井的问题。理论分析及实例计算表明，当布局问题陷入某－局部最优解时，该算法利用冲突决策策略能有效地春跳入另一个更好的局部最优点上。通过一系列这样的跳跃，最终使布局问题获得一个高质量的解。     

基于累积竞争神经网络的多约束路由算法

针对无约束最优路径问题，提出累积竞争神经网络模型及其搜索算法，该算法具有高度并行性、能获得最优解、结构简单等特点．以QoS路由选择为例，将算法推广到多约束路由问题．实验结果表明，对于大多数多约束QoS问题，在与相应最短路径上节点数目相当的迭代次数内，该算法能找到问题的满意解甚至最优解．     

一种多空间聚类算法

CLARANS算法是经典的划分聚类算法，其核心思想是采用随机重启的局部搜索方式搜索中心点．由于搜索空阀布满了局部最优解的“陷阱”，因此它难以获得全局最优解，从而影响了聚类质量．针对这个缺点，本文将多空闻思想与CLARANS算法相结合，提出了基于多空间思想的CLARANS算法-CABMS（CLARANS Algorithm Based on Multi—Space）．该算法的基本思路是采用空间变换策略构造一系列光滑程度不同的搜索空间，在不同的搜索空间中执行CLARANS算法，并利用前层搜索空间的聚类结果来引导本层搜索空间的聚类．CABMS能够跳过局部最优解的“陷阱”，增大获得全局最优解的概率，达到提高聚类质量的目的．本文给出了等距法多空间构造策略，并通过实验对比了CLARANS算法与CABMS算法的聚类质量．实验结果表明，CABMS的聚类质量较CLARANS有较大改进．     

自适应调整信息素的蚁群算法

蚁群算法是通过模拟蚂蚁觅食而发展出的一种新的启发算法．基于群体的协作与学 习，该算法已经成功地解决诸如TSP问题等多种组合优化问题．本文提出了一种基于自适应 调整信息素的改进蚁群算法．该算法根据人工蚂蚁所获得解的情况，动态地调整路径上的信 息素，从而使得算法跳离局部最优解．通过仿真实验获得的结果表明，该算法对于蚁群算法 具有较好的改进效果．     

单线图动态规划最优布局成图技术

提出了一种基于动态规划算法得到布局最优解实现区域电网单线图生成的方法.根据电网空间数据构建拓扑模型,执行广度优先算法得到多个能构成连通图的邻接矩阵以及矩阵遍历序列,根据邻接矩阵宽度计算出能容纳全部设备的正方形范围,并建立了设备最小间距为优化目标的数学模型.提出了动态规划最优布局求解的算法,应用该算法求解布局最优解数组,最后按照最少交叉原则进行正交化处理.应用实例表明通过最优解布局的成图美观且高效.     

三维实体布局的八叉树语言及优化算法

本文设计了一个八叉树操作语言，并利用该语言实现了三维实体布局的优化算法，该算法能从任一初始布局可行解迅速收敛到一个局部最优解上，从而明显改善初始布局方案。文章最后给出了一个简单的应用实例。     

一种混合全局寻优算法及其在布局中的应用

布局问题是NP完全问题,传统的优化算法很难求得全局最优欠解,遗传算法和模拟退火算法等的随机搜索算法的求解精度和效率不能令人满意,文中将启发式随机搜索策略的局部优化算法相结合,构造混合全局寻优算法,以旋转卫星舱布局问题的简化模型为背景,建立了多目标优化的数学模型,通过一已在最优解的布局算例与遗传算法和乘子法的计算结果比较,该算法求解的质量和效率更优,表明此算法在布局优化中具有应用潜力。     

直角多边形布图区域内的二次布局算法

提出了一种直角多边形布图区域内的基于动态划分的二次布局算法——DPRR．通过在传统的二次布局算法中引入一种新的圆盘划分和分布约束生成策略,解决了直角多边形布图区域里的单元布局问题,并且由于该算法在迭代优化过程中动态地划分电路并生成分布约束,且不限制单元在布图区域的不同部分间自由移动,所以它可以在一定程度上避免优化过程中出现的“局部最优”,从而达到更高的布局质量．对一些电路实例的测试和比较结果也证明DPRR是一种高效优良的布局算法,并且它十分适用于解决非矩形的直角多边形布图区域内的标准单元布局问题．     

量子程序中一种改进的延时估计算法研究

针对现有的量子算法处理时间长、成本过于昂贵这一不足,提出一种延时快速估计算法LEQA,以评估映射到瓦片量子结构的量子算法的延时.该算法使用程序化方法,通过计算量子周围相邻量子的数量来计算算法的延时.仿真结果表明,对中等规模的电路,LEQA的速度要比执行细致的布局、调度以及将量子运算依赖图中的量子指令和量子位通过路由传输到量子结构中的现代量子映射器速度快出两个数量级.此外,LEQA还能快速得出电路延时的估计,且精度很高,平均误差只有2.11％.     

A buffer planning algorithm for chip-level floorplanning

This paper studies the buffer planning problem for interconnect-centric floorplanning for nanometer technologies. The dead-spaces are the spaces left unused within a placement that are not held by any circuit block. In this paper, we proposed a buffer planning algorithm based on dead space redistribution to make good use of dead-spaces for buffer insertion. Associated with circuit blocks under topological representations, the dead space can be redistributed by moving freely some circuit blocks within their rooms in the placement. The total area and the topology of the placement keep unchanged while doing the dead space redistribution. The number of nets satisfying the delay constraint can be increased by redistributing the dead space all over the placement, which has been demonstrated by the experimental results. The increment of the number of nets that meet delay constraint is 9% on an average.     

基于性能的LUT结构的FPGA的再设计算法

本文提出一个基于性能的LUT结构的FPGA的再设计算法,该算法采用特征函数以及对原布尔网络进行相应的约束实现电路的再设计。因为不改变网络的拓扑结构,从而避免了在再设计过程中重新考虑电路的时延和布局布线结果。     

调整门和连线尺寸以减小串扰的拉格朗日松弛法

本文给出了一个布线后减小串扰噪声的算法。该算法通过调整逻辑门和互连线的尺寸有效地减小了串扰噪声，在减小噪声的同时约束电路的最大延时，使得在串扰噪声和时序都满足约束的条件下最小化芯片面积。算法保证了改变逻辑门和线网尺寸不会破坏电路的时序约束。实验结果证明，本算法有效地减小了串扰。此算法不需回到布线阶段来优
优化串扰，减少了设计迭代次数，加快了设计收敛时间。     

定时驱动布局问题的描述与算法

定时驱动布局是减小ＩＣ延时的重要手段。本文通过描述其目标函数与约束条件，给出一种用延时表示弹性系数的力向量算法。它具有速度快，布局目标准确等特点。     

一个有效的圆片规模布局算法

本文提出了一个圆片规模布局算法，它是国外一个相应算法的改进形式，区别在于利用力定向布局法的方式不同。在相对位置阶段，该算法利用布局的层次特性将需确定所有电路元件相对位置的问题缩减至仅需确定宏电路元件相对位置的问题；在实际位置阶段，采用分治策略和取消前阶段层次划分的方式回避了需确定任意元实际位置的问题．其时间复杂度远低于国外相应算法．     

块RAM与标准单元的混合模式布局算法

针对块RAM和标准CLB单元的电路布局问题,提出了一个新的混合模式布局算法。在标准单元采用模拟退火方式的前提下,对块RAM的布局进行算法改进。不但兼顾了块RAM的布局方式,也兼顾了原有的算法。     

用动态规划法求解延时/面积最小化工艺映射

本文提出了一个求解延时／面积最小化工艺映射动态规划法．它首先基干线性延时模型，给出了用动态规划法求解延时最小化工艺映射的步骤；然后从树型网络的面积计算公式入手，用动态规划法近似计算面积最小化工艺映射；最后用“线性加权和法”把延时／面积最小化工艺映射转变为单目标最优化问题求解．     

A PSO-based intelligent decision algorithm for VLSI floorplanning

Floorplanning is an important issue in the very large-scale integrated (VLSI) circuit design automation as it determines the performance, size, yield and reliability of VLSI chips. This paper proposes a novel intelligent decision algorithm based on the particle swarm optimization (PSO) technique to obtain a feasible floorplanning in VLSI circuit physical placement. The PSO was applied with integer coding based on module number and a new recommended value of acceleration coefficients for optimal placement solution. Inspired by the physics of genetic algorithm (GA), the principles of mutation and crossover operator in GA are incorporated into the proposed PSO algorithm to make this algorithm to break away from local optima and achieve a better diversity. Experiments employing MCNC and GSRC benchmarks show that the proposed algorithm is effective. The proposed algorithm can avoid local minimum and performs well in convergence. The experimental results of the proposed method in this paper can also greatly help floorplanning decision making in VLSI circuit design automation.     

一种线长和时延双重驱动的布局算法

针对标准单元模式的超大规模集成电路布局问题,本文提了一种新的基于线长和时延双重优化目标的布局算法。在以优化线长为目标函数的布局结果基础上,进一步优化了芯片的时延特性,并通过算法设计较好地解决了二者优化方向的一致性。通过标准单元测试电路的实验结果比对,该算法在线长及时延优化方面综合性能良好。     

面向电耗与网络同步代价优化的数据副本放置研究

在数据中心放置海量数据时,每个数据常有多个副本,服务提供商需要支付巨额电费以运行存储这些数据副本的服务器。同时,为保证多个数据副本的一致性,放置在不同数据中心的副本需要通过数据中心之间的网络进行同步,从而引发高额的网络传输费用。为此,以最小化多副本数据放置代价为目标,建立数据放置问题模型,并提出一种基于数据组和数据中心划分的数据放置算法DDDP。将数据划分为多个数据组,按用户访问数据的延迟要求将数据中心划分成数据中心子集,并将每个数据组中的数据放置到能满足访问延迟要求且能最小化放置代价的数据中心子集中。仿真结果表明,相比NPR算法,DDDP算法能有效降低数据中心存储数据时的放置代价。