Automated Memoization for Parameter Studies Implemented in Impure Languages

PDF DOI
bibtex
@inproceedings{stoffersAutomatedMemoizationParameter2016,
  author = {Stoffers, Mirko and Schemmel, Daniel and Soria Dustmann, Oscar and Wehrle, Klaus},
  title = {Automated {{Memoization}} for {{Parameter}} {{Studies}} {{Implemented}} in {{Impure}} {{Languages}}},
  booktitle = {{{ACM}} {{SIGSIM}} {{Conference}} on {{Principles}} of {{Advanced}} {{Discrete}} {{Simulation}} {{(PADS}} 2016)},
  location = {Banff, AB, Canada},
  pages = {221--232},
  year = {2016},
  doi = {10.1145/2901378.2901386},
}

In computer simulations many processes are highly repetitive. These repetitions are amplified further when a parameter study is conducted where the same model is repeatedly executed with varying parameters, especially when performing multiple runs to increase statistical confidence. Inevitably, such repetitions result in the execution of identical computations, with identical code, identical input, and hence identical output. Performing computations redundantly wastes resources and the execution time of a parameter study could be reduced if the redundancies were avoided.

To this end, the idea of memoization was proposed decades ago. However, until today memoization is either performed manually or automated memoization approaches are used that can only handle pure functions. This means that only the function parameters and the return value may be input and output of the function whereas side effects are not allowed. In order to expand the scope of automated memoization to a larger class of programs, we propose an approach able to reliably detect the full input and output of a function, including reading and writing objects through arbitrarily indirect pointers with some preconditions. We show the feasibility of our approach and derive simple performance approximations enabling rough predictions of the expected benefit. By means of a simple case study performing an OFDM network simulation, we demonstrate the practical suitability of our approach, speeding up the execution of the whole parameter study by a factor of 75, while only doubling memory consumption.

Awards