Paper Info
Title
Siblingrivalry: online autotuning through local competitions
Abstract
Modern high performance libraries, such as ATLAS and FFTW, and programming languages, such as PetaBricks, have shown that autotuning computer programs can lead to significant speedups. However, autotuning can be burdensome to the deployment of a program, since the tuning process can take a long time and should be re-run whenever the program, microarchitecture, execution environment, or tool chain changes. Failure to re-autotune programs often leads to widespread use of sub-optimal algorithms. With the growth of cloud computing, where computations can run in environments with unknown load and migrate between different (possibly unknown) microarchitectures, the need for online autotuning has become increasingly important. We present SiblingRivalry, a new model for always-on online autotuning that allows parallel programs to continuously adapt and optimize themselves to their environment. In our system, requests are processed by dividing the available cores in half, and processing two identical requests in parallel on each half. Half of the cores are devoted to a known safe program configuration, while the other half are used for an experimental program configuration chosen by our self-adapting evolutionary algorithm. When the faster configuration completes, its results are returned, and the slower configuration is terminated. Over time, this constant experimentation allows programs to adapt to changing dynamic environments and often outperform the original algorithm that uses the entire system.
Year
DOI
Venue
2012
10.1145/2380403.2380425
CASES
Keywords
Field
DocType
experimental program configuration,local competition,always-on online autotuning,faster configuration,slower configuration,online autotuning,entire system,dynamic environment,safe program configuration,parallel program,autotuning computer program,evolutionary algorithm,genetic algorithm
Software deployment,Division (mathematics),Evolutionary algorithm,Computer science,Parallel computing,Real-time computing,Genetic algorithm,Cloud computing,Distributed computing,Microarchitecture,Computation
Conference
Citations 
PageRank 
References 
16
0.53
25
Authors
7
Name
Order
Citations
PageRank
Jason Ansel142218.15
Maciej Pacula2312.54
Yee Lok Wong31796.64
Cy Chan41838.45
Marek Olszewski528211.85
Una-May O'Reilly61477181.38
Saman P. Amarasinghe74734395.55