期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于SAT的快速电路时延计算 被引量：2

Fast Circuit Delay Calculation Based on SAT Solvers
下载PDF
导出
摘要 针对现有的基于时间展开电路求解时延算法在电路规模较大或者时延模型精度较高时效率较低的问题,提出一种基于子电路抽取的电路时延计算方法.基于展开电路,通过分析输出端约束找到相关的输出端,利用回溯抽取与这些输出端相关的逻辑锥子电路,并在子电路而不是在展开电路上进行求解,由于抽取的子电路的规模远小于展开电路的规模,加速了求解过程;同时提出了抽象电路的概念,并分析了抽取子电路的同构特性,通过在抽象电路上进行预处理得到学习子句,从而可以利用学习子句加速每一次的SAT求解过程.在ISCAS85和ISCAS89电路上的实验结果表明,采用文中方法使得电路时延的求解效率平均提高了约8倍. Traditional time unrolling based circuit delay calculation method is inefficient in the case that large circuits are analyzed or accurate delay models are adopted. In order to speedup circuit delay calculation, an improved method by sub-circuit extraction is proposed in this paper. On one hand, a sub-circuit is constructed by analyzing output constraints and extracting related logic cones from the unrolled circuit. The circuit delay is checked on the extracted sub-circuit instead of the unrolled circuit, thus the calculation process is speeded up. On the other hand, the concept of abstract circuit is proposed and preprocess is applied on it to find out the shared structures among extracted sub-circuits. The learning clauses derived from preprocessing can be utilized to speed up SAT solving at each checking step. Experimental results on ISCAS85 and ISCAS89 benchmark demonstrate that the proposed approach can improve the efficiency of circuit delay calculation by about 8 times over the traditional method on average.
作者 何子键 吕涛 李华伟 李晓维
机构地区 中国科学院计算机系统结构重点实验室 中国科学院计算技术研究所 中国科学院研究生院
出处 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2011年第3期480-487,共8页 Journal of Computer-Aided Design & Computer Graphics
基金 国家自然科学基金(60776031 60633060 60906013 60921002 60831160526) 国家"九七三"重点基础研究发展计划项目(2011CB302503)
关键词 可满足性 电路时延 电路展开 satisfiability （SAT） circuit delay circuit unrolling
分类号 TP391.72 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献12

  • 1Long W N,Yang S Y,Li Z C,et al.Memory efficient ATPG for path delay faults[C]//Proceedings of the 6th Asian Test Symposium.Los Alamitos:IEEE Computer Society Press,1997:326-331.
  • 2Liou J J,Krstic A,Wang L C.et al.False-path-aware statistical timing analysis and efficient path selection for delay testing and timing validation[C]//Proceedings of the 39th Design Automation Conference.New York:ACM Press,2002:566-569.
  • 3Moskewicz M W,Madigan C F,Zhao Y,et al.Chaff:engineering an efficient SAT solver[C]//Proceedings of the 38th Design Automation Conference.New York:ACM Press,2001:530-535.
  • 4Zhang L T,Madigan C F,Moskewicz M H,et al.Efficient conflict driven learning in a Boolean satisfiability solver[C]//Proceedings of the IEEE//ACM International Conference on Computer-Aided Design.Los Alamitos:IEEE Computer Society Press,2001:279-285.
  • 5Eén N,Biere A.Effective preprocessing in SAT through variable and clause elimination[M]//Lecture Notes in Computer Science.Heidelberg:Springer,2005,3569:61-75.
  • 6张旻晋,李华伟,李晓维.面向最大串扰噪声的测试生成方法[J].计算机辅助设计与图形学学报,2009,21(4):448-453. 被引量：2
  • 7Lam W K C,Brayton R K,Sangiovanni-Vincentelli A L.Circuit delay models and their exact computation using timed boolean functions[C]//Proceedings of the 30th International Design Automation Conference.New York:ACM Press,1993:128-134.
  • 8Xiang D,Zhao Y,Li K W,et al.Fast and effective fault simulation for path delay faults based on selected testable paths[C]//Proceedings of IEEE International Test Conference.Los Alamitos:IEEE Computer Society Press,2007:1-10.
  • 9Roy S,Chakrabarti P P,Dasgupta P.Event propagation for accurate circuit delay calculation using SAT[J].ACM Transactions on Design Automation of Electronic Systems,2007,12(3):Article No.36.
  • 10Tadesse D,Sheffield D,Lenge E,et al.Accurate timing analysis using SAT and pattern-dependent delay models[C]//Proceedings of the Conference on Designs,Automation and Test in Europe.San Jose:EDA Consortium Press,2007:1018-1023.

二级参考文献16

  • 1Cheng K T, Dey S, Rodgers M, et al. Test challenges for deep sub-micron technologies [C] //Proceedings of Design Automation Conference, Los Angeles, 2000:142-149
  • 2Rubio A, Itazaki N, Xu X L, et al. An approach to the analysis and detection of crosstalk faults in digital VLSI circuits [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1994, 13(3):387-394
  • 3Lee K T, Nordquist C, Abraham J A. Automatic test pattern generation for crosstalk glitches in digital circuits [C]// Proceedings of IEEE VLSI Test Symposium, Princeton, 1998:34-39
  • 4Chen W Y, Gupta S K, Breuer M A. Test generation in VLSI circuits for crosstalk noise [C] //Proceedings of IEEE International Test Conference, Washington D C, 1998; 641- 650
  • 5Kundu S, Zachariah S T, Chang Y S, et al. On modeling erosstalk faults [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24 (12): 1909-1915
  • 6Glebov A, Gavrilov S, Blaauw D, etal. False-noise analysis using logic implications [C] //Proceedings of International Conference on Computer Aided Design, San Jose, 2001 : 515- 521
  • 7Bai X L, Dey S, Krstic A. HyAC: a hybrid structural SAT based ATPG for crosstalk [C] //Proceedings of International Test Conference, Charlotte, 2003 : 112-121
  • 8Chen P H, Keutzer K. Towards true crosstalk noise analysis [C] //Proceedings of International Conference on Computer Aided Design, San Jose, 1999; 132-138
  • 9Ganeshpure K, Kundu S. Automatic test pattern generation for maximal circuit noise in multiple aggressor crosstalk faults [C] //Proceedings of Design, Automation & Test in Europe Conference & Exhibition, Nice, 2007:540-545
  • 10Zhang M J, Li X W. Test generation for crosstalk glitches considering multiple coupling effects [C] //Proceedings of the 16th IEEE Asian Test Symposium, Beijing, 2007:259-264

共引文献1

同被引文献25

  • 1Sun Yu-feng, Zhao Guang-yan. Analog circuit fault simulation based on Saber[C]. International Conference on Computational and Information Sciences, 2010,388-391.
  • 2Sun Chuan-wei, Chang Xiao-wei, Liu Jin-gao. A novel teaching method for High Frequency Circuit[C]. 2nd International Conference on Education Technology and Computer, 2010:120-123.
  • 3Mita Makoto, Maruyama Satoshi, Yi Yuheon, et al. Multi-physics Analysis for micro electromechanical systems based on e-lectrical circuit simulator[J]. Journal of Transactions on Electrical and Electronic Engineering, 2011,6(2) :180-189.
  • 4Graupner, Achim, Jancke, etc. Generator Based Approach for Analog Circuit and Layout Design and Optimization[C]. Design, Automation and Test in Europe, 2011:1675-1680.
  • 5Georgakos G,Schlichtmann U,Schneider R,et al.Reliability challenges for electric vehicles:From devices to architecture and systems software[C]//Proceedings of the 50th ACM/EDAC/IEEE Design Automation Conference.Piscataway:IEEE Press,2013:1-9.
  • 6Cocharan R,Reda S.Consistent runtime thermal prediction and control through workload phase detection[C]//Proceedings of the 47th ACM/EDAC/IEEE Design Automation Conference.Piscataway:IEEE Press,2010:62-67.
  • 7Liu Yuxi,Ye Rong,Yuan Feng,et al.Optimization for timing-speculated circuits by redundancy addition and removal[C]//Proceedings of 18th IEEE European Test Symposium.Los Alamitos:IEEE Computer Society Press,2013:1-6.
  • 8Yang Y,Li KSM.Temperature-aware dynamic frequency and voltage scaling for reliability and yield enhancement[C]//Proceedings of Asia and South Pacific Design Automation Conference.New York:IEEE Press,2009:49-54.
  • 9Pourshaghaghi HR,De Gyvez JP.Dynamic voltage scaling based on supply current tracking using fuzzy logic controller[C]//Proceedings of 16th IEEE International Conference on Electronics,Circuits and Systems.Piscataway:IEEE Press,2009:779-782.
  • 10Shuji T,Masahiro F,Takashi K.A new delay distribution model to take long-term degradation into account[C]//Proceedings of the 13th International Symposium on Quality Electronic Design.Los Alamitos:IEEE Computer Society Press,2013:1-4.

引证文献2

二级引证文献2

计算机辅助设计与图形学学报
2011年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部