A compiler optimization to reduce soft errors in register files

ABSTRACT

Register file (RF) is extremely vulnerable to soft errors, and traditional redundancy based schemes to protect the RF are prohibitive not only because RF is often in the timing critical path of the processor, but also since it is one of the hottest blocks on the chip, and therefore adding any extra circuitry to it is not desirable. Pure software approaches would be ideal in this case, but previous approaches that are based on program duplication have very significant runtime overheads, and others based on instruction scheduling are only moderately effective due to local scope. We show that the problem of protecting registers inherently requires inter-procedural analysis, and intra-procedural optimization are ineffective. This paper presents a pure compiler approach, based on inter-procedural code analysis to reduce the vulnerability of registers by temporarily writing live variables to protected memory. We formulate the problem as an integer linear programming problem and also present a very efficient heuristic algorithm. Our experiments demonstrate that our proposed technique can reduce the vulnerability of the RF by 33 ~ 37% on average and up to 66%, with a small 2% increase in runtime. In addition, our overhead reduction optimizations can effectively reduce the code size overhead, by more than 40% on average, to a mere 5 ~ 6%, as compared to highly optimized binaries.

REFERENCES

• 1: Todd Austin. SimpleScalar LLC. URL http://www.simplescalar.com/.
• 2: Jason A. Blome , Shantanu Gupta , Shuguang Feng , Scott Mahlke, Cost-efficient soft error protection for embedded microprocessors, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176811]
• 3: Kaiyu Chen , Sharad Malik , David I. August, Retargetable static timing analysis for embedded software, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500011]
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 6: Mary Jean Harrold , Gregg Rothermel , Saurabh Sinha, Computation of interprocedural control dependence, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.11-20, March 02-04, 1998, Clearwater Beach, Florida, United States
• 7: ITRS. International technology roadmap for semiconductors 2007 executive summary. URL http://www.itrs.net/.
• 8: Mallik Kandala , Wei Zhang , Laurence T. Yang, An Area-Efficient Approach to Improving Register File Reliability against Transient Errors, Proceedings of the 21st International Conference on Advanced Information Networking and Applications Workshops, p.798-803, May 21-23, 2007 [doi>10.1109/AINAW.2007.78]
• 9: B. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell System Tech. Journal, 49:291--307, February 1970.
• 10: Israel Koren , C. Mani Krishna, Fault Tolerant Systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2007
• 11: Jongeun Lee , Aviral Shrivastava, Compiler-managed register file protection for energy-efficient soft error reduction, Proceedings of the 2009 Asia and South Pacific Design Automation Conference, January 19-22, 2009, Yokohama, Japan
• 12: Jongeun Lee and Aviral Shrivastava. Static analysis to mitigate soft errors in register files. In Proc. Int'l Conf. Design Automation and Test in Europe (DATE), 2009b.
• 13: Xiaodong Li , Sarita V. Adve , Pradip Bose , Jude A. Rivers, Online Estimation of Architectural Vulnerability Factor for Soft Errors, ACM SIGARCH Computer Architecture News, v.36 n.3, p.341-352, June 2008
• 14: Gokhan Memik , Arindam Mallik, Engineering Over-Clocking: Reliability-Performance Trade-Offs for High-Performance Register Files, Proceedings of the 2005 International Conference on Dependable Systems and Networks, p.770-779, June 28-July 01, 2005 [doi>10.1109/DSN.2005.43]
• 15: Subhasish Mitra , Norbert Seifert , Ming Zhang , Quan Shi , Kee Sup Kim, Robust System Design with Built-In Soft-Error Resilience, Computer, v.38 n.2, p.43-52, February 2005 [doi>10.1109/MC.2005.70]
• 16: Pablo Montesinos , Wei Liu , Josep Torrellas, Using Register Lifetime Predictions to Protect Register Files against Soft Errors, Proceedings of the 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, p.286-296, June 25-28, 2007 [doi>10.1109/DSN.2007.99]
• 17: Shubhendu S. Mukherjee , Christopher Weaver , Joel Emer , Steven K. Reinhardt , Todd Austin, A Systematic Methodology to Compute the Architectural Vulnerability Factors for a High-Performance Microprocessor, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.29, December 03-05, 2003
• 18: Nahmsuk Oh, Philip P. Shirvani, and Edward J. McCluskey. Control-flow checking by software signatures. IEEE Transactions on Reliability, 51:111--122, 2002a.
• 19: Nahmsuk Oh, Philip P. Shirvani, and Edward J. McCluskey. Error detection by duplicated instructions in super-scalar processors. IEEE Transactions on Reliability, 51:63--75, 2002b.
• 20: George A. Reis , Jonathan Chang , Neil Vachharajani , Ram Rangan , David I. August, SWIFT: Software Implemented Fault Tolerance, Proceedings of the international symposium on Code generation and optimization, p.243-254, March 20-23, 2005 [doi>10.1109/CGO.2005.34]
• 21: Aviral Shrivastava , Eugene Earlie , Nikil Dutt , Alex Nicolau, Operation tables for scheduling in the presence of incomplete bypassing, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016768]
• 22: Kevin Skadron , Mircea R. Stan , Wei Huang , Sivakumar Velusamy , Karthik Sankaranarayanan , David Tarjan, Temperature-aware microarchitecture, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 23: Timothy J. Slegel , Robert M. Averill III , Mark A. Check , Bruce C. Giamei , Barry W. Krumm , Christopher A. Krygowski , Wen H. Li , John S. Liptay , John D. MacDougall , Thomas J. McPherson , Jennifer A. Navarro , Eric M. Schwarz , Kevin Shum , Charles F. Webb, IBM's S/390 G5 Microprocessor Design, IEEE Micro, v.19 n.2, p.12-23, March 1999 [doi>10.1109/40.755464]
• 24: Kristen R. Walcott , Greg Humphreys , Sudhanva Gurumurthi, Dynamic prediction of architectural vulnerability from microarchitectural state, ACM SIGARCH Computer Architecture News, v.35 n.2, May 2007
• 25: Youfeng Wu , James R. Larus, Static branch frequency and program profile analysis, Proceedings of the 27th annual international symposium on Microarchitecture, p.1-11, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192725]
• 26: Jun Yan , Wei Zhang, Compiler-guided register reliability improvement against soft errors, Proceedings of the 5th ACM international conference on Embedded software, September 18-22, 2005, Jersey City, NJ, USA [doi>10.1145/1086228.1086266]
• 27: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

General Terms:
Algorithms, Performance, Reliability

Keywords:
architectural vulnerability factor, compilation, embedded system, link-time optimization, register file, soft error, static analysis