基于随机行走电容提取且保证准确度的线网时延计算方法

An Accuracy-Guaranteed Method for Calculating the Interconnect Delay Based on Random Walk Capacitance Extraction

从随机统计原理出发,考虑基于随机行走电容提取的多端线网时延计算,提出保证准确度的多端线网自适应互连时延计算方法.首先推导了互连时延的随机误差与随机行走电容提取结果误差的依赖关系,给出了时延误差的理论上限;然后提出了基于误差上限估计和基于误差微调的2种自适应互连时延计算策略,它们根据用户指定的时延误差阈值自动调整执行随机行走电容提取的精度设置与次数,并通过"断点续算"提取技术缩短整体计算时间.对实际电路版图中互连线网结构进行计算的实验结果表明,该方法能够保证时延结果的准确度,而基于误差微调的自适应策略比基于误差上限估计的策略效率更高,在确保时延误差可控的同时使包含电容提取的总计算时间最短.

Based on the stochastic theory, we consider the calculation of the delay of multi-terminal interconnect nets with random walk based capacitance extraction. An adaptive accuracy-guaranteed method for calculating the interconnect delay has been proposed. In this work, the relationship between the stochastic errors of interconnect delay and the stochastic errors of capacitances due to random walk algorithm has been derived, resulting to a theoretical upper bound of delay error. Then, two adaptive strategies are proposed for the accuracy-guaranteed delay calculation. One is based on the upper bound of delay error, and the other is based on an error fine-tuning approach. The method automatically adjusts the error threshold and the time of running the random walk based capacitance extraction, and employs a restoring extraction technique to largely reduce the runtime. The experimental results on interconnect structures from actual circuit layouts show that, the proposed method is able to guarantee the accuracy of calculated delay. And, the approach based on error fine-tuning is more efficient than the approach based on upper bound estimation of the delay error. The former reduces the total runtime including that for capacitance extraction to a small quantity while guaranteeing the stochastic delay error.