TU Darmstadt / ULB / TUbiblio

Automatic Loop Invariant Generation for Data Dependence Analysis

Tabar, Asmae Heydari ; Bubel, Richard ; Hähnle, Reiner (2022):
Automatic Loop Invariant Generation for Data Dependence Analysis.
In: Proceedings: IEEE/ACM 10th International Conference on Formal Methods in Software Engineering: FormaliSE 2022, pp. 34-45,
IEEE, 10th IEEE/ACM International Conference on Formal Methods in Software Engineering, Pittsburgh, 22.05.2022, ISBN 978-1-4503-9287-7,
[Conference or Workshop Item]

Abstract

Parallelization of programs relies on sound and precise analysis of data dependences in the code, specifically, when dealing with loops. State-of-art tools are based on dynamic profiling and static analysis. They tend to over- and, occasionally, to under-approximate dependences. The former misses parallelization opportunities, the latter can change the behavior of the parallelized program. In this paper we present a sound and highly precise approach to generate data dependences based on deductive verification. The central technique is to infer a specific form of loop invariant tailored to express dependences. To achieve full automation, we adapt predicate abstraction in a suitable manner. To retain as much precision as possible, we generalized logic-based symbolic execution to compute abstract dependence predicates. We implemented our approach for Java on top of a deductive verification tool. The evaluation shows that our approach can generate highly precise data dependences for representative code taken from HPC applications.

Item Type: Conference or Workshop Item
Erschienen: 2022
Creators: Tabar, Asmae Heydari ; Bubel, Richard ; Hähnle, Reiner
Title: Automatic Loop Invariant Generation for Data Dependence Analysis
Language: English
Abstract:

Parallelization of programs relies on sound and precise analysis of data dependences in the code, specifically, when dealing with loops. State-of-art tools are based on dynamic profiling and static analysis. They tend to over- and, occasionally, to under-approximate dependences. The former misses parallelization opportunities, the latter can change the behavior of the parallelized program. In this paper we present a sound and highly precise approach to generate data dependences based on deductive verification. The central technique is to infer a specific form of loop invariant tailored to express dependences. To achieve full automation, we adapt predicate abstraction in a suitable manner. To retain as much precision as possible, we generalized logic-based symbolic execution to compute abstract dependence predicates. We implemented our approach for Java on top of a deductive verification tool. The evaluation shows that our approach can generate highly precise data dependences for representative code taken from HPC applications.

Book Title: Proceedings: IEEE/ACM 10th International Conference on Formal Methods in Software Engineering: FormaliSE 2022
Publisher: IEEE
ISBN: 978-1-4503-9287-7
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Software Engineering
Event Title: 10th IEEE/ACM International Conference on Formal Methods in Software Engineering
Event Location: Pittsburgh
Event Dates: 22.05.2022
Date Deposited: 20 Jul 2022 07:17
URL / URN: https://ieeexplore.ieee.org/document/9796460
Additional Information:

co-located with ICSE 2022, the 44th International Conference on Software Engineering

PPN:
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details