From 18d917b3ac3afcf893fe7b04ab35ad6e00c6a8ab Mon Sep 17 00:00:00 2001 From: Hamed Gorjiara Date: Wed, 19 Dec 2018 17:46:14 -0800 Subject: [PATCH] Breaking Multituner into comptuner and kmeanstuner --- src/Test/analyzemultituner.cc | 4 +- src/Test/printtuner.cc | 2 +- src/Test/runcomptuner.cc | 4 +- src/Test/runmultituner.cc | 6 +- src/Tuner/{multituner.cc => comptuner.cc} | 137 ++------------------ src/Tuner/comptuner.h | 24 ++++ src/Tuner/kmeanstuner.cc | 144 ++++++++++++++++++++++ src/Tuner/kmeanstuner.h | 34 +++++ src/Tuner/multituner.h | 28 ----- src/Tuner/randomtuner.cc | 6 +- src/Tuner/randomtuner.h | 3 +- src/classlist.h | 2 +- 12 files changed, 228 insertions(+), 166 deletions(-) rename src/Tuner/{multituner.cc => comptuner.cc} (64%) create mode 100644 src/Tuner/comptuner.h create mode 100644 src/Tuner/kmeanstuner.cc create mode 100644 src/Tuner/kmeanstuner.h delete mode 100644 src/Tuner/multituner.h diff --git a/src/Test/analyzemultituner.cc b/src/Test/analyzemultituner.cc index fab9082..effe965 100644 --- a/src/Test/analyzemultituner.cc +++ b/src/Test/analyzemultituner.cc @@ -1,5 +1,5 @@ #include "csolver.h" -#include "multituner.h" +#include "comptuner.h" #include "searchtuner.h" int main(int argc, char **argv) { @@ -10,7 +10,7 @@ int main(int argc, char **argv) { uint numruns; sscanf(argv[1], "%u", &numruns); - MultiTuner *multituner = new MultiTuner(0, 0, 0); + CompTuner *multituner = new CompTuner(0, 0); multituner->readData(numruns); multituner->findBestThreeTuners(); delete multituner; diff --git a/src/Test/printtuner.cc b/src/Test/printtuner.cc index 1c63b2f..8a3ccbd 100644 --- a/src/Test/printtuner.cc +++ b/src/Test/printtuner.cc @@ -1,5 +1,5 @@ #include "csolver.h" -#include "multituner.h" +#include "comptuner.h" #include "searchtuner.h" int main(int argc, char **argv) { diff --git a/src/Test/runcomptuner.cc b/src/Test/runcomptuner.cc index de751d1..6d9b93f 100644 --- a/src/Test/runcomptuner.cc +++ b/src/Test/runcomptuner.cc @@ -1,5 +1,5 @@ #include "csolver.h" -#include "multituner.h" +#include "comptuner.h" #include "searchtuner.h" int main(int argc, char **argv) { @@ -14,7 +14,7 @@ int main(int argc, char **argv) { sscanf(argv[2], "%u", &rounds); sscanf(argv[3], "%u", &timeout); - MultiTuner *multituner = new MultiTuner(budget, rounds, timeout); + CompTuner *multituner = new CompTuner(budget, timeout); bool tunerfiles = false; for (int i = 4; i < argc; i++) { if (!tunerfiles) { diff --git a/src/Test/runmultituner.cc b/src/Test/runmultituner.cc index b66fa5e..659ad7e 100644 --- a/src/Test/runmultituner.cc +++ b/src/Test/runmultituner.cc @@ -1,6 +1,6 @@ #include "csolver.h" -#include "multituner.h" #include "searchtuner.h" +#include "kmeanstuner.h" int main(int argc, char **argv) { if (argc < 7) { @@ -14,7 +14,7 @@ int main(int argc, char **argv) { sscanf(argv[2], "%u", &rounds); sscanf(argv[3], "%u", &timeout); - MultiTuner *multituner = new MultiTuner(budget, rounds, timeout); + KMeansTuner *multituner = new KMeansTuner(budget, rounds, timeout); bool tunerfiles = false; for (int i = 4; i < argc; i++) { if (!tunerfiles) { @@ -31,7 +31,7 @@ int main(int argc, char **argv) { exit(-1); } - multituner->tuneK(); + multituner->tune(); delete multituner; return 0; } diff --git a/src/Tuner/multituner.cc b/src/Tuner/comptuner.cc similarity index 64% rename from src/Tuner/multituner.cc rename to src/Tuner/comptuner.cc index 743d4cb..be17c4b 100644 --- a/src/Tuner/multituner.cc +++ b/src/Tuner/comptuner.cc @@ -1,4 +1,4 @@ -#include "multituner.h" +#include "comptuner.h" #include #include #include "searchtuner.h" @@ -6,13 +6,16 @@ #include #include "solver_interface.h" -MultiTuner::MultiTuner(uint _budget, uint _rounds, uint _timeout) : - BasicTuner(_budget, _timeout), - rounds(_rounds) +CompTuner::CompTuner(uint _budget, uint _timeout) : + BasicTuner(_budget, _timeout) { } -void MultiTuner::findBestThreeTuners() { +CompTuner::~CompTuner(){ + +} + +void CompTuner::findBestThreeTuners() { if (allTuners.getSize() < 3) { printData(); return; @@ -57,7 +60,7 @@ void MultiTuner::findBestThreeTuners() { } } -void MultiTuner::readData(uint numRuns) { +void CompTuner::readData(uint numRuns) { for (uint i = 0; i < numRuns; i++) { ifstream myfile; char buffer[512]; @@ -118,7 +121,7 @@ void MultiTuner::readData(uint numRuns) { } -void MultiTuner::tune() { +void CompTuner::tune() { Vector *tunerV = new Vector(&tuners); for (uint b = 0; b < budget; b++) { model_print("Round %u of %u\n", b, budget); @@ -205,123 +208,3 @@ void MultiTuner::tune() { } printData(); } - -void MultiTuner::mapProblemsToTuners(Vector *tunerV) { - for (uint i = 0; i < problems.getSize(); i++) { - Problem *problem = problems.get(i); - TunerRecord *bestTuner = NULL; - long long bestscore = 0; - for (uint j = 0; j < tunerV->getSize(); j++) { - TunerRecord *tuner = tunerV->get(j); - long long metric = tuner->getTime(problem); - if (metric == -1) { - metric = evaluate(problem, tuner); - if (metric != -1) - tuner->setTime(problem, metric); - else - tuner->setTime(problem, -2); - } - if ((bestTuner == NULL && metric >= 0) || - (metric < bestscore && metric >= 0)) { - bestTuner = tuner; - bestscore = metric; - } - } - if (bestTuner != NULL) - bestTuner->addProblem(problem); - } -} - -void clearVector(Vector *tunerV) { - for (uint j = 0; j < tunerV->getSize(); j++) { - TunerRecord *tuner = tunerV->get(j); - tuner->problems.clear(); - } -} - -void MultiTuner::tuneK() { - Vector *tunerV = new Vector(&tuners); - for (uint i = 0; i < rounds; i++) { - clearVector(tunerV); - mapProblemsToTuners(tunerV); - improveTuners(tunerV); - } - model_print("Best tuners\n"); - for (uint j = 0; j < tunerV->getSize(); j++) { - TunerRecord *tuner = tunerV->get(j); - char buffer[256]; - sprintf(buffer, "tuner%u.conf", j); - tuner->getTuner()->serialize(buffer); - tuner->getTuner()->print(); - } - delete tunerV; -} - -void MultiTuner::improveTuners(Vector *tunerV) { - for (uint j = 0; j < tunerV->getSize(); j++) { - TunerRecord *tuner = tunerV->get(j); - TunerRecord *newtuner = tune(tuner); - tunerV->set(j, newtuner); - } -} - -double MultiTuner::evaluateAll(TunerRecord *tuner) { - double product = 1; - for (uint i = 0; i < tuner->problemsSize(); i++) { - Problem *problem = tuner->getProblem(i); - long long metric = tuner->getTime(problem); - if (metric == -1) { - metric = evaluate(problem, tuner); - if (metric != -1) - tuner->setTime(problem, metric); - else - tuner->setTime(problem, -2); - } - - double score = metric; - if (metric < 0) - score = timeout; - product *= score; - } - return pow(product, 1 / ((double)tuner->problemsSize())); -} - -TunerRecord *MultiTuner::tune(TunerRecord *tuner) { - TunerRecord *bestTuner = NULL; - double bestScore = DBL_MAX; - - TunerRecord *oldTuner = tuner; - double base_temperature = evaluateAll(oldTuner); - double oldScore = base_temperature; - - for (uint i = 0; i < budget; i++) { - SearchTuner *tmpTuner = mutateTuner(oldTuner->getTuner(), i); - TunerRecord *newTuner = oldTuner->changeTuner(tmpTuner); - newTuner->setTunerNumber( allTuners.getSize() ); - allTuners.push(newTuner); - double newScore = evaluateAll(newTuner); - newTuner->getTuner()->printUsed(); - model_print("Received score %f\n", newScore); - double scoreDiff = newScore - oldScore; //smaller is better - if (newScore < bestScore) { - bestScore = newScore; - bestTuner = newTuner; - } - - 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; - } - } - - return bestTuner; -} - diff --git a/src/Tuner/comptuner.h b/src/Tuner/comptuner.h new file mode 100644 index 0000000..dd28105 --- /dev/null +++ b/src/Tuner/comptuner.h @@ -0,0 +1,24 @@ +#ifndef COMPTUNER_H +#define COMPTUNER_H +#include "classlist.h" +#include "structs.h" +#include "basictuner.h" + + +class CompTuner : public BasicTuner { +public: + CompTuner(uint budget, uint timeout); + virtual ~CompTuner(); + void readData(uint numRuns); + void tune(); + void findBestThreeTuners(); +protected: + +}; + +inline long long min(long long num1, long long num2, long long num3) { + return num1 < num2 && num1 < num3 ? num1 : + num2 < num3 ? num2 : num3; +} + +#endif diff --git a/src/Tuner/kmeanstuner.cc b/src/Tuner/kmeanstuner.cc new file mode 100644 index 0000000..333d9d9 --- /dev/null +++ b/src/Tuner/kmeanstuner.cc @@ -0,0 +1,144 @@ +/* + * To change this license header, choose License Headers in Project Properties. + * To change this template file, choose Tools | Templates + * and open the template in the editor. + */ + +/* + * File: kmeanstuner.cc + * Author: hamed + * + * Created on December 19, 2018, 4:16 PM + */ + +#include "kmeanstuner.h" +#include "float.h" +#include "searchtuner.h" +#include "math.h" + +KMeansTuner::KMeansTuner(uint budget, uint _rounds, uint timeout) : + BasicTuner(budget, timeout), + rounds(_rounds) { +} + +KMeansTuner::~KMeansTuner() { +} + +void clearVector(Vector *tunerV) { + for (uint j = 0; j < tunerV->getSize(); j++) { + TunerRecord *tuner = tunerV->get(j); + tuner->problems.clear(); + } +} + +void KMeansTuner::tune() { + Vector *tunerV = new Vector(&tuners); + for (uint i = 0; i < rounds; i++) { + clearVector(tunerV); + mapProblemsToTuners(tunerV); + improveTuners(tunerV); + } + model_print("Best tuners\n"); + for (uint j = 0; j < tunerV->getSize(); j++) { + TunerRecord *tuner = tunerV->get(j); + char buffer[256]; + sprintf(buffer, "tuner%u.conf", j); + tuner->getTuner()->serialize(buffer); + tuner->getTuner()->print(); + } + delete tunerV; +} + +void KMeansTuner::improveTuners(Vector *tunerV) { + for (uint j = 0; j < tunerV->getSize(); j++) { + TunerRecord *tuner = tunerV->get(j); + TunerRecord *newtuner = tune(tuner); + tunerV->set(j, newtuner); + } +} + +double KMeansTuner::evaluateAll(TunerRecord *tuner) { + double product = 1; + for (uint i = 0; i < tuner->problemsSize(); i++) { + Problem *problem = tuner->getProblem(i); + long long metric = tuner->getTime(problem); + if (metric == -1) { + metric = evaluate(problem, tuner); + if (metric != -1) + tuner->setTime(problem, metric); + else + tuner->setTime(problem, -2); + } + + double score = metric; + if (metric < 0) + score = timeout; + product *= score; + } + return pow(product, 1 / ((double)tuner->problemsSize())); +} + +TunerRecord *KMeansTuner::tune(TunerRecord *tuner) { + TunerRecord *bestTuner = NULL; + double bestScore = DBL_MAX; + + TunerRecord *oldTuner = tuner; + double base_temperature = evaluateAll(oldTuner); + double oldScore = base_temperature; + + for (uint i = 0; i < budget; i++) { + SearchTuner *tmpTuner = mutateTuner(oldTuner->getTuner(), i); + TunerRecord *newTuner = oldTuner->changeTuner(tmpTuner); + newTuner->setTunerNumber( allTuners.getSize() ); + allTuners.push(newTuner); + double newScore = evaluateAll(newTuner); + newTuner->getTuner()->printUsed(); + model_print("Received score %f\n", newScore); + double scoreDiff = newScore - oldScore; //smaller is better + if (newScore < bestScore) { + bestScore = newScore; + bestTuner = newTuner; + } + + 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; + } + } + + return bestTuner; +} + +void KMeansTuner::mapProblemsToTuners(Vector *tunerV) { + for (uint i = 0; i < problems.getSize(); i++) { + Problem *problem = problems.get(i); + TunerRecord *bestTuner = NULL; + long long bestscore = 0; + for (uint j = 0; j < tunerV->getSize(); j++) { + TunerRecord *tuner = tunerV->get(j); + long long metric = tuner->getTime(problem); + if (metric == -1) { + metric = evaluate(problem, tuner); + if (metric != -1) + tuner->setTime(problem, metric); + else + tuner->setTime(problem, -2); + } + if ((bestTuner == NULL && metric >= 0) || + (metric < bestscore && metric >= 0)) { + bestTuner = tuner; + bestscore = metric; + } + } + if (bestTuner != NULL) + bestTuner->addProblem(problem); + } +} \ No newline at end of file diff --git a/src/Tuner/kmeanstuner.h b/src/Tuner/kmeanstuner.h new file mode 100644 index 0000000..a6025a3 --- /dev/null +++ b/src/Tuner/kmeanstuner.h @@ -0,0 +1,34 @@ +/* + * To change this license header, choose License Headers in Project Properties. + * To change this template file, choose Tools | Templates + * and open the template in the editor. + */ + +/* + * File: kmeanstuner.h + * Author: hamed + * + * Created on December 19, 2018, 4:16 PM + */ + +#ifndef KMEANSTUNER_H +#define KMEANSTUNER_H + +#include "basictuner.h" + + +class KMeansTuner : public BasicTuner { +public: + KMeansTuner(uint budget, uint rounds, uint timeout ); + virtual ~KMeansTuner(); + void tune(); +private: + double evaluateAll(TunerRecord *tuner); + void mapProblemsToTuners(Vector *tunerV); + void improveTuners(Vector *tunerV); + TunerRecord *tune(TunerRecord *tuner); + uint rounds; +}; + +#endif /* KMEANSTUNER_H */ + diff --git a/src/Tuner/multituner.h b/src/Tuner/multituner.h deleted file mode 100644 index cf42d9f..0000000 --- a/src/Tuner/multituner.h +++ /dev/null @@ -1,28 +0,0 @@ -#ifndef MULTITUNER_H -#define MULTITUNER_H -#include "classlist.h" -#include "structs.h" -#include "basictuner.h" - - -class MultiTuner : public BasicTuner { -public: - MultiTuner(uint budget, uint rounds, uint timeout); - void readData(uint numRuns); - void tuneK(); - void tune(); - void findBestThreeTuners(); -protected: - double evaluateAll(TunerRecord *tuner); - void mapProblemsToTuners(Vector *tunerV); - void improveTuners(Vector *tunerV); - TunerRecord *tune(TunerRecord *tuner); - uint rounds; -}; - -inline long long min(long long num1, long long num2, long long num3) { - return num1 < num2 && num1 < num3 ? num1 : - num2 < num3 ? num2 : num3; -} - -#endif diff --git a/src/Tuner/randomtuner.cc b/src/Tuner/randomtuner.cc index 1c1a0f3..2b0701c 100644 --- a/src/Tuner/randomtuner.cc +++ b/src/Tuner/randomtuner.cc @@ -1,7 +1,7 @@ #include "randomtuner.h" #include "csolver.h" #include "searchtuner.h" -#include "multituner.h" +#include "comptuner.h" #include #include #include @@ -12,6 +12,10 @@ RandomTuner::RandomTuner(uint _budget, uint _timeout) : BasicTuner(_budget, _timeout) { } +RandomTuner::~RandomTuner(){ + +} + void RandomTuner::tune() { for (uint r = 0; r < budget; r++) { model_print("Round %u of %u\n", r, budget); diff --git a/src/Tuner/randomtuner.h b/src/Tuner/randomtuner.h index bc063f0..75b8800 100644 --- a/src/Tuner/randomtuner.h +++ b/src/Tuner/randomtuner.h @@ -2,7 +2,7 @@ #define RANDOMTUNER_H #include "classlist.h" #include "structs.h" -#include "multituner.h" +#include "comptuner.h" #include "basictuner.h" /** @@ -11,6 +11,7 @@ class RandomTuner : public BasicTuner { public: RandomTuner(uint _budget, uint _timeout); + virtual ~RandomTuner(); void tune(); protected: bool randomMutation(SearchTuner *tuner); diff --git a/src/classlist.h b/src/classlist.h index cccf689..c182063 100644 --- a/src/classlist.h +++ b/src/classlist.h @@ -57,7 +57,7 @@ class OrderEdge; class DOREdge; class AutoTuner; -class MultiTuner; +class CompTuner; class SearchTuner; class TunableSetting; -- 2.34.1