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

We report on a detailed study of the application and effectiveness of program analysis based on abstract interpretation to automatic program parallelization. We study the case of parallelizing logic programs using the notion of strict independence. We first propose and prove correct a methodology for the application in the parallelization task of the information inferred by abstract interpretation, using a parametric domain. The methodology is generic in the sense of allowing the use of different analysis domains. A number of well-known approximation domains are then studied and the transformation into the parametric domain defined. The transformation directly illustrates the relevance and applicability of each abstract domain for the application. 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 obtained 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 important role in achieving efficient parallelizations, and that the cost of such analysis can be reasonable even for quite sophisticated abstract domains. Furthermore, the results also offer significant insight into the characteristics of the domains, the demands of the application, and the trade-offs involved.

Effectiveness of global analysis in strict independence-based automatic program parallelization

This paper presents a study of the effectiveness of global analysis in the parallelization of logic programs using strict independence. A number of well-known approximation domains are selected and tlieir usefulness for the application in hand is explained. Also, methods for using the information provided by such domains to improve parallelization are proposed. Local and global analyses are built using these domains and such analyses are embedded in a complete parallelizing compiler. Then, the performance of the domains (and the system in general) is assessed for this application through a number of experiments. We argüe that the results offer significant insight into the characteristics of these domains, the demands of the application, and the tradeoffs involved.

Effectiveness of combined sharing and freeness analysis using abstract interpretation

This paper presents improved unification algorithms, an implementation, and an analysis of the effectiveness of an abstract interpreter based on the sharing + freeness domain presented in a previous paper, which was designed to accurately and concisely represent combined freeness and sharing information for program variables. We first briefly review this domain and the unification algorithms previously proposed. We then improve these algorithms and correct them to deal with some cases which were not well analyzed previously, illustrating the improvement with an example. We then present the implementation of the improved algorithm and evaluate its performance by comparing the effectiveness of the information inferred to that of other interpreters available to us for an application (program parallelization) that is common to all these interpreters. All these systems have been embedded in a real parallelizing compiler. Effectiveness of the analysis is measured in terms of actual final performance of the system: i.e. in terms of the actual speedups obtained. The results show good performance for the combined domain in that it improves the accuracy of both types of information and also in that the analyzer using the combined domain is more effective in the application than any of the other analyzers it is compared to.

Ball possession effectiveness in men's and women's elite basketball according to situational variables in different game periods

The aim of the present study was to identify the importance of floorball tactical variables to predict ball possession effectiveness, when controlling quality of opposition and game periods. The sample was composed by 1500 ball possessions, corresponding to 14 games randomly selected from the International Championships played during 2008 and 2010 (World Championship, Four nations tournament and classificatory phases for World Championship) by teams from different competition levels (HIGH, INTERMEDIATE and LOW). The effects of the predictor variables on successful ball possessions according to the three game contexts (HIGH vs. HIGH; HIGH vs. LOW; LOW vs. LOW games) were analyzed using Binomial Logistic Regressions. The results showed no interaction with the game period. In HIGH vs. HIGH games, quality of opposition showed an association with ball possession effectiveness with ending zone, offensive system, possession duration, height of shooting and defensive pressures previous to the shot. In HIGH vs. LOW games the important factors were the starting zone, possession duration, defensive pressure previous to the last pass and to the shot, technique of shooting and the number players involved in each ball possession. Finally, in LOW vs. LOW games, the results emphasized the importance of starting and ending zones, the number of passes used and the technique of shooting. In conclusion, elite floorball performance is mainly affected by quality of opposition showing different game patterns in each context that should be considered by coaches when preparing practices and competitions.