More Web Proxy on the site http://driver.im/

research-article

Towards acceleration of fault simulation using graphics processing units

Authors:

Kanupriya Gulati,

Sunil P. KhatriAuthors Info & Claims

DAC '08: Proceedings of the 45th annual Design Automation Conference

Pages 822 - 827

https://doi.org/10.1145/1391469.1391679

Published: 08 June 2008 Publication History

Abstract

In this paper, we explore the implementation of fault simulation on a Graphics Processing Unit (GPU). In particular, we implement a fault simulator that exploits thread level parallelism. Fault simulation is inherently parallelizable, and the large number of threads that can be computed in parallel on a GPU results in a natural fit for the problem of fault simulation. Our implementation fault-simulates all the gates in a particular level of a circuit, including good and faulty circuit simulations, for all patterns, in parallel. Since GPUs have an extremely large memory bandwidth, we implement each of our fault simulation threads (which execute in parallel with no data dependencies) using memory lookup. Fault injection is also done along with gate evaluation, with each thread using a different fault injection mask. All threads compute identical instructions, but on different data, as required by the Single Instruction Multiple Data (SIMD) programming semantics of the GPU. Our results, implemented on a NVIDIA GeForce GTX 8800 GPU card, indicate that our approach is on average 35 x faster when compared to a commercial fault simulation engine. With the recently announced Tesla GPU servers housing up to eight GPUs, our approach would be potentially 238× faster. The correctness of the GPU based fault simulator has been verified by comparing its result with a CPU based fault simulator.

References

[1]

P. Banerjee, Parallel Algorithms for VLSI Computer-aided Design. Prentice Hall, June 1994. ISBN-13: 978--0130158352 (ISBN-10: 0130158356).

Digital Library

[2]

M. B. Amin and B. Vinnakota, "Workload distribution in fault simulation," J. Electron. Test., vol. 10, no. 3, pp. 277--282, 1997.

Digital Library

[3]

A. Abramovici, Y. Levendel, and P. Menon, "A logic simulation engine," in IEEE Transactions on Computer-Aided Design, vol. 2, pp. 82--94, April 1983.

Digital Library

[4]

P. Agrawal, W. J. Dally, W. C. Fischer, H. V. Jagadish, A. S. Krishnakumar, and R. Tutundjian, "Mars: A multiprocessor-based programmable accelerator," IEEE Des. Test, vol. 4, no. 5, pp. 28--36, 1987.

Digital Library

[5]

V. Narayanan and V. Pitchumani, "Fault simulation on massively parallel simd machines: algorithms, implementations and results," J. Electron. Test., vol. 3, no. 1, pp. 79--92, 1992.

Digital Library

[6]

S. Tai and D. Bhattacharya, "Pipelined fault simulation on parallel machines using the circuitflow graph," in Computer Design: VLSI in Computers and Processors, pp. 564--567, Oct 1993.

[7]

G. F. Pfister, "The yorktown simulation engine: Introduction," in DAC '82: Proceedings of the 19th conference on Design automation, (Piscataway, NJ, USA), pp. 51--54, IEEE Press, 1982.

Digital Library

[8]

D. K. Beece, G. Deibert, G. Papp, and F. Villante, "The ibm engineering verification engine," in DAC '88: Proceedings of the 25th ACM/IEEE conference on Design automation, (Los Alamitos, CA, USA), pp. 218--224, IEEE Computer Society Press, 1988.

Digital Library

[9]

F. Ozguner and R. Daoud, "Vectorized fault simulation on the cray x-mp supercomputer," in Computer-Aided Design, 1988. ICCAD-88. Digest of Technical Papers., IEEE International Conference on, pp. 198--201, Nov 1988.

[10]

F. Ozguner, C. Aykanat, and O. Khalid, "Logic fault simulation on a vector hypercube multiprocessor," in Proceedings of the third conference on Hypercube concurrent computers and applications, (New York, NY, USA), pp. 1108--1116, ACM, 1988.

Digital Library

[11]

R. Raghavan, J. Hayes, and W. Martin, "Logic simulation on vector processors," in Computer-Aided Design, Digest of Technical Papers., IEEE International Conference on, pp. 268--271, Nov 1988.

[12]

N. Ishiura, M. Ito, and S. Yajima, "High-speed fault simulation using a vector processor," in Proceedings of the International Conference on Computer-Aided Design ICCAD, Nov 1987.

[13]

M. B. Amin and B. Vinnakota, "Data parallel fault simulation," IEEE Transactions on Very Large Scale Integration (VLSI) systems, vol. 7, no. 2, pp. 183--190, 1999.

Digital Library

[14]

R. Mueller-Thuns, D. Saab, R. Damiano, and J. Abraham, "Vlsi logic and fault simulation on general-purpose parallel computers," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, pp. 446--460, March 1993.

Digital Library

[15]

Z. Fan, F. Qiu, A. Kaufman, and S. Yoakum-Stover, "GPU cluster for high performance computing," in SC '04: Proceedings of the 2004 ACM/IEEE conference on Supercomputing, (Washington, DC, USA), p. 47, IEEE Computer Society, 2004.

Digital Library

[16]

J. Owens, "GPU architecture overview," in SIGGRAPH '07: ACM SIGGRAPH 2007 courses, (New York, NY, USA), p. 2, ACM, 2007.

Digital Library

[17]

D. Luebke, M. Harris, N. Govindaraju, A. Lefohn, M. Houston, J. Owens, M. Segal, M. Papakipos, and I. Buck, "GPGPU: general-purpose computation on graphics hardware," in SC '06: Proceedings of the 2006 ACM/IEEE conference on Supercomputing, (New York, NY, USA), p. 208, ACM, 2006.

Digital Library

[18]

H.-Y. Schive, C.-H. Chien, S.-K. Wong, Y.-C. Tsai, and T. Chiueh, "Graphic-card cluster for astrophysics (GraCCA) - performance tests," in Submitted to New Astronomy, July 2007.

[19]

"IWLS 2005 Benchmarks." http://www.iwls.org/iwls2005/benchmarks.html.

[20]

"NVIDIA Tesla GPU Computing Processor." http://www.nvidia.com/object/IO_43499.html.

[21]

S. Parkes, P. Banerjee, and J. Patel, "A parallel algorithm for fault simulation based on proofs," in ICCD '95: Proceedings of the 1995 International Conference on Computer Design, (Washington, DC, USA), p. 616, IEEE Computer Society, 1995.

Digital Library

[22]

S. Patil and P. Banerjee, "Performance trade-offs in a parallel test generation/fault simulation environment," IEEE Transactions on Computer-Aided Design, pp. 1542--1558, Dec 1991.

Digital Library

[23]

"NVIDIA CUDA Introduction." http://www.beyond3d.com/content/articles/12/1.

[24]

"NVIDIA CUDA Homepage." http://developer.nvidia.com/object/cuda.html.

Cited By

Lu LChen JUlbricht MKrstic M(2024)Machine Learning Methodologies to Predict the Results of Simulation-Based Fault InjectionIEEE Transactions on Circuits and Systems I: Regular Papers10.1109/TCSI.2024.334992871:5(1978-1991)Online publication date: May-2024
https://doi.org/10.1109/TCSI.2024.3349928
Lu LChen JUlbricht MKrstic M(2024)Toward Critical Flip-Flop Identification for Soft-Error Tolerance With Graph Neural NetworksIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.333196843:4(1135-1148)Online publication date: Apr-2024
https://doi.org/10.1109/TCAD.2023.3331968
Wang YChao ZWang SGu FWang TYe JLi H(2024)Multi-Dimensional Acceleration of Fault Simulation on ARM Multicore CPU2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617648(283-288)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617648
Show More Cited By

Index Terms

Towards acceleration of fault simulation using graphics processing units
1. Hardware
  1. Hardware test
  2. Robustness

Recommendations

Algorithmic performance studies on graphics processing units

We report on our experience with integrating and using graphics processing units (GPUs) as fast parallel floating-point co-processors to accelerate two fundamental computational scientific kernels on the GPU: sparse direct factorization and nonlinear ...
Acceleration of grammatical evolution using graphics processing units: computational intelligence on consumer games and graphics hardware
GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation

Several papers show that symbolic regression is suitable for data analysis and prediction in financial markets. Grammatical Evolution (GE), a grammar-based form of Genetic Programming (GP), has been successfully applied in solving various tasks ...
Accelerating evolutionary computation with graphics processing units
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

Graphics Processing Units (GPUs) have become a major source of computational power for numerical applications. Originally designed for application of time-consuming graphics operations, GPUs are stream processors that implement the SIMD paradigm. Modern ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '08: Proceedings of the 45th annual Design Automation Conference

June 2008

993 pages

ISBN:9781605581156

DOI:10.1145/1391469

General Chair:
Limor Fix
Intel Research Pittsburgh, Pittsburgh, PA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

The EDA Consortium
IEEE/CASS/CANDE/CEDA
SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DAC '08

Sponsor:

SIGDA

DAC '08: The 45th Annual Design Automation Conference 2008

June 8 - 13, 2008

California, Anaheim

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

85
Total Citations
View Citations
556
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lu LChen JUlbricht MKrstic M(2024)Machine Learning Methodologies to Predict the Results of Simulation-Based Fault InjectionIEEE Transactions on Circuits and Systems I: Regular Papers10.1109/TCSI.2024.334992871:5(1978-1991)Online publication date: May-2024
https://doi.org/10.1109/TCSI.2024.3349928
Lu LChen JUlbricht MKrstic M(2024)Toward Critical Flip-Flop Identification for Soft-Error Tolerance With Graph Neural NetworksIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.333196843:4(1135-1148)Online publication date: Apr-2024
https://doi.org/10.1109/TCAD.2023.3331968
Wang YChao ZWang SGu FWang TYe JLi H(2024)Multi-Dimensional Acceleration of Fault Simulation on ARM Multicore CPU2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617648(283-288)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617648
Hu JDai GWang LLai LHuang YYang HWang Y(2023)Adaptive Multidimensional Parallel Fault Simulation Framework on Heterogeneous SystemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.321361742:6(1951-1964)Online publication date: Jun-2023
https://doi.org/10.1109/TCAD.2022.3213617
Karami MHaghbayan MEbrahimi MMiele APlosila J(2022)Thread-level Parallelism in Fault Simulation of Deep Neural Networks on Multi-Processor Systems2022 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFT)10.1109/DFT56152.2022.9962358(1-4)Online publication date: 19-Oct-2022
https://doi.org/10.1109/DFT56152.2022.9962358
Karami MHaghbayan MEbrahimi MNejatollahi HTenhunen HPlosila J(2021)High-Performance Parallel Fault Simulation for Multi-Core Systems2021 29th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)10.1109/PDP52278.2021.00040(207-211)Online publication date: Mar-2021
https://doi.org/10.1109/PDP52278.2021.00040
Zeng CYang FZeng X(2021)Accelerate Logic Re-simulation on GPU via Gate/Event Parallelism and State Compression2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD)10.1109/ICCAD51958.2021.9643571(1-8)Online publication date: 1-Nov-2021
https://doi.org/10.1109/ICCAD51958.2021.9643571
Li HLiang H(2021)GPU-based ATPG System by Scaling Memory Usage and Reducing Data Transfer2021 IEEE European Test Symposium (ETS)10.1109/ETS50041.2021.9465466(1-2)Online publication date: 24-May-2021
https://doi.org/10.1109/ETS50041.2021.9465466
Schneider EWunderlich H(2020)GPU-accelerated Time Simulation of Systems with Adaptive Voltage and Frequency Scaling2020 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE48585.2020.9116256(879-884)Online publication date: Mar-2020
https://doi.org/10.23919/DATE48585.2020.9116256
Lai LZhang QTsai HCheng W(2020)GPU-based Hybrid Parallel Logic Simulation for Scan Patterns2020 IEEE International Test Conference in Asia (ITC-Asia)10.1109/ITC-Asia51099.2020.00032(118-123)Online publication date: Sep-2020
https://doi.org/10.1109/ITC-Asia51099.2020.00032
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents