MaSiF: Machine learning guided auto-tuning of parallel skeletons

Alexander Collins, Christian Fensch, Hugh Leather, Murray Cole

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Parallel skeletons provide a predefined set of parallel templates that can be combined, nested and parameterized with sequential code to produce complex parallel programs. The implementation of each skeleton includes parameters that have a significant effect on performance; so carefully tuning them is vital. The optimization space formed by these parameters is complex, non-linear, exhibits multiple local optima and is program dependent. This makes manual tuning impractical. Effective automatic tuning is therefore essential for the performance of parallel skeleton programs. In this paper we present MaSiF, a novel tool to auto-tune the parallelization parameters of skeleton parallel programs. It reduces the size of the parameter space using a combination of machine learning, via nearest neighbor classification, and linear dimensionality reduction using Principal Components Analysis. To auto-tune a new program, a set of program features is determined statically and used to compute k nearest neighbors from a set of training programs. Previously collected performance data for the nearest neighbors is used to reduce the size of the search space using Principal Components Analysis. Good parallelization parameters are found quickly by searching this smaller search space. We evaluate MaSiF for two existing parallel frameworks: Threading Building Blocks and FastFlow. MaSiF achieves 89% of the performance of the oracle on average. This exploration requires just 45 parameters values on average, which is ∼0.05% of the optimization space. In contrast, a state-of-the-art machine learning approach achieves 51%. MaSiF achieves an average speedup of 1.32× over parallelization parameters chosen by human experts.

Original languageEnglish
Title of host publication20th Annual International Conference on High Performance Computing, HiPC 2013
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages186-195
Number of pages10
ISBN (Print)978-1-4799-0729-8
DOIs
Publication statusPublished - 2013
Event20th Annual International Conference on High Performance Computing, HiPC 2013 - Bangalore, United Kingdom
Duration: 18 Dec 201321 Dec 2013

Conference

Conference20th Annual International Conference on High Performance Computing, HiPC 2013
CountryUnited Kingdom
CityBangalore
Period18/12/1321/12/13

Fingerprint

Dive into the research topics of 'MaSiF: Machine learning guided auto-tuning of parallel skeletons'. Together they form a unique fingerprint.

Cite this