Tabar, Asmae Heydari ; Bubel, Richard ; Hähnle, Reiner (2022)
Automatic Loop Invariant Generation for Data Dependence Analysis.
10th IEEE/ACM International Conference on Formal Methods in Software Engineering. Pittsburgh (22.05.2022-22.05.2022)
Conference or Workshop Item, Bibliographie
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 |
| Type of entry: | Bibliographie |
| Title: | Automatic Loop Invariant Generation for Data Dependence Analysis |
| Language: | English |
| Date: | 20 June 2022 |
| Publisher: | IEEE |
| Book Title: | Proceedings: IEEE/ACM 10th International Conference on Formal Methods in Software Engineering: FormaliSE 2022 |
| Event Title: | 10th IEEE/ACM International Conference on Formal Methods in Software Engineering |
| Event Location: | Pittsburgh |
| Event Dates: | 22.05.2022-22.05.2022 |
| URL / URN: | https://ieeexplore.ieee.org/document/9796460 |
| 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. |
| Additional Information: | co-located with ICSE 2022, the 44th International Conference on Software Engineering |
| Divisions: | 20 Department of Computer Science 20 Department of Computer Science > Software Engineering |
| Date Deposited: | 20 Jul 2022 07:17 |
| Last Modified: | 20 Jul 2022 07:17 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Send an inquiry |
Options (only for editors)
 |
Show editorial Details |
Drucken
Impressum