基于关键路径的三模冗余表决器插入算法

在FPGA的三模冗余设计中,寄存器的反馈环路会导致错误持续出现,严重影响三模冗余的容错性能,因此需要在寄存器的反馈环路上插入表决器。该文首次提出了一种针对映射后网表进行三模冗余设计的方法,同时提出了基于关键路径的表决器插入算法,该算法在表决器的插入时避开关键路径,缓解了三模冗余设计中插入表决器时增加延时的影响。与国外同类算法相比,该文算法在不降低电路可靠性的前提下,以不到1%的面积开销,使得关键路径延时减少3%~10%,同时算法运算速度平均提高35.4%。     

DMR +: An efficient alternative to TMR to protect registers in Xilinx FPGAs

Registers are one of the circuit elements that can be affected by soft errors. To ensure that soft errors do not affect the system functionality, Triple Modular Redundancy (TMR) is commonly used to protect registers. TMR can effectively protect against errors affecting a single flip-flop and has a low overhead in terms of circuit delay. The main drawback of TMR is that it requires more than three times the original circuit area as the flip-flops are triplicated and additional voting logic is inserted. Another alternative is to protect registers using Error Correction Codes (ECCs), but those typically require a large circuit delay overhead and are not suitable for high speed implementations. In this paper, DMR + an alternative to TMR to protect registers in FPGAs, is presented. The proposed scheme exploits the FPGA structure to achieve a reduction in the FPGA resources (LUTs and Flip-Flops) at the cost of a certain overhead in delay. DMR + can correct all single bit errors like TMR but is more vulnerable to multiple bit errors. To evaluate the benefits, the DMR + technique has been implemented and compared with TMR considering standalone registers and also some simple designs.     

时延驱动的整平面整体布线算法

本文结出了一个新的时延驱动的整体布线算法．算法采用了整平面布线技术，从而具有快速求解的特点且无网序问题的困扰．算法优化的目标是使所有线网的最大时延之和最小，尤其是在关键路径上的线网实际电路的布线结果表明该算法可有效地改善关键路径上线网的时延．     

A routing algorithm for FPGAs with time-multiplexed interconnects

Previous studies show that interconnects occupy a large portion of the timing budget and area in FPGAs.In this work,we propose a time-multiplexing technique on FPGA interconnects.In order to fully exploit this interconnect architecture,we propose a time-multiplexed routing algorithm that can actively identify qualified nets and schedule them to multiplexable wires.We validate the algorithm by using the router to implement 20 benchmark circuits to time-multiplexed FPGAs.We achieve a 38%smaller minimum channel width and 3.8%smaller circuit critical path delay compared with the state-of-the-art architecture router when a wire can be time-multiplexed six times in a cycle.     

A fast and efficient technique to apply Selective TMR through optimization

Fault tolerance is an important factor for circuits in critical applications, especially those working in harsh environments. There are many techniques to increase reliability of circuits, being those based on redundancy very popular. In this way, Triple Modular Redundancy (TMR) is frequently used, but it usually incurs high area costs. That is why other alternative techniques, as Selective TMR, are used in order to reduce this cost. In this technique, only a subset of registers is tripled, those that are more sensitive and produce a higher error rate in the circuit. However, the problem of these methodologies is the complexity of finding the optimal set of registers to triple, what usually leads to very high computation times. In this paper, a novel solution that improves Selective TMR is presented, based on the automatic and fast calculation of an initial partition prior to the optimization process. The solution has been tested on a real communication circuit, a Feed-Forward Equalizer.     

An Area Optimization Method for Digital Filter Design

In this paper, we propose an efficient design method for area optimization in a digital filter. The conventional methods to reduce the number of adders in a filter have the problem of a long critical path delay caused by the deep logic depth of the filter due to adder sharing. Furthermore, there is such a disadvantage that they use the transposed direct form (TDF) filter which needs more registers than those of the direct form (DF) filter. In this paper, we present a hybrid structure of a TDF and DF based on the flattened coefficients method so that it can reduce the number of flip‐flops and full‐adders without additional critical path delay. We also propose a resource sharing method and sharing‐pattern searching algorithm to reduce the number of adders without deepening the logic depth. Simulation results show that the proposed structure can save the number of adders and registers by 22 and 26%, respectively, compared to the best one used in the past.     

Timing slack optimization approach using FPGA hybrid routing strategy of rip-up-retry and pathfinder

To improve the path slack of Field Programmable Gate Array （FPGA）, this paper proposes a timing slack optimization approach which utilizes the hybrid routing strategy of rip-up-retry and pathfinder. Firstly, effect of process variations on path slack is analyzed, and by constructing a col- location table of delay model that takes into account the multi-corner process, the complex statistical static timing analysis is successfully translated into a simple classical static timing analysis. Then, based on the hybrid routing strategy of rip-up-retry and pathfinder, by adjusting the critical path which detours a long distance, the critical path delay is reduced and the path slack is optimized. Experimental results show that, using the hybrid routing strategy, the number of paths with negative slack can be optimized （reduced） by 85.8% on average compared with the Versatile Place and Route （VPR） tim- ing-driven routing algorithm, while the run-time is only increased by 15.02% on average.     

一种基于时延配置表的FPGA静态时序分析算法

为减小现场可编程门阵列(FPGA)关键路径的延时误差,提出一种基于时延配置表的静态时序分析算法。算法建立了一种基于单元延时与互连线延时配置表的时延模型。该模型考虑了工艺角变化对延时参数的影响,同时在时序分析过程中,通过分析路径始节点与终节点的时钟关系,实现了复杂多时钟域下的路径搜索与延时计算。实验结果表明,与公认的基于查找表的项目评估技术(PERT)算法和VTR算法相比,关键路径延时的相对误差平均减少了8.58%和6.32%,而运行时间平均仅增加了19.96%和9.59%。     

一种考虑空间关联工艺偏差的统计静态时序分析方法

为了准确评估工艺参数偏差对电路延时的影响,该文提出一种考虑空间关联工艺偏差的统计静态时序分析方法。该方法采用一种考虑非高斯分布工艺参数的二阶延时模型,通过引入临时变量,将2维非线性模型降阶为1维线性模型;再通过计算到达时间的紧密度概率、均值、二阶矩、方差及敏感度系数,完成了非线性非高斯延时表达式的求和、求极大值操作。经ISCAS89电路集测试表明,与蒙特卡洛仿真(MC)相比,该方法对应延时分布的均值、标准差、5%延时点及95%延时点的平均相对误差分别为0.81%, -0.72%, 2.23%及-0.05%,而运行时间仅为蒙特卡洛仿真的0.21%,证明该方法具有较高的准确度和较快的运行速度。     

改进BM算法的高速RS译码器方案及其FPGA实现

介绍了一种高速的RS译码器的结构方案。由于一般BM算法的实现结构不规则,以及延时过长的缘故,在VLSI的设计中,广泛采用的是eE算法,采用的改进BM算法,使得BM算法的实现结构规则,并且延时更小。另外还采用了一种新的有限域乘法结构,有规则的结构,易于HDL语言实现。     

基于概率增益的电路划分算法

该文提出了一种新的划分算法,算法中引入可变线网权重。由于超图(hypergraph)中的线网连接节点数一般多于两个,为了充分将线网增加的权重作用到与该线网相连的所有节点上去,线网增益采用了概率增益模型。该算法与原有算法相比较,可以有效地让电路的划分跳出局部最小,结果有较大的改进,特别是当电路规模比较大的时候,改进更明显。由于采用概率增益模型,出现浮点数,节点增益的存储采用了平衡二叉树(balanced binary tree),因此算法的速度相对于FM算法有所下降,但是时间复杂度仍然接近为线性复杂度,时间复杂度为O(P log2(n))(P为电路所有逻辑单元的引脚数之和,n为电路的逻辑单元数)。     

The impact of intra-die device parameter variations on path delaysand on the design for yield of low voltage digital circuits

The yield of low voltage digital circuits is found to he sensitive to local gate delay variations due to uncorrelated intra-die parameter deviations. Caused by statistical deviations of the doping concentration they lead to more pronounced delay variations for minimum transistor sizes. Their influence on path delays in digital circuits is verified using a carry select adder test circuit fabricated in 0.5 and 0.35 μm complementary metal-oxide-semiconductor (CMOS) technologies with two different threshold voltages. The increase of the path delay variations for smaller device dimensions and reduced supply voltages as well as the dependence on the path length is shown. It is found that circuits with a large number of critical paths and with a low logic depth are most sensitive to uncorrelated gate delay variations. Scenarios for future technologies show the increased impact of uncorrelated delay variations on digital design. A reduction of the maximal clock frequency of 10% is found for, for example, highly pipelined systems realized in a 0.18-μm CMOS technology     

Design methodology for synthesizing clock distribution networksexploiting nonzero localized clock skew

An integrated top-down design methodology is presented in this brief for synthesizing high performance clock distribution networks based on application dependent localized clock skew. The methodology is divided into four phases: (1) determining an optimal clock skew schedule composed of a set of nonzero clock skew values and the related minimum clock path delays; (2) designing the topology of the clock distribution network with delays assigned to each branch based on the circuit hierarchy, the aforementioned clock skew schedule, and minimizing process and environmental delay variations; (3) designing circuit structures to emulate the delay values assigned to the individual branches of the clock tree; and (4) designing the physical layout of the clock distribution network. The clock distribution network synthesis methodology is based on CMOS technology. The clock lines are transformed from distributed resistive capacitive interconnect lines into purely capacitive interconnect lines by partitioning the RC interconnect lines with inverting repeaters. Variations in process parameters are considered during the circuit design of the clock distribution network to guarantee a race-free circuit. Nominal errors of less than 2.5% for the delay of the clock paths and 7% for the clock skew between any two registers belonging to the same global data path as compared with SPICE Level-3 are demonstrated     

可演化TMR容错表决电路的设计研究

在高温、辐射等恶劣环境下微电子设备的可靠性要求越来越高,利用演化硬件(EHW)原理,将EHW技术与三模块冗余(TMR)容错技术相结合,在FPGA上实现可演化的TMR表决电路,使硬件本身具有自我重构和自修复能力,大大提高了系统的可靠性.     

TOPEX/Poseidon microwave radiometer (TMR). III. Wet troposphererange correction algorithm and pre-launch error budget

For pt.II see ibid., vol.33, no.1, p.138-46 (1995). The sole mission function of the TOPEX/Poseidon microwave radiometer (TMR) is to provide corrections for the altimeter range errors induced by the highly variable atmospheric water vapor content. The three TMR frequencies are shown to be near-optimum for measuring the vapor-induced path delay within an environment of variable cloud cover and variable sea surface flux background. After a review of the underlying physics relevant to the prediction of 5-40 GHz nadir-viewing microwave brightness temperatures, the authors describe the development of the statistical, two-step algorithm used for the TMR retrieval of path delay. Test simulations are presented which demonstrate the uniformity of algorithm performance over a range of cloud liquid and sea surface wind speed conditions. The results indicate that the inherent algorithm error (assuming noise free measurements and an exact physical model) is less than 0.4 cm of retrieved path delay for a global representation of atmospheric conditions. An algorithm error budget is developed which predicts an overall algorithm accuracy of 0.9 cm when modeling uncertainties are included. When combined with expected TMR antenna and brightness temperature accuracies, an overall measurement accuracy of 1.2 cm for the wet troposphere range correction is predicted     

一种多线程FPGA时序驱动布线算法

随着现场可编程门阵列(FPGA)器件尺寸不断增大,计算机辅助设计(CAD)工具运行时间成为突出的问题。布线是FPGA的CAD流程中最为耗时的一个阶段,一种能有效缩短布线时间的方法就是并行布线。本文提出一种减少FPGA时序驱动布线算法运行时间的多线程方法。该算法首先将信号按照线网的扇出数量进行排序,再将排序后的线网均匀分配到各个线程中,最后并发执行所有的线程。在布线质量没有受到显著影响的前提下,即线长增加2.58%,关键路径延时增加1.78%的情况下,相对于传统通用布局布线工具(VPR)时序驱动布线算法8线程下的加速比为2.46。     

Critical Path Selection for Delay Testing Considering Coupling Noise

The objective of delay testing is to detect any defects or variations that manifest into timing failures. In path based delay testing this is done by testing a subset of paths in the circuit that are more likely to fail and hence are critical. Since path delays are vector dependent, the set of critical paths selected depends on the vectors assumed when estimating the path delays. This implies that to find the real critical paths, it is important to consider the effect of dynamic (vector dependent) delay effects such as coupling noise and supply noise during path selection. In this work a methodology to incorporate the effect of coupling noise during path selection is described. For any given path, both logic and timing constraints are extracted and a constrained optimization problem is formulated to estimate the maximum path delay in the presence of coupling noise.     

Seamless Pipelining of DSP Circuits

Pipelining is a popularly used technique to achieve higher frequency of operation of digital signal processing (DSP) applications, by reducing the critical path of circuits. But conventionally critical path is estimated by the discrete component timing model in terms of the times required for the computation of additions and multiplications, where arithmetic circuits are considered as discrete components. Pipeline registers are inserted in between arithmetic circuits to reduce the estimated critical path. In this paper, we show that very often the architecture-level pipelining, based on the discrete component timing model, does not result in significant reduction in critical path, but on the other hand increases the latency and register complexity. In order to derive greater advantage of pipelining, propagation delays of different combinational sections could be evaluated precisely at gate level or at least at the level of one-bit adders, and based on that, the critical path could be reduced by placing the pipeline registers seamlessly across the combinational datapath without restricting them to be placed only in between arithmetic circuits. In this paper, we present adequately precise evaluation of propagation delays across combinational path as a network of arithmetic circuits based on seamless view of signal propagation. Using the precise information of propagation delay of combinational sections, we identify the best possible locations of pipeline registers in order to reduce the critical path up to the desired limit. The proposed seamless pipelining approach is found to achieve the desired acceleration of DSP applications without significant pipeline overhead in terms of latency and register complexity.     

Crosstalk noise reduction in synthesized digital logic circuits

As CMOS technology scales into the deep submicrometer regime, digital noise is becoming a metric of importance comparable to area, timing, and power, for analysis and design of CMOS VLSI systems. Noise has two detrimental effects in digital circuits: First, it can destroy logical information carried by a circuit net. Second, it causes delay uncertainty: Non critical paths might become critical because of noise. As a result, circuit speed becomes limited by noise, primarily because of capacitive coupling between wires. Most design approaches address the crosstalk noise problem at the layout generation stage, or via postlayout corrections. With continued scaling, too many circuit nets require corrections for noise, causing a design convergence problem. This work suggests to consider noise at the gate-level netlist generation stage. The paper presents a simplified analysis of on-chip crosstalk models, and demonstrates the significance of crosstalk between local wires within synthesized circuit blocks. A design flow is proposed for automatically synthesizing CMOS circuits that have improved robustness to noise effects, using standard tools, by limiting the range of gate strengths available in the cell library. The synthesized circuits incur a penalty in area/power, which can be partially recovered in a single postlayout corrective iteration. Results of design experiments indicate that delay uncertainty is the most important noise-related concern in synthesized static CMOS logic. Using a standard synthesis methodology, critical path delay differences up to 18% of the clock cycle time have been observed in functional blocks of microprocessor circuits. By using the proposed design flow, timing uncertainty was reduced to below 3%, with area and power penalties below 20%.     

Efficient logic-level timing analysis using constraint-guidedcritical path search

As the operating speed of digital circuits dramatically increases with the advance of VLSI technology, it is becoming more critical to ensure that the circuits are free from timing-related design errors. In a traditional static timing approach nonfunctional paths cannot be distinguished from functional ones since the functionality of a circuit is ignored. This often results in overestimation of circuit delay and can degrade the circuit performance. In today's design methodology where the use of automated logic synthesis and module-based design are popular, circuits with a very large number of nonfunctional (false) paths are common. This paper describes an efficient logic-level timing analysis approach that can provide an accurate delay estimate of a digital circuit which may have many long false paths. By using logic incompatibilities in a circuit as constraints for critical path search, the algorithm determines the longest sensitizable path without explicit path enumeration. Since the number of false paths that can be implicitly eliminated is potentially exponential to the number of path constraints, performance improvement is significant