Array-Aware Matching: Taming the Complexity of Large-Scale Simulation Models

Abstract

Equation-based modelling is a powerful approach to tame the complexity of large-scale simulation problems. Equation-based tools automatically translate models into imperative languages. When confronted with nowadays’ problems, however, well assessed model translation techniques exhibit scalability issues that are particularly severe when models contain very large arrays. In fact, such models can be made very compact by enclosing equations into looping constructs, but reflecting the same compactness into the translated imperative code is nontrivial. In this paper, we face this issue by concentrating on a key step of equations-to-code translation, the equation/variable matching. We first show that an efficient translation of models with (large) arrays needs awareness of their presence, by defining a figure of merit to measure how much the looping constructs are preserved along the translation. We then show that the said figure of merit allows to define an optimal array-aware matching, and as our main result, that the so stated optimal array-aware matching problem is NP-complete. As an additional result, we propose a heuristic algorithm capable of performing array-aware matching in polynomial time. The proposed algorithm can be proficiently used by model translator developers in the implementation of efficient tools for large-scale system simulation.

Publication
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE
Daniele Cattaneo
Daniele Cattaneo
Postdoctoral Researcher
Federico Terraneo
Federico Terraneo
Associate Professor

Federico Terraneo received his B.Sc. and M.Sc. degrees in computer engineering from the Politecnico di Milano, Milan, Italy, and his Ph.D. degree in Information Technology from Politecnico di Milano in 2015. Currently he holds a Postdoc position at Politecnico di Milano. His research interests include embedded systems and the application of principles of control theory to the design of software systems. Since 2008 he has been the main developer and maintainer of the Miosix embedded operating system.

Stefano Cherubin
Ph.D. Student
Giovanni Agosta
Giovanni Agosta
Associate Professor

Giovanni Agosta, Associate Professor at Politecnico di Milano, holds a Laurea in Computer Engineering (2000) and a PhD in Information Technology (2004). His research focuses on compiler-computer architecture interaction, emphasizing performance, energy-efficiency, and security. He has authored 100+ papers, won multiple awards, and participated in 17 EU-funded projects.