Computational Caches

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