Static analysis and compiler design for idempotent processing

ABSTRACT

Recovery functionality has many applications in computing systems, from speculation recovery in modern microprocessors to fault recovery in high-reliability systems. Modern systems commonly recover using checkpoints. However, checkpoints introduce overheads, add complexity, and often save more state than necessary.

This paper develops a novel compiler technique to recover program state without the overheads of explicit checkpoints. The technique breaks programs into idempotent regions---regions that can be freely re-executed---which allows recovery without checkpointed state. Leveraging the property of idempotence, recovery can be obtained by simple re-execution. We develop static analysis techniques to construct these regions and demonstrate low overheads and large region sizes for an LLVM-based implementation. Across a set of diverse benchmark suites, we construct idempotent regions close in size to those that could be obtained with perfect runtime information. Although the resulting code runs more slowly, typical performance overheads are in the range of just 2-12%.

The paradigm of executing entire programs as a series of idempotent regions we call idempotent processing, and it has many applications in computer systems. As a concrete example, we demonstrate it applied to the problem of compiler-automated hardware fault recovery. In comparison to two other state-of-the-art techniques, redundant execution and checkpoint-logging, our idempotent processing technique outperforms both by over 15%.

References

1. A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison Wesley, 2nd edition, 2007.
2. B. N. Bershad, D. D. Redell, and J. R. Ellis. Fast mutual exclusion for uniprocessors. In ASPLOS '92.
3. C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC benchmark suite: Characterization and architectural implications. In PACT '08.
4. N. Binkert, B. Beckmann, G. Black, S. K. Reinhardt, A. Saidi, A. Basu, J. Hestness, D. R. Hower, T. Krishna, S. Sardashti, R. Sen, K. Sewell, M. Shoaib, N. Vaish, M. D. Hill, and D. A. Wood. The gem5 simulator. SIGARCH Comput. Archit. News, 39:1--7, Aug. 2011.
5. E. Borin, C. Wang, Y. Wu, and G. Araujo. Software-based transparent and comprehensive control-flow error detection. In CGO '06.
6. J. Chang, G. A. Reis, and D. I. August. Automatic instruction-level software-only recovery. In DSN '06.
7. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.
8. R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. An efficient method of computing static single assignment form. POPL '89.
9. M. de Kruijf, S. Nomura, and K. Sankaralingam. Relax: An architectural framework for software recovery of hardware faults. In ISCA '10, 2010.
10. M. de Kruijf and K. Sankaralingam. Idempotent processor architecture. In MICRO '11.
11. J. C. Dehnert, B. K. Grant, J. P. Banning, R. Johnson, T. Kistler, A. Klaiber, and J. Mattson. The Transmeta code morphing software: Using speculation, recovery, and adaptive retranslation to address real-life challenges. In CGO '03.
12. S. Feng, S. Gupta, A. Ansari, S. Mahlke, and D. August. Encore: Low-cost, fine-grained transient fault recovery. In MICRO '11.
13. D. M. Gallagher, W. Y. Chen, S. A. Mahlke, J. C. Gyllenhaal, and W.-m. W. Hwu. Dynamic memory disambiguation using the memory conflict buffer. In ASPLOS '94.
14. M. Gschwind and E. R. Altman. Precise exception semantics in dynamic compilation. In CC '02.
15. J. Guo, F. HÃijffner, E. Kenar, R. Niedermeier, and J. Uhlmann. Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs. European Journal of Operational Research, 186(2):542--553, 2008.
16. M. Hampton and K. Asanović. Implementing virtual memory in a vector processor with software restart markers. In ICS '06.
17. T. Harris, J. R. Larus, and R. Rajwar. Transactional Memory. Morgan & Claypool, 2nd edition, 2010.
18. Intel. Itanium Architecture Software Developer's Manual Rev. 2.3. http://www.intel.com/design/itanium/manuals/iiasdmanual.htm.
19. S. W. Kim, C.-L. Ooi, R. Eigenmann, B. Falsafi, and T. N. Vijaykumar. Exploiting reference idempotency to reduce speculative storage overflow. ACM Trans. Program. Lang. Syst., 28:942--965, September 2006.
20. C. Lattner and V. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In CGO '04.
21. C.-C. J. Li, S.-K. Chen, W. K. Fuchs, and W.-M. W. Hwu. Compiler-based multiple instruction retry. IEEE Transactions on Computers, 44(1):35--46, 1995.
22. C.-C. J. Li and W. K. Fuchs. CATCH -- Compiler-assisted techniques for checkpointing. In FTCS '90.
23. S. A. Mahlke, W. Y. Chen, W.-m. W. Hwu, B. R. Rau, and M. S. Schlansker. Sentinel scheduling for VLIW and superscalar processors. In ASPLOS '92.
24. A. Meixner, M. E. Bauer, and D. J. Sorin. Argus: Low-cost comprehensive error detection in simple cores. IEEE Micro, 28(1):52--59, 2008.
25. J. Menon, M. de Kruijf, and K. Sankaralingam. iGPU: exception support and speculative execution on GPUs. In ISCA '12, 2012.
26. N. Oh, P. Shirvani, and E. McCluskey. Error detection by duplicated instructions in super-scalar processors. Reliability, IEEE Transactions on, 51(1):63--75, March 2002.
27. J. S. Plank, Y. Chen, K. Li, M. Beck, and G. Kingsley. Memory exclusion: Optimizing the performance of checkpointing systems. Software -- Practice & Experience, 29(2):125--142, 1999.
28. R. Rajwar and J. R. Goodman. Speculative lock elision: enabling highly concurrent multithreaded execution. In MICRO '01.
29. G. Reis, J. Chang, N. Vachharajani, R. Rangan, and D. August. Swift: software implemented fault tolerance. In CGO '05.
30. G. A. Reis, J. Chang, N. Vachharajani, R. Rangan, D. I. August, and S. S. Mukherjee. Design and evaluation of hybrid fault-detection systems. In ISCA '05, pages 148--159.
31. O. Shivers, J. W. Clark, and R. McGrath. Atomic heap transactions and fine-grain interrupts. In ICFP '99.
32. T. J. Slegel et al. IBM's S/390 G5 microprocessor design. IEEE Micro, 19(2):12--23, 1999.
33. J. E. Smith and A. R. Pleszkun. Implementing precise interrupts in pipelined processors. IEEE Transactions on Computers, 37:562--573, May 1988.
34. D. J. Sorin. Fault Tolerant Computer Architecture. Morgan & Claypool, 2009.
35. Standard Performance Evaluation Corporation. SPEC CPU2006, 2006.
36. H.-W. Tseng and D. Tullsen. Data-triggered threads: Eliminating redundant computation. In HPCA '11.
37. K. C. Yeager. The MIPS R10000 superscalar microprocessor. IEEE Micro, 16(2):28--40, 1996.
38. T.-Y. Yeh and Y. N. Patt. Two-level adaptive training branch prediction. In MICRO '91.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

      • Source code generation