线长驱动的层次式FPGA布局算法

针对层次式FPGA结构的特点,提出了以线长为目标的层次式FPGA布局算法.该算法基于模拟退火优化策略,针对层次式FPGA实际芯片结构的特点,提出了线长计算方法和搜索范围确定方法;同时,给出了提高算法速度的快速布局方法.实验结果表明,该方法不仅能够减小时间代价,也能够得到比较好的布局质量.     

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

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

一种M-ary扩频信号的盲同步方法

针对通信侦察领域M-ary扩频信号的盲同步问题,根据M-ary扩频信号的结构特点及扩频码集元素间的相关特性,提出了一种扩频码长度和失步时间联合估计方法。该方法能够同时估计出M-ary扩频信号的扩频码长度及失步时间,且不受扩频码集类型的限制。仿真实验表明,该算法能在较低的信噪比条件下对三种不同码集的扩频信号进行估计,且算法的性能随着所使用数据的增多而提高。     

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

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

一种定性控制的电路布局优化方法

以总线长为优化目标的优化方法是电路布局优化的重要分支,模拟退火是常用的迭代优化方法.关注优化过程中布局的定性表现,提出一种定性控制的线长优化方案.云模型是一种定性定量转换模型,使用二维云模型可以对元件的布局位置进行建模.迭代过程中,制定布局收缩、布局扩展和布局重置三种策略,通过调整云模型的熵和超熵达到定性控制的目的.使用标准测试电路与模拟退火方法相比,本问题提出的方法能获得更好的优化效果.     

反熔丝FPGA线长驱动布局算法

针对反熔丝FPGA的结构特点,提出了一种线长驱动的反熔丝FPGA布局算法.该算法基于VPR的模拟退火布局算法,针对反熔丝FPGA垂直布线资源有限的特点,提出了新型的成本函数并在CAD实验平台上予以实现.实验结果表明,与VPR布局算法相比,该方法不仅优化了线网总长度,使得线网总长度平均减少了12%,同时还减少了编程的通路反熔丝数目.     

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

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

Quadratic布局算法力模型的建立和一种均匀展开的方法

布局是FPGA软件设计中一个基本而且非常重要的环节。随着FPGA规模的不断扩大,在大规模、复杂的设计约束条件下,花费较少时间获得高质量的相关逻辑单元物理位置是布局算法的关键问题。在二次线性规划布局算法的基础上,以线长为优化目标,介绍了一种力模型的建立理论和在力模型基础上的一种均匀展开方法。     

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

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

改进的MB-OFDM UWB 信道估计算法

在MB-OFDM UWB 系统中,传统的信道估计方法没有充分利用信道长度这一信息,估计信道长度常大于实际长度,造成了性能损失。针对这一缺陷,提出一种新的信道估计算法。首先利用LS 算法估计出信道,然后通过信号能量估计(SEE)方法估计出信道长度。算法有效地降低了估计维数,因此提高了LS 算法的估计性能,同时对各算法的性能进行了分析比较。最后利用实验仿真证实了算法的有效性和分析的正确性。     

具有单元自动生成的多元胞布图方法

本文提出一种新的多元胞自动布图方法.主要由四个部分构成,块的生成、块内一维布局、单元生成、通道布线.其中第一部分采用了分析的方法完成各个块的生成,目标为使连线最短和块之间连线和隔块连线最少.第二部分中引入了伪单元的概念以处理含有约束的一维布局问题,解决了各个块之间的相互连线关系以及隔块连线.第三部分中的单元生成,引入了类似硅编译的一些思想,在硅编译与传统的自动布局方法之间的结合方面做一些有益的尝试.第四部分的通道布线是一个比较灵活的方法,可以解决用户提出的各种工艺上的要求的布线,提高了布图的物理性能. 整个过程用C语言编成程序并已在PCS-68000机上运行.     

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

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

Reliability and routability consideration for MCM placement

This paper presents a methodology based on the fuzzy logic approach for the placement of the power dissipating chips on the multichip module substrate. Our methodology considers both thermal distribution and routing length constraints during multichip module placement. In this paper, the main design issue is the coupled placement for reliability and routability. The objective of the coupled placement is to enhance the system performance and reliability by obtaining an optimal cost during multichip module placement. For reliability considerations, the design methodology is addressed on the placement of the power dissipating chips to achieve uniform thermal distribution. The thermal placement analysis is based on the modified fuzzy force-directed placement method. Placement for routability is based on minimizing the total wire length estimated by semi-perimeter method. The placement trade-off between routability and reliability is illustrated by varying a weighting factor. Case studies of the coupled placement are presented. In addition, the thermal distribution of the coupled placement results is simulated with the finite element method.     

IO单元自动排布算法IOAP

提出了一种应用于芯片物理设计过程中IO单元自动排布的新算法。IO单元排布是芯片物理设计过程中长期依赖经验的环节。IO单元排布的优化对布线,电源网格和设计收敛性的优化有很大贡献。文章重点研究边缘IO单元排布,提出了IO单元自动排布算法(IOAP)。此算法及其相关软件直接应用于视频解码芯片和无线传感器网络处理器芯片(已流片成功)的物理设计流程中。结果表明,IOAP有效改善了芯片的电源网格,时序和布线结果,减少了布线努力,提高了设计收敛性。     

Grey relational clustering associated with CAPRI applied to FPGA placement

Grey relational clustering is used to minimise wire length during field programmable gate arrays (FPGA) placement and routing. The proposed Grey Relational Clustering Apply to Placement (GRAP) algorithm combines grey relational clustering and convex assigned placement for regular ICs method to construct a placement netlist, which was successfully used to solve the problem of minimising wire length in an FPGA placement. Upon calculating the grey relational grade, GRAP can rank the sequence and analyse the minimal distance in configuration logic blocks based on the grey relational sequence and combined connection-based approaches. The experimental results demonstrate that the GRAP effectively compares the Hibert, Z and Snake with bounding box (BB) cost function in the space-filling curve. The GRAP improved BB cost by 0.753%, 0.324% and 0.096% for the Hilbert, Z and Snake, respectively. This study also compares the critical path with the space-filling curve. The GRAP approach improved the critical path for Snake by 1.3% in the space-filling curve; however, the GRAP increased critical path wire by 1.38% and 0.03% over that of the Hilbert and Z of space-filling curve, respectively.     

超大规模集成电路无网格布线算法研究

本文提出一种高性能超大规模集成电路无网格布线算法，对于给定的布线平面，算法首先生成该布线平面的非均匀网格图，然后以绕障长度为布线参数，采用优化迷宫算法完成具体的布线过程。算法保证能够找到存在的最短布线路径，并能进行变线宽、变线距布线，布线速度很快，效果很好。     

A priori wire length distribution models with multiterminal nets

Interconnections are quickly becoming a dominant factor in the design of computer chips. Techniques to estimate interconnection lengths a priori (very early in the design flow) therefore gain attention and will become important for making the right design decisions when one still has the freedom to do so. However, at that time, one also knows least about the possible results of subsequent design steps. Conventional models for a priori estimation of wire lengths in computer chips use Rent's rule to estimate the number of terminals needed for communication between sets of gates. The number of interconnections then follows by taking into account that most nets are point-to-point connections. In this paper, we apply our previously introduced model for multiterminal nets to show that such nets have a fundamentally different influence on the wire length estimations than point-to-point nets. We then estimate the wire length distribution of Steiner tree lengths for applications related to routing resource estimation. Experiments show that the new estimated Steiner-length distributions capture the multiterminal effects much better than the previous point-to-point length distributions. The accuracy of the estimated values is still too low, as for the conventional point-to-point models, because we are still lacking a good model for placement optimization. However, the new results are a step closer to the application of wire length estimation techniques in real-world situations.     

A heuristic for constructing a rectilinear Steiner tree by reusing routing resources over obstacles

The obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem is a hot topic in very-large-scale integration physical design. In practice, most of the obstacles occupy the device layer and certain lower metal layers. Therefore, we can place wires on top of the obstacles. To maximize routing resources over obstacles, we propose a heuristic for constructing a rectilinear Steiner tree with slew constraints. Our algorithm adopts an extended rectilinear full Steiner tree grid as the routing graph. We mark two types of Steiner point candidates, which are used for constructing Steiner trees and refining solutions. A shortest path heuristic variant is designed for constructing Steiner trees and it takes into account slew constraint by inhibiting growth. Furthermore, we use a pre-computed strategy to avoid calculating slew rate repeatedly. Experimental results show that our algorithm maximizes routing resources over obstacles and saves routing resources outside obstacles. Compared with the conventional OARSMT algorithm, our algorithm reduces the wire length outside obstacles by as much as 18.74% and total wire length by as much as 6.03%. Our algorithm improves the latest related algorithm by approximately 2% in terms of wire length within a reasonable running time. Additionally, calculating the slew rate only accounts for approximately 15% of the total runing time.     

A fast congestion estimator for routing with bounded detours

Congestion estimation is an important issue for design automation of the VLSI layout. Fast congestion estimation provides an efficient means to adjust the placement and wire planning. A probabilistic model of interconnections enables designers to quickly predict routing congestion. We propose a powerful and fast estimation approach that allows wires to have bounded-length detours to bypass congestions. The method is more realistic and precise than the previous work. The experimental results demonstrate the effectiveness of the method on routing benchmarks.     

Wire congestion estimation in a bounded-bend model

Interconnect congestion estimation plays an important role in the physical design of integrated circuits. Fast congestion analysis prior to global routing enhances the placement quality and improves the routability for the subsequent routing phases. This article presents a novel congestion estimation method for a wire layout with bounded detours and bends. Experimental results on benchmarks demonstrate the efficiency and accuracy of our approach.