Soft error vulnerability of iterative linear algebra methods

ABSTRACT

Devices are increasingly vulnerable to soft errors as their feature sizes shrink. Previously, soft error rates were significant primarily in space and high-atmospheric computing. Modern architectures now use features so small at sufficiently low voltages that soft errors are becoming important even at terrestrial altitudes. Due to their large number of components, supercomputers are particularly susceptible to soft errors. Since many large scale parallel scientific applications use iterative linear algebra methods, the soft error vulnerability of these methods constitutes a large fraction of the applications' overall vulnerability. Many users consider these methods invulnerable to most soft errors since they converge from an imprecise solution to a precise one. However, we show in this paper that iterative methods are vulnerable to soft errors, exhibiting both silent data corruptions and poor ability to detect errors. Further, we evaluate a variety of soft error detection and tolerance techniques, including checkpointing, linear matrix encodings, and residual tracking techniques.

REFERENCES

• 1: International technology roadmap for semiconductors. White paper, ITRS, 2005.
• 2: Jesd89a: Measurement and reporting of alpha particle and terrestrial cosmic ray-induced soft errors in semiconductor devices. Technical report, JEDEC Solid State Technology Association, October 2006.
• 3: Natasa Miskov-Zivanov , Diana Marculescu, Soft error rate analysis for sequential circuits, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 4: J. Anfinson , F. T. Luk, A Linear Algebraic Model of Algorithm-Based Fault Tolerance, IEEE Transactions on Computers, v.37 n.12, p.1599-1604, December 1988 [doi>10.1109/12.9736]
• 5: Jean Arlat , Yves Crouzet , Johan Karlsson , Peter Folkesson , Emmerich Fuchs , Günther H. Leber, Comparison of Physical and Software-Implemented Fault Injection Techniques, IEEE Transactions on Computers, v.52 n.9, p.1115-1133, September 2003 [doi>10.1109/TC.2003.1228509]
• 6: R. C. Baumann. Radiation-induced soft errors in advanced semiconductor technologies. IEEE Transactions on Device and Materials Reliability, 5(3):305--316, September 2005.
• 7: Daniel L. Boley , Richard P. Brent , Gene H. Golub , Franklin T. Luk, Algorithmic fault tolerance using the Lanczos method, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.312-332, Jan. 1992 [doi>10.1137/0613023]
• 8: Charng-da Lu , Daniel A. Reed, Assessing Fault Sensitivity in MPI Applications, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.37, November 06-12, 2004 [doi>10.1109/SC.2004.12]
• 9: Tim Davis. University of Florida Sparse Matrix Collection. NA Digest, 97(23), June 1997.
• 10: J. Dongarra, A. Lumsdaine, R. Pozo, and K. Remington. A sparse matrix library in C++ for high performance architectures. In Object Oriented Numerics Conference, pages 214--218, 1994.
• 11: J. F. Ziegler , H. W. Curtis , H. P. Muhlfeld , C. J. Montrose , B. Chin, IBM experiments in soft fails in computer electronics (1978–1994), IBM Journal of Research and Development, v.40 n.1, p.3-18, Jan. 1996
• 12: Gene H. Golub and Charles F. Van Loan. Matrix computations. Johns Hopkins University Press, 1996.
• 13: J. Greenough, L. Howell A. Kuhl, A. Shestakov, U. Creach, A.Miller, E. Tarwater, A. Cook, and B. Cabot. Raptor: Software and applications on BlueGene/L. In BlueGene/L Workshop, October 2003.
• 14: David M. Hiemstra and Allan Baril. Single event upset characterization of the pentium mmx and pentium II microprocessors using proton. IEEE Transactions on Nuclear Science, 46(6):1453--1460, December 1999.
• 15: Kuang-Hua Huang , J. A. Abraham, Algorithm-Based Fault Tolerance for Matrix Operations, IEEE Transactions on Computers, v.33 n.6, p.518-528, June 1984 [doi>10.1109/TC.1984.1676475]
• 16: P. Kudva, Jeffrey W. Kellington, Pia N. Sanda, Ryan McBeth, John Schumann, and Ron Kalla. Soft error derating of ibm power6 microprocessor using statistical fault injection. In IEEE Workshop on Silicon Errors in Logic -- System Effects, April 2007.
• 17: J. Langou , Z. Chen , G. Bosilca , J. Dongarra, Recovery Patterns for Iterative Methods in a Parallel Unstable Environment, SIAM Journal on Scientific Computing, v.30 n.1, p.102-116, November 2007 [doi>10.1137/040620394]
• 18: Austin Lesea and Joe Fabula. The Rosetta experiment: Atmospheric soft error rate testing in differing technology FPGAs -- 90 nanometer update. In Workshop on System Effects of Logic Soft Errors, April 2005.
• 19: Hatem Ltaief, Marc Garbey, and Edgar Gabriel. Parallel fault tolerant algorithms for parabolic problems. In Euro-Par Conference on Parallel Processing, pages 700--709, November 2006.
• 20: M. A. McClelland, J. L. Maienschein, A. L. Nichols, J. F. Wardell, A. I. Atwood, and P. O. Curran. ALE3D model predictions and materials characterization for the cookoff response. In Joint Army Navy NASA Air Force 38th Combustions Subcommittee, 26th Airbreathing Propulsion Subcommittee, 20th Propulsion Systems Hazards Subcommittee and 2nd Modeling and Simulation Subcommittee Joint Meeting, March 2007.
• 21: P.T. McDonald, W.J. Stapor, and B.G. Henson. PC603E 32-bit RISC microprocessor radiation effects study. White paper, Innovative Concepts Inc., 1999.
• 22: Alan Messer , Philippe Bernadat , Guangrui Fu , Deqing Chen , Zoran Dimitrijevic , David Lie , Durga Devi Mannaru , Alma Riska , Dejan Milojicic, Susceptibility of Commodity Systems and Software to Memory Soft Errors, IEEE Transactions on Computers, v.53 n.12, p.1557-1568, December 2004 [doi>10.1109/TC.2004.119]
• 23: Sarah Michalak, Kevin W. Harris, Nicolas W. Hengartner, Bruce E. Takala, and Stephen A. Wender. Predicting the number of fatal soft errors in Los Alamos National Laboratory's ASC Q supercomputer. IEEE Transactions on Device and Materials Reliability, 5(3), 2005.
• 24: Amitabh Mishra , Prithviraj Banerjee, An Algorithm Based Error Detection Scheme for the Multigrid Algorithm, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.12, June 15-18, 1999
• 25: Couchman H. M. P., Thomas P. A., and Pearce F. R. Hydra: an adaptive-mesh implementation of SPH. Astrophysical Journal, 452:797--813, April 1995.
• 26: Paula Prata , João Gabriel Silva, Algorithm Based Fault Tolerance versus Result-Checking for Matrix Computations, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.4, June 15-18, 1999
• 27: Heather Quinn , Paul Graham, Terrestrial-Based Radiation Upsets: A Cautionary Tale, Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.193-202, April 18-20, 2005 [doi>10.1109/FCCM.2005.61]
• 28: A. Roy-Chowdhury and P. Banerjee. Algorithm-based fault location and recovery for matrix computations. In International Symposium on Fault-Tolerant Computing, June 1994.
• 29: Terrazon Semiconductor. Soft errors in electronic memory. White paper, Terrazon Semiconductor, 2004.
• 30: Premkishore Shivakumar , Michael Kistler , Stephen W. Keckler , Doug Burger , Lorenzo Alvisi, Modeling the Effect of Technology Trends on the Soft Error Rate of Combinational Logic, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.389-398, June 23-26, 2002
• 31: Daniel Skarin, Martin Sanfridson, and Johan Karlsson. Impact of soft errors in a brake-by-wire system. In IEEE Workshop on Silicon Errors in Logic -- System Effects, April 2007.
• 32: Nicholas J. Wang , Aqeel Mahesri , Sanjay J. Patel, Examining ACE analysis reliability estimates using fault-injection, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 33: Hamid R. Zarandi and Seyed Ghassem Miremadi. Dependability evaluation of altera FPGA-based embedded systems subjected to SEUs. Microelectronics and Reliability, 47(2--3):461--470, 2006.
• 34: Qihong Zhang and Jung H. Kim. An efficient method to reduce roundoff error in matrix multiplication with algorithm-based fault tolerance. In International Conference on Wafer Scale Integration, pages 32--39, January 1994

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Distributed architectures

General Terms:
Algorithms, Experimentation, Performance, Reliability

Keywords:
fault tolerance, iterative methods, linear algebra, parallel, soft errors