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
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.