Chad Barb committed May 07, 2002 1 2 ``````/**** wanlinksolve - `````` Chad Barb committed May 30, 2002 3 4 5 `````` Resilient Overlay Network Reasonably Effective Algorithm for Genetically Assigning Nodes. `````` Chad Barb committed May 07, 2002 6 7 `````` Chad Barb, May 3, 2002 `````` Chad Barb committed May 16, 2002 8 `````` Applies a standard genetic algorithm (with crossover and elitism) `````` Chad Barb committed May 07, 2002 9 10 11 12 `````` to solve the problem of mapping a smaller "virtual" graph into a larger "physical" graph, such that the actual weights between acquired nodes are similar to desired weights. `````` Chad Barb committed May 30, 2002 13 `````` The penalty function is the sum of error square roots (for the first dimension). `````` Chad Barb committed May 07, 2002 14 15 16 17 `````` For the application this was designed for, "weights" are values of latency time in milliseconds. `````` Chad Barb committed May 10, 2002 18 `````` switches: `````` Chad Barb committed May 15, 2002 19 20 `````` -v Extra verbosity -v -v Jumbo verbosity `````` Chad Barb committed May 10, 2002 21 `````` `````` Chad Barb committed May 30, 2002 22 23 24 25 `````` -1 Multiply penalty for latency by . (optional, default weight is 1.0) `````` Chad Barb committed May 10, 2002 26 `````` -2 `````` Chad Barb committed May 14, 2002 27 `````` Solve for 2nd (bandwidth) dimension; `````` Chad Barb committed May 10, 2002 28 29 30 31 32 `````` Penalty for error is sum of differences of natural logs, multiplied by . A good weight seems to be around 7, but the appropriate value is pretty much application-dependent. `````` Chad Barb committed May 30, 2002 33 34 35 36 37 38 `````` -3 Solve for 3rd (loss) dimension Penalty for error is difference of %% (10 * percent) loss, multiplied by . -2 must be specified first. `````` Chad Barb committed May 14, 2002 39 40 41 `````` -m Handle multiple virtual->physical mapping. For each vnode beyond 1 assigned to a pnode, will be assessed. `````` Chad Barb committed May 14, 2002 42 43 44 `````` Asks for 'p' lines of input, with the maximum number of virtual nodes allowed on a given physical node, per line (See below) `````` Chad Barb committed May 14, 2002 45 46 47 `````` -s Use a specific random seed. `````` Chad Barb committed May 16, 2002 48 49 `````` -r Specify the number of rounds to continue going without a better solution. `````` Chad Barb committed May 10, 2002 50 51 52 53 54 `````` default: DEFAULT_ROUNDS -R Specify the absolute maximum number of rounds. default: -1 (infinite) `````` Chad Barb committed May 07, 2002 55 56 57 58 59 60 61 `````` takes input from stdin, outputs to stdout. input format: * One line containing a single number 'p'-- the number of physical nodes. * 'p' lines containing the name of each physical node `````` Chad Barb committed May 14, 2002 62 63 `````` ? 'p' lines containing the maximum number of virtual nodes each physical node can accommodate. ('-m' switch only) `````` Chad Barb committed May 07, 2002 64 65 66 `````` * 'p' lines each containing 'p' space-delimited numbers; this is a P x P matrix of the _actual_ weight from pnodes to pnodes. For latencies, there are zeros along the diagonal. `````` Chad Barb committed May 10, 2002 67 `````` ? 'p' lines, a P x P matrix of actual bandwidth ('-2' switch only) `````` Chad Barb committed May 30, 2002 68 `````` ? 'p' lines, a P x P matrix of actual loss ('-3' switch only) `````` Chad Barb committed May 10, 2002 69 `````` `````` Chad Barb committed May 07, 2002 70 71 `````` * One line containing a single number 'v'-- the number of virtual nodes. `````` Chad Barb committed May 14, 2002 72 `````` * 'v' lines containing the name of each virtual node. `````` Chad Barb committed May 15, 2002 73 74 `````` appending a space then the name of a physical node will permanently "fix" the mapping of this vnode to the named pnode. `````` Chad Barb committed May 07, 2002 75 76 77 78 79 80 `````` * 'v' lines each containing 'v' space delimited numbers; this is a V x V matrix of the _desired_ weight between vnodes. '-1's indicate "don't care"s.. (e.g. for the weight between two not-connected vnodes.) If link weights are symmetrical, this matrix will be its own transpose (symmetric over the diagonal.) `````` Chad Barb committed May 10, 2002 81 `````` ? 'v' lines, a V x V matrix of desired bandwidth ('-2' switch only) `````` Chad Barb committed May 30, 2002 82 `````` ? 'v' lines, a V x V matrix of desired loss ('-3' switch only) `````` Chad Barb committed May 07, 2002 83 84 85 86 `````` output format: Easily inferred. Note that the perl regexp: `````` Chad Barb committed May 14, 2002 87 `````` /(\S+)\smapsTo\s(\S+)/ `````` Chad Barb committed May 07, 2002 88 `````` will grab vnode to pnode mappings (in \$1 and \$2, respectively.) `````` Chad Barb committed May 16, 2002 89 90 91 92 93 94 95 96 97 98 `````` Some references on GA's: Goldberg 89 D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA, 1989. Holland 75 J. Holland. Adaptation In Natural and Artificial Systems. The University of Michigan Press, Ann Arbour, 1975. `````` Chad Barb committed May 07, 2002 99 100 101 102 103 `````` ****/ #include #include `````` Chad Barb committed May 10, 2002 104 105 ``````#include #include `````` Chad Barb committed May 15, 2002 106 ``````#include `````` Chad Barb committed May 07, 2002 107 ``````#include `````` Chad Barb committed May 22, 2002 108 109 110 ``````#include #include #include `````` Chad Barb committed May 07, 2002 111 112 113 114 115 `````` // To keep things lightweight, // structures are statically sized to // accommodate up to MAX_NODES nodes. // These could be changed to STL vectors in the future. `````` Chad Barb committed May 22, 2002 116 ``````#define MAX_NODES 32 `````` Chad Barb committed May 30, 2002 117 ``````#define MAX_DIMENSIONS 3 `````` Chad Barb committed May 10, 2002 118 `````` `````` Chad Barb committed May 16, 2002 119 120 ``````// default rounds to keep going without finding a better solution. #define DEFAULT_ROUNDS 512 `````` Chad Barb committed May 07, 2002 121 122 `````` // The size of our "population." `````` Chad Barb committed May 16, 2002 123 ``````// (number of phenotypes) `````` Chad Barb committed May 16, 2002 124 ``````#define SOLUTIONS 400 `````` Chad Barb committed May 07, 2002 125 `````` `````` Chad Barb committed May 16, 2002 126 ``````// The probability a given child will mutate (out of 1000) `````` Chad Barb committed May 16, 2002 127 128 ``````//#define MUTATE_PROB 40 #define MUTATE_PROB 10 `````` Chad Barb committed May 07, 2002 129 `````` `````` Chad Barb committed May 16, 2002 130 131 ``````// probability crossover will happen (out of 1000) #define CROSSOVER_PROB 700 `````` Chad Barb committed May 07, 2002 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 `````` // A score below Epsilon means we've found a perfect solution, // so stop immediately. #define EPSILON 0.0001f // lets STL it up a notch. #include #include // BAM! using namespace std; // keep freebsd from mumbling about gets(3) being unsafe. #define gets( x ) fgets( x, sizeof( x ), stdin ) `````` Chad Barb committed May 16, 2002 147 ``````// some code to enable when the solver wedges and we don't know why. `````` Chad Barb committed May 15, 2002 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 ``````#ifdef DEBUG int wedgecount; static inline void BEGIN_LOOP() { wedgecount = 0; } static inline void IN_LOOP_hlp( int line ) { ++wedgecount; if (wedgecount == 66666) { printf( "possibly wedged in line %i.\n", line ); assert(false); } } #define IN_LOOP() IN_LOOP_hlp(__LINE__) #else #define BEGIN_LOOP() #define IN_LOOP() #endif `````` Chad Barb committed May 07, 2002 167 168 ``````// keep track of user names for nodes. static map< int, string > pnodeNames; `````` Chad Barb committed May 14, 2002 169 ``````static map< string, int > reversePNodeNames; `````` Chad Barb committed May 07, 2002 170 171 172 173 ``````static map< int, string > vnodeNames; static int pnodes, vnodes; `````` Chad Barb committed May 10, 2002 174 175 176 ``````static int pLatency[MAX_DIMENSIONS][MAX_NODES][MAX_NODES]; static int vDesiredLatency[MAX_DIMENSIONS][MAX_NODES][MAX_NODES]; `````` Chad Barb committed May 14, 2002 177 ``````static float plexPenalty = 0.0f; `````` Chad Barb committed May 14, 2002 178 179 180 181 182 ``````static int maxplex[MAX_NODES]; static int userSpecifiedMultiplex = 0; static int fixed[MAX_NODES]; `````` Chad Barb committed May 10, 2002 183 ``````static int dimensions; `````` Chad Barb committed May 30, 2002 184 ``````static float d1weight, d2weight, d3weight; `````` Chad Barb committed May 10, 2002 185 186 187 188 `````` static int verbose = 0; static int minrounds, maxrounds; `````` Chad Barb committed May 07, 2002 189 `````` `````` Chad Barb committed May 16, 2002 190 191 ``````static bool himutate = false; `````` Chad Barb committed May 07, 2002 192 193 194 ``````class Solution { public: `````` Chad Barb committed May 30, 2002 195 `````` // the beef, as it were. `````` Chad Barb committed May 14, 2002 196 `````` int vnode_mapping[MAX_NODES]; `````` Chad Barb committed May 14, 2002 197 198 199 200 201 202 `````` // Keep around a list of how many times each physical node is used // in this solution, rather than recomputing it each time it is needed // (which is often.) unsigned char pnode_uses[MAX_NODES]; `````` Chad Barb committed May 30, 2002 203 `````` // calculated penalty `````` Chad Barb committed May 07, 2002 204 `````` float error; `````` Chad Barb committed May 30, 2002 205 206 207 `````` // probability of selecting this particular one (or any before it) // out of MAXINT `````` Chad Barb committed May 16, 2002 208 `````` unsigned int prob; `````` Chad Barb committed May 07, 2002 209 210 ``````}; `````` Chad Barb committed May 16, 2002 211 212 213 ``````// the population pool. // at any one time, one of these is the "current" pool (where the parents come from) // and one is the "next" pool (where the children go) `````` Chad Barb committed May 07, 2002 214 ``````static Solution pool[SOLUTIONS]; `````` Chad Barb committed May 15, 2002 215 ``````static Solution pool2[SOLUTIONS]; `````` Chad Barb committed May 07, 2002 216 `````` `````` Chad Barb committed May 30, 2002 217 218 ``````const char dimName[3][12] = { "latency", "bandwidth", "loss" }; `````` Chad Barb committed May 16, 2002 219 ``````// determines probabilities of selecting each solution. `````` Chad Barb committed May 15, 2002 220 ``````static inline void prepick( Solution * currentPool ) `````` Chad Barb committed May 07, 2002 221 ``````{ `````` Chad Barb committed May 15, 2002 222 223 224 225 226 227 228 `````` float totalFitness = 0.0f; int i; for (i = 0; i < SOLUTIONS; i++) { totalFitness += 1.0f / currentPool[i].error; } `````` Chad Barb committed May 16, 2002 229 `````` unsigned int probsofar = 0; `````` Chad Barb committed May 15, 2002 230 `````` for (i = 0; i < SOLUTIONS; i++) { `````` Chad Barb committed May 16, 2002 231 232 `````` probsofar += (unsigned int)(((float)0xFFFFFFFF / currentPool[i].error) / totalFitness); currentPool[i].prob = probsofar; `````` Chad Barb committed May 15, 2002 233 `````` } `````` Chad Barb committed May 16, 2002 234 235 `````` currentPool[SOLUTIONS - 1].prob = 0xFFFFFFFF; `````` Chad Barb committed May 15, 2002 236 237 ``````} `````` Chad Barb committed May 16, 2002 238 239 ``````// optimized to 1. not use fp 2. use a binary search, rather than a linear one. // win: according to gprof, was taking 75% of the total time, now takes 17%. `````` Chad Barb committed May 15, 2002 240 241 ``````static inline int pickABest( Solution * currentPool ) { `````` Chad Barb committed May 16, 2002 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 `````` unsigned int x = rand(); int lo = 0; int hi = SOLUTIONS; int mid; while (1) { mid = (hi + lo) / 2; if (x <= currentPool[mid].prob) { if (mid == 0 || x > currentPool[mid - 1].prob) break; hi = mid; } else { lo = mid; } } `````` Chad Barb committed May 15, 2002 257 `````` `````` Chad Barb committed May 16, 2002 258 259 `````` return mid; /* `````` Chad Barb committed May 15, 2002 260 261 `````` int i = 0; while (1) { `````` Chad Barb committed May 16, 2002 262 `````` if (x < currentPool[i].prob) break; `````` Chad Barb committed May 15, 2002 263 `````` i++; `````` Chad Barb committed May 16, 2002 264 `````` if (i == SOLUTIONS) { printf("Ick.\n"); i = 0; break;} `````` Chad Barb committed May 15, 2002 265 266 `````` } return i - 1; `````` Chad Barb committed May 16, 2002 267 `````` */ `````` Chad Barb committed May 15, 2002 268 269 ``````} `````` Chad Barb committed May 16, 2002 270 `````` `````` Chad Barb committed May 14, 2002 271 ``````// uses a template to avoid massive numbers `````` Chad Barb committed May 07, 2002 272 273 274 275 276 277 278 279 280 281 282 ``````// of "if" choices.. compiler should generate two versions, // one with dump and one without. template static inline void calcError( Solution * t ) { float err = 0.0f; if (verbose) { printf("Error listing:\n"); } `````` Chad Barb committed May 14, 2002 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 `````` if (userSpecifiedMultiplex) { for (int x = 0; x < pnodes; x++) { if (t->pnode_uses[x] > 1) { float errDelta = (float)(t->pnode_uses[x] - 1) * plexPenalty; if (verbose) { printf("%i nodes multiplexed on physical node %s, (err [(vnodes - 1) * plexPenalty] %4.3f)\n", t->pnode_uses[x], pnodeNames[x].c_str(), errDelta ); } err += errDelta; } } } `````` Chad Barb committed May 07, 2002 298 `````` { `````` Chad Barb committed May 10, 2002 299 300 301 302 303 `````` for (int z = 0; z < dimensions; z++) { for (int x = 0; x < vnodes; x++) { for (int y = 0; y < vnodes; y++) { int should = vDesiredLatency[z][x][y]; if (should != -1) { `````` Chad Barb committed May 14, 2002 304 `````` int is = pLatency[z][ t->vnode_mapping[x] ][ t->vnode_mapping[y] ]; `````` Chad Barb committed May 16, 2002 305 306 307 308 309 310 311 `````` if (is == -1) { if (verbose) { printf("%s -> %s link nonexistant! Super-icky penality of 10000 assessed.\n", vnodeNames[x].c_str(), vnodeNames[y].c_str() ); } err += 10000.0f; } else if (should != is) { `````` Chad Barb committed May 10, 2002 312 313 314 `````` float errDelta; if (z == 0) { `````` Chad Barb committed May 30, 2002 315 316 `````` errDelta = d1weight * sqrtf((float)(abs(should - is))); } else if (z == 1) { `````` Chad Barb committed May 10, 2002 317 `````` errDelta = d2weight * (float)(abs(should - is)); `````` Chad Barb committed May 14, 2002 318 `````` if (should < is) { errDelta *= 0.5f; } `````` Chad Barb committed May 30, 2002 319 320 `````` } else { errDelta = d3weight * (float)(abs( should - is )); `````` Chad Barb committed May 10, 2002 321 322 323 324 `````` } if (verbose) { if (z == 0) { `````` Chad Barb committed May 30, 2002 325 `````` printf("%s -> %s latency (ms) should be %i; is %i (err [wt * sqrt |a-b|] %4.3f)\n", `````` Chad Barb committed May 10, 2002 326 327 `````` vnodeNames[x].c_str(), vnodeNames[y].c_str(), should, is, errDelta ); `````` Chad Barb committed May 30, 2002 328 `````` } else if (z == 1) { `````` Chad Barb committed May 14, 2002 329 `````` printf("%s -> %s bandwidth (kB/s) should be ~%i; is ~%i (err [wt %s* ln (a/b)] %4.3f)\n", `````` Chad Barb committed May 10, 2002 330 331 332 `````` vnodeNames[x].c_str(), vnodeNames[y].c_str(), (int)expf((float)should / 1000.0f), (int)expf((float)is / 1000.0f), `````` Chad Barb committed May 14, 2002 333 `````` (should < is) ? "* 0.5 " : "", `````` Chad Barb committed May 10, 2002 334 `````` errDelta ); `````` Chad Barb committed May 30, 2002 335 336 337 338 339 340 `````` } else { printf("%s -> %s loss should be %1.4f; is %1.4f (err [wt * |a-b|] %4.3f)\n", vnodeNames[x].c_str(), vnodeNames[y].c_str(), (float)should / 65536.0f, (float)is / 65536.0f, errDelta ); `````` Chad Barb committed May 10, 2002 341 342 343 `````` } } err += errDelta; `````` Chad Barb committed May 07, 2002 344 345 346 347 348 349 350 `````` } } } } } } `````` Chad Barb committed May 10, 2002 351 `````` if (verbose) { printf("error of %4.3f\n", err ); } `````` Chad Barb committed May 07, 2002 352 353 354 355 356 357 358 359 360 361 362 363 364 `````` t->error = err; } static int compar( const void * a , const void * b ) { Solution * sa = (Solution *)a; Solution * sb = (Solution *)b; if (sa->error > sb->error) { return 1; } else if (sa->error < sb->error) { return -1; } else { return 0; } } `````` Chad Barb committed May 15, 2002 365 ``````static inline void sortByError( Solution * t ) `````` Chad Barb committed May 07, 2002 366 367 ``````{ // Ahh.. sweet, sweet qsort. `````` Chad Barb committed May 15, 2002 368 `````` qsort( t, SOLUTIONS, sizeof( Solution ), compar ); `````` Chad Barb committed May 07, 2002 369 370 371 372 373 374 375 ``````} // "Mutating" is swapping what vnode a pnode maps to in // the solution with what vnode a different pnode maps to. // (if both are -1, e.g. not mapped to vnodes, nothing happens.) static inline void mutate( Solution * t ) { `````` Chad Barb committed May 15, 2002 376 `````` BEGIN_LOOP(); `````` Chad Barb committed May 07, 2002 377 `````` while(1) { `````` Chad Barb committed May 15, 2002 378 `````` IN_LOOP(); `````` Chad Barb committed May 07, 2002 379 `````` // forecast calls for a 1% chance of mutation... `````` Chad Barb committed May 16, 2002 380 `````` if ((rand() % 1000) > (himutate ? 500 : MUTATE_PROB)) { break; } `````` Chad Barb committed May 14, 2002 381 382 383 384 `````` if ((rand() % 3)) { // swap mutation. int a, b; `````` Chad Barb committed May 15, 2002 385 386 `````` BEGIN_LOOP(); `````` Chad Barb committed May 14, 2002 387 `````` do { `````` Chad Barb committed May 15, 2002 388 `````` IN_LOOP(); `````` Chad Barb committed May 14, 2002 389 `````` a = rand() % vnodes; `````` Chad Barb committed May 15, 2002 390 391 392 393 394 `````` } while (fixed[a] != -1); BEGIN_LOOP(); do { IN_LOOP(); `````` Chad Barb committed May 14, 2002 395 `````` b = rand() % vnodes; `````` Chad Barb committed May 15, 2002 396 397 398 399 400 401 402 `````` } while (fixed[b] != -1); if (a != b) { int temp = t->vnode_mapping[a]; t->vnode_mapping[a] = t->vnode_mapping[b]; t->vnode_mapping[b] = temp; } `````` Chad Barb committed May 14, 2002 403 404 405 406 407 `````` } else { // reassign mutation int a, b; // find which vnode to remap `````` Chad Barb committed May 15, 2002 408 `````` BEGIN_LOOP(); `````` Chad Barb committed May 14, 2002 409 `````` do { `````` Chad Barb committed May 15, 2002 410 `````` IN_LOOP(); `````` Chad Barb committed May 14, 2002 411 412 413 414 415 416 417 `````` a = rand() % vnodes; } while (fixed[a] != -1); // de-map it. --t->pnode_uses[ t->vnode_mapping[a] ]; // now find a suitable physical node. `````` Chad Barb committed May 15, 2002 418 `````` BEGIN_LOOP(); `````` Chad Barb committed May 14, 2002 419 `````` do { `````` Chad Barb committed May 15, 2002 420 `````` IN_LOOP(); `````` Chad Barb committed May 14, 2002 421 422 423 424 425 426 427 `````` b = rand() % pnodes; } while (t->pnode_uses[b] >= maxplex[b]); // now map it. t->vnode_mapping[a] = b; ++t->pnode_uses[b]; } `````` Chad Barb committed May 07, 2002 428 429 430 431 432 433 434 435 `````` } } // TODO: make sure that failed matings don't happen too // often for difficult graphs. // (perhaps have a limited retry) static inline void splice( Solution * t, Solution * a, Solution * b) { `````` Chad Barb committed May 16, 2002 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 `````` if ((rand() % 1000) > CROSSOVER_PROB) { if (rand() % 2) { for (int x = 0; x < vnodes; x++) { t->vnode_mapping[x] = a->vnode_mapping[x]; } for (int y = 0; y < vnodes; y++) { t->pnode_uses[y] = a->pnode_uses[y]; } } else { for (int x = 0; x < vnodes; x++) { t->vnode_mapping[x] = b->vnode_mapping[x]; } for (int y = 0; y < vnodes; y++) { t->pnode_uses[y] = b->pnode_uses[y]; } `````` Chad Barb committed May 07, 2002 451 `````` } `````` Chad Barb committed May 16, 2002 452 `````` } else { `````` Chad Barb committed May 07, 2002 453 `````` `````` Chad Barb committed May 16, 2002 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 `````` bzero( t->pnode_uses, sizeof( t->pnode_uses ) ); for (int i = 0; i < vnodes; i++) { if (fixed[i] != -1) { t->vnode_mapping[i] = fixed[i]; ++t->pnode_uses[ fixed[i] ]; } } // go through each mapping, and pick randomly // which one of the two parents' mappings the child // will inherit. // Inherit the one that makes sense if the other would // conflict with a previously chosen mapping. // If both would conflict with a previously chosen mapping. // its a failed mating, and we return. int pos = rand() % vnodes; for (int i = 0; i < vnodes; i++) { pos = (pos + 1) % vnodes; if (fixed[pos] != -1) continue; if (rand() % 2) { if (t->pnode_uses[ a->vnode_mapping[pos] ] < maxplex[ a->vnode_mapping[pos] ]) { t->vnode_mapping[pos] = a->vnode_mapping[pos]; ++t->pnode_uses[ a->vnode_mapping[pos] ]; `````` Chad Barb committed May 07, 2002 479 `````` } else { `````` Chad Barb committed May 16, 2002 480 481 482 483 484 485 486 487 488 489 490 491 `````` if (t->pnode_uses[ b->vnode_mapping[pos] ] < maxplex[ b->vnode_mapping[pos] ]) { t->vnode_mapping[pos] = b->vnode_mapping[pos]; ++t->pnode_uses[ b->vnode_mapping[pos] ]; } else { // failed mating (asexually clone a parent) for (int x = 0; x < vnodes; x++) { t->vnode_mapping[x] = a->vnode_mapping[x]; } for (int y = 0; y < vnodes; y++) { t->pnode_uses[y] = a->pnode_uses[y]; } break; `````` Chad Barb committed May 15, 2002 492 `````` } `````` Chad Barb committed May 07, 2002 493 494 `````` } } else { `````` Chad Barb committed May 16, 2002 495 496 497 `````` if (t->pnode_uses[ b->vnode_mapping[pos] ] < maxplex[ b->vnode_mapping[pos] ]) { t->vnode_mapping[pos] = b->vnode_mapping[pos]; ++t->pnode_uses[ b->vnode_mapping[pos] ]; `````` Chad Barb committed May 07, 2002 498 `````` } else { `````` Chad Barb committed May 16, 2002 499 500 501 502 503 504 505 506 507 508 509 510 `````` if (t->pnode_uses[ a->vnode_mapping[pos] ] < maxplex[ a->vnode_mapping[pos] ]) { t->vnode_mapping[pos] = a->vnode_mapping[pos]; ++t->pnode_uses[ a->vnode_mapping[pos] ]; } else { // failed mating (asexually clone a parent) for (int x = 0; x < vnodes; x++) { t->vnode_mapping[x] = b->vnode_mapping[x]; } for (int y = 0; y < vnodes; y++) { t->pnode_uses[y] = b->pnode_uses[y]; } break; `````` Chad Barb committed May 15, 2002 511 `````` } `````` Chad Barb committed May 07, 2002 512 513 514 515 516 517 518 519 520 521 522 523 524 `````` } } } } mutate( t ); calcError( t ); } // Generate a random solution // for the initial population. static inline void generateRandomSolution( Solution * t ) { `````` Chad Barb committed May 14, 2002 525 526 `````` //int pnode_uses[MAX_NODES]; bzero( t->pnode_uses, sizeof( t->pnode_uses ) ); `````` Chad Barb committed May 14, 2002 527 528 529 530 `````` for (int i = 0; i < vnodes; i++) { if (fixed[i] != -1) { t->vnode_mapping[i] = fixed[i]; `````` Chad Barb committed May 14, 2002 531 `````` ++t->pnode_uses[ fixed[i] ]; `````` Chad Barb committed May 07, 2002 532 533 `````` } } `````` Chad Barb committed May 14, 2002 534 535 536 537 `````` for (int i = 0; i < vnodes; i++) { if (fixed[i] == -1) { int x; `````` Chad Barb committed May 15, 2002 538 `````` BEGIN_LOOP(); `````` Chad Barb committed May 14, 2002 539 `````` do { `````` Chad Barb committed May 15, 2002 540 `````` IN_LOOP(); `````` Chad Barb committed May 14, 2002 541 `````` x = rand() % pnodes; `````` Chad Barb committed May 14, 2002 542 543 `````` } while( t->pnode_uses[x] >= maxplex[x] ); ++t->pnode_uses[x]; `````` Chad Barb committed May 14, 2002 544 545 546 547 `````` t->vnode_mapping[i] = x; } } `````` Chad Barb committed May 07, 2002 548 549 550 `````` calcError( t ); } `````` Chad Barb committed May 10, 2002 551 ``````void usage( char * appname ) `````` Chad Barb committed May 07, 2002 552 ``````{ `````` Chad Barb committed May 10, 2002 553 554 `````` fprintf(stderr, "Usage:\n" `````` Chad Barb committed May 30, 2002 555 556 `````` "%s [-v [-v]] [-m ] [-s ] [-1 ]\n" "\t[-2 [-3 ]] [-r ] [-R ]\n\n" `````` Chad Barb committed May 10, 2002 557 `````` " -v extra verbosity\n" `````` Chad Barb committed May 15, 2002 558 `````` " -v -v jumbo verbosity\n" `````` Chad Barb committed May 14, 2002 559 560 `````` " -m enable many-to-one virtual to physical mappings\n" " -s seed the random number generator with a specific value\n" `````` Chad Barb committed May 30, 2002 561 `````` " -1 assign weight to latency penalty (optional; default 1.0)\n" `````` Chad Barb committed May 10, 2002 562 563 `````` " -2 enable solving for bandwidth;\n" " multiply bandwidth penalties by .\n" `````` Chad Barb committed May 30, 2002 564 565 `````` " -3 enable solving for loss.\n" " (must specify -2 first)\n" `````` Chad Barb committed May 16, 2002 566 `````` " -r number of rounds to go without a solution before stopping\n" `````` Chad Barb committed May 10, 2002 567 568 569 `````` " default: %i\n" " -R set maximum rounds\n" " default: infinite (-1)\n\n", appname, DEFAULT_ROUNDS ); `````` Chad Barb committed May 15, 2002 570 `````` exit(1); `````` Chad Barb committed May 10, 2002 571 572 ``````} `````` Chad Barb committed May 22, 2002 573 574 575 576 577 578 579 580 581 582 ``````unsigned int msecscpu() { struct rusage r; getrusage( 0, &r ); return r.ru_utime.tv_sec * 1000 + r.ru_utime.tv_usec / 1000; } `````` Chad Barb committed May 10, 2002 583 584 ``````int main( int argc, char ** argv ) { `````` Chad Barb committed May 15, 2002 585 586 `````` int available = 0; int fixedNodeCount = 0; `````` Chad Barb committed May 22, 2002 587 `````` unsigned int bestSpeed = 0; `````` Chad Barb committed May 15, 2002 588 `````` `````` Chad Barb committed May 10, 2002 589 590 `````` verbose = 0; dimensions = 1; `````` Chad Barb committed May 30, 2002 591 `````` d1weight = 1.0f; `````` Chad Barb committed May 10, 2002 592 `````` d2weight = 1.0f / 1000.0f; `````` Chad Barb committed May 30, 2002 593 `````` d3weight = 1.0f / 65536.0f; `````` Chad Barb committed May 10, 2002 594 595 596 597 598 599 `````` minrounds = DEFAULT_ROUNDS; maxrounds = -1; int ch; `````` Chad Barb committed May 30, 2002 600 `````` while ((ch = getopt(argc, argv, "v1:2:3:r:R:s:m:")) != -1) { `````` Chad Barb committed May 10, 2002 601 `````` switch (ch) { `````` Chad Barb committed May 14, 2002 602 603 604 `````` case 's': srand( atoi( optarg ) ); break; `````` Chad Barb committed May 10, 2002 605 606 607 `````` case 'v': verbose++; break; `````` Chad Barb committed May 14, 2002 608 `````` case 'm': `````` Chad Barb committed May 14, 2002 609 `````` plexPenalty = atof( optarg ); `````` Chad Barb committed May 14, 2002 610 611 `````` userSpecifiedMultiplex++; break; `````` Chad Barb committed May 30, 2002 612 613 614 `````` case '1': d1weight = atof( optarg ); break; `````` Chad Barb committed May 10, 2002 615 616 617 618 `````` case '2': dimensions = 2; d2weight = atof( optarg ) / 1000.0f; break; `````` Chad Barb committed May 30, 2002 619 620 621 622 623 624 625 626 627 `````` case '3': if (dimensions != 2) { fprintf(stderr, "Must specify -2 option first when using -3.\n"); exit(1); } else { dimensions = 3; d3weight = atof( optarg ) / 65536.0f; } break; `````` Chad Barb committed May 10, 2002 628 629 630 631 632 633 634 635 `````` case 'r': minrounds = atoi( optarg ); break; case 'R': maxrounds = atoi( optarg ); break; default: usage( argv[0] ); `````` Chad Barb committed May 30, 2002 636 `````` break; `````` Chad Barb committed May 10, 2002 637 638 639 640 `````` } } `````` Chad Barb committed May 22, 2002 641 `````` char line[4096]; `````` Chad Barb committed May 07, 2002 642 643 `````` { `````` Chad Barb committed May 15, 2002 644 `````` if (verbose > 1) { printf("How many physical nodes?\n"); } `````` Chad Barb committed May 07, 2002 645 646 647 `````` gets( line ); sscanf( line, "%i", &pnodes ); `````` Chad Barb committed May 15, 2002 648 `````` if (verbose > 1) { printf("Okay, enter %i names for the physical nodes, one per line.\n", pnodes ); } `````` Chad Barb committed May 07, 2002 649 650 651 652 653 `````` for (int i = 0; i < pnodes; i++) { char name[1024]; gets( line ); sscanf( line, "%s", name ); pnodeNames[i] = string( name ); `````` Chad Barb committed May 14, 2002 654 655 656 657 `````` reversePNodeNames[string(name)] = i; } if (userSpecifiedMultiplex) { `````` Chad Barb committed May 15, 2002 658 `````` if (verbose > 1) { printf("Enter %i numbers, one per line, indicating the" `````` Chad Barb committed May 14, 2002 659 660 661 662 663 `````` " maximum number of virtual nodes allowed on each" " physical node.\n", pnodes ); } for (int i = 0; i < pnodes; i++) { gets( line ); sscanf( line, "%i", &(maxplex[i])); `````` Chad Barb committed May 15, 2002 664 `````` available += maxplex[i]; `````` Chad Barb committed May 14, 2002 665 666 667 668 `````` } } else { for (int i = 0; i < pnodes; i++) { maxplex[i] = 1; `````` Chad Barb committed May 15, 2002 669 `````` ++available; `````` Chad Barb committed May 14, 2002 670 `````` } `````` Chad Barb committed May 07, 2002 671 672 `````` } `````` Chad Barb committed May 10, 2002 673 `````` for (int z = 0; z < dimensions; z++) { `````` Chad Barb committed May 15, 2002 674 `````` if (verbose > 1) { `````` Chad Barb committed May 30, 2002 675 `````` printf("Enter %ix%i grid o' actual %s.\n", pnodes, pnodes, dimName[z]); `````` Chad Barb committed May 10, 2002 676 677 678 679 680 681 `````` } for (int y = 0; y < pnodes; y++) { char * linePos = line; gets( line ); while (*linePos == ' ') { linePos++; } // skip leading whitespace for (int x = 0; x < pnodes; x++) { `````` Chad Barb committed May 30, 2002 682 `````` float temp; `````` Chad Barb committed May 10, 2002 683 `````` sscanf( linePos, "%i", &pLatency[z][x][y] ); `````` Chad Barb committed May 30, 2002 684 `````` sscanf( linePos, "%f", &temp ); `````` Chad Barb committed May 16, 2002 685 `````` if (pLatency[z][x][y] != -1) { `````` Chad Barb committed May 30, 2002 686 687 688 689 690 `````` if (z == 1) { pLatency[z][x][y] = (int)( logf(pLatency[z][x][y]) * 1000.0f ); } else if (z == 2) { pLatency[z][x][y] = (int)(temp * 65536.0f); } `````` Chad Barb committed May 16, 2002 691 `````` } `````` Chad Barb committed May 10, 2002 692 693 694 `````` while (*linePos != ' ' && *linePos != '\n') { linePos++; } while (*linePos == ' ') { linePos++; } } `````` Chad Barb committed May 07, 2002 695 696 697 698 699 `````` } } } { `````` Chad Barb committed May 15, 2002 700 `````` if (verbose > 1) { printf("How many virtual nodes?\n"); } `````` Chad Barb committed May 07, 2002 701 702 703 `````` gets( line ); sscanf( line, "%i", &vnodes ); `````` Chad Barb committed May 15, 2002 704 705 706 707 708 709 710 711 712 713 714 `````` if (vnodes > available) { fprintf(stderr, "More nodes required (%i) than can be mapped (%i).\n", vnodes, available ); exit(2); } if (verbose > 1) { printf("Okay, enter %i names for the virtual nodes, one per line.\n" "to fix a node, suffix a space then the name of the physical node.\n", vnodes ); } `````` Chad Barb committed May 07, 2002 715 716 `````` for (int i = 0; i < vnodes; i++) { char name[1024]; `````` Chad Barb committed May 15, 2002 717 `````` char pname[1024]; `````` Chad Barb committed May 07, 2002 718 `````` gets( line ); `````` Chad Barb committed May 15, 2002 719 720 `````` if (sscanf( line, "%s %s", name, pname ) == 2) { map< string, int >::iterator it = reversePNodeNames.find( string( pname ) ); `````` Chad Barb committed May 14, 2002 721 `````` if (it == reversePNodeNames.end()) { `````` Chad Barb committed May 15, 2002 722 723 `````` fprintf(stderr,"pnode '%s' does not exist; can't fix.\n", pname ); exit(3); `````` Chad Barb committed May 14, 2002 724 `````` } `````` Chad Barb committed May 15, 2002 725 726 `````` if (verbose > 1) { printf("Fixing assignment from vnode %s to pnode %s.\n", name, pname ); `````` Chad Barb committed May 14, 2002 727 `````` } `````` Chad Barb committed May 15, 2002 728 729 `````` fixed[i] = reversePNodeNames[ string( pname ) ]; fixedNodeCount++; `````` Chad Barb committed May 14, 2002 730 731 732 `````` } else { fixed[i] = -1; } `````` Chad Barb committed May 15, 2002 733 `````` vnodeNames[i] = string( name ); `````` Chad Barb committed May 07, 2002 734 735 `````` } `````` Chad Barb committed May 10, 2002 736 `````` for (int z = 0; z < dimensions; z++) { `````` Chad Barb committed May 15, 2002 737 `````` if (verbose > 1) { `````` Chad Barb committed May 10, 2002 738 `````` printf("Enter %ix%i grid o' desired %s (-1 is don't care.)\n", vnodes, vnodes, `````` Chad Barb committed May 30, 2002 739 `````` dimName[z]); `````` Chad Barb committed May 07, 2002 740 `````` } `````` Chad Barb committed May 10, 2002 741 742 743 744 745 `````` for (int y = 0; y < vnodes; y++) { char * linePos = line; gets( line ); while (*linePos == ' ') { linePos++; } // skip leading whitespace for (int x = 0; x < vnodes; x++) { `````` Chad Barb committed May 30, 2002 746 `````` float temp; `````` Chad Barb committed May 10, 2002 747 `````` sscanf( linePos, "%i", &vDesiredLatency[z][x][y] ); `````` Chad Barb committed May 30, 2002 748 749 750 `````` sscanf( linePos, "%f", &temp ); if (vDesiredLatency[z][x][y] != -1) { if (z == 1) { `````` Chad Barb committed May 10, 2002 751 `````` vDesiredLatency[z][x][y] = (int)(logf(vDesiredLatency[z][x][y]) * 1000.0f); `````` Chad Barb committed May 30, 2002 752 753 `````` } else if (z == 2) { vDesiredLatency[z][x][y] = (int)(temp * 65536.0f); `````` Chad Barb committed May 10, 2002 754 755 756 757 758 759 760 761 `````` } } while (*linePos != ' ' && *linePos != '\n') { linePos++; } while (*linePos == ' ') { linePos++; } } } } } `````` Chad Barb committed May 07, 2002 762 `````` `````` Chad Barb committed May 15, 2002 763 764 765 `````` Solution * currentPool = pool; Solution * nextPool = pool2; `````` Chad Barb committed May 15, 2002 766 767 `````` if (fixedNodeCount < vnodes) { if (verbose) { printf("Now running...\n"); } `````` Chad Barb committed May 07, 2002 768 `````` `````` Chad Barb committed May 15, 2002 769 770 `````` { for (int i = 0; i < SOLUTIONS; i++) { `````` Chad Barb committed May 15, 2002 771 `````` generateRandomSolution( &(currentPool[i]) ); `````` Chad Barb committed May 15, 2002 772 `````` } `````` Chad Barb committed May 15, 2002 773 `````` sortByError( currentPool ); `````` Chad Barb committed May 07, 2002 774 775 776 `````` } int highestFoundRound = 0; `````` Chad Barb committed May 15, 2002 777 778 `````` float last = currentPool[0].error; `````` Chad Barb committed May 16, 2002 779 `````` himutate = false; `````` Chad Barb committed May 16, 2002 780 `````` for (int i = 0; i != maxrounds && i < (highestFoundRound + minrounds); i++) { `````` Chad Barb committed May 16, 2002 781 782 783 784 785 786 787 788 789 790 791 792 `````` float avg = 0.0f; int xy; for (xy = 0; xy < SOLUTIONS; xy++) { avg += currentPool[xy].error; } avg /= (float)SOLUTIONS; float stddev = 0.0f; for (xy = 0; xy < SOLUTIONS; xy++) { float diff = currentPool[xy].error - avg; stddev += diff * diff; } stddev = sqrtf(stddev / (float)(SOLUTIONS - 1)); `````` Chad Barb committed May 15, 2002 793 `````` `````` Chad Barb committed May 16, 2002 794 `````` if (verbose && !(i % 100)) { `````` Chad Barb committed May 16, 2002 795 `````` printf("Round %i. (best %4.3f; avg %4.3f; sdev %4.3f)\n", i, currentPool[0].error, avg, stddev); `````` Chad Barb committed May 07, 2002 796 `````` } `````` Chad Barb committed May 15, 2002 797 `````` `````` Chad Barb committed May 15, 2002 798 `````` if (currentPool[0].error < last) { `````` Chad Barb committed May 10, 2002 799 800 `````` if (verbose) { printf("Better solution found in round %i (error %4.3f)\n", `````` Chad Barb committed May 15, 2002 801 `````` i, currentPool[0].error); `````` Chad Barb committed May 10, 2002 802 `````` } `````` Chad Barb committed May 22, 2002 803 `````` bestSpeed = msecscpu(); `````` Chad Barb committed May 15, 2002 804 `````` last = currentPool[0].error; `````` Chad Barb committed May 07, 2002 805 806 `````` highestFoundRound = i; } `````` Chad Barb committed May 15, 2002 807 `````` `````` Chad Barb committed May 16, 2002 808 809 `````` // this is "elitism" -- the best solution is guaranteed to survive. // (otherwise, a good solution may be found, but may be lost by the next generation.) `````` Chad Barb committed May 15, 2002 810 811 812 813 814 `````` memcpy( &(nextPool[0]), &(currentPool[0]), sizeof( Solution ) ); prepick( currentPool ); int j; `````` Chad Barb committed May 16, 2002 815 816 817 818 819 820 `````` // if there is not enough variety, more mutation! if (stddev < (avg / 10.0f)) { himutate = true; } for (j = 1; j < SOLUTIONS; j++) { `````` Chad Barb committed May 15, 2002 821 822 823 824 825 `````` splice( &(nextPool[j]), &(currentPool[pickABest( currentPool )]), &(currentPool[pickABest( currentPool )]) ); } `````` Chad Barb committed May 16, 2002 826 827 `````` if (stddev < 0.1f) { himutate = false; `````` Chad Barb committed May 15, 2002 828 `````` } `````` Chad Barb committed May 30, 2002 829 `````` `````` Chad Barb committed May 15, 2002 830 831 832 833 834 835 836 `````` sortByError( nextPool ); Solution * temp = currentPool; currentPool = nextPool; nextPool = temp; if (currentPool[0].error < EPSILON) { `````` Chad Barb committed May 15, 2002 837 `````` if (verbose > 1) { printf("Found perfect solution.\n"); } `````` Chad Barb committed May 07, 2002 838 839 840 `````` break; } } `````` Chad Barb committed May 15, 2002 841 842 `````` } else { if (verbose) { printf("No non-fixed vnodes (or no vnodes at all,) so nothing to be done!\n"); } `````` Chad Barb committed May 07, 2002 843 844 845 `````` } { `````` Chad Barb committed May 10, 2002 846 `````` if (verbose) { printf("\nYour solution is as follows:\n"); } `````` Chad Barb committed May 14, 2002 847 `````` for (int x = 0; x < vnodes; x++) { `````` Chad Barb committed May 15, 2002 848 849 `````` if (pnodeNames.find( currentPool[0].vnode_mapping[x] ) == pnodeNames.end()) { pnodeNames[ currentPool[0].vnode_mapping[x] ] = "CRAP"; `````` Chad Barb committed May 15, 2002 850 851 852 `````` } printf("%s mapsTo %s\n", vnodeNames[x].c_str(), `````` Chad Barb committed May 15, 2002 853 `````` pnodeNames[currentPool[0].vnode_mapping[x]].c_str() ); `````` Chad Barb committed May 07, 2002 854 `````` } `````` Chad Barb committed May 14, 2002 855 `````` `````` Chad Barb committed May 07, 2002 856 857 858 `````` printf("\n"); // dump a detailed report of the returned solution's errors. `````` Chad Barb committed May 22, 2002 859 860 861 862 `````` if (verbose > 1) { calcError( &(currentPool[0]) ); printf("Found in %i msecs\n", bestSpeed ); } `````` Chad Barb committed May 07, 2002 863 864 `````` } `````` Chad Barb committed May 15, 2002 865 `````` if (verbose > 1) { printf("Bye now.\n"); } `````` Chad Barb committed May 07, 2002 866 867 `````` return 0; }``````