src/Tuner/multituner.cc

   1 #include "multituner.h"
   2 #include "csolver.h"
   3 #include "searchtuner.h"
   4 #include <math.h>
   5 #include <stdlib.h>
   6 #include <float.h>
   7 #include <string.h>
   8 #include <iostream>
   9 #include <fstream>
  10 #include <limits>
  11
  12 #define UNSETVALUE -1
  13
  14 Problem::Problem(const char *_problem, uint _timeout) :
  15         problemnumber(-1),
  16         result(UNSETVALUE) ,
  17         besttime(std::numeric_limits<double>::infinity()),
  18         timeout(_timeout)
  19 {
  20         uint len = strlen(_problem);
  21         problem = (char *) ourmalloc(len + 1);
  22         memcpy(problem, _problem, len + 1);
  23 }
  24
  25 Problem::~Problem() {
  26         ourfree(problem);
  27 }
  28
  29 void TunerRecord::setTime(Problem *problem, long long time) {
  30         timetaken.put(problem, time);
  31 }
  32
  33 long long TunerRecord::getTime(Problem *problem) {
  34         if (timetaken.contains(problem))
  35                 return timetaken.get(problem);
  36         else return -1;
  37 }
  38
  39 TunerRecord *TunerRecord::changeTuner(SearchTuner *_newtuner) {
  40         TunerRecord *tr = new TunerRecord(_newtuner);
  41         for (uint i = 0; i < problems.getSize(); i++) {
  42                 tr->problems.push(problems.get(i));
  43         }
  44         return tr;
  45 }
  46
  47 MultiTuner::MultiTuner(uint _budget, uint _rounds, uint _timeout) :
  48         budget(_budget), rounds(_rounds), timeout(_timeout), execnum(0) {
  49 }
  50
  51 MultiTuner::~MultiTuner() {
  52         for (uint i = 0; i < problems.getSize(); i++)
  53                 ourfree(problems.get(i));
  54         for (uint i = 0; i < allTuners.getSize(); i++)
  55                 delete allTuners.get(i);
  56 }
  57
  58 void MultiTuner::addProblem(const char *filename) {
  59         Problem *p = new Problem(filename, timeout);
  60         p->problemnumber = problems.getSize();
  61         problems.push(p);
  62 }
  63
  64 void MultiTuner::printData() {
  65         model_print("*********** DATA DUMP ***********\n");
  66         for (uint i = 0; i < allTuners.getSize(); i++) {
  67                 TunerRecord *tuner = allTuners.get(i);
  68                 SearchTuner *stun = tuner->getTuner();
  69                 model_print("Tuner %u\n", i);
  70                 stun->print();
  71                 model_print("----------------------------------\n\n\n");
  72                 for (uint j = 0; j < tuner->problems.getSize(); j++) {
  73                         Problem *problem = tuner->problems.get(j);
  74                         model_print("Problem %s\n", problem->getProblem());
  75                         model_print("Time = %lld\n", tuner->getTime(problem));
  76                 }
  77         }
  78 }
  79
  80 void MultiTuner::addTuner(SearchTuner *tuner) {
  81         TunerRecord *t = new TunerRecord(tuner);
  82         tuners.push(t);
  83         t->tunernumber = allTuners.getSize();
  84         allTuners.push(t);
  85 }
  86
  87
  88 void MultiTuner::readData(uint numRuns) {
  89         for (uint i = 0; i < numRuns; i++) {
  90                 ifstream myfile;
  91                 char buffer[512];
  92                 uint tunernumber;
  93                 snprintf(buffer, sizeof(buffer), "tunernum%u", i);
  94                 myfile.open (buffer, ios::in);
  95                 myfile >> tunernumber;
  96                 myfile.close();
  97                 if (allTuners.getSize() <= tunernumber)
  98                         allTuners.setSize(tunernumber + 1);
  99                 if (allTuners.get(tunernumber) == NULL) {
 100                         snprintf(buffer, sizeof(buffer), "tuner%u", i);
 101                         allTuners.set(tunernumber, new TunerRecord(new SearchTuner(buffer)));
 102                 }
 103                 //Add any new used records
 104                 snprintf(buffer, sizeof(buffer), "tuner%uused", i);
 105                 TunerRecord *tuner = allTuners.get(tunernumber);
 106                 tuner->getTuner()->addUsed(buffer);
 107
 108                 char problemname[512];
 109                 uint problemnumber;
 110                 snprintf(buffer, sizeof(buffer), "problem%u", i);
 111                 myfile.open(buffer, ios::in);
 112                 myfile.getline(problemname, sizeof(problemname));
 113                 myfile >> problemnumber;
 114                 myfile.close();
 115                 if (problems.getSize() <= problemnumber)
 116                         problems.setSize(problemnumber + 1);
 117                 if (problems.get(problemnumber) == NULL)
 118                         problems.set(problemnumber, new Problem(problemname, timeout));
 119                 Problem *problem = problems.get(problemnumber);
 120                 long long metric = -1;
 121                 int sat = IS_INDETER;
 122                 //Read data in from results file
 123                 snprintf(buffer, sizeof(buffer), "result%u", i);
 124
 125                 myfile.open (buffer, ios::in);
 126
 127
 128                 if (myfile.is_open()) {
 129                         myfile >> metric;
 130                         myfile >> sat;
 131                         myfile.close();
 132                 }
 133                 if (problem->result == UNSETVALUE && sat != IS_INDETER) {
 134                         problem->result = sat;
 135                 } else if (problem->result != sat && sat != IS_INDETER) {
 136                         model_print("******** Result has changed ********\n");
 137                 }
 138
 139                 if (metric != -1) {
 140                         if (tuner->getTime(problem) == -1)
 141                                 tuner->problems.push(problem);
 142                         tuner->setTime(problem, metric);
 143                 }
 144
 145         }
 146
 147 }
 148
 149 long long MultiTuner::evaluate(Problem *problem, TunerRecord *tuner) {
 150         char buffer[512];
 151         {
 152                 snprintf(buffer, sizeof(buffer), "problem%u", execnum);
 153
 154                 ofstream myfile;
 155                 myfile.open (buffer, ios::out);
 156
 157
 158                 if (myfile.is_open()) {
 159                         myfile << problem->getProblem() << endl;
 160                         myfile << problem->problemnumber << endl;
 161                         myfile.close();
 162                 }
 163         }
 164
 165         {
 166                 snprintf(buffer, sizeof(buffer), "tunernum%u", execnum);
 167
 168                 ofstream myfile;
 169                 myfile.open (buffer, ios::out);
 170
 171
 172                 if (myfile.is_open()) {
 173                         myfile << tuner->tunernumber << endl;
 174                         myfile.close();
 175                 }
 176         }
 177
 178         //Write out the tuner
 179         snprintf(buffer, sizeof(buffer), "tuner%u", execnum);
 180         tuner->getTuner()->serialize(buffer);
 181
 182         //Do run
 183         snprintf(buffer, sizeof(buffer), "./run.sh deserializerun %s %u tuner%u result%u > log%u", problem->getProblem(), problem->timeout, execnum, execnum, execnum);
 184         int status = system(buffer);
 185
 186         long long metric = -1;
 187         int sat = IS_INDETER;
 188
 189         if (status == 0) {
 190                 //Read data in from results file
 191                 snprintf(buffer, sizeof(buffer), "result%u", execnum);
 192
 193                 ifstream myfile;
 194                 myfile.open (buffer, ios::in);
 195
 196
 197                 if (myfile.is_open()) {
 198                         myfile >> metric;
 199                         myfile >> sat;
 200                         myfile.close();
 201                 }
 202                 updateTimeout(problem, metric);
 203                 snprintf(buffer, sizeof(buffer), "tuner%uused", execnum);
 204                 tuner->getTuner()->addUsed(buffer);
 205         }
 206         //Increment execution count
 207         execnum++;
 208
 209         if (problem->result == UNSETVALUE && sat != IS_INDETER) {
 210                 problem->result = sat;
 211         } else if (problem->result != sat && sat != IS_INDETER) {
 212                 model_print("******** Result has changed ********\n");
 213         }
 214         if(sat == IS_INDETER && metric != -1){ //The case when we have a timeout
 215                 metric = -1;
 216         }
 217         return metric;
 218 }
 219
 220 void MultiTuner::updateTimeout(Problem *problem, long long metric){
 221         double currentTime= metric / NANOSEC;
 222         if(currentTime < problem->besttime){
 223                 problem->besttime = currentTime;
 224         }
 225         uint adoptive;
 226         if(problem->besttime > 30){
 227                 adoptive = problem->besttime * 5;
 228         }else {
 229                 adoptive = 150;
 230         }
 231         if(adoptive < problem->timeout){
 232                 problem->timeout = adoptive;
 233         }
 234         LOG("Timeout=%u\tadoptive%u\tcurrentTime=%f\n", problem->timeout, adoptive, currentTime);
 235 }
 236
 237 void MultiTuner::tuneComp() {
 238         Vector<TunerRecord *> *tunerV = new Vector<TunerRecord *>(&tuners);
 239         for (uint b = 0; b < budget; b++) {
 240                 model_print("Round %u of %u\n", b, budget);
 241                 uint tSize = tunerV->getSize();
 242                 for (uint i = 0; i < tSize; i++) {
 243                         SearchTuner *tmpTuner = mutateTuner(tunerV->get(i)->getTuner(), b);
 244                         TunerRecord *tmp = new TunerRecord(tmpTuner);
 245                         tmp->tunernumber = allTuners.getSize();
 246                         model_print("Mutated tuner %u to generate tuner %u\n", tunerV->get(i)->tunernumber, tmp->tunernumber);
 247                         allTuners.push(tmp);
 248                         tunerV->push(tmp);
 249                 }
 250
 251                 Hashtable<TunerRecord *, int, uint64_t> scores;
 252                 for (uint i = 0; i < problems.getSize(); i++) {
 253                         Problem *problem = problems.get(i);
 254                         Vector<TunerRecord *> places;
 255                         for (uint j = 0; j < tunerV->getSize(); j++) {
 256                                 TunerRecord *tuner = tunerV->get(j);
 257                                 long long metric = tuner->getTime(problem);
 258                                 if (metric == -1) {
 259                                         metric = evaluate(problem, tuner);
 260                                         if (tuner->getTime(problem) == -1) {
 261                                                 tuner->problems.push(problem);
 262                                         }
 263                                         LOG("%u.Problem<%s>\tTuner<%p, %d>\tMetric<%lld>\n", i, problem->problem,tuner, tuner->tunernumber, metric);
 264                                         LOG("*****************************\n");
 265                                         if (metric != -1)
 266                                                 tuner->setTime(problem, metric);
 267                                 }
 268                                 if (metric != -1) {
 269                                         uint k = 0;
 270                                         for (; k < places.getSize(); k++) {
 271                                                 if (metric < places.get(k)->getTime(problem))
 272                                                         break;
 273                                         }
 274                                         LOG("place[%u]=Tuner<%p,%d>\n", k, tuner, tuner->tunernumber);
 275                                         places.insertAt(k, tuner);
 276                                 }
 277                         }
 278                         int points = 9;
 279                         for (uint k = 0; k < places.getSize() && points; k++) {
 280                                 TunerRecord *tuner = places.get(k);
 281                                 int currScore = 0;
 282                                 if (scores.contains(tuner))
 283                                         currScore = scores.get(tuner);
 284                                 currScore += points;
 285                                 LOG("Problem<%s>\tTuner<%p,%d>\tmetric<%d>\n", problem->problem, tuner, tuner->tunernumber,  currScore);
 286                                 LOG("**************************\n");
 287                                 scores.put(tuner, currScore);
 288                                 points = points / 3;
 289                         }
 290                 }
 291                 Vector<TunerRecord *> ranking;
 292                 for (uint i = 0; i < tunerV->getSize(); i++) {
 293                         TunerRecord *tuner = tunerV->get(i);
 294                         int score = 0;
 295                         if (scores.contains(tuner))
 296                                 score = scores.get(tuner);
 297                         uint j = 0;
 298                         for (; j < ranking.getSize(); j++) {
 299                                 TunerRecord *t = ranking.get(j);
 300                                 int tscore = 0;
 301                                 if (scores.contains(t))
 302                                         tscore = scores.get(t);
 303                                 if (score > tscore)
 304                                         break;
 305                         }
 306                         LOG("ranking[%u]=tuner<%p,%u>(Score=%d)\n", j, tuner, tuner->tunernumber, score);
 307                         LOG("************************\n");
 308                         ranking.insertAt(j, tuner);
 309                 }
 310                 LOG("tunerSize=%u\trankingSize=%u\ttunerVSize=%u\n", tuners.getSize(), ranking.getSize(), tunerV->getSize());
 311                 for (uint i = tuners.getSize(); i < ranking.getSize(); i++) {
 312                         TunerRecord *tuner = ranking.get(i);
 313                         LOG("Removing tuner %u\n", tuner->tunernumber);
 314                         for (uint j = 0; j < tunerV->getSize(); j++) {
 315                                 if (tunerV->get(j) == tuner)
 316                                         tunerV->removeAt(j);
 317                         }
 318                 }
 319         }
 320         printData();
 321 }
 322
 323 void MultiTuner::mapProblemsToTuners(Vector<TunerRecord *> *tunerV) {
 324         for (uint i = 0; i < problems.getSize(); i++) {
 325                 Problem *problem = problems.get(i);
 326                 TunerRecord *bestTuner = NULL;
 327                 long long bestscore = 0;
 328                 for (uint j = 0; j < tunerV->getSize(); j++) {
 329                         TunerRecord *tuner = tunerV->get(j);
 330                         long long metric = tuner->getTime(problem);
 331                         if (metric == -1) {
 332                                 metric = evaluate(problem, tuner);
 333                                 if (metric != -1)
 334                                         tuner->setTime(problem, metric);
 335                         }
 336                         if ((bestTuner == NULL && metric != -1) ||
 337                                         (metric < bestscore && metric != -1)) {
 338                                 bestTuner = tuner;
 339                                 bestscore = metric;
 340                         }
 341                 }
 342                 if (bestTuner != NULL)
 343                         bestTuner->problems.push(problem);
 344         }
 345 }
 346
 347 void clearVector(Vector<TunerRecord *> *tunerV) {
 348         for (uint j = 0; j < tunerV->getSize(); j++) {
 349                 TunerRecord *tuner = tunerV->get(j);
 350                 tuner->problems.clear();
 351         }
 352 }
 353
 354 void MultiTuner::tuneK() {
 355         Vector<TunerRecord *> *tunerV = new Vector<TunerRecord *>(&tuners);
 356         for (uint i = 0; i < rounds; i++) {
 357                 clearVector(tunerV);
 358                 mapProblemsToTuners(tunerV);
 359                 improveTuners(tunerV);
 360         }
 361         model_print("Best tuners\n");
 362         for (uint j = 0; j < tunerV->getSize(); j++) {
 363                 TunerRecord *tuner = tunerV->get(j);
 364                 char buffer[256];
 365                 sprintf(buffer, "tuner%u.conf", j);
 366                 tuner->getTuner()->serialize(buffer);
 367                 tuner->getTuner()->print();
 368         }
 369         delete tunerV;
 370 }
 371
 372 void MultiTuner::improveTuners(Vector<TunerRecord *> *tunerV) {
 373         for (uint j = 0; j < tunerV->getSize(); j++) {
 374                 TunerRecord *tuner = tunerV->get(j);
 375                 TunerRecord *newtuner = tune(tuner);
 376                 tunerV->set(j, newtuner);
 377         }
 378 }
 379
 380 double MultiTuner::evaluateAll(TunerRecord *tuner) {
 381         double product = 1;
 382         for (uint i = 0; i < tuner->problems.getSize(); i++) {
 383                 Problem *problem = tuner->problems.get(i);
 384                 long long metric = tuner->getTime(problem);
 385                 if (metric == -1) {
 386                         metric = evaluate(problem, tuner);
 387                         if (metric != -1)
 388                                 tuner->setTime(problem, metric);
 389                 }
 390
 391                 double score = metric;
 392                 product *= score;
 393         }
 394         return pow(product, 1 / ((double)tuner->problems.getSize()));
 395 }
 396
 397 SearchTuner *MultiTuner::mutateTuner(SearchTuner *oldTuner, uint k) {
 398         SearchTuner *newTuner = oldTuner->copyUsed();
 399         uint numSettings = oldTuner->getSize();
 400         uint settingsToMutate = (uint)(AUTOTUNERFACTOR * (((double)numSettings) * (budget - k)) / (budget));
 401         if (settingsToMutate < 1)
 402                 settingsToMutate = 1;
 403         model_print("Mutating %u settings\n", settingsToMutate);
 404         while (settingsToMutate-- != 0) {
 405                 newTuner->randomMutate();
 406         }
 407         return newTuner;
 408 }
 409
 410 TunerRecord *MultiTuner::tune(TunerRecord *tuner) {
 411         TunerRecord *bestTuner = NULL;
 412         double bestScore = DBL_MAX;
 413
 414         TunerRecord *oldTuner = tuner;
 415         double base_temperature = evaluateAll(oldTuner);
 416         double oldScore = base_temperature;
 417
 418         for (uint i = 0; i < budget; i++) {
 419                 SearchTuner *tmpTuner = mutateTuner(oldTuner->getTuner(), i);
 420                 TunerRecord *newTuner = oldTuner->changeTuner(tmpTuner);
 421                 newTuner->tunernumber = allTuners.getSize();
 422                 allTuners.push(newTuner);
 423                 double newScore = evaluateAll(newTuner);
 424                 newTuner->tuner->printUsed();
 425                 model_print("Received score %f\n", newScore);
 426                 double scoreDiff = newScore - oldScore; //smaller is better
 427                 if (newScore < bestScore) {
 428                         bestScore = newScore;
 429                         bestTuner = newTuner;
 430                 }
 431
 432                 double acceptanceP;
 433                 if (scoreDiff < 0) {
 434                         acceptanceP = 1;
 435                 } else {
 436                         double currTemp = base_temperature * (((double)budget - i) / budget);
 437                         acceptanceP = exp(-scoreDiff / currTemp);
 438                 }
 439                 double ran = ((double)random()) / RAND_MAX;
 440                 if (ran <= acceptanceP) {
 441                         oldScore = newScore;
 442                         oldTuner = newTuner;
 443                 }
 444         }
 445
 446         return bestTuner;
 447 }
 448