 |
Partial Memoization of Concurrency and Communication
Lukasz Ziarek, KC Sivaramakrishnan and Suresh Jagannathan
The 14th ACM SIGPLAN International Conference on Functional Programming (ICFP 2009)Edinburgh, Scotland, 31st August - 2nd September 2009
Abstract
Memoization is a well-known optimization technique used to eliminate redundant calls for pure functions. If a call to a function $f$ with argument $v$ yields result $r$, a subsequent call to $f$ with $v$ can be immediately reduced to $r$ without the need to re-evaluate $f$'s body.Understanding memoization in the presence of concurrency and communication is significantly more challenging. For example, if $f$ communicates with other threads, it is not sufficient to simply record its input/output behavior; we must also track inter-thread dependencies induced by these communication actions. Subsequent calls to $f$ can be elided only if we can identify an interleaving of actions from these call-sites that lead to states in which these dependencies are satisfied. Similar issues arise if $f$ spawns additional threads.
In this paper, we consider the memoization problem for a higher-order concurrent language whose threads may communicate through synchronous message-based communication. To avoid the need to perform unbounded state space search that may be necessary to determine if {\em all} communication dependencies manifest in an earlier call can be satisfied in a later one, we introduce a weaker notion of memoization called {\em partial memoization} that gives implementations the freedom to avoid performing some part, if not all, of a previously memoized call.
To validate the effectiveness of our ideas, we consider the benefits of memoization for reducing the overhead of recomputation for streaming and transactional applications executed on a multi-core machine. We show that on some workloads, memoization can lead to substantial performance improvements without incurring high memory costs.
START Conference Manager (V2.56.8 - Rev. 748M)