src/Tuner/satuner.cc

   1 #include "satuner.h"
   2 #include <float.h>
   3 #include <math.h>
   4 #include "searchtuner.h"
   5 #include <iostream>
   6 #include <fstream>
   7 #include "solver_interface.h"
   8 #include <stdlib.h>
   9
  10 SATuner::SATuner(uint _budget, uint _timeout) :
  11         BasicTuner(_budget, _timeout)
  12 {
  13 }
  14
  15 SATuner::~SATuner() {
  16
  17 }
  18
  19 void SATuner::rankTunerForProblem(Vector<TunerRecord *> *places, TunerRecord *tuner, Problem *problem, long long metric) {
  20         uint k = 0;
  21         for (; k < places->getSize(); k++) {
  22                 if (metric < places->get(k)->getTime(problem))
  23                         break;
  24         }
  25         model_print("Problem<%s>:place[%u]=Tuner<%p,%d>\n", problem->getProblem(), k, tuner, tuner->getTunerNumber());
  26         places->insertAt(k, tuner);
  27 }
  28
  29 void SATuner::removeTunerIndex(Vector<TunerRecord *> *tunerV, int index,  Vector<Vector<TunerRecord *> *> &allplaces) {
  30         TunerRecord *tuner = tunerV->get(index);
  31         model_print("Removing Tuner %d\n", tuner->getTunerNumber());
  32         tunerV->set(index, NULL);
  33         for (uint i = 0; i < allplaces.getSize(); i++) {
  34                 Vector<TunerRecord *> *places = allplaces.get(i);
  35                 for (uint j = 0; j < places->getSize(); j++) {
  36                         if (tuner == places->get(j)) {
  37                                 places->removeAt(j);
  38                                 break;
  39                         }
  40                 }
  41         }
  42
  43 }
  44
  45 void SATuner::removeNullsFromTunerVector( Vector<TunerRecord *> *tunerV) {
  46         for (int i = tunerV->getSize() - 1; i >= 0; i--) {
  47                 if (tunerV->get(i) == NULL) {
  48                         tunerV->removeAt(i);
  49                 }
  50         }
  51         model_print("TunerV size after removing nulls = %u\n", tunerV->getSize());
  52 }
  53
  54 void SATuner::initialize(Vector<TunerRecord *> *tunerV, Vector<Vector<TunerRecord *> *> &allplaces) {
  55         for (uint ii = 0; ii < problems.getSize(); ii++) {
  56                 allplaces.push(new Vector<TunerRecord *>());
  57         }
  58         for (uint j = 0; j < tunerV->getSize(); j++) {
  59                 TunerRecord *tuner = tunerV->get(j);
  60                 for (uint i = 0; i < problems.getSize(); i++) {
  61                         Problem *problem = problems.get(i);
  62                         long long metric = evaluate(problem, tuner);
  63                         ASSERT(tuner->getTime(problem) == -1);
  64                         tuner->addProblem(problem);
  65                         if (metric != -1) {
  66                                 tuner->setTime(problem, metric);
  67                         } else {
  68                                 tuner->setTime(problem, -2);
  69                         }
  70                         if (metric >= 0) {
  71                                 Vector<TunerRecord *> *places = allplaces.get(i);
  72                                 rankTunerForProblem(places, tuner, problem, metric);
  73                         }
  74                 }
  75         }
  76
  77 }
  78
  79 void SATuner::tune() {
  80         Vector<TunerRecord *> *tunerV = new Vector<TunerRecord *>(&tuners);
  81         Vector<Vector<TunerRecord *> *> allplaces;
  82         uint tunerNumber = tuners.getSize();
  83         //Initialization
  84         initialize(tunerV, allplaces);
  85         //Starting the body of algorithm
  86         for (uint t = budget; t > 0; t--) {
  87                 model_print("Current Temperature = %u\n", t);
  88                 Hashtable<TunerRecord *, int, uint64_t> scores;
  89                 for (uint i = 0; i < tunerNumber; i++) {
  90                         SearchTuner *tmpTuner = mutateTuner(tunerV->get(i)->getTuner(), budget - t);
  91                         int tunerIndex = subTunerIndex(tmpTuner);
  92                         TunerRecord *tmp = NULL;
  93                         if (tunerIndex == -1) {
  94                                 tmp = new TunerRecord(tmpTuner);
  95                                 tmp->setTunerNumber(allTuners.getSize());
  96                                 model_print("Mutated tuner %u to generate tuner %u\n", tunerV->get(i)->getTunerNumber(), tmp->getTunerNumber());
  97                                 allTuners.push(tmp);
  98                         } else {
  99                                 //Previous tuners might get explored with new combination of tuners.
 100                                 tmp = explored.get(tunerIndex);
 101                                 model_print("Using exploread tuner <%u>\n", tmp->getTunerNumber());
 102                         }
 103                         tunerV->push(tmp);
 104                 }
 105                 ASSERT(tunerNumber * 2 == tunerV->getSize());
 106                 for (uint j = tunerNumber; j < tunerV->getSize(); j++) {
 107                         TunerRecord *tuner = tunerV->get(j);
 108                         for (uint i = 0; i < problems.getSize(); i++) {
 109                                 Problem *problem = problems.get(i);
 110                                 long long metric = tuner->getTime(problem);
 111                                 if (metric == -1) {
 112                                         metric = evaluate(problem, tuner);
 113                                         if (tuner->getTime(problem) == -1) {
 114                                                 tuner->addProblem(problem);
 115                                         }
 116                                         model_print("%u.Problem<%s>\tTuner<%p, %d>\tMetric<%lld>\n", i, problem->getProblem(),tuner, tuner->getTunerNumber(), metric);
 117                                         model_print("*****************************\n");
 118                                         if (metric != -1)
 119                                                 tuner->setTime(problem, metric);
 120                                         else
 121                                                 tuner->setTime(problem, -2);
 122
 123                                 }
 124                                 if (metric >= 0) {
 125                                         ASSERT(i < allplaces.getSize());
 126                                         Vector<TunerRecord *> *places = allplaces.get(i);
 127                                         model_print("Problem<%s>:place[size=%u]=Tuner<%p,%d>\n", problem->getProblem(), places->getSize(), tuner, tuner->getTunerNumber());
 128                                         rankTunerForProblem(places, tuner, problem, metric);
 129                                 }
 130                         }
 131                 }
 132                 for (uint ii = 0; ii < problems.getSize(); ii++) {
 133                         Problem *problem = problems.get(ii);
 134                         ASSERT(ii < allplaces.getSize());
 135                         Vector<TunerRecord *> *places = allplaces.get(ii);
 136                         int points = pow(tunerNumber * 1.0, 2 * tunerNumber - 1);
 137                         for (uint k = 0; k < places->getSize() && points; k++) {
 138                                 TunerRecord *tuner = places->get(k);
 139                                 int currScore = 0;
 140                                 if (scores.contains(tuner))
 141                                         currScore = scores.get(tuner);
 142                                 currScore += points;
 143                                 model_print("Problem<%s>\tTuner<%p,%d>\tmetric<%d>\n", problem->getProblem(), tuner, tuner->getTunerNumber(),  currScore);
 144                                 model_print("**************************\n");
 145                                 scores.put(tuner, currScore);
 146                                 points = points / tunerNumber;
 147                         }
 148                 }
 149
 150                 for (uint i = 0; i < tunerNumber; i++) {
 151                         ASSERT(i < tunerV->getSize());
 152                         TunerRecord *tuner1 = tunerV->get(i);
 153                         TunerRecord *tuner2 = tunerV->get(tunerNumber + i);
 154                         ASSERT( tunerNumber + i < tunerV->getSize());
 155                         model_print("Tuner1 = %d \tTuner2 = %d\n", tuner1->getTunerNumber(), tuner2->getTunerNumber());
 156
 157                         int score1, score2;
 158                         if (!scores.contains(tuner1)) {
 159                                 score1 = 0;
 160                         } else {
 161                                 score1 = scores.get(tuner1);
 162                         }
 163                         if (!scores.contains(tuner2)) {
 164                                 score2 = 0;
 165                         } else {
 166                                 score2 = scores.get(tuner2);
 167                         }
 168
 169                         if ( score2 > score1 ) {
 170                                 removeTunerIndex(tunerV, i, allplaces);
 171                         } else if ( score2 < score1) {
 172                                 model_print("score1=%d\tscore2=%d\tt=%u\texp=%f\n", score1, score2, t, exp((score1 - score2) * 1.0 / t));
 173                                 double prob = 1 / (exp((score1 - score2) * 1.0 / t) );
 174                                 double random = ((double) rand() / (RAND_MAX));
 175                                 model_print("prob=%f\trandom=%f\n", prob, random);
 176                                 if (prob > random) {
 177                                         removeTunerIndex(tunerV, i, allplaces);
 178                                 } else {
 179                                         removeTunerIndex(tunerV, tunerNumber + i, allplaces);
 180                                 }
 181                         } else {
 182                                 double random = ((double) rand() / (RAND_MAX));
 183                                 int index = random > 0.5 ? i : tunerNumber + i;
 184                                 removeTunerIndex(tunerV, index, allplaces);
 185                         }
 186                 }
 187                 removeNullsFromTunerVector(tunerV);
 188
 189         }
 190         for (uint ii = 0; ii < allplaces.getSize(); ii++) {
 191                 delete allplaces.get(ii);
 192         }
 193         printData();
 194 }