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