12. Spatial and Temporal Memoization

In this chapter, we further combine the methods in detecting and correcting errors with the methods in accepting errors to devise a new hybrid methods Rahimi et al. (IEEE Trans. Circuits Syst. II Express Briefs 60:847–851, 2013) [1], Rahimi et al. (Design, Automation and Test in Europe Conference and Exhibition (DATE), 2014, pp. 1–6, 2014) [2], Rahimi et al. (Temporal memoization for energy-efficient timing error recovery in GPGPU architectures. Technical Report CS2014-1006, Department of Computer Science and Engineering, University of California San Diego, La Jolla, CA 92093, 2014) [3], Rahimi et al. (IEEE Des. Test 33:85–92, 2016) [4]. The cost and speed of error recovery can be improved by memoization-based optimization method as a form of computational reuse. Accordingly, we propose two techniques, spatial memoization and temporal memoization, that exploit parallelism in suitable computing fabrics such as GP-GPUs. These memoization techniques exploit value locality and similarity inside data-parallel programs for use in floating-point units (FPUs). Spatial memoization alleviates cost of timing errors recovery, building upon lock-step execution of single-instruction, multiple-data (SIMD) architectures. To support spatial memoization at the level of instruction, we propose a single strong lane, multiple weak lanes (SSMW) architecture. Spatial memoization recalls result of error-free execution of an instruction on the SS lane, and concurrently reuses it to spatially correct any errant instructions across MW lanes. This error correction can be done exactly or approximately. Temporal memoization recalls the context of error-free execution of an instruction on a FPU. To enable scalable and independent error recovery, a single-cycle lookup table (LUT) is tightly coupled to every FPU to maintain few contexts of recent error-free executions. The LUT reuses these memorized contexts to exactly, or approximately, correct errant FP instructions based on application needs. The proposed memoization techniques eliminate the cost of error recovery (e.g., on average 62% for the voltage droop-affected timing errors) and enhance energy efficiency. Spatio-temporal memoization techniques are implemented in standard CMOS technology as a joint method for detecting and correcting with accepting the timing errors in GP-GPUs.