Pruning Strategies in Adaptive Off-Line Tuning for Optimized Composition of Components on Heterogeneous Systems

L. Li, Usman Dastgeer, Christoph Kessler

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


Adaptive program optimizations, such as automatic selection of the expected fastest implementation variant for a computation component depending on runtime context, are important especially for heterogeneous computing systems but require good performance models. Empirical performance models based on trial executions which require no or little human efforts show more practical feasibility if the sampling and training cost can be reduced to a reasonable level. In previous work we proposed an early version of adaptive pruning algorithm for efficient selection of training samples, a decision-tree based method for representing, predicting and selecting the fastest implementation variants for given run-time call context properties, and a composition tool for building the overall composed application from its components. For adaptive pruning we use a heuristic convexity assumption. In this paper we consolidate and improve the method by new pruning techniques to better support the convexity assumption and better control the trade-off between sampling time, prediction accuracy and runtime prediction overhead. Our results show that the training time can be reduced by up to 39 times without noticeable prediction accuracy decrease. Furthermore, we evaluate the effect of combinations of pruning strategies and compare our adaptive sampling method with random sampling. We also use our smart-sampling method as a preprocessor to a state-of-the-art decision tree learning algorithm and compare the result to the predictor directly calculated by our method.
Original languageEnglish
Title of host publication2014 43rd International Conference on Parallel Processing Workshops
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages10
ISBN (Electronic)978-1-4799-5615-9
Publication statusPublished - 2014
Event43rd International Conference on Parallel Processing - Commons Hotel, Minneapolis, United States
Duration: 9 Sep 201414 Sep 2014


Conference43rd International Conference on Parallel Processing
Abbreviated titleICPP 2014
Country/TerritoryUnited States
Internet address


  • decision trees
  • parallel processing
  • random processes
  • sampling methods
  • adaptive off-line tuning
  • adaptive program optimization
  • decision-tree
  • heterogeneous computing system
  • pruning strategy
  • random sampling
  • sampling time
  • smart-sampling method
  • Accuracy
  • Adaptation models
  • Benchmark testing
  • Context
  • Predictive models
  • Training
  • Tuning
  • Adaptive sampling
  • Autotuning
  • GPU
  • Heterogeneous computing
  • Implementation selection
  • Machine learning
  • Performance optimization


Dive into the research topics of 'Pruning Strategies in Adaptive Off-Line Tuning for Optimized Composition of Components on Heterogeneous Systems'. Together they form a unique fingerprint.

Cite this