Predicting Parallelization of Sequential Programs Using Supervised Learning

We investigate an automatic method for classifying which regions of sequential programs could be parallelized, using dynamic features of the code collected at runtime. We train a supervised learning algorithm on versions of the NAS Parallel Benchmark (NPB) code hand-annotated with OpenMP parallelization directives in order to approximate the parallelization that might be produced by a human expert. A model comparison shows that support vector machines and decision trees have comparable performance on this classification problem, but boosting using AdaBoost is able to increase the performance of the decision trees. We further analyze the relative importance of the collected program features and demonstrate that within-loop instruction counts provide the greatest contribution to decision tree error reduction, with dependency graph features of secondary importance.