Avoiding of Redundant Computations in Simulation Parameter Studies by Memoization

• Applicant: Professor Dr.-Ing. Klaus Wehrle, Ph.D.
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2015 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 283852788

Simulations are essential in the development and optimization of communication systems. In parameter studies a system model is simulated in manifoldly different configurations to obtain early conclusions about the behavior of the system under study. Their execution time increases with model complexity and network size, typically more than linear, hence easily becomes a critical bottleneck in research and development.Till today, runtime reductions were primarily achieved through increasing computational power (by additional processor cores and parallel and distributed simulation). In many cases the theoretical optimum is already almost reached. To nevertheless improve performance while model complexity steadily increases, fundamentally new approaches have to be investigated.In preliminary studies and by many years of experience in network simulation, we observed that often many complex operations are performed repeatedly during the execution of a parameter study, which is actually not necessary. Unfortunately, those computations are not automatically recognized.This results in the research question of this proposal: Is it possible to recognize and avoid redundant computations in parameter studies? If so, up to which degree? This reduction shall be applied orthogonally and additionally to parallelization and offers a great potential for optimization, allowing investigation of even more complex and detailed simulation models without increasing computational power.Our proposal for avoiding redundant computations bases on the concept of memoization. This approach caches results of computations in memory to allow direct application if demanded later. While this can in general be realized manually, it had to be performed individually for every simulation model; this results in huge manual effort for the developers.Consequently, the goal of this proposal is to investigate concepts to automated memoization. To this end, we will design, investigate, and evaluate methods able to automatically recognize and avoid redundant computations. We will (1) research and develop methods to automatically identify complex, redundant computations, whose elision seems promising, (2) design approaches allowing automated memoization of the identified code blocks, such that redundant computations are efficiently avoided, and (3) investigate to which extent these approaches are comparable to high-quality, manual memoizations, hence if we can provide developers access to efficient and automated tools for this purpose.Our research project will answer the questions whether we can realize automated approaches for Memoized Simulation (MemoSim) and how efficient these approaches are.

• DFG Programme: Research Grants