FAME:一个标准单元模式下基于最小割和枚举的快速详细布局算法(英文)

随着制造工艺的快速进步 ,超大规模集成电路的物理设计技术在速度和质量上面临很大挑战 .提出了一个快速详细布局算法以适应这种要求 .算法继承总体布局得到的单元全局最佳位置 ,然后采用局部优化将单元精确定位 .FM最小割和局部枚举方法分别用于优化 y和 x两个方向的连线长度 ,这两个方向的优化在同一迭代过程中交替进行 .另外 ,采用改进的枚举策略加速算法 ,对于有障碍和宏模块情况下的布局也加以讨论 .实例测试结果表明 ,FAME的运行速度比 RITUAL快 4倍 ,并使总连线长度平均减小 5% .     

FAME：一个标准单元模式下基于最小割和枚举的快速详细布局算法

随着制造工艺的快速进步,超大规模集成电路的物理设计技术在速度和质量上面临很大挑战。提出了一个快速详细布局算法以适应这种要求,算法继续总体布局得到的单元全局最佳位置,然后采用局部优化将单元精确定位。ＦＭ最小割和局部枚举方法分别用于优化ｙ和ｘ两个方面的连线长度,这两个方向的同一迭代过程中交替进行。另外,采用改进的枚举策略加速算法,对于有障碍和宏模块情况下的布局也加以讨论,实例测试结果表明,ＦＡＭＥ的运     

可编程逻辑阵列分段递进优化布局算法研究

为了提高FPGA(Field Programmable Gate Array)的布通率并优化电路的连线长度,在模拟退火算法的基础上,该文提出一种新的FPGA布局算法。该算法在不同的温度区间采用不同的评价函数,高温阶段采用半周长法进行快速优化布局,低温阶段在评价函数中加入变量因子并进行适度的回火处理,以此来优化布局。实验表明,该算法提高了布通率,优化了连线长度,与最具代表性的VPR(Versatile Place and Route)布局算法相比布线通道宽度提高了近6%,电路总的连线长度降低了4~23%。     

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

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

LSI二维布局的分析算法

本文提出一种适合于门阵列的布局算法,该算法采用分析方法处理二次分配的组合问题,具体使用最优相对布局及线性分配定位或快速定位方法得到一个接近最优解.实际结果表明不论初始分布如何,均可在差不多相同的时间内获得优化结果大致相同的结果. 本算法(用快速定位)的计算复杂性为O(n),计算速度很快,一般对一百至二百个单元的芯片,计算速度比通常的力交换法快一个数量级.本算法对大系统的适应性特别好.     

用模拟退火算法实现集成电路热布局优化

介绍了一种综合考虑集成电路电学性能指标以及热效应影响的布局优化方法.在保证传统设计目标(如芯片面积、连线长度、延迟等)不被恶化的基础上,通过降低或消除芯片上的热点来优化集成电路芯片的温度分布情况,进而优化整个电路性能.并将改进的模拟退火算法应用于集成电路的热布局优化,模拟结果表明该方法与传统布局方法相比在保持了较好的延迟与连线长度等设计目标的同时,很好地改善了芯片表面的热分配情况.     

用模拟退火算法实现集成电路热布局优化

介绍了一种综合考虑集成电路电学性能指标以及热效应影响的布局优化方法 .在保证传统设计目标 (如芯片面积、连线长度、延迟等 )不被恶化的基础上 ,通过降低或消除芯片上的热点来优化集成电路芯片的温度分布情况 ,进而优化整个电路性能 .并将改进的模拟退火算法应用于集成电路的热布局优化 ,模拟结果表明该方法与传统布局方法相比在保持了较好的延迟与连线长度等设计目标的同时 ,很好地改善了芯片表面的热分配情况     

双边单元的LSI自动布局算法

本文采用带冗余通道的双边单元模型,提出了一种有效的LSI自动布局算法.算法中运用“等分接点法”进行单向的布局初始构造,并用多种方式进行布局的迭代优化处理.由于在布局过程中对所有纵向连线的通道分配进行了统一的考虑,提高了设计的整体合理性.本文提出的布局算法和我们提出的“通道区布线的通道损益分析法”可望成为一个有效的布图设计系统的基础.     

复合左右手传输线平衡点的三点快速优化方法

提出了一种基于遗传算法的快速优化算法,使复合左右手传输线达到平衡状态且拥有较低的回损值.算法使用商用软件分析出两个级联单元在3个邻近频率点的转移矩阵.利用Bloch方法计算出传输线的衰减系数和相移系数,据此提出一种适应度函数,并利用其进行优化.优化过程中采用自适应变异率和移民策略避免了早熟收敛与随机搜索问题;所分析的模型与原模型相比,减少了传输线单元,且无须大规模扫频,从而提高了优化速度.通过比较发现,该算法有更广阔的适用范围和更好的优化效果.     

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

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

Clock Mesh Network Design with Through‐Silicon Vias in 3D Integrated Circuits

Many methodologies for clock mesh networks have been introduced for two‐dimensional integrated circuit clock distribution networks, such as methods to reduce the total wirelength for power consumption and to reduce the clock skew variation through consideration of buffer placement and sizing. In this paper, we present a methodology for clock mesh to reduce both the clock skew and the total wirelength in three‐dimensional integrated circuits. To reduce the total wirelength, we construct a smaller mesh size on a die where the clock source is not directly connected. We also insert through‐silicon vias (TSVs) to distribute the clock signal using an effective clock TSV insertion algorithm, which can reduce the total wirelength on each die. The results of our proposed methods show that the total wirelength was reduced by 12.2%, the clock skew by 16.11%, and the clock skew variation by 11.74%, on average. These advantages are possible through increasing the buffer area by 2.49% on the benchmark circuits.     

Net Clustering Based Constructive and Iterative Improvement Approaches for Macro-Cell Placement

We propose a net clustering based RT-level macro-cell placement approaches. Static timing analysis identifies critical nets and critical primary input/output paths. Net clustering (based on shared macro-cells and net criticality) yields clusters wherein each cluster has strongly interdependent nets. The circuit is modeled as a graph in which each vertex v represents a net and each edge (v,u) a shared cell between nets v and u. The net clusters are obtained by applying a clique partitioning algorithm on the circuit graph. Two approaches to generate placements at RTL are proposed: constructive (cluster growth) approach and iterative improvement (simulated annealing) based approach. In the constructive approach, a cluster-level floorplanning is performed and a cluster ordering is obtained. The cluster ordering is used by a constructive procedure to generate the physical placement. In the case of iterative improvement based approach, a good ordering of clusters is obtained using simulated annealing.We report experimental results for five RTL datapaths implemented in 0.35 m technology to demonstrate the efficacy of the proposed approaches. We compared the layouts produced by our approaches with those produced by Flint, an automatic floor planner in Lager IV Silicon Compiler [1]. For constructive placement approach, we obtained an average decrease of 43.4% in longest wirelength and 32.4% in total wirelength. The average area reduction is 7.3%. On the other hand, for the SA-based approach, we obtained an average decrease of 57.6% in longest wirelength and 42.2% in total wirelength. The average reduction in the bounding-box area is 12.3%. As expected, the SA-based approach yielded better optimization results, due to its ability to climb out of local minima.     

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

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

APWL-Y: An accurate and efficient wirelength estimation technique for hexagon/triangle placement

The Y architecture has recently received much attention due to its many potential advantages, such as substantially reduced wirelength, power consumption and significantly improved throughput. To fully utilize the virtues of Y architecture, several hexagon/triangle placement (HTP) algorithms suitable for the Y architecture were presented, however the wirelength optimization is not included in the algorithms. Wirelength estimation is fundamental to guide the wirelength optimization process in early design stages. In this paper, we present an accurate and efficient wirelength estimation technique called APWL-Y appropriate for the Y architecture, and especially for HTP floorplanner and placer. The average error of APWL-Y is 4.41% for 1.57 million nets from industrial circuits. When developing APWL-Y, we find out that 3-SMT wirelength is a power function of aspect ratio of bounding box of the given n-pin nets. The time complexity of APWL-Y is O(n). APWL-Y is very effective to guide the wirelength optimization in a HTP placer. Moreover, we develop an efficient HTP algorithm with wirelength optimization driven by APWL-Y estimator. The placement results by our placer subject to different optimization objectives are presented. Compared to the HTP placer with only area optimization, our placer can reduce the wirelength by 54.3% with a small area overhead of 9.07% on average. In addition, we explore the HPWL technique in the Y architecture. To the best of our knowledge, this paper is the first in-depth study on wirelength estimation technique in Y architecture and HTP floorplanning optimization with consideration of interconnects.     

固定边框的多电压布图规划算法

多电压设计是应对SoC功耗挑战的一种有效方法,但会带来线长、面积等的开销。为减少线长、芯片的空白面积及提高速度,提出了一种改进的固定边框多电压布图方法.对基于NPE（Normalized Polish Expression）表示的布图解,采用形状曲线相加算法来计算其最优的布图实现,并通过增量计算方法来减少计算NPE及多电压分配的时间.为使所得布图解满足给定的边框约束,提出了一个考虑固定边框约束的目标函数,并采用删除后插入（Insertion after Delete,IAD）算子对SA求得布图解进行后优化.实验结果表明,和已有方法相比,所提出方法在线长和空白面积率方面有较明显优势,且所有电路在不同高宽比、不同电压岛数下均实现了极低的空白面积率（< <1%）.     

Pattern-matching-based X-architecture zero-skew clock tree construction with X-Flip technique and via delay consideration

As IC fabrication technologies get into nanometer era, clock routing gradually dominates chip performance indicated by delay, cost, and power consumption. X-architecture can be applied for routing metal wires in diagonal and rectilinear directions to overcome the above challenges due to wirelength reduction. In this paper, we present a clock routing algorithm, called PMXF, to construct an X-architecture zero-skew clock tree with minimum delay. An X-pattern library is defined for simplifying the merging procedure of the DME approach, an X-Flip technique is proposed for reducing the wirelength between the paired points, and a wire sizing technique is applied for achieving zero skew. In terms of clock delay, wirelength, power consumption, and via count listed in the experimental results on benchmarks, the proposed PMXF algorithm can respectively achieve more reductions compared with other previous X-architecture clock routing algorithms.     

Design Migration From Peripheral ASIC Design to Area-I/O Flip-Chip Design by Chip I/O Planning and Legalization

Due to higher input/output (I/O) count and power delivery problem in deep submicrometer (DSM) regime, flip-chip technology, especially for area-array architecture, has provided more opportunities for adoption than traditional peripheral bonding design style in high-performance application-specific integrated circuit and microprocessor designs. However, it is hard to tell which technique can provide better design cost edge in usually concerned perspectives. In this paper, we present a methodology to convert a previous peripheral bonding design to an area-I/O flip-chip design. It is based on an I/O buffer modeling and an I/O planning algorithm to legalize I/O buffer blocks with core placement without sacrificing much of the previous optimization in the original core placement. The experimental results have shown that we have achieved better area and I/O wirelength in area-IO flip-chip configuration (especially for pad-limit designs), compared with peripheral bonding configuration in packaging consideration.