From ad00cff7e27c843373ee952a069aff006db949fc Mon Sep 17 00:00:00 2001 From: bdemsky Date: Mon, 28 Aug 2017 14:14:46 -0700 Subject: [PATCH] Autotune Framework --- src/Collections/hashset.h | 17 ++++++++ src/Collections/hashtable.h | 11 ++++++ src/Tuner/autotuner.cc | 78 ++++++++++++++++++++++++++++++++++++- src/Tuner/autotuner.h | 9 ++++- src/Tuner/searchtuner.cc | 39 ++++++++++++++++++- src/Tuner/searchtuner.h | 10 ++++- 6 files changed, 157 insertions(+), 7 deletions(-) diff --git a/src/Collections/hashset.h b/src/Collections/hashset.h index 6a823f5..c86217c 100644 --- a/src/Collections/hashset.h +++ b/src/Collections/hashset.h @@ -148,6 +148,23 @@ public: return false; } + /** @brief Return random key from set. */ + + _Key getRandomElement() { + if (getSize() == 0) + return NULL; + else if (getSize() < 6) { + uint count = random() % getSize(); + LinkNode<_Key> *ptr=list; + while(count > 0) { + ptr = ptr->next; + count--; + } + return ptr->key; + } else + return table->getRandomValue()->key; + } + /** @brief Gets the original key corresponding to this one from the * hashset. Returns NULL if not present. */ diff --git a/src/Collections/hashtable.h b/src/Collections/hashtable.h index 528f5f2..3e60048 100644 --- a/src/Collections/hashtable.h +++ b/src/Collections/hashtable.h @@ -115,6 +115,17 @@ public: size = 0; } + /** Doesn't work with zero value */ + _Val getRandomValue() { + while(true) { + unsigned int index=random() & capacitymask; + struct hashlistnode<_Key, _Val> *bin = &table[index]; + if (bin->key != NULL && bin->val != NULL) { + return bin->val; + } + } + } + void resetanddelete() { for (unsigned int i = 0; i < capacity; i++) { struct hashlistnode<_Key, _Val> *bin = &table[i]; diff --git a/src/Tuner/autotuner.cc b/src/Tuner/autotuner.cc index 0ebcc2f..78d16c8 100644 --- a/src/Tuner/autotuner.cc +++ b/src/Tuner/autotuner.cc @@ -1,11 +1,85 @@ #include "autotuner.h" #include "csolver.h" +#include "searchtuner.h" +#include +#include +#include + +AutoTuner::AutoTuner(uint _budget) : + budget(_budget) { +} void AutoTuner::addProblem(CSolver *solver) { solvers.push(solver); } +long long AutoTuner::evaluate(CSolver * problem, SearchTuner *tuner) { + CSolver * copy=problem->clone(); + copy->setTuner(tuner); + int result = copy->startEncoding(); + long long elapsedTime=copy->getElapsedTime(); + long long encodeTime=copy->getEncodeTime(); + long long solveTime=copy->getSolveTime(); + long long metric=elapsedTime; + delete copy; + return metric; +} + +double AutoTuner::evaluateAll(SearchTuner *tuner) { + double product=1; + for(uint i=0;icopyUsed(); + uint numSettings=oldTuner->getSize(); + double factor=0.3;//Adjust this factor... + uint settingsToMutate=(uint)(factor*(((double)numSettings) * k)/(budget)); + if (settingsToMutate < 1) + settingsToMutate=1; + model_print("Mutating %u settings\n", settingsToMutate); + while(settingsToMutate-- != 0) { + newTuner->randomMutate(); + } + return newTuner; +} + + void AutoTuner::tune() { - - + SearchTuner * bestTuner = NULL; + double bestScore=DBL_MAX; + + SearchTuner * oldTuner=new SearchTuner(); + double base_temperature=evaluateAll(oldTuner); + double oldScore=base_temperature; + + for (uint i=0;icopyUsed(); + } + + double acceptanceP; + if (scoreDiff < 0) { + acceptanceP = 1; + } else { + double currTemp=base_temperature * (((double)budget - i) / budget); + acceptanceP = exp(-scoreDiff / currTemp); + } + double ran = ((double)random()) / RAND_MAX; + if (ran <= acceptanceP) { + oldScore = newScore; + oldTuner = newTuner; + } else { + delete newTuner; + } + } } diff --git a/src/Tuner/autotuner.h b/src/Tuner/autotuner.h index 0b56541..2490d56 100644 --- a/src/Tuner/autotuner.h +++ b/src/Tuner/autotuner.h @@ -5,11 +5,16 @@ class AutoTuner { public: - AutoTuner(); + AutoTuner(uint budget); void addProblem(CSolver *solver); void tune(); MEMALLOC; private: - Vector solvers; + long long evaluate(CSolver *problem, SearchTuner *tuner); + double evaluateAll(SearchTuner *tuner); + SearchTuner * mutateTuner(SearchTuner * oldTuner, uint k); + + Vector solvers; + uint budget; }; #endif diff --git a/src/Tuner/searchtuner.cc b/src/Tuner/searchtuner.cc index f9873c0..fdc9835 100644 --- a/src/Tuner/searchtuner.cc +++ b/src/Tuner/searchtuner.cc @@ -12,6 +12,17 @@ TunableSetting::TunableSetting(TunableParam _param) : param(_param) { } +TunableSetting::TunableSetting(TunableSetting * ts) : + hasVar(ts->hasVar), + type(ts->type), + param(ts->param), + lowValue(ts->lowValue), + highValue(ts->highValue), + defaultValue(ts->defaultValue), + selectedValue(ts->selectedValue) +{ +} + void TunableSetting::setDecision(int _low, int _high, int _default, int _selection) { lowValue = _low; highValue = _high; @@ -32,6 +43,18 @@ bool tunableSettingEquals(TunableSetting *setting1, TunableSetting *setting2) { SearchTuner::SearchTuner() { } +SearchTuner * SearchTuner::copyUsed() { + SearchTuner * tuner = new SearchTuner(); + HSIteratorTunableSetting *iterator=usedSettings.iterator(); + while(iterator->hasNext()) { + TunableSetting *setting=iterator->next(); + TunableSetting *copy=new TunableSetting(setting); + tuner->settings.add(copy); + } + delete iterator; + return tuner; +} + SearchTuner::~SearchTuner() { HSIteratorTunableSetting *iterator=settings.iterator(); while(iterator->hasNext()) { @@ -48,7 +71,8 @@ int SearchTuner::getTunable(TunableParam param, TunableDesc *descriptor) { result = settings.get(&setting); if ( result == NULL) { result=new TunableSetting(param); - result->setDecision(descriptor->lowValue, descriptor->highValue, descriptor->defaultValue, descriptor->defaultValue); + uint value = descriptor->lowValue + (random() % (1+ descriptor->highValue - descriptor->lowValue)); + result->setDecision(descriptor->lowValue, descriptor->highValue, descriptor->defaultValue, value); settings.add(result); } usedSettings.add(result); @@ -63,10 +87,21 @@ int SearchTuner::getVarTunable(VarType vartype, TunableParam param, TunableDesc result = settings.get(&setting); if ( result == NULL) { result=new TunableSetting(vartype, param); - result->setDecision(descriptor->lowValue, descriptor->highValue, descriptor->defaultValue, descriptor->defaultValue); + uint value = descriptor->lowValue + (random() % (1+ descriptor->highValue - descriptor->lowValue)); + result->setDecision(descriptor->lowValue, descriptor->highValue, descriptor->defaultValue, value); settings.add(result); } usedSettings.add(result); } return result->selectedValue; } + +void SearchTuner::randomMutate() { + TunableSetting * randomSetting = settings.getRandomElement(); + uint range=randomSetting->highValue-randomSetting->lowValue; + uint randomchoice=(random() % range) + randomSetting->lowValue; + if (randomchoice < randomSetting->selectedValue) + randomSetting->selectedValue = randomchoice; + else + randomSetting->selectedValue = randomchoice + 1; +} diff --git a/src/Tuner/searchtuner.h b/src/Tuner/searchtuner.h index c136dc1..bf96b29 100644 --- a/src/Tuner/searchtuner.h +++ b/src/Tuner/searchtuner.h @@ -8,6 +8,7 @@ class TunableSetting { public: TunableSetting(VarType type, TunableParam param); TunableSetting(TunableParam param); + TunableSetting(TunableSetting * ts); void setDecision(int _low, int _high, int _default, int _selection); MEMALLOC; private: @@ -35,10 +36,17 @@ class SearchTuner : public Tuner { ~SearchTuner(); int getTunable(TunableParam param, TunableDesc *descriptor); int getVarTunable(VarType vartype, TunableParam param, TunableDesc *descriptor); + SearchTuner * copyUsed(); + void randomMutate(); + uint getSize() { return usedSettings.getSize();} + MEMALLOC; private: + /** Used Settings keeps track of settings that were actually used by + the example. Mutating settings may cause the Constraint Compiler + not to query other settings.*/ HashSetTunableSetting usedSettings; + /** Settings contains all settings. */ HashSetTunableSetting settings; }; - #endif -- 2.34.1