SC20 Proceedings

The International Conference for High Performance Computing, Networking, Storage, and Analysis

Developing Models for the Runtime of Programs with Exponential Runtime Behavior


Workshop:PMBS20: The 11th International Workshop on Performance Modeling, Benchmarking and Simulation of High-Performance Computer Systems

Authors: Michael Burger, Giang Nam Nguyen, and Christian Bischof (Technical University Darmstadt)


Abstract: In this paper, we present a new approach to generate runtime models for programs whose runtime grows exponentially with the value of one input parameter. Such programs are, e.g., of high interest for cryptanalysis to analyze practical security of traditional and post-quantum secure schemes. The model generation approach on the base of profiled training runs is built on ideas realized in the open source tool Extra-P, extended with a new class of model functions and a shared-memory parallel simulated annealing approach to heuristically determine coefficients for the model functions. Our approach is implemented in the open source software SimAnMo (Simulated Annealing Modeler). We demonstrate on various theoretical and synthetic, practical test cases that our approach delivers very accurate models and reliable predictions, compared to standard approaches on x86 and ARM architectures. SimAnMo is also employed to generate models of four codes which are employed to solve the so-called shortest vector problem. This is an important problem from the field of lattice-based cryptography. We demonstrate the quality of our models with measurements for higher lattice dimensions, as far as it is feasible. Additionally, we highlight inherent problems with models for algorithms with exponential runtime.





Back to PMBS20: The 11th International Workshop on Performance Modeling, Benchmarking and Simulation of High-Performance Computer Systems Archive Listing



Back to Full Workshop Archive Listing