Fast automatic heuristic construction using active learning

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Building effective optimization heuristics is a challenging task which often takes developers several months if not years to complete. Predictive modelling has recently emerged as a promising solution, automatically constructing heuristics from training data. However, obtaining this data can take months per platform. This is becoming an ever more critical problem and if no solution is found we shall be left with out of date heuristics which cannot extract the best performance from modern machines. In this work, we present a low-cost predictive modelling approach for automatic heuristic construction which significantly reduces this training overhead. Typically in supervised learning the training instances are randomly selected to evaluate regardless of how much useful information they carry. This wastes effort on parts of the space that contribute little to the quality of the produced heuristic. Our approach, on the other hand, uses active learning to select and only focus on the most useful training examples. We demonstrate this technique by automatically constructing a model to determine on which device to execute four parallel programs at differing problem dimensions for a representative Cpu–Gpu based heterogeneous system. Our methodology is remarkably simple and yet effective, making it a strong candidate for wide adoption. At high levels of classification accuracy the average learning speed-up is 3x, as compared to the state-of-the-art.

Bibliographical metadata

Original languageEnglish
Title of host publicationLanguages and Compilers for Parallel Computing - 27th International Workshop, LCPC 2014, Revised Selected Papers
EditorsJames Brodman, Peng Tu
PublisherSpringer Nature
Pages146-160
Number of pages15
ISBN (Electronic)9783319174723
DOIs
Publication statusPublished - 1 Jan 2015
Event27th International Workshop on Languages and Compilers for Parallel Computing - Hillsboro, United States
Event duration: 15 Sep 201417 Sep 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8967
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th International Workshop on Languages and Compilers for Parallel Computing
Abbreviated titleLCPC 2014
CountryUnited States
CityHillsboro
Period15/09/1417/09/14