考虑拥挤度和性能的全芯片可控布线系统框架

提出一个全新的全芯片可控布线系统框架,同时考虑布线拥挤度和芯片性能.为了在总体布线和详细布线之间架起桥梁,该框架把总体布线和详细布线集成起来,交互进行,每完成一个线网的布线,都及时对布线资源进行更新,由此可以得到精确的资源估计结果,有利于指导后续总体布线决策.该系统框架的主要特征包括快速的基于模式的和基于外框约束下最短路算法的总体布线器、基于迷宫算法的拥挤度驱动的详细布线器以及在两个布线器之间很好的交互性.在该布线系统框架中,为了优化电路性能,在布线中关键线网被赋予更高的优先级.同时,为了优化不同的布线目标,可以采用不同的线网排序策略.该布线系统框架在一套公用的测试电路上完成测试,并与之前提出的多级布线系统框架进行比较,实验结果表明,文中提出的布线系统框架在电路性能、布通率和运行时间方面都取得了很大改进.     

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

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

针对一种岛式FPGA布局布线方法的研究与改进

针对一种岛式FPGA(Field Programmable Gate Array)芯片VS1000的架构,开发了一种布局布线工具VA,该工具在VPR的基础上做了两方面改进.第一,在传统布线算法的布线资源图基础上建立了全局信号布线资源图,完成了对全局信号的布线,使全局信号布线与其他信号布线独立起来,以达到减少全局信号相对延时和节省通用布线资源的目的.第二,提出了两种新的布线顺序:高扇出线网优先和高关键度线网优先.实验结果表明,对于标准测试电路,高扇出优先的布线顺序平均可减少21.8%的迭代次数,高关键度优先的布线顺序平均可减少22.3%的关键路径延时.     

一个快速高效进行布线拥挤优化的总体布线器

设计实现了一个高效的线长模式下基于多处理机的并行总体布线器.通过对非时延驱动模式下串、并行算法的总运行时间和求解时间的比较,表明该并行算法能够在保证求解质量无明显变化的前提下大大加快总体布线算法的求解速度.同时,也提出了基于分布式体系结构的并行总体布线算法.     

一个快速高效进行布线拥挤优化的总体布线器

设计实现了一个高效的线长模式下基于多处理机的并行总体布线器.通过对非时延驱动模式下串、并行算法的总运行时间和求解时间的比较,表明该并行算法能够在保证求解质量无明显变化的前提下大大加快总体布线算法的求解速度.同时,也提出了基于分布式体系结构的并行总体布线算法.     

Full-Chip Scalable Routing Framework Considering Congestion and Performance

提出一个全新的全芯片可控布线系统框架,同时考虑布线拥挤度和芯片性能.为了在总体布线和详细布线之间架起桥梁,该框架把总体布线和详细布线集成起来,交互进行,每完成一个线网的布线,都及时对布线资源进行更新,由此可以得到精确的资源估计结果,有利于指导后续总体布线决策.该系统框架的主要特征包括快速的基于模式的和基于外框约束下最短路算法的总体布线器、基于迷宫算法的拥挤度驱动的详细布线器以及在两个布线器之间很好的交互性.在该布线系统框架中,为了优化电路性能,在布线中关键线网被赋予更高的优先级.同时,为了优化不同的布线目标,可以采用不同的线网排序策略.该布线系统框架在一套公用的测试电路上完成测试,并与之前提出的多级布线系统框架进行比较,实验结果表明,文中提出的布线系统框架在电路性能、布通率和运行时间方面都取得了很大改进.     

一种减小关键路径延迟的回路布线法

传统的性能驱动布线算法受限于树形或固定的布线拓扑结构．本文提出一种回路性能优化布线算法，针对树形线网布线，通过在已存在的布线树上加入回路来减小所选择关键路径的延迟时间或线网的最大延迟．我们将互连线树归结为分布传输线网络并采用Ｅｌｍｏｒｅ延迟计算方法．本文证明，通过选择适当的ＲＣ，在连接节点与关键节点之间加入连线可达到减小所选择线网中关键路径延迟或线网最大延迟的目的．实验结果表明，我们的方法有效且可以集成在现有ＣＡＤ性能优化布线系统中．本文同时给出了所加入线段长度的计算方法．     

单主干权重排序布线算法

随着集成电路的发展,芯片的特征尺寸变得越来越小,模拟电路中的电流也变得越来越大,因大电流使互连线出现短路或开路的现象称为电迁移现象。针对电迁移现象,本文提出了一种单主干权重排序布线算法,它根据各端点电流值的大小将端点的布线顺序进行排序,使电流较大的线网先完成布线,以达到缩小布线面积的目标。这种算法满足了布线设计当中的基尔霍夫电流定律,最小设计规则以及避开障碍物等约束条件,最终实现多源多漏的线网拓扑结构。     

一种加速FPGA布线的不可满足子式求解算法

随着VLSI(Very Large Scale Integrated)芯片设计的规模越来越大,功能越来越复杂,在FPGA(Field Pro-grammable Gate Array)上实现或进行原型验证时,往往会出现布线拥塞或无法布通的情况.而不可满足子式能够迅速诊断FPGA无法布通的原因,并且精确定位关键线网.针对如何加速FPGA详细布线过程,提出了一种基于消解否证的启发式局部搜索算法,能够快速从布尔公式中提取不可满足子式.基于典型的FPGA布线测试集,与两种求解最小不可满足子式效率最高的算法进行了比较,结果表明局部搜索算法在运行效率方面显著优于分支限界算法与贪心遗传算法,而局部搜索算法也能得到最小不可满足子式;并且深入分析了不可满足子式在FPGA详细布线中的作用,能够加速芯片的设计与验证过程.     

FPGA布线结构的蒙特卡罗评估

提出一种基于蒙特卡罗技术的FPGA结构研究新方法。该方法在布线资源中随机产生均匀分布的开路故障,并绕开障碍物布线互连,不依赖于CAD算法和基准电路。开关块拓扑分析实例表明该方法与CAD方法的结论一致,而评估时间从15小时缩短到15分钟。     

Simultaneous Shield and Buffer Insertion for Crosstalk Noise Reduction in Global Routing

As VLSI technologies scale down, interconnect performance is greatly affected by crosstalk noise due to the decreasing wire separation and increased wire aspect ratio, and crosstalk has become a major bottleneck for design closure. The effectiveness of traditional buffering and spacing techniques for noise reduction is constrained by the limited available resources on chip. In this paper, we present a method for incorporating crosstalk reduction criteria into global routing under a broad power supply network paradigm. This method utilizes power/ground wires as shields between signal wires to reduce capacitive coupling, while considering the constraints imposed by limited routing and buffering resources. An iterative procedure is employed to route signal wires, assign supply shields, and insert buffers so that both buffer/routing capacity and signal integrity goals are met. In each iteration, shield assignment and buffer insertion are considered simultaneously via a dynamic programming-like approach. Our noise calculations are based on Devgan's metric, and our work demonstrates, for the first time, that this metric shows good fidelity on average. An effective noise margin inflation technique is also proposed to compensate for the pessimism of Devgan's metric. Experimental results on testcases with up to about 10000 nets point towards an asymptotic runtime that increases linearly with the number of nets. Our algorithm achieves noise reduction improvements of up to 53% and 28%, respectively, compared to methods considering only buffer insertion or only shield insertion after buffer planning.     

Improved predictability, timing yield and power consumption using hierarchical highways-on-chip planning methodology

Interconnect mis-prediction is a major problem in nano-scale design that may diminish the quality of physical design algorithms or may even result in design divergence. In this paper, a new interconnect-planning methodology based on assume and enforce strategy is presented. In this methodology, some regions of the chip are planned to provide auxiliary routing resources and improve the interconnect delay of critical nets during the floor-placement process. Each of these wealthy regions is called a highway-on-chip. The location of highways and their resources are gradually determined during the hierarchical floor-placement process. Experimental results show that the performance, timing yield, predictability and power consumption of the attempted benchmarks are improved by 13.66%, 10.02%, 20.11%, and 6.83% on average. These improvements are obtained at the cost of about 7.82% runtime overhead and less than 0.8% wirelength growth.     

一种新的基于知识的四边通道布线算法

本文提出了一种新的基于知识的双层四边通道布线算法,该算法对四边通道的布线是通过以下四步完成的。首先,对四边通道的四个角布线,其次,对关键线网优先布线,接下来,利用线网间相互制约关系进行同步增长布线;最后,对仍然没有完成连接的线网,用李氏算法布线。由于使用了启发式规则,使得该算法具有较高的布通率和布线效率。     

LSI版图设计中的一种P／G网布线法

本文提出了一种有效的P/G网布线算法和在积木块式布图系统中实现的策略。与以往算法比较,此算法允许每条电源网具有多个馈电脚存在。其策略包括四个部分:(1)一种有效的层次式自上而下的P/G网平面性分析和拓扑路径分配算法;(2)P/G网线宽的确定;(3)总体压缩和再布线后P/G网布线信息的动态修改;(4)与信号网一起的平面性无网格电源网通道详细嵌入。实验结果表明我们的P/G网布线方法可获得令人满意的布线结果。     

SAT based solutions for detailed routing of island style FPGA architectures

Detailed routing solutions for island style FPGA architectures using Boolean satisfiability (SAT) based formulations have been proposed in this paper. Due to decreasing size of ICs and hence, the increasing complexity of the routing resource constraints, routing has been a big challenge in electronic design automation field. Our proposed techniques work on multi-pin net routing where all nets are considered for routing in their intact form whereas, most of the existing routing solutions decompose multi-pin nets into two-pin nets for detailed routing to ease the problem. However this approach, apart from increasing the number of nets in the circuits, may also introduce pin doglegging which, when not permitted by the architecture of FPGA, would require extra constraints to eliminate. Many detailed routers adopt sequential detailed routing approaches which are vulnerable to the net ordering problem which may cause a routable circuit to be erroneously classified as unroutable. Our proposed techniques avoid these pitfalls by keeping the multi-pin nets intact and solve all nets simultaneously using SAT. The SAT-based multi-pin net dogleg-free formulations presented here achieve significant improvement over existing SAT-based solutions with respect to the number of variables and clauses used, thereby achieving greater scalability and also display comparable and sometimes better routability results on benchmark circuits when compared with other detailed routing solutions. Detailed routing is also significantly affected by the architecture of the switching blocks. This paper proposes SAT-based formulation for three different switch box architectures i.e. Subset, Wilton, and Universal switches. Our experiments clearly demonstrate how routing solutions for a circuit can differ significantly for different types of switch boxes.     

现代层次化可编程逻辑器件软件系统FDE2009

本文提出并实现了适用于现代层次化结构的FPGA芯片的CAD软件系统:FDE2009(FPGA Development Environment).该软件系统不但由工艺映射,布局布线,位流生成,编程下载等功能模块构成了一套完整的FPGA CAD流程,并且根据现代FPGA芯片层次化的结构特点,提出了逻辑分层的布局思想及由底至上逐层构建布线资源图的算法,提高了硬件资源的利用率及程序的运行效率.此外,本软件自定义了一套使用扩展性标志语言的文件系统,从而使其具有一定的通用性及良好的扩展性.软硬件协同测试结果表明该软件系统各模块功能正确,并能配合硬件高效的实现各类功能电路,是一套实用的FPGA软件系统.     

Stochastic Physical Synthesis Considering Prerouting Interconnect Uncertainty and Process Variation for FPGAs

Process variation and prerouting interconnect delay uncertainty affect timing and power for modern VLSI designs in nanometer technologies. This paper presents the first in-depth study on stochastic physical synthesis algorithms leveraging statistical static timing analysis (SSTA) with process variation and prerouting interconnect delay uncertainty for field-programmable gate arrays (FPGAs). Evaluated by SSTA using the placed and routed circuits, the stochastic clustering, placement, and routing reduce the mean delay by 5.0%, 4.0%, and 1.4%, respectively, and reduce the standard deviation of delay by 6.4%, 6.1%, and 1.4%, respectively for MCNC designs. The majority of improvements come from modeling interconnect delay uncertainty for clustering and from considering process variation for placement, while routing has less improvement on delay. In addition, we study the interaction between each individual design stage. When applying all stochastic algorithms concurrently, the mean delay and standard deviation are reduced by 6.2% and 7.5%, respectively. On the other hand, stochastic clustering with deterministic placement and routing is a good flow with little change to the entire flow, but the mean delay is reduced by 5.0%, the standard deviation is reduced by 6.4%, and the runtime is slightly reduced compared to the deterministic flow. Finally, while its improvement over timing is small, stochastic routing is able to reduce the total wire length by 4.5% and to reduce the overall runtime by 4.2% compared to deterministic routing.     

Fast coupled noise estimation for crosstalk avoidance in the MCGmultichip module autorouter

A multilayer, multichip module (MCM) router, called MCG, is introduced for x-y routing. An efficient method has been derived to allow candidate routes for the nets to be considered simultaneously for compatibility rather than incrementally extending routes or routing one net at a time as in many other techniques. This allows incorporation of accurate models for determining the potential for crosstalk problems during the routing process. MCG incorporates a crosstalk avoidance procedure which facilitates correct-by-design routing in systems susceptible to noise problems. In comparisons with other routers on industrial benchmarks, the MCG router has shown substantial improvement in routing density, number of layers, number of vias, and total interconnect length over routers such as V4R and SLICE. Our test results show up to 18% improvement in via count and up to 33% improvement in the required number of routing layers for these examples over V4R. One of the benchmarks presented contains 37 VHSIC gate arrays, over 7000 nets, and over 14000 pins (pads). Routing at finer pitches with crosstalk avoidance shows a further improvement in interconnect density