src/Tuner/multituner.cc

   1 #include "multituner.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
   9 MultiTuner::MultiTuner(uint _budget, uint _rounds, uint _timeout) :
  10         BasicTuner(_budget, _timeout),
  11         rounds(_rounds)
  12 {
  13 }
  14
  15 void MultiTuner::findBestThreeTuners() {
  16         if (allTuners.getSize() < 3) {
  17                 printData();
  18                 return;
  19         }
  20         TunerRecord *bestTuners[3];
  21         double score = DBL_MAX;
  22         for (uint i = 0; i < allTuners.getSize() - 2; i++) {
  23                 for (uint j = i + 1; j < allTuners.getSize() - 1; j++) {
  24                         for (uint k = j + 1; k < allTuners.getSize(); k++) {
  25                                 TunerRecord *tuner1 = allTuners.get(i);
  26                                 TunerRecord *tuner2 = allTuners.get(j);
  27                                 TunerRecord *tuner3 = allTuners.get(k);
  28                                 double mintimes[problems.getSize()];
  29                                 for (uint l = 0; l < problems.getSize(); l++) {
  30                                         Problem *problem = problems.get(l);
  31                                         mintimes[l] = pow(min(tuner1->getTime(problem), tuner2->getTime(problem), tuner3->getTime(problem)), (double)1 / problems.getSize());
  32                                 }
  33                                 double result = 1;
  34                                 for (uint l = 0; l < problems.getSize(); l++) {
  35                                         result *= mintimes[l];
  36                                 }
  37                                 if (result < score) {
  38                                         score = result;
  39                                         bestTuners[0] = tuner1;
  40                                         bestTuners[1] = tuner2;
  41                                         bestTuners[2] = tuner3;
  42                                 }
  43                         }
  44                 }
  45         }
  46         model_print("Best 3 tuners:\n");
  47         for (uint i = 0; i < 3; i++) {
  48                 TunerRecord *tuner = bestTuners[i];
  49                 SearchTuner *stun = tuner->getTuner();
  50                 char buffer[512];
  51                 snprintf(buffer, sizeof(buffer), "best%u.tuner", i);
  52                 stun->serialize(buffer);
  53                 model_print("Tuner %u\n", tuner->getTunerNumber());
  54                 stun->print();
  55                 tuner->printProblemsInfo();
  56                 model_print("----------------------------------\n\n\n");
  57         }
  58 }
  59
  60 void MultiTuner::readData(uint numRuns) {
  61         for (uint i = 0; i < numRuns; i++) {
  62                 ifstream myfile;
  63                 char buffer[512];
  64                 uint tunernumber;
  65                 snprintf(buffer, sizeof(buffer), "tunernum%u", i);
  66                 myfile.open (buffer, ios::in);
  67                 myfile >> tunernumber;
  68                 myfile.close();
  69                 if (allTuners.getSize() <= tunernumber)
  70                         allTuners.setSize(tunernumber + 1);
  71                 if (allTuners.get(tunernumber) == NULL) {
  72                         snprintf(buffer, sizeof(buffer), "tuner%u", i);
  73                         allTuners.set(tunernumber, new TunerRecord(new SearchTuner(buffer), tunernumber));
  74                 }
  75                 //Add any new used records
  76                 snprintf(buffer, sizeof(buffer), "tuner%uused", i);
  77                 TunerRecord *tuner = allTuners.get(tunernumber);
  78                 tuner->getTuner()->addUsed(buffer);
  79
  80                 char problemname[512];
  81                 uint problemnumber;
  82                 snprintf(buffer, sizeof(buffer), "problem%u", i);
  83                 myfile.open(buffer, ios::in);
  84                 myfile.getline(problemname, sizeof(problemname));
  85                 myfile >> problemnumber;
  86                 myfile.close();
  87                 if (problems.getSize() <= problemnumber)
  88                         problems.setSize(problemnumber + 1);
  89                 if (problems.get(problemnumber) == NULL)
  90                         problems.set(problemnumber, new Problem(problemname));
  91                 Problem *problem = problems.get(problemnumber);
  92                 long long metric = -1;
  93                 int sat = IS_INDETER;
  94                 //Read data in from results file
  95                 snprintf(buffer, sizeof(buffer), "result%u", i);
  96
  97                 myfile.open (buffer, ios::in);
  98
  99
 100                 if (myfile.is_open()) {
 101                         myfile >> metric;
 102                         myfile >> sat;
 103                         myfile.close();
 104                 }
 105                 if (problem->getResult() == TUNERUNSETVALUE && sat != IS_INDETER) {
 106                         problem->setResult(sat);
 107                 } else if (problem->getResult() != sat && sat != IS_INDETER) {
 108                         model_print("******** Result has changed ********\n");
 109                 }
 110
 111                 if (metric != -1) {
 112                         if (tuner->getTime(problem) == -1)
 113                                 tuner->addProblem(problem);
 114                         tuner->setTime(problem, metric);
 115                 }
 116
 117         }
 118
 119 }
 120
 121 void MultiTuner::tune() {
 122         Vector<TunerRecord *> *tunerV = new Vector<TunerRecord *>(&tuners);
 123         for (uint b = 0; b < budget; b++) {
 124                 model_print("Round %u of %u\n", b, budget);
 125                 uint tSize = tunerV->getSize();
 126                 for (uint i = 0; i < tSize; i++) {
 127                         SearchTuner *tmpTuner = mutateTuner(tunerV->get(i)->getTuner(), b);
 128                         TunerRecord *tmp = new TunerRecord(tmpTuner);
 129                         tmp->setTunerNumber(allTuners.getSize());
 130                         model_print("Mutated tuner %u to generate tuner %u\n", tunerV->get(i)->getTunerNumber(), tmp->getTunerNumber());
 131                         allTuners.push(tmp);
 132                         tunerV->push(tmp);
 133                 }
 134
 135                 Hashtable<TunerRecord *, int, uint64_t> scores;
 136                 for (uint i = 0; i < problems.getSize(); i++) {
 137                         Problem *problem = problems.get(i);
 138                         Vector<TunerRecord *> places;
 139                         for (uint j = 0; j < tunerV->getSize(); j++) {
 140                                 TunerRecord *tuner = tunerV->get(j);
 141                                 long long metric = tuner->getTime(problem);
 142                                 if (metric == -1) {
 143                                         metric = evaluate(problem, tuner);
 144                                         if (tuner->getTime(problem) == -1) {
 145                                                 tuner->addProblem(problem);
 146                                         }
 147                                         model_print("%u.Problem<%s>\tTuner<%p, %d>\tMetric<%lld>\n", i, problem->getProblem(),tuner, tuner->getTunerNumber(), metric);
 148                                         model_print("*****************************\n");
 149                                         if (metric != -1)
 150                                                 tuner->setTime(problem, metric);
 151                                         else
 152                                                 tuner->setTime(problem, -2);
 153                                 }
 154                                 if (metric >= 0) {
 155                                         uint k = 0;
 156                                         for (; k < places.getSize(); k++) {
 157                                                 if (metric < places.get(k)->getTime(problem))
 158                                                         break;
 159                                         }
 160                                         model_print("place[%u]=Tuner<%p,%d>\n", k, tuner, tuner->getTunerNumber());
 161                                         places.insertAt(k, tuner);
 162                                 }
 163                         }
 164                         int points = 9;
 165                         for (uint k = 0; k < places.getSize() && points; k++) {
 166                                 TunerRecord *tuner = places.get(k);
 167                                 int currScore = 0;
 168                                 if (scores.contains(tuner))
 169                                         currScore = scores.get(tuner);
 170                                 currScore += points;
 171                                 model_print("Problem<%s>\tTuner<%p,%d>\tmetric<%d>\n", problem->getProblem(), tuner, tuner->getTunerNumber(),  currScore);
 172                                 model_print("**************************\n");
 173                                 scores.put(tuner, currScore);
 174                                 points = points / 3;
 175                         }
 176                 }
 177                 Vector<TunerRecord *> ranking;
 178                 for (uint i = 0; i < tunerV->getSize(); i++) {
 179                         TunerRecord *tuner = tunerV->get(i);
 180                         int score = 0;
 181                         if (scores.contains(tuner))
 182                                 score = scores.get(tuner);
 183                         uint j = 0;
 184                         for (; j < ranking.getSize(); j++) {
 185                                 TunerRecord *t = ranking.get(j);
 186                                 int tscore = 0;
 187                                 if (scores.contains(t))
 188                                         tscore = scores.get(t);
 189                                 if (score > tscore)
 190                                         break;
 191                         }
 192                         model_print("ranking[%u]=tuner<%p,%u>(Score=%d)\n", j, tuner, tuner->getTunerNumber(), score);
 193                         model_print("************************\n");
 194                         ranking.insertAt(j, tuner);
 195                 }
 196                 model_print("tunerSize=%u\trankingSize=%u\ttunerVSize=%u\n", tuners.getSize(), ranking.getSize(), tunerV->getSize());
 197                 for (uint i = tuners.getSize(); i < ranking.getSize(); i++) {
 198                         TunerRecord *tuner = ranking.get(i);
 199                         model_print("Removing tuner %u\n", tuner->getTunerNumber());
 200                         for (uint j = 0; j < tunerV->getSize(); j++) {
 201                                 if (tunerV->get(j) == tuner)
 202                                         tunerV->removeAt(j);
 203                         }
 204                 }
 205         }
 206         printData();
 207 }
 208
 209 void MultiTuner::mapProblemsToTuners(Vector<TunerRecord *> *tunerV) {
 210         for (uint i = 0; i < problems.getSize(); i++) {
 211                 Problem *problem = problems.get(i);
 212                 TunerRecord *bestTuner = NULL;
 213                 long long bestscore = 0;
 214                 for (uint j = 0; j < tunerV->getSize(); j++) {
 215                         TunerRecord *tuner = tunerV->get(j);
 216                         long long metric = tuner->getTime(problem);
 217                         if (metric == -1) {
 218                                 metric = evaluate(problem, tuner);
 219                                 if (metric != -1)
 220                                         tuner->setTime(problem, metric);
 221                                 else
 222                                         tuner->setTime(problem, -2);
 223                         }
 224                         if ((bestTuner == NULL && metric >= 0) ||
 225                                         (metric < bestscore && metric >= 0)) {
 226                                 bestTuner = tuner;
 227                                 bestscore = metric;
 228                         }
 229                 }
 230                 if (bestTuner != NULL)
 231                         bestTuner->addProblem(problem);
 232         }
 233 }
 234
 235 void clearVector(Vector<TunerRecord *> *tunerV) {
 236         for (uint j = 0; j < tunerV->getSize(); j++) {
 237                 TunerRecord *tuner = tunerV->get(j);
 238                 tuner->problems.clear();
 239         }
 240 }
 241
 242 void MultiTuner::tuneK() {
 243         Vector<TunerRecord *> *tunerV = new Vector<TunerRecord *>(&tuners);
 244         for (uint i = 0; i < rounds; i++) {
 245                 clearVector(tunerV);
 246                 mapProblemsToTuners(tunerV);
 247                 improveTuners(tunerV);
 248         }
 249         model_print("Best tuners\n");
 250         for (uint j = 0; j < tunerV->getSize(); j++) {
 251                 TunerRecord *tuner = tunerV->get(j);
 252                 char buffer[256];
 253                 sprintf(buffer, "tuner%u.conf", j);
 254                 tuner->getTuner()->serialize(buffer);
 255                 tuner->getTuner()->print();
 256         }
 257         delete tunerV;
 258 }
 259
 260 void MultiTuner::improveTuners(Vector<TunerRecord *> *tunerV) {
 261         for (uint j = 0; j < tunerV->getSize(); j++) {
 262                 TunerRecord *tuner = tunerV->get(j);
 263                 TunerRecord *newtuner = tune(tuner);
 264                 tunerV->set(j, newtuner);
 265         }
 266 }
 267
 268 double MultiTuner::evaluateAll(TunerRecord *tuner) {
 269         double product = 1;
 270         for (uint i = 0; i < tuner->problemsSize(); i++) {
 271                 Problem *problem = tuner->getProblem(i);
 272                 long long metric = tuner->getTime(problem);
 273                 if (metric == -1) {
 274                         metric = evaluate(problem, tuner);
 275                         if (metric != -1)
 276                                 tuner->setTime(problem, metric);
 277                         else
 278                                 tuner->setTime(problem, -2);
 279                 }
 280
 281                 double score = metric;
 282                 if (metric < 0)
 283                         score = timeout;
 284                 product *= score;
 285         }
 286         return pow(product, 1 / ((double)tuner->problemsSize()));
 287 }
 288
 289 TunerRecord *MultiTuner::tune(TunerRecord *tuner) {
 290         TunerRecord *bestTuner = NULL;
 291         double bestScore = DBL_MAX;
 292
 293         TunerRecord *oldTuner = tuner;
 294         double base_temperature = evaluateAll(oldTuner);
 295         double oldScore = base_temperature;
 296
 297         for (uint i = 0; i < budget; i++) {
 298                 SearchTuner *tmpTuner = mutateTuner(oldTuner->getTuner(), i);
 299                 TunerRecord *newTuner = oldTuner->changeTuner(tmpTuner);
 300                 newTuner->setTunerNumber( allTuners.getSize() );
 301                 allTuners.push(newTuner);
 302                 double newScore = evaluateAll(newTuner);
 303                 newTuner->getTuner()->printUsed();
 304                 model_print("Received score %f\n", newScore);
 305                 double scoreDiff = newScore - oldScore; //smaller is better
 306                 if (newScore < bestScore) {
 307                         bestScore = newScore;
 308                         bestTuner = newTuner;
 309                 }
 310
 311                 double acceptanceP;
 312                 if (scoreDiff < 0) {
 313                         acceptanceP = 1;
 314                 } else {
 315                         double currTemp = base_temperature * (((double)budget - i) / budget);
 316                         acceptanceP = exp(-scoreDiff / currTemp);
 317                 }
 318                 double ran = ((double)random()) / RAND_MAX;
 319                 if (ran <= acceptanceP) {
 320                         oldScore = newScore;
 321                         oldTuner = newTuner;
 322                 }
 323         }
 324
 325         return bestTuner;
 326 }
 327