Chad Barb committed May 07, 2002 1 2 3 4 5 ``````/**** wanlinksolve - A Reasonably Effective Algorithm for Genetically Assigning Nodes. Chad Barb, May 3, 2002 `````` Chad Barb committed May 16, 2002 6 `````` Applies a standard genetic algorithm (with crossover and elitism) `````` Chad Barb committed May 07, 2002 7 8 9 10 11 12 13 14 15 `````` 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. The penalty function is the sum of error square roots. For the application this was designed for, "weights" are values of latency time in milliseconds. `````` Chad Barb committed May 10, 2002 16 `````` switches: `````` Chad Barb committed May 15, 2002 17 18 `````` -v Extra verbosity -v -v Jumbo verbosity `````` Chad Barb committed May 10, 2002 19 20 `````` -2 `````` Chad Barb committed May 14, 2002 21 `````` Solve for 2nd (bandwidth) dimension; `````` Chad Barb committed May 10, 2002 22 23 24 25 26 `````` 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 14, 2002 27 28 29 `````` -m Handle multiple virtual->physical mapping. For each vnode beyond 1 assigned to a pnode, will be assessed. `````` Chad Barb committed May 14, 2002 30 31 32 `````` 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 33 34 35 `````` -s Use a specific random seed. `````` Chad Barb committed May 16, 2002 36 37 `````` -r Specify the number of rounds to continue going without a better solution. `````` Chad Barb committed May 10, 2002 38 39 40 41 42 `````` default: DEFAULT_ROUNDS -R Specify the absolute maximum number of rounds. default: -1 (infinite) `````` Chad Barb committed May 07, 2002 43 44 45 46 47 48 49 `````` 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 50 51 `````` ? 'p' lines containing the maximum number of virtual nodes each physical node can accommodate. ('-m' switch only) `````` Chad Barb committed May 07, 2002 52 53 54 `````` * '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 55 56 `````` ? 'p' lines, a P x P matrix of actual bandwidth ('-2' switch only) `````` Chad Barb committed May 07, 2002 57 58 `````` * One line containing a single number 'v'-- the number of virtual nodes. `````` Chad Barb committed May 14, 2002 59 `````` * 'v' lines containing the name of each virtual node. `````` Chad Barb committed May 15, 2002 60 61 `````` 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 62 63 64 65 66 67 `````` * '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 68 `````` ? 'v' lines, a V x V matrix of desired bandwidth ('-2' switch only) `````` Chad Barb committed May 07, 2002 69 70 71 72 `````` output format: Easily inferred. Note that the perl regexp: `````` Chad Barb committed May 14, 2002 73 `````` /(\S+)\smapsTo\s(\S+)/ `````` Chad Barb committed May 07, 2002 74 `````` will grab vnode to pnode mappings (in \$1 and \$2, respectively.) `````` Chad Barb committed May 16, 2002 75 76 77 78 79 80 81 82 83 84 85 `````` 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 86 87 88 89 90 `````` ****/ #include #include `````` Chad Barb committed May 10, 2002 91 92 ``````#include #include `````` Chad Barb committed May 15, 2002 93 ``````#include `````` Chad Barb committed May 07, 2002 94 ``````#include `````` Chad Barb committed May 22, 2002 95 96 97 ``````#include #include #include `````` Chad Barb committed May 07, 2002 98 99 100 101 102 `````` // 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 103 ``````#define MAX_NODES 32 `````` Chad Barb committed May 10, 2002 104 105 ``````#define MAX_DIMENSIONS 2 `````` Chad Barb committed May 16, 2002 106 107 ``````// default rounds to keep going without finding a better solution. #define DEFAULT_ROUNDS 512 `````` Chad Barb committed May 07, 2002 108 109 `````` // The size of our "population." `````` Chad Barb committed May 16, 2002 110 ``````// (number of phenotypes) `````` Chad Barb committed May 16, 2002 111 ``````#define SOLUTIONS 400 `````` Chad Barb committed May 07, 2002 112 `````` `````` Chad Barb committed May 16, 2002 113 ``````// The probability a given child will mutate (out of 1000) `````` Chad Barb committed May 16, 2002 114 115 ``````//#define MUTATE_PROB 40 #define MUTATE_PROB 10 `````` Chad Barb committed May 07, 2002 116 `````` `````` Chad Barb committed May 16, 2002 117 118 ``````// probability crossover will happen (out of 1000) #define CROSSOVER_PROB 700 `````` Chad Barb committed May 07, 2002 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 `````` // 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 134 ``````// some code to enable when the solver wedges and we don't know why. `````` Chad Barb committed May 15, 2002 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 ``````#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 154 155 ``````// keep track of user names for nodes. static map< int, string > pnodeNames; `````` Chad Barb committed May 14, 2002 156 ``````static map< string, int > reversePNodeNames; `````` Chad Barb committed May 07, 2002 157 158 159 160 ``````static map< int, string > vnodeNames; static int pnodes, vnodes; `````` Chad Barb committed May 10, 2002 161 162 163 ``````static int pLatency[MAX_DIMENSIONS][MAX_NODES][MAX_NODES]; static int vDesiredLatency[MAX_DIMENSIONS][MAX_NODES][MAX_NODES]; `````` Chad Barb committed May 14, 2002 164 ``````static float plexPenalty = 0.0f; `````` Chad Barb committed May 14, 2002 165 166 167 168 169 ``````static int maxplex[MAX_NODES]; static int userSpecifiedMultiplex = 0; static int fixed[MAX_NODES]; `````` Chad Barb committed May 10, 2002 170 171 172 173 174 175 ``````static int dimensions; static float d2weight; static int verbose = 0; static int minrounds, maxrounds; `````` Chad Barb committed May 07, 2002 176 `````` `````` Chad Barb committed May 16, 2002 177 178 ``````static bool himutate = false; `````` Chad Barb committed May 07, 2002 179 180 181 ``````class Solution { public: `````` Chad Barb committed May 14, 2002 182 `````` int vnode_mapping[MAX_NODES]; `````` Chad Barb committed May 14, 2002 183 184 185 186 187 188 `````` // 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 07, 2002 189 `````` float error; `````` Chad Barb committed May 16, 2002 190 `````` unsigned int prob; `````` Chad Barb committed May 07, 2002 191 192 ``````}; `````` Chad Barb committed May 16, 2002 193 194 195 ``````// 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 196 ``````static Solution pool[SOLUTIONS]; `````` Chad Barb committed May 15, 2002 197 ``````static Solution pool2[SOLUTIONS]; `````` Chad Barb committed May 07, 2002 198 `````` `````` Chad Barb committed May 16, 2002 199 ``````// determines probabilities of selecting each solution. `````` Chad Barb committed May 15, 2002 200 ``````static inline void prepick( Solution * currentPool ) `````` Chad Barb committed May 07, 2002 201 ``````{ `````` Chad Barb committed May 15, 2002 202 203 204 205 206 207 208 `````` float totalFitness = 0.0f; int i; for (i = 0; i < SOLUTIONS; i++) { totalFitness += 1.0f / currentPool[i].error; } `````` Chad Barb committed May 16, 2002 209 `````` unsigned int probsofar = 0; `````` Chad Barb committed May 15, 2002 210 `````` for (i = 0; i < SOLUTIONS; i++) { `````` Chad Barb committed May 16, 2002 211 212 `````` probsofar += (unsigned int)(((float)0xFFFFFFFF / currentPool[i].error) / totalFitness); currentPool[i].prob = probsofar; `````` Chad Barb committed May 15, 2002 213 `````` } `````` Chad Barb committed May 16, 2002 214 215 `````` currentPool[SOLUTIONS - 1].prob = 0xFFFFFFFF; `````` Chad Barb committed May 15, 2002 216 217 ``````} `````` Chad Barb committed May 16, 2002 218 219 ``````// 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 220 221 ``````static inline int pickABest( Solution * currentPool ) { `````` Chad Barb committed May 16, 2002 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 `````` 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 237 `````` `````` Chad Barb committed May 16, 2002 238 239 `````` return mid; /* `````` Chad Barb committed May 15, 2002 240 241 `````` int i = 0; while (1) { `````` Chad Barb committed May 16, 2002 242 `````` if (x < currentPool[i].prob) break; `````` Chad Barb committed May 15, 2002 243 `````` i++; `````` Chad Barb committed May 16, 2002 244 `````` if (i == SOLUTIONS) { printf("Ick.\n"); i = 0; break;} `````` Chad Barb committed May 15, 2002 245 246 `````` } return i - 1; `````` Chad Barb committed May 16, 2002 247 `````` */ `````` Chad Barb committed May 15, 2002 248 249 ``````} `````` Chad Barb committed May 16, 2002 250 `````` `````` Chad Barb committed May 14, 2002 251 ``````// uses a template to avoid massive numbers `````` Chad Barb committed May 07, 2002 252 253 254 255 256 257 258 259 260 261 262 ``````// 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 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 `````` 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 278 `````` { `````` Chad Barb committed May 10, 2002 279 280 281 282 283 `````` 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 284 `````` int is = pLatency[z][ t->vnode_mapping[x] ][ t->vnode_mapping[y] ]; `````` Chad Barb committed May 16, 2002 285 286 287 288 289 290 291 `````` 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 292 293 294 295 296 297 `````` float errDelta; if (z == 0) { errDelta = sqrtf((float)(abs(should - is))); } else { errDelta = d2weight * (float)(abs(should - is)); `````` Chad Barb committed May 14, 2002 298 `````` if (should < is) { errDelta *= 0.5f; } `````` Chad Barb committed May 10, 2002 299 300 301 302 303 304 305 306 `````` } if (verbose) { if (z == 0) { printf("%s -> %s latency (ms) should be %i; is %i (err [sqrt |a-b|] %4.3f)\n", vnodeNames[x].c_str(), vnodeNames[y].c_str(), should, is, errDelta ); } else { `````` Chad Barb committed May 14, 2002 307 `````` 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 308 309 310 `````` 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 311 `````` (should < is) ? "* 0.5 " : "", `````` Chad Barb committed May 10, 2002 312 313 314 315 `````` errDelta ); } } err += errDelta; `````` Chad Barb committed May 07, 2002 316 317 318 319 320 321 322 `````` } } } } } } `````` Chad Barb committed May 10, 2002 323 `````` if (verbose) { printf("error of %4.3f\n", err ); } `````` Chad Barb committed May 07, 2002 324 325 326 327 328 329 330 331 332 333 334 335 336 `````` 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 337 ``````static inline void sortByError( Solution * t ) `````` Chad Barb committed May 07, 2002 338 339 ``````{ // Ahh.. sweet, sweet qsort. `````` Chad Barb committed May 15, 2002 340 `````` qsort( t, SOLUTIONS, sizeof( Solution ), compar ); `````` Chad Barb committed May 07, 2002 341 342 343 344 345 346 347 ``````} // "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 348 `````` BEGIN_LOOP(); `````` Chad Barb committed May 07, 2002 349 `````` while(1) { `````` Chad Barb committed May 15, 2002 350 `````` IN_LOOP(); `````` Chad Barb committed May 07, 2002 351 `````` // forecast calls for a 1% chance of mutation... `````` Chad Barb committed May 16, 2002 352 `````` if ((rand() % 1000) > (himutate ? 500 : MUTATE_PROB)) { break; } `````` Chad Barb committed May 14, 2002 353 354 355 356 `````` if ((rand() % 3)) { // swap mutation. int a, b; `````` Chad Barb committed May 15, 2002 357 358 `````` BEGIN_LOOP(); `````` Chad Barb committed May 14, 2002 359 `````` do { `````` Chad Barb committed May 15, 2002 360 `````` IN_LOOP(); `````` Chad Barb committed May 14, 2002 361 `````` a = rand() % vnodes; `````` Chad Barb committed May 15, 2002 362 363 364 365 366 `````` } while (fixed[a] != -1); BEGIN_LOOP(); do { IN_LOOP(); `````` Chad Barb committed May 14, 2002 367 `````` b = rand() % vnodes; `````` Chad Barb committed May 15, 2002 368 369 370 371 372 373 374 `````` } 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 375 376 377 378 379 380 381 382 383 384 385 386 387 388 `````` } else { // reassign mutation /* int pnode_uses[MAX_NODES]; bzero( pnode_uses, sizeof( pnode_uses ) ); for (int i = 0; i < vnodes; i++) { ++pnode_uses[ t->vnode_mapping[i] ]; } */ int a, b; // find which vnode to remap `````` Chad Barb committed May 15, 2002 389 `````` BEGIN_LOOP(); `````` Chad Barb committed May 14, 2002 390 `````` do { `````` Chad Barb committed May 15, 2002 391 `````` IN_LOOP(); `````` Chad Barb committed May 14, 2002 392 393 394 395 396 397 398 `````` 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 399 `````` BEGIN_LOOP(); `````` Chad Barb committed May 14, 2002 400 `````` do { `````` Chad Barb committed May 15, 2002 401 `````` IN_LOOP(); `````` Chad Barb committed May 14, 2002 402 403 404 405 406 407 408 `````` 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 409 410 411 412 413 414 415 416 `````` } } // 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 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 `````` 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 432 `````` } `````` Chad Barb committed May 16, 2002 433 `````` } else { `````` Chad Barb committed May 07, 2002 434 `````` `````` Chad Barb committed May 16, 2002 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 `````` 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 460 `````` } else { `````` Chad Barb committed May 16, 2002 461 462 463 464 465 466 467 468 469 470 471 472 `````` 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 473 `````` } `````` Chad Barb committed May 07, 2002 474 475 `````` } } else { `````` Chad Barb committed May 16, 2002 476 477 478 `````` 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 479 `````` } else { `````` Chad Barb committed May 16, 2002 480 481 482 483 484 485 486 487 488 489 490 491 `````` 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 492 `````` } `````` Chad Barb committed May 07, 2002 493 494 495 496 497 498 499 500 501 502 503 504 505 `````` } } } } mutate( t ); calcError( t ); } // Generate a random solution // for the initial population. static inline void generateRandomSolution( Solution * t ) { `````` Chad Barb committed May 14, 2002 506 507 `````` //int pnode_uses[MAX_NODES]; bzero( t->pnode_uses, sizeof( t->pnode_uses ) ); `````` Chad Barb committed May 14, 2002 508 509 510 511 `````` for (int i = 0; i < vnodes; i++) { if (fixed[i] != -1) { t->vnode_mapping[i] = fixed[i]; `````` Chad Barb committed May 14, 2002 512 `````` ++t->pnode_uses[ fixed[i] ]; `````` Chad Barb committed May 07, 2002 513 514 `````` } } `````` Chad Barb committed May 14, 2002 515 516 517 518 `````` for (int i = 0; i < vnodes; i++) { if (fixed[i] == -1) { int x; `````` Chad Barb committed May 15, 2002 519 `````` BEGIN_LOOP(); `````` Chad Barb committed May 14, 2002 520 `````` do { `````` Chad Barb committed May 15, 2002 521 `````` IN_LOOP(); `````` Chad Barb committed May 14, 2002 522 `````` x = rand() % pnodes; `````` Chad Barb committed May 14, 2002 523 524 `````` } while( t->pnode_uses[x] >= maxplex[x] ); ++t->pnode_uses[x]; `````` Chad Barb committed May 14, 2002 525 526 527 528 `````` t->vnode_mapping[i] = x; } } `````` Chad Barb committed May 07, 2002 529 530 531 `````` calcError( t ); } `````` Chad Barb committed May 10, 2002 532 ``````void usage( char * appname ) `````` Chad Barb committed May 07, 2002 533 ``````{ `````` Chad Barb committed May 10, 2002 534 535 536 537 `````` fprintf(stderr, "Usage:\n" "%s [-v] [-2 ] [-r ] [-R ]\n\n" " -v extra verbosity\n" `````` Chad Barb committed May 15, 2002 538 `````` " -v -v jumbo verbosity\n" `````` Chad Barb committed May 14, 2002 539 540 `````` " -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 10, 2002 541 542 `````` " -2 enable solving for bandwidth;\n" " multiply bandwidth penalties by .\n" `````` Chad Barb committed May 16, 2002 543 `````` " -r number of rounds to go without a solution before stopping\n" `````` Chad Barb committed May 10, 2002 544 545 546 `````` " default: %i\n" " -R set maximum rounds\n" " default: infinite (-1)\n\n", appname, DEFAULT_ROUNDS ); `````` Chad Barb committed May 15, 2002 547 `````` exit(1); `````` Chad Barb committed May 10, 2002 548 549 ``````} `````` Chad Barb committed May 22, 2002 550 551 552 553 554 555 556 557 558 559 ``````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 560 561 ``````int main( int argc, char ** argv ) { `````` Chad Barb committed May 15, 2002 562 563 `````` int available = 0; int fixedNodeCount = 0; `````` Chad Barb committed May 22, 2002 564 `````` unsigned int bestSpeed = 0; `````` Chad Barb committed May 15, 2002 565 `````` `````` Chad Barb committed May 10, 2002 566 567 568 569 570 571 572 573 574 `````` verbose = 0; dimensions = 1; d2weight = 1.0f / 1000.0f; minrounds = DEFAULT_ROUNDS; maxrounds = -1; int ch; `````` Chad Barb committed May 14, 2002 575 `````` while ((ch = getopt(argc, argv, "v2:r:R:s:m:")) != -1) { `````` Chad Barb committed May 10, 2002 576 `````` switch (ch) { `````` Chad Barb committed May 14, 2002 577 578 579 `````` case 's': srand( atoi( optarg ) ); break; `````` Chad Barb committed May 10, 2002 580 581 582 `````` case 'v': verbose++; break; `````` Chad Barb committed May 14, 2002 583 `````` case 'm': `````` Chad Barb committed May 14, 2002 584 `````` plexPenalty = atof( optarg ); `````` Chad Barb committed May 14, 2002 585 586 `````` userSpecifiedMultiplex++; break; `````` Chad Barb committed May 10, 2002 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 `````` case '2': dimensions = 2; d2weight = atof( optarg ) / 1000.0f; break; case 'r': minrounds = atoi( optarg ); break; case 'R': maxrounds = atoi( optarg ); break; default: usage( argv[0] ); } } `````` Chad Barb committed May 22, 2002 603 `````` char line[4096]; `````` Chad Barb committed May 07, 2002 604 605 `````` { `````` Chad Barb committed May 15, 2002 606 `````` if (verbose > 1) { printf("How many physical nodes?\n"); } `````` Chad Barb committed May 07, 2002 607 608 609 `````` gets( line ); sscanf( line, "%i", &pnodes ); `````` Chad Barb committed May 15, 2002 610 `````` if (verbose > 1) { printf("Okay, enter %i names for the physical nodes, one per line.\n", pnodes ); } `````` Chad Barb committed May 07, 2002 611 612 613 614 615 `````` 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 616 617 618 619 `````` reversePNodeNames[string(name)] = i; } if (userSpecifiedMultiplex) { `````` Chad Barb committed May 15, 2002 620 `````` if (verbose > 1) { printf("Enter %i numbers, one per line, indicating the" `````` Chad Barb committed May 14, 2002 621 622 623 624 625 `````` " 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 626 `````` available += maxplex[i]; `````` Chad Barb committed May 14, 2002 627 628 629 630 `````` } } else { for (int i = 0; i < pnodes; i++) { maxplex[i] = 1; `````` Chad Barb committed May 15, 2002 631 `````` ++available; `````` Chad Barb committed May 14, 2002 632 `````` } `````` Chad Barb committed May 07, 2002 633 634 `````` } `````` Chad Barb committed May 10, 2002 635 `````` for (int z = 0; z < dimensions; z++) { `````` Chad Barb committed May 15, 2002 636 `````` if (verbose > 1) { `````` Chad Barb committed May 10, 2002 637 638 639 640 641 642 643 644 645 `````` printf("Enter %ix%i grid o' actual %s.\n", pnodes, pnodes, (z == 0) ? "latency" : "bandwidth"); } 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++) { sscanf( linePos, "%i", &pLatency[z][x][y] ); `````` Chad Barb committed May 16, 2002 646 647 648 649 650 `````` if (z == 1) { if (pLatency[z][x][y] != -1) { pLatency[z][x][y] = (int)( logf(pLatency[z][x][y]) * 1000.0f ); } } `````` Chad Barb committed May 10, 2002 651 652 653 `````` while (*linePos != ' ' && *linePos != '\n') { linePos++; } while (*linePos == ' ') { linePos++; } } `````` Chad Barb committed May 07, 2002 654 655 656 657 658 `````` } } } { `````` Chad Barb committed May 15, 2002 659 `````` if (verbose > 1) { printf("How many virtual nodes?\n"); } `````` Chad Barb committed May 07, 2002 660 661 662 `````` gets( line ); sscanf( line, "%i", &vnodes ); `````` Chad Barb committed May 15, 2002 663 664 665 666 667 668 669 670 671 672 673 `````` 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 674 675 `````` for (int i = 0; i < vnodes; i++) { char name[1024]; `````` Chad Barb committed May 15, 2002 676 `````` char pname[1024]; `````` Chad Barb committed May 07, 2002 677 `````` gets( line ); `````` Chad Barb committed May 15, 2002 678 679 `````` if (sscanf( line, "%s %s", name, pname ) == 2) { map< string, int >::iterator it = reversePNodeNames.find( string( pname ) ); `````` Chad Barb committed May 14, 2002 680 `````` if (it == reversePNodeNames.end()) { `````` Chad Barb committed May 15, 2002 681 682 `````` fprintf(stderr,"pnode '%s' does not exist; can't fix.\n", pname ); exit(3); `````` Chad Barb committed May 14, 2002 683 `````` } `````` Chad Barb committed May 15, 2002 684 685 `````` if (verbose > 1) { printf("Fixing assignment from vnode %s to pnode %s.\n", name, pname ); `````` Chad Barb committed May 14, 2002 686 `````` } `````` Chad Barb committed May 15, 2002 687 688 `````` fixed[i] = reversePNodeNames[ string( pname ) ]; fixedNodeCount++; `````` Chad Barb committed May 14, 2002 689 690 691 `````` } else { fixed[i] = -1; } `````` Chad Barb committed May 15, 2002 692 `````` vnodeNames[i] = string( name ); `````` Chad Barb committed May 07, 2002 693 694 `````` } `````` Chad Barb committed May 10, 2002 695 `````` for (int z = 0; z < dimensions; z++) { `````` Chad Barb committed May 15, 2002 696 `````` if (verbose > 1) { `````` Chad Barb committed May 10, 2002 697 698 `````` printf("Enter %ix%i grid o' desired %s (-1 is don't care.)\n", vnodes, vnodes, (z == 0) ? "latency" : "bandwidth"); `````` Chad Barb committed May 07, 2002 699 `````` } `````` Chad Barb committed May 10, 2002 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 `````` 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++) { sscanf( linePos, "%i", &vDesiredLatency[z][x][y] ); if (z == 1) { if (vDesiredLatency[z][x][y] != -1) { vDesiredLatency[z][x][y] = (int)(logf(vDesiredLatency[z][x][y]) * 1000.0f); } } while (*linePos != ' ' && *linePos != '\n') { linePos++; } while (*linePos == ' ') { linePos++; } } } } } `````` Chad Barb committed May 07, 2002 717 `````` `````` Chad Barb committed May 15, 2002 718 719 720 `````` Solution * currentPool = pool; Solution * nextPool = pool2; `````` Chad Barb committed May 15, 2002 721 722 `````` if (fixedNodeCount < vnodes) { if (verbose) { printf("Now running...\n"); } `````` Chad Barb committed May 07, 2002 723 `````` `````` Chad Barb committed May 15, 2002 724 725 `````` { for (int i = 0; i < SOLUTIONS; i++) { `````` Chad Barb committed May 15, 2002 726 `````` generateRandomSolution( &(currentPool[i]) ); `````` Chad Barb committed May 15, 2002 727 `````` } `````` Chad Barb committed May 15, 2002 728 `````` sortByError( currentPool ); `````` Chad Barb committed May 07, 2002 729 730 731 `````` } int highestFoundRound = 0; `````` Chad Barb committed May 15, 2002 732 733 `````` float last = currentPool[0].error; `````` Chad Barb committed May 16, 2002 734 `````` himutate = false; `````` Chad Barb committed May 16, 2002 735 `````` for (int i = 0; i != maxrounds && i < (highestFoundRound + minrounds); i++) { `````` Chad Barb committed May 15, 2002 736 `````` /* `````` Chad Barb committed May 16, 2002 737 `````` `````` Chad Barb committed May 15, 2002 738 `````` */ `````` Chad Barb committed May 16, 2002 739 740 741 742 743 744 745 746 747 748 749 750 `````` 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 751 `````` `````` Chad Barb committed May 16, 2002 752 `````` if (verbose && !(i % 100)) { `````` Chad Barb committed May 16, 2002 753 `````` 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 754 `````` } `````` Chad Barb committed May 15, 2002 755 `````` `````` Chad Barb committed May 15, 2002 756 `````` if (currentPool[0].error < last) { `````` Chad Barb committed May 10, 2002 757 758 `````` if (verbose) { printf("Better solution found in round %i (error %4.3f)\n", `````` Chad Barb committed May 15, 2002 759 `````` i, currentPool[0].error); `````` Chad Barb committed May 10, 2002 760 `````` } `````` Chad Barb committed May 22, 2002 761 `````` bestSpeed = msecscpu(); `````` Chad Barb committed May 15, 2002 762 `````` last = currentPool[0].error; `````` Chad Barb committed May 07, 2002 763 764 `````` highestFoundRound = i; } `````` Chad Barb committed May 15, 2002 765 `````` `````` Chad Barb committed May 16, 2002 766 767 `````` // 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 768 769 770 771 772 `````` memcpy( &(nextPool[0]), &(currentPool[0]), sizeof( Solution ) ); prepick( currentPool ); int j; `````` Chad Barb committed May 16, 2002 773 774 775 776 777 778 `````` // 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 779 780 781 782 783 `````` splice( &(nextPool[j]), &(currentPool[pickABest( currentPool )]), &(currentPool[pickABest( currentPool )]) ); } `````` Chad Barb committed May 16, 2002 784 785 `````` if (stddev < 0.1f) { himutate = false; `````` Chad Barb committed May 15, 2002 786 `````` } `````` Chad Barb committed May 16, 2002 787 788 789 790 791 792 793 `````` /* printf("NUKE!\n"); for (j = SOLUTIONS - 10; j != SOLUTIONS; j++) { generateRandomSolution( &(nextPool[j]) ); } } */ `````` Chad Barb committed May 15, 2002 794 `````` /* `````` Chad Barb committed May 07, 2002 795 796 797 798 799 800 `````` for (int j = 0; j < CHILDREN_PER_ROUND; j++) { // Overwrite a "bad" solution with the child of two "good" ones. splice( &(pool[pickAWorst()]), &(pool[pickABest()]), &(pool[pickABest()]) ); } `````` Chad Barb committed May 15, 2002 801 802 803 804 805 806 807 808 `````` */ sortByError( nextPool ); Solution * temp = currentPool; currentPool = nextPool; nextPool = temp; if (currentPool[0].error < EPSILON) { `````` Chad Barb committed May 15, 2002 809 `````` if (verbose > 1) { printf("Found perfect solution.\n"); } `````` Chad Barb committed May 07, 2002 810 811 812 `````` break; } } `````` Chad Barb committed May 15, 2002 813 814 `````` } 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 815 816 817 `````` } { `````` Chad Barb committed May 10, 2002 818 `````` if (verbose) { printf("\nYour solution is as follows:\n"); } `````` Chad Barb committed May 14, 2002 819 `````` for (int x = 0; x < vnodes; x++) { `````` Chad Barb committed May 15, 2002 820 821 `````` if (pnodeNames.find( currentPool[0].vnode_mapping[x] ) == pnodeNames.end()) { pnodeNames[ currentPool[0].vnode_mapping[x] ] = "CRAP"; `````` Chad Barb committed May 15, 2002 822 823 824 `````` } printf("%s mapsTo %s\n", vnodeNames[x].c_str(), `````` Chad Barb committed May 15, 2002 825 `````` pnodeNames[currentPool[0].vnode_mapping[x]].c_str() ); `````` Chad Barb committed May 07, 2002 826 `````` } `````` Chad Barb committed May 14, 2002 827 `````` `````` Chad Barb committed May 07, 2002 828 829 830 `````` printf("\n"); // dump a detailed report of the returned solution's errors. `````` Chad Barb committed May 22, 2002 831 832 833 834 `````` if (verbose > 1) { calcError( &(currentPool[0]) ); printf("Found in %i msecs\n", bestSpeed ); } `````` Chad Barb committed May 07, 2002 835 836 `````` } `````` Chad Barb committed May 15, 2002 837 `````` if (verbose > 1) { printf("Bye now.\n"); } `````` Chad Barb committed May 07, 2002 838 839 `````` return 0; }``````