BandiTS: Dynamic Timing Speculation Using Multi-Armed Bandit Based Optimization

Jeff (Jun) Zhanga and Siddharth Gargb
Department of Electrical and Computer Engineering, New York University, Brooklyn, New York.


Timing speculation has recently been proposed as a method for increasing performance beyond that achievable by conventional worst-case design techniques. Starting with the observation of fast temporal variations in timing error probabilities, we propose a run-time technique to dynamically determine the optimal degree of timing speculation (i.e., how aggressively the processor is over-clocked) based on a novel formulation of the dynamic timing speculation problem as a multi-armed bandit problem. By conducting detailed postsynthesis timing simulations on a 5-stage MIPS processor running a variety of workloads, the proposed adaptive mechanism improves processor's performance significantly comparing with a competing approach (about 8:3% improvement); on the other hand, it shows only about 2:8% performance loss on average, compared with the oracle results.

Full Text (PDF)