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)
Konferenzveröffentlichung, Bibliographie
Kurzbeschreibung (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.
| Typ des Eintrags: | Konferenzveröffentlichung |
|---|---|
| Erschienen: | 2022 |
| Autor(en): | Tabar, Asmae Heydari ; Bubel, Richard ; Hähnle, Reiner |
| Art des Eintrags: | Bibliographie |
| Titel: | Automatic Loop Invariant Generation for Data Dependence Analysis |
| Sprache: | Englisch |
| Publikationsjahr: | 20 Juni 2022 |
| Verlag: | IEEE |
| Buchtitel: | Proceedings: IEEE/ACM 10th International Conference on Formal Methods in Software Engineering: FormaliSE 2022 |
| Veranstaltungstitel: | 10th IEEE/ACM International Conference on Formal Methods in Software Engineering |
| Veranstaltungsort: | Pittsburgh |
| Veranstaltungsdatum: | 22.05.2022-22.05.2022 |
| URL / URN: | https://ieeexplore.ieee.org/document/9796460 |
| Kurzbeschreibung (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. |
| Zusätzliche Informationen: | co-located with ICSE 2022, the 44th International Conference on Software Engineering |
| Fachbereich(e)/-gebiet(e): | 20 Fachbereich Informatik 20 Fachbereich Informatik > Software Engineering |
| Hinterlegungsdatum: | 20 Jul 2022 07:17 |
| Letzte Änderung: | 20 Jul 2022 07:17 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum