Computational Caches

Waterland, A., Angelino, E., Cubuk, E., Kaxiras, E., Adams, R., Appavoo, J., Seltzer, M.,


Caching is a well-known technique for speeding up com- putation. We cache data from file systems and databases; we cache dynamically generated code blocks; we cache page translations in TLBs. We propose to cache the act of com- putation, so that we can apply it later and in different con- texts. We use a state-space model of computation to sup- port such caching, involving two interrelated parts: spec- ulatively memoized predicted/resultant state pairs that we use to accelerate sequential computation, and trained proba- bilistic models that we use to generate predicted states from which to speculatively execute. The key techniques that make this approach feasible are designing probabilistic mod- els that automatically focus on regions of program execution state space in which prediction is tractable and identifying state space equivalence classes so that predictions need not be exact.
Postscript Slides