4 #include "searchtuner.h"
7 #include "solver_interface.h"
10 SATuner::SATuner(uint _budget, uint _timeout) :
11 BasicTuner(_budget, _timeout)
19 void SATuner::rankTunerForProblem(Vector<TunerRecord *> *places, TunerRecord *tuner, Problem *problem, long long metric) {
21 for (; k < places->getSize(); k++) {
22 if (metric < places->get(k)->getTime(problem))
25 model_print("Problem<%s>:place[%u]=Tuner<%p,%d>\n", problem->getProblem(), k, tuner, tuner->getTunerNumber());
26 places->insertAt(k, tuner);
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)) {
45 void SATuner::removeNullsFromTunerVector( Vector<TunerRecord *> *tunerV) {
46 for (int i = tunerV->getSize() - 1; i >= 0; i--) {
47 if (tunerV->get(i) == NULL) {
51 model_print("TunerV size after removing nulls = %u\n", tunerV->getSize());
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 *>());
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);
66 tuner->setTime(problem, metric);
68 tuner->setTime(problem, -2);
71 Vector<TunerRecord *> *places = allplaces.get(i);
72 rankTunerForProblem(places, tuner, problem, metric);
79 void SATuner::tune() {
80 Vector<TunerRecord *> *tunerV = new Vector<TunerRecord *>(&tuners);
81 Vector<Vector<TunerRecord *> *> allplaces;
82 uint tunerNumber = tuners.getSize();
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());
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());
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);
112 metric = evaluate(problem, tuner);
113 if (tuner->getTime(problem) == -1) {
114 tuner->addProblem(problem);
116 model_print("%u.Problem<%s>\tTuner<%p, %d>\tMetric<%lld>\n", i, problem->getProblem(),tuner, tuner->getTunerNumber(), metric);
117 model_print("*****************************\n");
119 tuner->setTime(problem, metric);
121 tuner->setTime(problem, -2);
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);
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);
140 if (scores.contains(tuner))
141 currScore = scores.get(tuner);
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;
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 ASSERT(scores.contains(tuner1));
157 ASSERT(scores.contains(tuner2));
158 int score1 = scores.get(tuner1);
159 int score2 = scores.get(tuner2);
160 if ( score2 > score1 ) {
161 removeTunerIndex(tunerV, i, allplaces);
162 } else if ( score2 < score1) {
163 model_print("score1=%d\tscore2=%d\tt=%u\texp=%f\n", score1, score2, t, exp((score1 - score2) * 1.0 / t));
164 double prob = 1 / (exp((score1 - score2) * 1.0 / t) );
165 double random = ((double) rand() / (RAND_MAX));
166 model_print("prob=%f\trandom=%f\n", prob, random);
168 removeTunerIndex(tunerV, i, allplaces);
170 removeTunerIndex(tunerV, tunerNumber + i, allplaces);
173 double random = ((double) rand() / (RAND_MAX));
174 int index = random > 0.5 ? i : tunerNumber + i;
175 removeTunerIndex(tunerV, index, allplaces);
178 removeNullsFromTunerVector(tunerV);
181 for (uint ii = 0; ii < allplaces.getSize(); ii++) {
182 delete allplaces.get(ii);