精确时延模型下满足时延约束的缓冲器数目最小化的算法

提出了在精确时延模型下,满足时延约束的缓冲器数目最小化的算法.给出一个两端线网,该算法可以求出满足时延约束的最小缓冲器数目.运用高阶时延模型计算互连线的时延,运用基于查找表的非线性时延模型计算缓冲器的时延.实验结果证明此算法有效地优化了缓冲器插入数目和线网的时延,在二者之间取得了较好的折中.算法的运行时间也是令人满意的.     

基于精确时延模型考虑缓冲器插入的互连线优化算法

随着VLSI电路集成度增大和特征尺寸的不断减小,连线的寄生效应不可忽略,互连线的时延在电路总时延中占了很大的比例,成为决定电路性能的主要因素.在互连时延的优化技术中,缓冲器插入是最有效的减小连线时延的方法.本文提出了一个在精确时延模型下,在布线区域内给定一些可行的缓冲器插入位置,对两端线网进行拓扑优化,并同时插入缓冲器以优化时延的多项式时间实现内的算法.我们的算法不但可以实现时延的最小化,也可以在满足时延约束的条件下,最小化缓冲器的插入数目,从而避免不必要的面积和功耗的浪费.     

采用精确时延模型基于路径的缓冲器插入时延优化

提出了一种基于路径的缓冲器插入时延优化算法 ,算法采用高阶模型估计连线时延 ,用基于查表的非线性时延模型估计门延迟 .在基于路径的时延分析基础上 ,提出了缓冲器插入的时延优化启发式算法 .工业测试实例实验表明 ,该算法能够有效地优化电路时延 ,满足时延约束     

采用精确时延模型基于路径的缓冲器插入时延优化

提出了一种基于路径的缓冲器插入时延优化算法,算法采用高阶模型估计连线时延,用基于查表的非线性时延模型估计门延迟.在基于路径的时延分析基础上,提出了缓冲器插入的时延优化启发式算法.工业测试实例实验表明,该算法能够有效地优化电路时延,满足时延约束.     

SOC布图设计中的互连优化算法

使用Elmore时延模型,对二端连线的缓冲器插入方法进行了详细的讨论.给出了最小时延下,缓冲器的最佳数量和位置;同时给出了在一定时延约束条件下的缓冲器的最小数量及位置;并在典型的0.18μm工艺参数条件下进行了测试.测试结果显示,缓冲器插入方法可以显著地减小线上的时延,而且缓冲器的数目将随着时延约束的放宽而迅速下降.当时延约束仅比最优时延多5%时,插入的缓冲器数目就降到了最佳缓冲器数的70%左右,这一结果对缓冲器插入算法具有普遍的指导意义.     

SOC布图设计中的互连优化算法

使用Elmore时延模型,对二端连线的缓冲器插入方法进行了详细的讨论.给出了最小时延下,缓冲器的最佳数量和位置;同时给出了在一定时延约束条件下的缓冲器的最小数量及位置;并在典型的0 .18μm工艺参数条件下进行了测试.测试结果显示,缓冲器插入方法可以显著地减小线上的时延,而且缓冲器的数目将随着时延约束的放宽而迅速下降.当时延约束仅比最优时延多5 %时,插入的缓冲器数目就降到了最佳缓冲器数的70 %左右,这一结果对缓冲器插入算法具有普遍的指导意义.     

优化时延与拥挤度的增量式布局算法

提出了一种优化时延的增量式布局算法,该算法根据时延分析的结果在迭代求解的过程中动态调整线网权值.在此基础上,提出了三种同时优化时延和拥挤度的多目标优化的布局算法,在满足时延和拥挤度约束的前提下对关键路径上的单元进行位置调整.实验结果表明该算法能够有效地提高芯片速度并降低走线拥挤.对于优化线长得到的布局方案,最长路径上的时延值在增量式布局之后能够降低10 % .     

优化时延与拥挤度的增量式布局算法

提出了一种优化时延的增量式布局算法,该算法根据时延分析的结果在迭代求解的过程中动态调整线网权值.在此基础上,提出了三种同时优化时延和拥挤度的多目标优化的布局算法,在满足时延和拥挤度约束的前提下对关键路径上的单元进行位置调整.实验结果表明该算法能够有效地提高芯片速度并降低走线拥挤.对于优化线长得到的布局方案,最长路径上的时延值在增量式布局之后能够降低10%.     

互连线网时延估算的一种有效算法

本文提出一种基于传递函数递推和系数匹配的互连线网时延估算法,该算法用二极点模型逼近互连线网的传递函数,仅通过计算某一频率点上的传递函数,就可利用导出的解析公式或拟合的经验公式进行快速时延估算,不必进行复杂的分量计算,算例表明,对于各个门限值,其计算结果均与ｓｐｉｃｅ计算的时延值发接近,计算量也比通常基于高阶分量计算的算法大为减少,在计算效率和模拟精度两方面得到较好折衷,对于互连线网时延估算具有实用     

带时延约束的FPGA布线算法

基于ＳＲＡＭ编程结构的门海型ＦＰＧＡ连线上的时延较之ＡＳＩＣ来说比较大,连线延迟不可预测．在很多应用中必须对关键路径的时延加以定量限制（包括上限、下限和一组路径的时延差）．时延约束的实现需要布图算法来保证．一般时延驱动的布线算法只能定性地优化时延性能,不能满足定量要求．本文提出了高性能ＦＰＧＡ最短路径布线算法,以它为主体的ＦＰＧＡ布线器能全面地考虑各种时延约束,更好地利用布线资源,对其它无时延约束的线网也可进行时延优化,提高整个芯片的性能     

Optimum buffer circuits for driving long uniform lines

The design of optimum buffer circuits for driving long uniform lines is discussed. Given a uniform line, the size of the buffer driving the line, and the value of the capacitive load driven by the line, the problem considered consists of determining the type, number, and position of buffers that minimize the delay in the line. A variation of this problem that is also considered consists of minimizing the delay in the line when the area occupied by the buffers is constrained; this leads to the solution of the problem of minimizing the delay in driving a pure capacitive load under buffer area constraint. The optimal solution is formally developed, and some very good approximate solutions that can be obtained via simple computations are presented. It is shown that accepting a small increase in delay (of usually 5% over the minimum) can lead to a significant (about 50%) decrease in the area occupied by the buffers. Design curves that allow the reader to determine the optimum buffers with little effort are presented     

The impact of network topology on delay bound in wireless Ad Hoc networks

We consider single channel wireless networks with interference constraint among the links that can be activated simultaneously. The traffic flows are assumed to be single hop. Delay performance of the well known throughput optimal maximum weight link scheduling algorithm has been studied recently. In this paper, we study the relation between network topology and delay of maximum weight link scheduling algorithm. First, we consider 1-hop interference model. Under this interference model, an upper bound for the average delay of packets is derived analytically in terms of edge chromatic number of the network graph. Then the results have been extended to the case of general interference model. Under this model of interference, an upper bound for delay as a function of chromatic number of conflict graph is derived. Since chromatic number and edge chromatic number are network topology parameters, the results show that how the upper bound of delay is affected by network topology. Simulation results confirm our analytical relations.     

Dynamic burst length controlling algorithm-based loss differentiation in OBS networks through shared FDL buffers

The FDL buffers can have only discrete delay values. Because of this discontinuity, in order to construct the FDL buffers, some parameters such as the offered load, the average data burst length, and the basic delay unit, of which the length of each FDL is consecutive multiples, should be considered. This means that if one or more parameters change, new FDL buffers are required. So, even when one or more parameters change, in order to minimize the effect of the change, a new service differentiation algorithm dynamically controlling data burst length based on a shared-type feed-forward FDL architecture is proposed in this paper. Various results show that the algorithm improves fairness between classes and significantly reduces the fluctuation of the number of delay lines for each class.     

A unified design methodology for CMOS tapered buffers

In this paper, the various disparate approaches to CMOS tapered buffer design are unified into an integrated design methodology. Circuit speed, power dissipation, physical area, and system reliability are the four performance criteria of concern in tapered buffers, and each places a separate, often conflicting, constraint on the design of a tapered buffer. Enhanced short-channel tapered buffer design equations are presented for propagation delay and power dissipation, as well as a new split-capacitor model of hot-carrier reliability of tapered buffers and a two-component physical area model. Each performance criterion is individually investigated and analyzed with respect to the number of stages and tapering factor, and the interaction of the four criteria is examined to develop both a qualitative and a quantitative understanding of the various design tradeoffs. The creation of process dependent look-up tables for optimal buffer design is described, and a methodology to apply these look-up tables to application-specific tapered buffers for both unconstrained and constrained systems is developed     

Packet delay in optical circuit-switched networks

A framework is provided for evaluation of packet delay distribution in an optical circuit-switched network. The framework is based on a fluid traffic model, packet queueing at edge routers, and circuit-switched transmission between edge routers. Packets are assigned to buffers according to their destination, delay constraint, physical route and wavelength. At every decision epoch, a subset of buffers is allocated to end-to-end circuits for transmission, where circuit holding times are based on limited and exhaustive circuit allocation policies. To ensure computational tractability, the framework approximates the evolution of each buffer independently. "Slack variables" are introduced to decouple amongst buffers in a way that the evolution of each buffer remains consistent with all other buffers in the network. The delay distribution is derived for a single buffer and an approximation is given for a network of buffers. The approximation entails finding a fixed point for the functional relation between the "slack variables" and a specific circuit allocation policy. An analysis of a specific policy, in which circuits are probabilistically allocated based on buffer size, is given as an illustrative example. The framework is shown to be in good agreement with a discrete event simulation model.     

Joint selection of source and channel rate for VBR videotransmission under ATM policing constraints

Variable bit-rate (VBR) transmission of video over ATM networks has long been said to provide substantial benefits, both in terms of network utilization and video quality, when compared with conventional constant bit-rate (CBR) approaches. However, realistic VBR transmission environments will certainly impose constraints on the rate that each source can submit to the network. We formalize the problem of optimizing the quality of the transmitted video by jointly selecting the source rate (number of bits used for a given frame) and the channel rate (number of bits transmitted during a given frame interval). This selection is subject to two sets of constraints, namely, (1) the end-to-end delay has to be constant to allow for real-time video display and (2) the transmission rate has to be consistent with the traffic parameters negotiated by user and network. For a general class of constraints, including such popular ones as the leaky bucket, we introduce an algorithm to find the optimal solution to this problem. This algorithm allows us to compare VBR and CBR under the same end-to-end delay constraints. Our results indicate that variable-rate transmission can increase the quality of the decoded sequences without increases in the end-to-end delay. Finally, we show that for the leaky-bucket channel, the channel constraints can be combined with the buffer constraints, such that the system is identical to CBR transmission with an additional, infrequently imposed constraint. Therefore, video quality with a leaky-bucket channel can achieve the same quality of a CBR channel with larger physical buffers, without adding to the physical delay in the system