Autotune Framework

diff --git a/src/Collections/hashset.h b/src/Collections/hashset.h
index 6a823f5c58643f142c0397db13141cdae4f9f4f4..c86217cc8033cb3c20b045340317c236337a0972 100644 (file)
--- 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 528f5f2e8239acdbe225ebb31438b3153e11e2e6..3e60048a536f46a0a3e823fe36dee564a440556c 100644 (file)
--- 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 0ebcc2f51bfd16d91896a77b8e5533f1b336024b..78d16c82f78911c7b42e4790b193dde72d2ab818 100644 (file)
--- a/src/Tuner/autotuner.cc
+++ b/src/Tuner/autotuner.cc
@@ -1,11 +1,85 @@
 #include "autotuner.h"
 #include "csolver.h"
+#include "searchtuner.h"
+#include <math.h>
+#include <stdlib.h>
+#include <float.h>
+
+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;i<solvers.getSize();i++) {
+               CSolver * problem=solvers.get(i);
+               double score=evaluate(problem, tuner);
+               product*=score;
+       }
+       return pow(product, 1/((double)solvers.getSize()));
+}
+
+SearchTuner * AutoTuner::mutateTuner(SearchTuner * oldTuner, uint k) {
+       SearchTuner *newTuner=oldTuner->copyUsed();
+       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;i<budget;i++) {
+               SearchTuner *newTuner=mutateTuner(oldTuner, i);
+               double newScore=evaluateAll(newTuner);
+               double scoreDiff=newScore - oldScore; //smaller is better
+               if (newScore < bestScore) {
+                       bestScore = newScore;
+                       bestTuner = newTuner->copyUsed();
+               }
+
+               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 0b565410f9fa90003254bce3f9f907aae7ce0f1f..2490d564c71f721e8bd9972f2e58f2e3c3c06179 100644 (file)
--- 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<CSolver *> solvers;
+       long long evaluate(CSolver *problem, SearchTuner *tuner);
+       double evaluateAll(SearchTuner *tuner);
+       SearchTuner * mutateTuner(SearchTuner * oldTuner, uint k);
+
+       Vector<CSolver *> solvers;      
+       uint budget;
 };
 #endif

diff --git a/src/Tuner/searchtuner.cc b/src/Tuner/searchtuner.cc
index f9873c0b003e7084c06e6bdca0c6bfa90164ea83..fdc9835bf067033ab3b2bf144e3a5d5ee3fb1204 100644 (file)
--- 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 c136dc12359a215cf46dbb214e6503c0f638e40b..bf96b299529c40c58a8527313e5980b4d9511275 100644 (file)
--- 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