Effectiveness of abstract interpretation in automatic parallelization: A case study in logic programming

Citation
F. Bueno et al., Effectiveness of abstract interpretation in automatic parallelization: A case study in logic programming, ACM T PROGR, 21(2), 1999, pp. 189-239
Citations number
86
Categorie Soggetti
Computer Science & Engineering
Journal title
ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS
ISSN journal
01640925 → ACNP
Volume
21
Issue
2
Year of publication
1999
Pages
189 - 239
Database
ISI
SICI code
0164-0925(199903)21:2<189:EOAIIA>2.0.ZU;2-6
Abstract
We report on a detailed study of the application and effectiveness of progr am analysis based on abstract interpretation to automatic program paralleli zation. We study the case of parallelizing logic programs using the notion of strict independence. We first propose and prove correct a methodology fo r the application in the parallelization task of the information inferred b y abstract interpretation, using a parametric domain. The methodology is ge neric in the sense of allowing the use of different analysis domains. A num ber of well-known approximation domains are then studied and the transforma tion into the parametric domain defined. The transformation directly illust rates the relevance and applicability of each abstract domain for the appli cation. Both local and global analyzers are then built using these domains and embedded in a complete parallelizing compiler. Then, the performance of the domains in this context is assessed through a number of experiments. A comparatively wide range of aspects is studied, from the resources needed by the analyzers in terms of time and memory to the actual benefits obtaine d from the information inferred. Such benefits are evaluated both in terms of the characteristics of the parallelized code and of the actual speedups obtained from it. The results show that data flow analysis plays an importa nt role in achieving efficient parallelizations, and that the cost of such analysis can be reasonable even for quite sophisticated abstract domains. F urthermore, the results also offer significant insight into the characteris tics of the domains, the demands of the application, and the trade-offs inv olved.