Constraint Programming with External Worst-Case Traversal Time Analysis

abstract interpretation; external function; multi-objective optimization; network analysis; worst-case traversal time analysis; allocation problem; constraint programming

Abstract :

[en] The allocation of software functions to processors under compute capacity and network links constraints is an important optimization problem in the field of embedded distributed systems. We present a hybrid approach to solve the allocation problem combining a constraint solver and a worst-case traversal time (WCTT) analysis that verifies the network timing constraints. The WCTT analysis is implemented as an industrial black-box program, which makes a tight integration with constraint solving challenging. We contribute to a new multi-objective constraint solving algorithm for integrating external under-approximating functions, such as the WCTT analysis, with constraint solving, and prove its correctness. We apply this new algorithm to the allocation problem in the context of automotive service-oriented architectures based on Ethernet networks, and provide a new dataset of realistic instances to evaluate our approach.

Research center :

ULHPC - University of Luxembourg: High Performance Computing

Disciplines :

Computer science

Author, co-author :

TALBOT, Pierre ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS) ; Interdisciplinary Centre for Security, Reliability and Trust (SnT), Luxembourg

HU, Tingting ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)

NAVET, Nicolas ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)

External co-authors :

Language :

English

Title :

Constraint Programming with External Worst-Case Traversal Time Analysis

Publication date :

September 2023

Event name :

29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Event place :

Toronto, Can

Event date :

27-08-2023 => 31-08-2023

Audience :

International

Main work title :

29th International Conference on Principles and Practice of Constraint Programming, CP 2023

Editor :

Yap, Roland H. C. Yap

Publisher :

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

ISBN/EAN :

978-3-9597730-0-3

Peer reviewed :

Peer reviewed

FnR Project :

FNR16101289 - A Concurrent Model Of Computation For Trustworthy Gpu Programming, 2021 (01/01/2022-31/12/2024) - Pascal Bouvry

Funders :

FNR - Fonds National de la Recherche [LU]

Funding text :

Funding Pierre Talbot: This work is supported by the Luxembourg National Research Fund (FNR) – COMOC Project, ref. C21/IS/16101289.

Available on ORBilu :

since 30 October 2023

Statistics

Number of views

38 (18 by Unilu)

Number of downloads

15 (7 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

Krzysztof R. Apt. The essence of constraint propagation. Theoretical computer science, 221(1-2):179-210, 1999. doi:10.1016/S0304-3975(99)00032-8.
Anne Bouillard and Éric Thierry. An algorithmic toolbox for network calculus. Discrete Event Dynamic Systems, 18(1):3-49, 2008. doi:10.1007/s10626-007-0028-x.
Marc Boyer and Hugo Daigmorte. Improved service curve for element with known transmission rate. IEEE Networking Letters, 5(1):46-49, 2023. doi:10.1109/LNET.2022.3150649.
Marc Boyer, Jörn Migge, and Nicolas Navet. An efficient and simple class of functions to model arrival curve of packetised flows. In Proceedings of the 1st International Workshop on Worst-Case Traversal Time, WCTT'11, pages 43-50, New York, NY, USA, 2011. Association for Computing Machinery. doi:10.1145/2071589.2071595.
Gabriel Campeanu, Jan Carlson, and Severine Sentilles. Component Allocation Optimization for Heterogeneous CPU-GPU Embedded Systems. In 2014 40th EUROMICRO Conference on Software Engineering and Advanced Applications, pages 229-236, Verona, Italy, 2014. IEEE. doi:10.1109/SEAA.2014.29.
Patrick Cousot and Radhia Cousot. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL'77, pages 238-252, New York, NY, USA, 1977. Association for Computing Machinery. doi:10.1145/512950.512973.
Robert I. Davis, Alan Burns, Reinder J. Bril, and Johan J. Lukkien. Controller Area Network (CAN) Schedulability Analysis: Refuted, Revisited and Revised. Real-Time Systems, 35(3):239-272, 2007. doi:10.1007/s11241-007-9012-7.
Rina Dechter and Avi Dechter. Belief Maintenance in Dynamic Constraint Networks. In Proceedings of the Seventh AAAI National Conference on Artificial Intelligence, AAAI'88, pages 37-42. AAAI Press, 1988.
Jip J. Dekker. MiniZinc Python, 2023. URL: https://github.com/MiniZinc/minizinc-python.
Vijay D'Silva, Leopold Haller, and Daniel Kroening. Abstract satisfaction. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages - POPL'14, pages 139-150, San Diego, California, USA, 2014. ACM Press. doi:10.1145/2535838.2535868.
Johannes Eder, Sebastian Voss, Andreas Bayha, Alexandru Ipatiov, and Maged Khalil. Hardware architecture exploration: automatic exploration of distributed automotive hardware architectures. Software and Systems Modeling, 19(4):911-934, 2020. doi:10.1007/s10270-020-00786-6.
Alexander Ek, Maria Garcia de la Banda, Andreas Schutt, Peter J. Stuckey, and Guido Tack. Modelling and Solving Online Optimisation Problems. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02):1477-1485, 2020. doi:10.1609/aaai.v34i02.5506.
Marco Gavanelli. An algorithm for multi-criteria optimization in CSPs. In ECAI 2002: 15th European Conference on Artificial Intelligence, July 21-26, 2002, Lyon France: Including Prestigious Applications of Intelligent Systems (PAIS 2002): Proceedings, volume 77, page 136. IOS Press, 2002.
Tias Guns, Peter J. Stuckey, and Guido Tack. Solution Dominance over Constraint Satisfaction Problems, 2018. arXiv:1812.09207 [cs]. URL: http://arxiv.org/abs/1812.09207.
Pierre-Emmanuel Hladik, Hadrien Cambazard, Anne-Marie Déplanche, and Narendra Jussien. Solving a real-time allocation problem with constraint programming. Journal of Systems and Software, 81(1):132-149, 2008. doi:10.1016/j.jss.2007.02.032.
J.N. Hooker and G. Ottosson. Logic-based Benders decomposition. Mathematical Programming, 96(1):33-60, 2003. doi:10.1007/s10107-003-0375-9.
Stefan Kugele, Philipp Obergfell, and Eric Sax. Model-based resource analysis and synthesis of service-oriented automotive software architectures. Software and Systems Modeling, 20(6):1945-1975, December 2021. doi:10.1007/s10270-021-00896-9.
Jean-Yves Le Boudec and Patrick Thiran. Network Calculus. In Network Calculus: A Theory of Deterministic Queuing Systems for the Internet, pages 3-81. Springer Berlin Heidelberg, Berlin, Heidelberg, 2001. doi:10.1007/3-540-45318-0_1.
Martin Lukasiewycz, Michael Glaß, Christian Haubelt, and Jürgen Teich. Solving Multi-objective Pseudo-Boolean Problems. In Theory and Applications of Satisfiability Testing - SAT 2007, pages 56-69. Springer Berlin Heidelberg, Berlin, Heidelberg, 2007. doi:10.1007/978-3-540-72788-0_9.
Bjørnar Luteberget, Koen Claessen, Christian Johansen, and Martin Steffen. SAT modulo discrete event simulation applied to railway design capacity analysis. Formal Methods in System Design, 57(2):211-245, August 2021. doi:10.1007/s10703-021-00368-2.
Irene Moser and Sanaz Mostaghim. The automotive deployment problem: A practical application for constrained multiobjective evolutionary optimisation. In IEEE Congress on Evolutionary Computation, pages 1-8, Barcelona, Spain, July 2010. IEEE. doi:10.1109/CEC. 2010.5585991.
Ahmed Nasrallah, Akhilesh S. Thyagaturu, Ziyad Alharbi, Cuixiang Wang, Xing Shao, Martin Reisslein, and Hesham ElBakoury. Ultra-Low Latency (ULL) Networks: The IEEE TSN and IETF DetNet Standards and Related 5G ULL Research. IEEE Communications Surveys & Tutorials, 21(1):88-145, 2019. doi:10.1109/COMST.2018.2869350.
Mitra Nasri, Sanjoy Baruah, Gerhard Fohler, and Mehdi Kargahi. On the Optimality of RM and EDF for Non-Preemptive Real-Time Harmonic Tasks. In Proceedings of the 22nd International Conference on Real-Time Networks and Systems - RTNS'14, pages 331-340, Versaille, France, 2014. ACM Press. doi:10.1145/2659787.2659806.
Asef Nazari, Dhananjay Thiruvady, Aldeida Aleti, and Irene Moser. A mixed integer linear programming model for reliability optimisation in the component deployment problem. Journal of the Operational Research Society, 67(8):1050-1060, August 2016. doi:10.1057/jors.2015. 119.
Nicholas Nethercote, Peter J. Stuckey, Ralph Becket, Sebastian Brand, Gregory J. Duck, and Guido Tack. MiniZinc: Towards a standard CP modelling language. In Principles and Practice of Constraint Programming-CP 2007, pages 529-543. Springer, 2007.
Olga Ohrimenko, Peter J. Stuckey, and Michael Codish. Propagation via Lazy Clause Generation. Constraints, 14(3):357-391, September 2009. doi:10.1007/s10601-008-9064-x.
Marie Pelleau, Antoine Miné, Charlotte Truchet, and Frédéric Benhamou. A Constraint Solver Based on Abstract Domains. In Verification, Model Checking, and Abstract Interpretation, pages 434-454. Springer, 2013. doi:10.1007/978-3-642-35873-9_26.
R. Queck. Analysis of Ethernet AVB for automotive networks using Network Nalculus. In 2012 IEEE International Conference on Vehicular Electronics and Safety (ICVES 2012), pages 61-67, July 2012. doi:10.1109/ICVES.2012.6294261.
RealTime-at-Work. Rtaw-pegase, 2022. URL: https://www.realtimeatwork.com/rtaw-pegase/.
Andrea Rendl, Tias Guns, Peter J. Stuckey, and Guido Tack. MiniSearch: a solver-independent meta-search language for MiniZinc. In Principles and Practice of Constraint Programming, pages 376-392. Springer, 2015. doi:10.1007/978-3-319-23219-5_27.
Pierre Schaus and Renaud Hartert. Multi-Objective Large Neighborhood Search. In Principles and Practice of Constraint Programming, volume 8124, pages 611-627. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. doi:10.1007/978-3-642-40627-0_46.
Christian Schulte, Guido Tack, and Mikael Lagerkvist. Modeling and Programming with Gecode, 2020.
Joseph Scott. Other Things Besides Number: Abstraction, Constraint Propagation, and String Variable Types. PhD thesis, Acta Universitatis Upsaliensis, Uppsala, 2016. OCLC: 943721122.
Seyed Mohammadhossein Tabatabaee, Marc Boyer, Jean-Yves Le Boudec, and Jörn Migge. Efficient and accurate handling of periodic flows in time-sensitive networks. In 2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 303-315, 2023. doi:10.1109/RTAS58335.2023.00031.
Pierre Talbot, Éric Monfroy, and Charlotte Truchet. Modular Constraint Solver Cooperation via Abstract Interpretation. Theory and Practice of Logic Programming, 20(6):848-863, 2020. doi:10.1017/S1471068420000162.
Dhananjay Thiruvady, I. Moser, Aldeida Aleti, and Asef Nazari. Constraint Programming and Ant Colony System for the Component Deployment Problem. Procedia Computer Science, 29:1937-1947, 2014. doi:10.1016/j.procs.2014.05.178.
Tindell, Hansson, and Wellings. Analysing real-time communications: controller area network (CAN). In Proceedings Real-Time Systems Symposium REAL-94, pages 259-263, San Juan, Puerto Rico, 1994. IEEE Comput. Soc. Press. doi:10.1109/REAL.1994.342710.
K. W. Tindell, A. Burns, and A. J. Wellings. Allocating hard real-time tasks: An NP-Hard problem made easy. Real-Time Systems, 4(2):145-165, June 1992. doi:10.1007/BF00365407.
P. M. Yomsi, D. Bertrand, N. Navet, and R. Davis. Controller Area Network (CAN): Response Time Analysis with Offsets. In 9th IEEE International Workshop on Factory Communication Systems, pages 43-52, United States, May 2012. IEEE. doi:10.1109/WFCS.2012.6242539.