From: Hamed Gorjiara Date: Fri, 4 Jan 2019 19:10:12 +0000 (-0800) Subject: Adding Simulated Annealing Tuner ... X-Git-Url: http://plrg.eecs.uci.edu/git/?p=satune.git;a=commitdiff_plain;h=277157ed17fd19fe51ae9ed82921c8f371d6ccf3;ds=sidebyside Adding Simulated Annealing Tuner ... --- diff --git a/src/Test/runcomptuner.cc b/src/Test/runcomptuner.cc deleted file mode 100644 index 6d9b93f..0000000 --- a/src/Test/runcomptuner.cc +++ /dev/null @@ -1,37 +0,0 @@ -#include "csolver.h" -#include "comptuner.h" -#include "searchtuner.h" - -int main(int argc, char **argv) { - if (argc < 7) { - printf("You should specify %s budget rounds timeout problemfilenames - tunerfilenames", argv[0]); - exit(-1); - } - uint budget; - uint rounds; - uint timeout; - sscanf(argv[1], "%u", &budget); - sscanf(argv[2], "%u", &rounds); - sscanf(argv[3], "%u", &timeout); - - CompTuner *multituner = new CompTuner(budget, timeout); - bool tunerfiles = false; - for (int i = 4; i < argc; i++) { - if (!tunerfiles) { - if (argv[i][0] == '-' && argv[i][1] == 0) - tunerfiles = true; - else - multituner->addProblem(argv[i]); - } else - multituner->addTuner(new SearchTuner(argv[i], true )); //add settings to usedsettigs - } - - if (!tunerfiles) { - printf("You should specify %s budget rounds timeout problemfilenames - tunerfilenames", argv[0]); - exit(-1); - } - - multituner->tune(); - delete multituner; - return 0; -} diff --git a/src/Test/runmultituner.cc b/src/Test/runmultituner.cc index 659ad7e..e2ecbd8 100644 --- a/src/Test/runmultituner.cc +++ b/src/Test/runmultituner.cc @@ -1,29 +1,53 @@ #include "csolver.h" #include "searchtuner.h" #include "kmeanstuner.h" +#include "satuner.h" +#include "comptuner.h" +#include "randomtuner.h" + +void printKnownTunerTypes(){ + printf("Known Tuner Types:\nRandom Tuner=1\nComp Tuner=2\nKmeans Tuner=3\nSimulated Annealing Tuner=4\n"); +} + +BasicTuner *createTuner(uint tunertype, uint budget, uint rounds, uint timeout){ + switch(tunertype){ + case 1: return new RandomTuner(budget, timeout); + case 2: return new CompTuner(budget, timeout); + case 3: return new KMeansTuner(budget, rounds, timeout); + case 4: return new SATuner(budget, timeout); + default: + printf("Tuner type %u is unknown\n", tunertype); + printKnownTunerTypes(); + exit(-1); + } + +} int main(int argc, char **argv) { - if (argc < 7) { - printf("You should specify %s budget rounds timeout problemfilenames - tunerfilenames", argv[0]); + if (argc < 8) { + printf("You should specify: %s TunerType budget rounds timeout problemfilenames - tunerfilenames\n", argv[0]); + printKnownTunerTypes(); exit(-1); } + uint tunertype; uint budget; uint rounds; uint timeout; - sscanf(argv[1], "%u", &budget); - sscanf(argv[2], "%u", &rounds); - sscanf(argv[3], "%u", &timeout); + sscanf(argv[1], "%u", &tunertype); + sscanf(argv[2], "%u", &budget); + sscanf(argv[3], "%u", &rounds); + sscanf(argv[4], "%u", &timeout); - KMeansTuner *multituner = new KMeansTuner(budget, rounds, timeout); + BasicTuner *multituner = createTuner(tunertype, budget, rounds, timeout); bool tunerfiles = false; - for (int i = 4; i < argc; i++) { + for (int i = 5; i < argc; i++) { if (!tunerfiles) { if (argv[i][0] == '-' && argv[i][1] == 0) tunerfiles = true; else multituner->addProblem(argv[i]); } else - multituner->addTuner(new SearchTuner(argv[i])); + multituner->addTuner(new SearchTuner(argv[i], true )); //add settings to usedsettigs } if (!tunerfiles) { diff --git a/src/Test/runrandomtuner.cc b/src/Test/runrandomtuner.cc deleted file mode 100644 index 429d07a..0000000 --- a/src/Test/runrandomtuner.cc +++ /dev/null @@ -1,35 +0,0 @@ -#include "csolver.h" -#include "randomtuner.h" -#include "searchtuner.h" - -int main(int argc, char **argv) { - if (argc < 6) { - printf("You should specify %s rounds timeout problemfilenames - tunerfilenames", argv[0]); - exit(-1); - } - uint rounds; - uint timeout; - sscanf(argv[1], "%u", &rounds); - sscanf(argv[2], "%u", &timeout); - - RandomTuner *randomTuner = new RandomTuner(rounds, timeout); - bool tunerfiles = false; - for (int i = 3; i < argc; i++) { - if (!tunerfiles) { - if (argv[i][0] == '-' && argv[i][1] == 0) - tunerfiles = true; - else - randomTuner->addProblem(argv[i]); - } else - randomTuner->addTuner(new SearchTuner(argv[i])); - } - - if (!tunerfiles) { - printf("You should specify %s budget rounds timeout problemfilenames - tunerfilenames", argv[0]); - exit(-1); - } - - randomTuner->tune(); - delete randomTuner; - return 0; -} diff --git a/src/Tuner/basictuner.cc b/src/Tuner/basictuner.cc index 23e4d38..889b543 100644 --- a/src/Tuner/basictuner.cc +++ b/src/Tuner/basictuner.cc @@ -102,10 +102,13 @@ void BasicTuner::printData() { } } -bool BasicTuner::tunerExists(SearchTuner *tuner){ +bool BasicTuner::tunerExists(TunerRecord *tunerec){ + SearchTuner *tuner = tunerec->getTuner(); for(uint i=0; i< explored.getSize(); i++){ - if(explored.get(i)->getTuner()->equalUsed(tuner)) + if(explored.get(i)->getTuner()->equalUsed(tuner)){ + model_print("************Tuner <%d> is replicate of Tuner <%d>\n", tunerec->getTunerNumber(), explored.get(i)->getTunerNumber()); return true; + } } return false; } @@ -206,14 +209,14 @@ SearchTuner *BasicTuner::mutateTuner(SearchTuner *oldTuner, uint k) { return newTuner; } -bool BasicTuner::subTunerExist(SearchTuner *newTuner){ +int BasicTuner::subTunerIndex(SearchTuner *newTuner){ for (uint i=0; i< explored.getSize(); i++){ SearchTuner *tuner = explored.get(i)->getTuner(); if(tuner->isSubTunerof(newTuner)){ - return true; + return i; } } - return false; + return -1; } @@ -221,4 +224,4 @@ void BasicTuner::updateTimeout(Problem *problem, long long metric) { if (metric < problem->getBestTime()) { problem->setBestTime( metric ); } -} \ No newline at end of file +} diff --git a/src/Tuner/basictuner.h b/src/Tuner/basictuner.h index 83d1196..14ab7d8 100644 --- a/src/Tuner/basictuner.h +++ b/src/Tuner/basictuner.h @@ -42,8 +42,8 @@ private: class TunerRecord { public: - TunerRecord(SearchTuner *_tuner) : tuner(_tuner), tunernumber(-1) {} - TunerRecord(SearchTuner *_tuner, int _tunernumber) : tuner(_tuner), tunernumber(_tunernumber) {} + TunerRecord(SearchTuner *_tuner) : tuner(_tuner), tunernumber(-1), isduplicate(false) {} + TunerRecord(SearchTuner *_tuner, int _tunernumber) : tuner(_tuner), tunernumber(_tunernumber), isduplicate(false) {} SearchTuner *getTuner() {return tuner;} void inline addProblem(Problem * problem){problems.push(problem);} TunerRecord *changeTuner(SearchTuner *_newtuner); @@ -53,6 +53,8 @@ public: inline void setTunerNumber(int numb){tunernumber = numb;} inline int getTunerNumber(){return tunernumber;} inline uint problemsSize() {return problems.getSize();} + inline void setDuplicate(bool _duplicate) { isduplicate = _duplicate;} + inline bool isDuplicate() {return isduplicate;} inline Problem *getProblem(uint index){return problems.get(index);} void print(); void printProblemsInfo(); @@ -63,6 +65,7 @@ private: Hashtable timetaken; int tunernumber; friend void clearVector(Vector *tunerV); + bool isduplicate; }; class BasicTuner { @@ -82,8 +85,8 @@ protected: * @param newTuner * @return */ - bool subTunerExist(SearchTuner *newTuner); - bool tunerExists(SearchTuner *tunerRec); + int subTunerIndex(SearchTuner *newTuner); + bool tunerExists(TunerRecord *tunerRec); SearchTuner *mutateTuner(SearchTuner *oldTuner, uint k); void updateTimeout(Problem *problem, long long metric); Vector allTuners; diff --git a/src/Tuner/comptuner.cc b/src/Tuner/comptuner.cc index be17c4b..895e06b 100644 --- a/src/Tuner/comptuner.cc +++ b/src/Tuner/comptuner.cc @@ -125,22 +125,17 @@ void CompTuner::tune() { Vector *tunerV = new Vector(&tuners); for (uint b = 0; b < budget; b++) { model_print("Round %u of %u\n", b, budget); - uint tSize = tunerV->getSize(); - for (uint i = 0; i < tSize; i++) { - SearchTuner *tmpTuner = mutateTuner(tunerV->get(i)->getTuner(), b); - TunerRecord *tmp = new TunerRecord(tmpTuner); - tmp->setTunerNumber(allTuners.getSize()); - model_print("Mutated tuner %u to generate tuner %u\n", tunerV->get(i)->getTunerNumber(), tmp->getTunerNumber()); - allTuners.push(tmp); - tunerV->push(tmp); - } - Hashtable scores; - for (uint i = 0; i < problems.getSize(); i++) { - Problem *problem = problems.get(i); - Vector places; - for (uint j = 0; j < tunerV->getSize(); j++) { - TunerRecord *tuner = tunerV->get(j); + Vector *> allplaces; + for(uint ii=0; ii< problems.getSize(); ii++){ + allplaces.push(new Vector()); + } + for (uint j = 0; j < tunerV->getSize(); j++) { + TunerRecord *tuner = tunerV->get(j); + + for (uint i = 0; i < problems.getSize(); i++) { + Vector *places = allplaces.get(i); + Problem *problem = problems.get(i); long long metric = tuner->getTime(problem); if (metric == -1) { metric = evaluate(problem, tuner); @@ -153,20 +148,34 @@ void CompTuner::tune() { tuner->setTime(problem, metric); else tuner->setTime(problem, -2); + + if(tunerExists(tuner)){ + //Solving the problem and noticing the tuner + //already exists + tuner->setDuplicate(true); + break; + } } if (metric >= 0) { uint k = 0; - for (; k < places.getSize(); k++) { - if (metric < places.get(k)->getTime(problem)) + for (; k < places->getSize(); k++) { + if (metric < places->get(k)->getTime(problem)) break; } model_print("place[%u]=Tuner<%p,%d>\n", k, tuner, tuner->getTunerNumber()); - places.insertAt(k, tuner); + places->insertAt(k, tuner); } } + } + for(uint ii=0; ii < problems.getSize(); ii++){ + Problem *problem = problems.get(ii); + Vector *places = allplaces.get(ii); int points = 9; - for (uint k = 0; k < places.getSize() && points; k++) { - TunerRecord *tuner = places.get(k); + for (uint k = 0; k < places->getSize() && points; k++) { + TunerRecord *tuner = places->get(k); + if(tuner->isDuplicate()){ + continue; + } int currScore = 0; if (scores.contains(tuner)) currScore = scores.get(tuner); @@ -177,6 +186,9 @@ void CompTuner::tune() { points = points / 3; } } + for(uint ii=0; ii< problems.getSize(); ii++){ + delete allplaces.get(ii); + } Vector ranking; for (uint i = 0; i < tunerV->getSize(); i++) { TunerRecord *tuner = tunerV->get(i); @@ -205,6 +217,20 @@ void CompTuner::tune() { tunerV->removeAt(j); } } + uint tSize = tunerV->getSize(); + for (uint i = 0; i < tSize; i++) { + SearchTuner *tmpTuner = mutateTuner(tunerV->get(i)->getTuner(), b); + while(subTunerIndex(tmpTuner) != -1){ + model_print("******** New Tuner already explored...\n"); + delete tmpTuner; + tmpTuner = mutateTuner(tunerV->get(i)->getTuner(), b); + } + TunerRecord *tmp = new TunerRecord(tmpTuner); + tmp->setTunerNumber(allTuners.getSize()); + model_print("Mutated tuner %u to generate tuner %u\n", tunerV->get(i)->getTunerNumber(), tmp->getTunerNumber()); + allTuners.push(tmp); + tunerV->push(tmp); + } } printData(); } diff --git a/src/Tuner/randomtuner.cc b/src/Tuner/randomtuner.cc index 2b0701c..6fefc46 100644 --- a/src/Tuner/randomtuner.cc +++ b/src/Tuner/randomtuner.cc @@ -34,7 +34,7 @@ void RandomTuner::tune() { tuner->setTime(problem, metric); else tuner->setTime(problem, -2); - if(tunerExists(tuner->getTuner())){ + if(tunerExists(tuner)){ //Solving the problem and noticing the tuner //already exists isNew = false; @@ -50,7 +50,7 @@ void RandomTuner::tune() { uint tSize = tuners.getSize(); for (uint i = 0; i < tSize; i++) { SearchTuner *tmpTuner = mutateTuner(tuners.get(i)->getTuner(), budget); - while(subTunerExist(tmpTuner)){ + while(subTunerIndex(tmpTuner) != -1){ tmpTuner->randomMutate(); } TunerRecord *tmp = new TunerRecord(tmpTuner); diff --git a/src/Tuner/satuner.cc b/src/Tuner/satuner.cc new file mode 100644 index 0000000..61c9c35 --- /dev/null +++ b/src/Tuner/satuner.cc @@ -0,0 +1,185 @@ +#include "satuner.h" +#include +#include +#include "searchtuner.h" +#include +#include +#include "solver_interface.h" +#include + +SATuner::SATuner(uint _budget, uint _timeout) : + BasicTuner(_budget, _timeout) +{ +} + +SATuner::~SATuner(){ + +} + +void SATuner::rankTunerForProblem(Vector *places, TunerRecord *tuner, Problem *problem, long long metric){ + uint k = 0; + for (; k < places->getSize(); k++) { + if (metric < places->get(k)->getTime(problem)) + break; + } + model_print("Problem<%s>:place[%u]=Tuner<%p,%d>\n", problem->getProblem(), k, tuner, tuner->getTunerNumber()); + places->insertAt(k, tuner); +} + +void SATuner::removeTunerIndex(Vector *tunerV, int index, Vector *> &allplaces){ + TunerRecord *tuner = tunerV->get(index); + model_print("Removing Tuner %d\n", tuner->getTunerNumber()); + tunerV->set(index, NULL); + for(uint i=0; i < allplaces.getSize(); i++){ + Vector *places = allplaces.get(i); + for(uint j=0; j < places->getSize(); j++){ + if(tuner == places->get(j)){ + places->removeAt(j); + break; + } + } + } + +} + +void SATuner::removeNullsFromTunerVector( Vector *tunerV){ + for (int i= tunerV->getSize() -1; i >= 0; i--){ + if(tunerV->get(i) == NULL){ + tunerV->removeAt(i); + } + } + model_print("TunerV size after removing nulls = %u\n", tunerV->getSize()); +} + +void SATuner::initialize(Vector *tunerV, Vector *> &allplaces){ + for(uint ii=0; ii< problems.getSize(); ii++){ + allplaces.push(new Vector()); + } + for (uint j = 0; j< tunerV->getSize(); j++){ + TunerRecord *tuner = tunerV->get(j); + for (uint i=0; i < problems.getSize(); i++){ + Problem *problem = problems.get(i); + long long metric = evaluate(problem, tuner); + ASSERT(tuner->getTime(problem) == -1); + tuner->addProblem(problem); + if(metric != -1){ + tuner->setTime(problem , metric); + }else{ + tuner->setTime(problem , -2); + } + if(metric >=0){ + Vector *places = allplaces.get(i); + rankTunerForProblem(places, tuner, problem, metric); + } + } + } + +} + +void SATuner::tune() { + Vector *tunerV = new Vector(&tuners); + Vector *> allplaces; + uint tunerNumber = tuners.getSize(); + //Initialization + initialize(tunerV, allplaces); + //Starting the body of algorithm + for (uint t = budget; t >0; t--) { + model_print("Current Temperature = %u\n", t); + Hashtable scores; + for (uint i = 0; i < tunerNumber; i++) { + SearchTuner *tmpTuner = mutateTuner(tunerV->get(i)->getTuner(), budget-t); + int tunerIndex = subTunerIndex(tmpTuner); + TunerRecord *tmp = NULL; + if(tunerIndex == -1){ + tmp = new TunerRecord(tmpTuner); + tmp->setTunerNumber(allTuners.getSize()); + model_print("Mutated tuner %u to generate tuner %u\n", tunerV->get(i)->getTunerNumber(), tmp->getTunerNumber()); + allTuners.push(tmp); + }else{ + //Previous tuners might get explored with new combination of tuners. + tmp = explored.get(tunerIndex); + model_print("Using exploread tuner <%u>\n", tmp->getTunerNumber()); + } + tunerV->push(tmp); + } + ASSERT(tunerNumber * 2 == tunerV->getSize()); + for (uint j = tunerNumber; j < tunerV->getSize(); j++) { + TunerRecord *tuner = tunerV->get(j); + for (uint i = 0; i < problems.getSize(); i++) { + Problem *problem = problems.get(i); + long long metric = tuner->getTime(problem); + if (metric == -1) { + metric = evaluate(problem, tuner); + if (tuner->getTime(problem) == -1) { + tuner->addProblem(problem); + } + model_print("%u.Problem<%s>\tTuner<%p, %d>\tMetric<%lld>\n", i, problem->getProblem(),tuner, tuner->getTunerNumber(), metric); + model_print("*****************************\n"); + if (metric != -1) + tuner->setTime(problem, metric); + else + tuner->setTime(problem, -2); + + } + if (metric >= 0) { + ASSERT(i < allplaces.getSize()); + Vector *places = allplaces.get(i); + model_print("Problem<%s>:place[size=%u]=Tuner<%p,%d>\n", problem->getProblem(), places->getSize(), tuner, tuner->getTunerNumber()); + rankTunerForProblem(places, tuner, problem, metric); + } + } + } + for(uint ii=0; ii < problems.getSize(); ii++){ + Problem *problem = problems.get(ii); + ASSERT(ii < allplaces.getSize()); + Vector *places = allplaces.get(ii); + int points = pow(tunerNumber*1.0, 2*tunerNumber - 1); + for (uint k = 0; k < places->getSize() && points; k++) { + TunerRecord *tuner = places->get(k); + int currScore = 0; + if (scores.contains(tuner)) + currScore = scores.get(tuner); + currScore += points; + model_print("Problem<%s>\tTuner<%p,%d>\tmetric<%d>\n", problem->getProblem(), tuner, tuner->getTunerNumber(), currScore); + model_print("**************************\n"); + scores.put(tuner, currScore); + points = points / tunerNumber; + } + } + + for(uint i= 0; i < tunerNumber; i++){ + ASSERT(i < tunerV->getSize()); + TunerRecord *tuner1 = tunerV->get(i); + TunerRecord *tuner2 = tunerV->get(tunerNumber + i); + ASSERT( tunerNumber + i < tunerV->getSize()); + model_print("Tuner1 = %d \tTuner2 = %d\n", tuner1->getTunerNumber(), tuner2->getTunerNumber()); + ASSERT(scores.contains(tuner1)); + ASSERT(scores.contains(tuner2)); + int score1 = scores.get(tuner1); + int score2 = scores.get(tuner2); + if( score2 > score1 ){ + removeTunerIndex(tunerV, i, allplaces); + } else if( score2 < score1){ + model_print("score1=%d\tscore2=%d\tt=%u\texp=%f\n", score1, score2, t, exp((score1-score2)*1.0/t)); + double prob = 1/(exp((score1-score2)*1.0/t) ); + double random = ((double) rand() / (RAND_MAX)); + model_print("prob=%f\trandom=%f\n", prob, random); + if(prob > random){ + removeTunerIndex(tunerV, i, allplaces); + }else{ + removeTunerIndex(tunerV, tunerNumber + i, allplaces); + } + } else{ + double random = ((double) rand() / (RAND_MAX)); + int index = random > 0.5? i : tunerNumber + i; + removeTunerIndex(tunerV, index, allplaces); + } + } + removeNullsFromTunerVector(tunerV); + + } + for(uint ii=0; ii< allplaces.getSize(); ii++){ + delete allplaces.get(ii); + } + printData(); +} diff --git a/src/Tuner/satuner.h b/src/Tuner/satuner.h new file mode 100644 index 0000000..fd05423 --- /dev/null +++ b/src/Tuner/satuner.h @@ -0,0 +1,25 @@ +#ifndef SATUNER_H +#define SATUNER_H +#include "classlist.h" +#include "structs.h" +#include "basictuner.h" + +/** +*This tuner has the simulated annealing in its core +* +*/ +class SATuner : public BasicTuner { +public: + SATuner(uint budget, uint timeout); + virtual ~SATuner(); + void tune(); +protected: + void insertInPlace(Vector *places, TunerRecord *tuner, Problem *problem, long long metric); + void initialize(Vector *tunerV, Vector *> &allplaces); + void rankTunerForProblem(Vector *places, TunerRecord *tuner, Problem *problem, long long metric); + void removeTunerIndex(Vector *tunerV, int index, Vector *> &allplaces); + void removeNullsFromTunerVector( Vector *tunerV); +}; + + +#endif