Memoization: A Powerful Caching Technique

Memoization Gone Wild! (Generalized Computational Caching) Micah Beck, Assoc. Prof. EECS, Univ of Tennessee CS 494 Sept 28, 2017

What is Memoization Memoization is a widely used strategy for trading off computation for memory Rather than compute an expensive function every time its value is needed, we capture and replay such results at a much lower cost.

Example: Primality Testing Unmemoized bool is_prime(int n) begin for (i = 2; I < n; i++) if (is_prime(i) and (i divides n)) return false; fi return true; end

Prime Sieve: Store Previously Computer Values is_prime(5)? is_prime(5) = true i prime[i] i prime[i] 2 doesn t divides 5 2 true 2 true 3 doesn t divide 5 4 is not prime 3 true 3 true 4 false 4 false 5 5 true 6 6 Thus 5 is prime!

Example: Prime Sieve Unmemoized Memoized bool stored[*] = false; bool prime[*]; bool is_prime(int n) begin bool prime(int n) begin if (stored[n]) return prime[n]; for (i = 2; i < n; i++) if (is_prime(i) and (i divides n)) stored[n] = true; prime[n] = false; return false; fi stored[n] = true; prime[n] = true; return true; end for (i = 2; I < n; i++) if (is_prime(i) and (i divides n)) fi return false; return true; end

The Principle is General, Common Caching of graphical elements Chess End-Game Databases Search Engine Indices Browser Histories Note: Memoization/caching need not be complete or even deterministic!

When to Memoize? Memoization requires a combination of function- and application-specific characteristics, including: sufficient locality in the patterns of calls to allow a small cache of results to be effective a sufficient differential between the cost of computation and the cost of look-up

Generalized Computational Caching (GCC) Compiler memoization allows results to be shared within a single program (early to late) Other GCC sharing modes: Medical Share between Isologous Isolated Same code & user Autologous Private Same user Syngeneic Kibbutznik Same code, different users P2P Synthetic Oracular Trusted source Allogeneic Cooperative Trusted users P2P Xenogenic Public Anything goes! P2P

Sharing Mechanisms 1 Publication Isologous or Autologous: private database Acceptance Isologous or Autologous: unguarded

Private Databases

Sharing Mechanisms 2 Publication Syngenic or Allogenic: shared database (hygienic) Acceptance Syngenic or Allogenic: metadata-based consensus

Shared Database publication filter acceptance filter

Sharing Mechanisms 3 Publication Synthetic: published database Xenogenic: shared database (sanitized) Acceptance Synthetic: reputation-based Xenogenic: think twice!

Public Cloud evil doer firewall save me! trusted source your mama

Some Possible Strengths of GCC Wider sharing justifies larger tables Peers in the wide area can look up in parallel Use of caches may focus applications on common computations (increasing locality).

Possible GCC Examples Sorting Not hard enough (computational profit) Real Matrix Operations Inputs & outputs too large (table size) How about satisfiability? Given a boolean expression over a set of variables, determine whether any assignment of values to those variables yields the value true .

Is Memoization of 3SAT Plausible? An NP-Complete problem Best known algorithms are EXP-time P-time reductions to every problem in NP Results verifiable in P-time There are lots of open source 3SAT solvers On the other hand Non-trivial problem instances are big (table size) P-time may not be the best algorithm in practice The distribution of hard instances is unknown!

Other GCC Candidates Other NP-Complete Problems Traveling Salesman may have direct applications, simple reductions to other graph problems Integer Programming Widely used, computationally intensive Less general than satisfiability Kernels for combinatorial compiler optimizations such as register allocation

Some Possible Weaknesses of GCC Lack of trust may limit sharing (retractability) Preserving rich metadata may help Metadata increases storage requirements Great danger of privacy violation (show me what you ve got!) Where are the killer apps? Lookups across a network are expensive The computation/storage tradeoff must add up Peer-to-peer modes may be hard to manage

Issues/Challenges Are there domains where GCC is a clear win? Can we share effectively through dynamic mechanisms (as in memory caches)? How many cycles is it worth paying for safety? How thin can the client get? Your questions? Thank you!