Fault simulation with parallel exact critical path tracing in multiple core environment
Pages 1180 - 1185
Abstract
A novel fault simulation method is proposed, based on exact critical path tracing beyond the Fan-out-Free Regions (FFR) throughout the full circuit. The method exploits two types of parallelism: bit-level parallelism for multiple pattern reasoning, and distribution the fault reasoning process between different cores in a multi-core processor environment. To increase the speed and accuracy of fault simulation, compared with previous methods, a mixed level fault reasoning approach is developed, were the fan-out re-convergence is handled on the higher FFR network level, and the fault simulation inside of FFRs relies on the gate-level information. To allow a uniform and seamless fault reasoning, Structurally Synthesized BDDs (SSBDD) are used for modeling on both levels. Experimental research demonstrated very promising results in increasing the speed and scalability of the method.
References
[1]
J. A. Waicukauski and et al., Fault simulation for structured VLSI, VLSI Systems Design, pp. 20--32, Dec. 1985
[2]
B. Underwood, J. Ferguson. The Parallel Test Detect Fault Simulation Algorithm. ITC, pp. 712--717, 1989
[3]
M. Abramovici, P. R. Menon, D. T. Miller. Critical Path Tracing An Alternative to Fault Simulation. Proc. 20th Design Automation Conference, pp. 2--5, 1987.
[4]
K. J. Antreich, M. H. Schulz. Accelerated Fault Simulation and Fault Grading in Combinational Circuits. IEEE Trans. On Computer-Aided Design, Vol. 6, No. 5, pp. 704--712, 1987.
[5]
F. Maamari, J. Rajski. A Method of Fault Simulation Based on Stem Region. IEEE Trans. on CAD, Vol. 9, No. 2, pp. 212--220, 1990.
[6]
D. Harel, R. Sheng, J. Udell. Efficient Single Fault Propagation in Combinational Circuits. Int. Conf. on CAD, pp. 2--5, 1987.
[7]
D. B. Armstrong. A deductive method for simulating faults in logic circuits. IEEE Trans. Comp., C-21(5), 464--471, 1972.
[8]
E. G. Ulrich, T. Baker. Concurrent simulator of nearly identical digital networks. IEEE Trans. on Comp., 7(4), pp. 39--44, 1974.
[9]
W. T. Cheng, M. L. Yu. Differential fault simulation: a fast method using minimal memory. DAC, pp. 424--428, 1989.
[10]
L. Wu, D. M. H. Walker, A Fast Algorithm for Critical Path Tracing in VLSI Digital Circuits, 20th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems(DFT'05), 3--5 October, 2005, pp. 178--186.
[11]
R. Ubar, S. Devadze, J. Raik, A. Jutman. Ultra Fast Parallel Fault Analysis on Structural BDDs. 12th IEEE European Test Symposium ETS 2007, Freiburg, Germany, May 20--24, 2007.
[12]
R. Ubar, S. Devadze, J. Raik, A. Jutman. Parallel X-Fault Simulation with Critical Path Tracing Technique. IEEE Conf. Design, Automation & Test in Europe - DATE-2010, Dresden, Germany, March 8--12, 2010, pp. 1--6.
[13]
Thayse, Boolean Calculus of Differences, Springer Verlag, 1981.
[14]
R. Ubar, S. Devadze, J. Raik, A. Jutman. Parallel Fault Backtracing for Calculation of fault Coverage. 13th Asia and South Pacific Design Automation Conference - ASP-DAC 2008, Seoul, Korea, Jan. 21--24, 2008, pp. 667--672.
[15]
R. Ubar. Test Synthesis with Alternative Graphs. IEEE Design and Test of Computers. Spring, 1996, pp. 48--59.
[16]
R. Ubar. Combining Functional and Structural Approaches in Test Generation for Digital Systems. Journal of Microelectronics and Reliability, Elsevier Science Ltd. Vol. 38:3, pp. 317--329, 1998.
[17]
Minato, S. BDDs and Applications for VLSI CAD. Kluwer Academic Publishers. 1996.
[18]
D. Mironov, R. Ubar, J. Raik. Logic Simulation and Fault Collapsing with Shared Structurally Synthesized BDDs. IEEE European Test Symposium, Paderborn, Germany, May 26--30, 2014.
[19]
D. Mironov, R. Ubar. Lower Bounds of the Size of Shared Structurally Synthesized BDDs. IEEE 17th International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS). Warsaw, April, 23--25, 2014, pp. 77--82.
[20]
Amin, M. B.; Vinnakota, B., Data parallel fault simulation. International Conference on Computer Design: VLSI in Computers and Processors (ICCD '95), 1995, pp. 610--615.
[21]
OpenCL standard for parallel programming of heterogenious systems. https://www.khronos.org/opencl/
[22]
Varshney, A. K., Vinnakota, B., Skuldt, E., Keller, B., High Performance Parallel Fault Simulation. International Conference on Computer Design 2001 (ICCD 2001), 2001, pp. 308--313.
[23]
Gulati, K., Khatri, S. P., Towards Acceleration of Fault Simulation using Graphics Processing Units. 45th ACM/IEEE Design Automation Conference 2008 (DAC 2008), 2008, pp. 822--827.
[24]
Gulati, K.; Khatri, S. P., Fault Table Generation using Graphics Processing Units. IEEE International High Level Design Validation and Test Workshop 2009 (HLDVT 2009), 2009, pp. 60--67.
Index Terms
- Fault simulation with parallel exact critical path tracing in multiple core environment
Recommendations
Parallel X-fault simulation with critical path tracing technique
DATE '10: Proceedings of the Conference on Design, Automation and Test in EuropeIn this paper, a new very fast fault simulation method to handle the X-fault model is proposed. The method is based on a two-phase procedure. In the first phase, a parallel exact critical path fault tracing is used to determine all the detected stuck-at ...
Transition delay fault simulation with parallel critical path back-tracing and 7-valued algebra
A new method is presented for simulating of Transition Delay Faults (TDF) based on the parallel exact critical path tracing for Stuck-at Fault (SAF) analysis and subsequent TDF reasoning. A method is proposed to extend the TDF model, traditionally ...
Efficient fault simulation on many-core processors
DAC '10: Proceedings of the 47th Design Automation ConferenceFault simulation is essential in test generation, design for test and reliability assessment of integrated circuits. Reliability analysis and the simulation of self-test structures are particularly computationally expensive as a large number of patterns ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- EDAA: European Design Automation Association
- ECSI
- EDAC: Electronic Design Automation Consortium
- SIGDA: ACM Special Interest Group on Design Automation
- Russian Acadamy of Sciences: Russian Acadamy of Sciences
- IEEE Council on Electronic Design Automation (CEDA)
Publisher
EDA Consortium
San Jose, CA, United States
Publication History
Published: 09 March 2015
Check for updates
Qualifiers
- Research-article
Conference
DATE '15
Sponsor:
- EDAA
- EDAC
- SIGDA
- Russian Acadamy of Sciences
Acceptance Rates
DATE '15 Paper Acceptance Rate 206 of 915 submissions, 23%;
Overall Acceptance Rate 518 of 1,794 submissions, 29%
Upcoming Conference
DATE '25
- Sponsor:
- sigda
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 66Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in