Avoiding of Redundant Computations in Simulation Parameter Studies by Memoization

通过记忆避免仿真参数研究中的冗余计算

• 批准号: 283852788
• 负责人: Professor Dr.-Ing. Klaus Wehrle, Ph.D.
• 金额: --
• 依托单位: Informatik 4 - Lehrstuhl Kommunikation und Verteilte Systeme
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2015
• 资助国家: 德国
• 起止时间: 2014-12-31 至 2019-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/283852788?language=en
• 关键词: Avoiding; Redundant; Computations; Simulation; Parameter

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.

仿真在通信系统的开发和优化中至关重要。在参数研究中，系统模型在各种不同的配置下进行模拟，以获得有关所研究系统行为的早期结论。它们的执行时间随着模型复杂度和网络规模的增加而增加，通常超过线性，因此很容易成为研究和开发的关键瓶颈。到目前为止，运行时间的减少主要是通过增加计算能力（通过额外的处理器核心以及并行和分布式仿真）来实现的。在许多情况下，理论上的最佳值几乎已经达到。然而，为了提高性能，而模型的复杂性稳步增加，从根本上新的方法必须investigated.In初步的研究和多年的经验，在网络模拟，我们观察到，经常有许多复杂的操作执行过程中重复执行的参数研究，这实际上是没有必要的。不幸的是，这些计算不能自动识别，这导致了本提案的研究问题：是否有可能识别和避免参数研究中的冗余计算？如果是，达到什么程度？这种减少应适用于正交和额外的并行化，并提供了一个很大的潜力，优化，允许调查更复杂和详细的仿真模型，而不增加计算能力。我们的建议，以避免冗余计算的基础上的概念memoization。这种方法将计算结果缓存在内存中，以便在以后需要时直接应用。虽然这可以在一般手动实现，它必须单独为每个仿真模型进行，这导致了巨大的手动工作的开发人员。因此，本提案的目标是调查的概念，自动memoization。为此，我们将设计、研究和评估能够自动识别和避免冗余计算的方法。我们将（1）研究和开发自动识别复杂的冗余计算的方法，其省略似乎很有希望，（2）设计方法，允许自动记忆所识别的代码块，从而有效地避免冗余计算，以及（3）调查这些方法在何种程度上可与高质量的手动记忆相媲美，因此，如果我们可以提供开发人员访问高效和自动化的工具，为此目的。我们的研究项目将回答的问题，我们是否可以实现自动化的方法记忆模拟（MemoSim），以及如何有效地这些方法。

项目成果

On Automated Memoization in the Field of Simulation Parameter Studies

论仿真参数研究领域的自动记忆

• DOI: 10.1145/3186316
• 发表时间: 2018
• 期刊: ACM Transactions on Modeling and Computer Simulation (TOMACS)
• 作者: M. Stoffers;D. Schemmel;O. Soria Dustmann;K. Wehrle
• 通讯作者: K. Wehrle

Automated memoization: Automatically identifying memoization units in simulation parameter studies

自动记忆：自动识别模拟参数研究中的记忆单位

• DOI: 10.1109/distra.2017.8167664
• 发表时间: 2017
• 期刊: 2017 IEEE/ACM 21st International Symposium on Distributed Simulation and Real Time Applications (DS-RT)
• 作者: M. Stoffers;R. Bettermann;K. Wehrle
• 通讯作者: K. Wehrle

Automated Memoization for Parameter Studies Implemented in Impure Languages

用不纯语言实现参数研究的自动记忆

• DOI: 10.1145/2901378.2901386
• 发表时间: 2016
• 期刊: Proceedings of the 2016 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation
• 作者: M. Stoffers;D. Schemmel;O. Soria Dustmann;K. Wehrle
• 通讯作者: K. Wehrle

Code-transparent Discrete Event Simulation for Time-accurate Wireless Prototyping

用于时间精确无线原型设计的代码透明离散事件仿真

• DOI: 10.1145/3064911.3064913
• 发表时间: 2017
• 期刊: Proceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation
• 作者: M. Serror;J. C. Kirchhof;M. Stoffers;K. Wehrle;J. Gross
• 通讯作者: J. Gross