wanlinksolve.cc 18.4 KB
Newer Older
1 2 3 4 5
/**** 
 wanlinksolve - 
 A Reasonably Effective Algorithm for Genetically Assigning Nodes.
 Chad Barb, May 3, 2002

6
 Applies a standard genetic algorithm (with crossover)
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's avatar
Chad Barb committed
16
 switches: 
Chad Barb's avatar
Chad Barb committed
17 18
   -v     Extra verbosity
   -v -v  Jumbo verbosity 
Chad Barb's avatar
Chad Barb committed
19 20

   -2 <weight>
21
       Solve for 2nd (bandwidth) dimension;
Chad Barb's avatar
Chad Barb committed
22 23 24 25 26
       Penalty for error is sum of differences of natural logs,
       multiplied by <weight>.
       A good weight seems to be around 7, but the appropriate
       value is pretty much application-dependent.

27 28 29
   -m <plexpenalty>
       Handle multiple virtual->physical mapping.
       For each vnode beyond 1 assigned to a pnode, <plexpenalty> will be assessed.
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)

33 34 35
   -s <seed>
       Use a specific random seed.

Chad Barb's avatar
Chad Barb committed
36 37 38 39 40 41 42 43 44 45
   -r <minrounds>
       Specify the minimum number of rounds to go before stopping.
       Note that the algorithm won't actually stop until
       round 3n, where "n" is the round which found the best solution so far,
       or if it hits maxrounds.
       default: DEFAULT_ROUNDS

   -R <maxrounds>
       Specify the absolute maximum number of rounds.
       default: -1 (infinite)
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
53 54
 ? 'p' lines containing the maximum number of virtual nodes each 
       physical node can accommodate. ('-m' switch only)
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's avatar
Chad Barb committed
58 59
 ? 'p' lines, a P x P matrix of actual bandwidth ('-2' switch only)

60 61

 * One line containing a single number 'v'-- the number of virtual nodes.
62
 * 'v' lines containing the name of each virtual node.
Chad Barb's avatar
Chad Barb committed
63 64
       appending a space then the name of a physical node will permanently
       "fix" the mapping of this vnode to the named pnode.
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's avatar
Chad Barb committed
71
 ? 'v' lines, a V x V matrix of desired bandwidth ('-2' switch only)
72 73 74 75

 output format:
 
 Easily inferred. Note that the perl regexp:
76
 /(\S+)\smapsTo\s(\S+)/
77 78 79 80 81 82
 will grab vnode to pnode mappings (in $1 and $2, respectively.)
 
****/

#include <stdio.h>
#include <stdlib.h>
Chad Barb's avatar
Chad Barb committed
83 84
#include <stdarg.h>
#include <unistd.h>
Chad Barb's avatar
Chad Barb committed
85
#include <assert.h>
86 87 88 89 90 91 92
#include <math.h>

// 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's avatar
Chad Barb committed
93 94 95
#define MAX_DIMENSIONS 2

#define DEFAULT_ROUNDS 160
96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125

// The size of our "population."
// (100,000 seems to work well.)
#define SOLUTIONS 100000

// The number of new children to produce each round.
// (20,000 seems to work well.)
#define CHILDREN_PER_ROUND 20000

// 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.
#define MUTATE_PROB 500

// 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 <map>
#include <string>

// BAM!
using namespace std;

// keep freebsd from mumbling about gets(3) being unsafe.
#define gets( x ) fgets( x, sizeof( x ), stdin  )

Chad Barb's avatar
Chad Barb committed
126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
#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

145 146
// keep track of user names for nodes.
static map< int, string > pnodeNames;
147
static map< string, int > reversePNodeNames;
148 149 150 151
static map< int, string > vnodeNames;

static int pnodes, vnodes;

Chad Barb's avatar
Chad Barb committed
152 153 154
static int pLatency[MAX_DIMENSIONS][MAX_NODES][MAX_NODES];
static int vDesiredLatency[MAX_DIMENSIONS][MAX_NODES][MAX_NODES];

155
static float plexPenalty = 0.0f;
156 157 158 159 160
static int maxplex[MAX_NODES];
static int userSpecifiedMultiplex = 0;

static int fixed[MAX_NODES];

Chad Barb's avatar
Chad Barb committed
161 162 163 164 165 166
static int dimensions;
static float d2weight;

static int verbose = 0;

static int minrounds, maxrounds;
167 168 169 170

class Solution
{
public:
171
  int vnode_mapping[MAX_NODES];
172 173 174 175 176 177

  // 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];

178 179 180 181 182 183 184 185 186 187 188 189 190 191 192
  float error;
};

static Solution pool[SOLUTIONS];

static inline int pickABest()
{
  // a hacky (but damn fast) probibility curve to
  // favor mating better solutions.

  switch (rand() % 4) {
  case 0: return rand() % (SOLUTIONS / 32);
  case 1: return rand() % (SOLUTIONS / 16);
  case 2: return rand() % (SOLUTIONS / 4);
  case 3: return rand() % (SOLUTIONS / 2);
193
  default: return 0; // can't happen, but -Wall doesn't realize this.
194 195 196 197 198 199 200 201
  }
}

static inline int pickAWorst()
{
  return SOLUTIONS - pickABest();
}

202
// uses a template to avoid massive numbers
203 204 205 206 207 208 209 210 211 212 213
// of "if" choices.. compiler should generate two versions,
// one with dump and one without.
template <bool verbose>
static inline void calcError( Solution * t )
{ 
  float err = 0.0f;

  if (verbose) {
    printf("Error listing:\n");
  }

214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
  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;
      }
    }
  }

229
  {
Chad Barb's avatar
Chad Barb committed
230 231 232 233 234
    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) {
235
	    int is     = pLatency[z][ t->vnode_mapping[x] ][ t->vnode_mapping[y] ];
Chad Barb's avatar
Chad Barb committed
236 237 238 239 240 241 242
	    if (should != is) { 
	      float errDelta;

	      if (z == 0) {
		errDelta = sqrtf((float)(abs(should - is)));
	      } else {
		errDelta = d2weight * (float)(abs(should - is));
243
		if (should < is) { errDelta *= 0.5f; }
Chad Barb's avatar
Chad Barb committed
244 245 246 247 248 249 250 251
	      }

	      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 {
252
		  printf("%s -> %s bandwidth (kB/s) should be ~%i; is ~%i (err [wt %s* ln (a/b)] %4.3f)\n", 
Chad Barb's avatar
Chad Barb committed
253 254 255
			 vnodeNames[x].c_str(), vnodeNames[y].c_str(), 
			 (int)expf((float)should / 1000.0f), 
			 (int)expf((float)is / 1000.0f),
256
			 (should < is) ? "* 0.5 " : "",
Chad Barb's avatar
Chad Barb committed
257 258 259 260
			 errDelta );
		}
	      }
	      err += errDelta;
261 262 263 264 265 266 267
	    }
	  }
	}
      }
    }
  }

Chad Barb's avatar
Chad Barb committed
268
  if (verbose) { printf("error of %4.3f\n", err ); }
269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292
  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; }
}

static inline void sortByError()
{
  // Ahh.. sweet, sweet qsort.
  qsort( pool, SOLUTIONS, sizeof( Solution ), compar );
}

// "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's avatar
Chad Barb committed
293
  BEGIN_LOOP();
294
  while(1) {
Chad Barb's avatar
Chad Barb committed
295
    IN_LOOP();
296 297
    // forecast calls for a 1% chance of mutation...
    if ((rand() % 1000) < MUTATE_PROB) { break; }
298 299 300 301
    
    if ((rand() % 3)) {
      // swap mutation. 
      int a, b;
Chad Barb's avatar
Chad Barb committed
302 303

      BEGIN_LOOP();
304
      do {
Chad Barb's avatar
Chad Barb committed
305
	IN_LOOP();
306
	a = rand() % vnodes;
Chad Barb's avatar
Chad Barb committed
307 308 309 310 311
      } while (fixed[a] != -1);

      BEGIN_LOOP();
      do {
	IN_LOOP();
312
	b = rand() % vnodes;
Chad Barb's avatar
Chad Barb committed
313 314 315 316 317 318 319
      } 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;
      }
320 321 322 323 324 325 326 327 328 329 330 331 332 333
    } 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's avatar
Chad Barb committed
334
      BEGIN_LOOP();
335
      do {
Chad Barb's avatar
Chad Barb committed
336
	IN_LOOP();
337 338 339 340 341 342 343
	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's avatar
Chad Barb committed
344
      BEGIN_LOOP();
345
      do {
Chad Barb's avatar
Chad Barb committed
346
	IN_LOOP();
347 348 349 350 351 352 353
	b = rand() % pnodes;
      } while (t->pnode_uses[b] >= maxplex[b]);

      // now map it.
      t->vnode_mapping[a] = b;
      ++t->pnode_uses[b];
    }
354 355 356 357 358 359 360 361
  }
}

// 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)
{
362 363 364
  // temp storage so we don't clobber t unless the child turns out to be
  // cromulent.
  int vnode_mapping_t[MAX_NODES]; 
365
  int pnode_uses_t[MAX_NODES];
366

367
  bzero( pnode_uses_t, sizeof( pnode_uses_t ) );
368 369 370 371

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] != -1) {
      vnode_mapping_t[i] = fixed[i];
372
      ++pnode_uses_t[ fixed[i] ];
373 374 375 376 377 378 379 380 381 382 383 384 385 386
    }
  }

  // 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;
387
    if (fixed[pos] != -1) continue;
388
    if (rand() % 2) {
389
      if (pnode_uses_t[ a->vnode_mapping[pos] ] < maxplex[ a->vnode_mapping[pos] ]) {
390
	vnode_mapping_t[pos] = a->vnode_mapping[pos];
391
	++pnode_uses_t[ a->vnode_mapping[pos] ];
392
      } else {
393
	if (pnode_uses_t[ b->vnode_mapping[pos] ] < maxplex[ b->vnode_mapping[pos] ]) {
394
	  vnode_mapping_t[pos] = b->vnode_mapping[pos];
395
	  ++pnode_uses_t[ b->vnode_mapping[pos] ];
396 397 398 399 400 401
	} else {
	  // failed mating.
	  return;
	}
      }
    } else {
402
      if (pnode_uses_t[ b->vnode_mapping[pos] ] < maxplex[ b->vnode_mapping[pos] ]) {
403
	vnode_mapping_t[pos] = b->vnode_mapping[pos];
404
	++pnode_uses_t[ b->vnode_mapping[pos] ];
405
      } else {
406
	if (pnode_uses_t[ a->vnode_mapping[pos] ] < maxplex[ a->vnode_mapping[pos] ]) {
407
	  vnode_mapping_t[pos] = a->vnode_mapping[pos];
408
	  ++pnode_uses_t[ a->vnode_mapping[pos] ];
409 410 411 412 413 414 415 416
	} else {
	  // failed mating.
	  return;
	}
      }
    }
  }

417 418
  // ok.. good one..
  // since we have a cromulent child, we now clobber t.
419
  for(int d = 0; d < vnodes; d++) {
420 421 422 423 424
    t->vnode_mapping[d] = vnode_mapping_t[d];
  }

  for(int e = 0; e < pnodes; e++) {
    t->pnode_uses[e] = pnode_uses_t[e];
425 426 427 428 429 430 431 432 433 434 435 436
  }

  // Mazeltov!

  mutate( t );
  calcError<false>( t );  
} 

// Generate a random solution 
// for the initial population.
static inline void generateRandomSolution( Solution * t )
{
437 438
  //int pnode_uses[MAX_NODES];
  bzero( t->pnode_uses, sizeof( t->pnode_uses ) );
439 440 441 442

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] != -1) {
      t->vnode_mapping[i] = fixed[i];
443
      ++t->pnode_uses[ fixed[i] ];
444 445
    }
  }
446 447 448 449

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] == -1) {
      int x;
Chad Barb's avatar
Chad Barb committed
450
      BEGIN_LOOP();
451
      do {
Chad Barb's avatar
Chad Barb committed
452
	IN_LOOP();
453
	x = rand() % pnodes;
454 455
      } while( t->pnode_uses[x] >= maxplex[x] );
      ++t->pnode_uses[x];
456 457 458 459
      t->vnode_mapping[i] = x;
    }
  }

460 461 462
  calcError<false>( t );
}

Chad Barb's avatar
Chad Barb committed
463
void usage( char * appname )
464
{
Chad Barb's avatar
Chad Barb committed
465 466 467 468
  fprintf(stderr,
	  "Usage:\n"
	  "%s [-v] [-2 <weight>] [-r <minrounds>] [-R <maxrounds>]\n\n"
	  "  -v              extra verbosity\n"
Chad Barb's avatar
Chad Barb committed
469
	  "  -v -v           jumbo verbosity\n"
470 471
	  "  -m <penalty>    enable many-to-one virtual to physical mappings\n"
	  "  -s <seed>       seed the random number generator with a specific value\n"
Chad Barb's avatar
Chad Barb committed
472 473 474 475 476 477
	  "  -2 <weight>     enable solving for bandwidth;\n"
	  "                  multiply bandwidth penalties by <weight>.\n"
	  "  -r <minrounds>  set minimum rounds (a.k.a. generations)\n"
	  "                  default: %i\n"
	  "  -R <maxrounds>  set maximum rounds\n"
	  "                  default: infinite (-1)\n\n", appname, DEFAULT_ROUNDS );
Chad Barb's avatar
Chad Barb committed
478
  exit(1);
Chad Barb's avatar
Chad Barb committed
479 480 481 482
}

int main( int argc, char ** argv )
{
Chad Barb's avatar
Chad Barb committed
483 484 485
  int available = 0;
  int fixedNodeCount = 0;

Chad Barb's avatar
Chad Barb committed
486 487 488 489 490 491 492 493 494
  verbose = 0;
  dimensions = 1;
  d2weight = 1.0f / 1000.0f;

  minrounds = DEFAULT_ROUNDS;
  maxrounds = -1;

  int ch;

495
  while ((ch = getopt(argc, argv, "v2:r:R:s:m:")) != -1) {
Chad Barb's avatar
Chad Barb committed
496
    switch (ch) {
497 498 499
    case 's':
      srand( atoi( optarg ) );
      break;
Chad Barb's avatar
Chad Barb committed
500 501 502
    case 'v': 
      verbose++; 
      break;
503
    case 'm':
504
      plexPenalty = atof( optarg );
505 506
      userSpecifiedMultiplex++;
      break;
Chad Barb's avatar
Chad Barb committed
507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522
    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] );
    }
  }


523 524 525
  char line[1024];

  {
Chad Barb's avatar
Chad Barb committed
526
    if (verbose > 1) { printf("How many physical nodes?\n"); }
527 528 529
    gets( line );
    sscanf( line, "%i", &pnodes );

Chad Barb's avatar
Chad Barb committed
530
    if (verbose > 1) { printf("Okay, enter %i names for the physical nodes, one per line.\n", pnodes ); }
531 532 533 534 535
    for (int i = 0; i < pnodes; i++) {
      char name[1024];
      gets( line );
      sscanf( line, "%s", name );
      pnodeNames[i] = string( name );
536 537 538 539
      reversePNodeNames[string(name)] = i;
    }

    if (userSpecifiedMultiplex) {
Chad Barb's avatar
Chad Barb committed
540
      if (verbose > 1) { printf("Enter %i numbers, one per line, indicating the"
541 542 543 544 545
			    " 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's avatar
Chad Barb committed
546
	available += maxplex[i];
547 548 549 550
      }
    } else {
      for (int i = 0; i < pnodes; i++) {
	maxplex[i] = 1;
Chad Barb's avatar
Chad Barb committed
551
	++available;
552
      }
553 554
    }

Chad Barb's avatar
Chad Barb committed
555
    for (int z = 0; z < dimensions; z++) {
Chad Barb's avatar
Chad Barb committed
556
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
557 558 559 560 561 562 563 564 565 566 567 568 569
	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++; }
	}
570 571 572 573 574
      }
    }
  } 

  {
Chad Barb's avatar
Chad Barb committed
575
    if (verbose > 1) { printf("How many virtual nodes?\n"); }
576 577 578
    gets( line );
    sscanf( line, "%i", &vnodes );

Chad Barb's avatar
Chad Barb committed
579 580 581 582 583 584 585 586 587 588 589
    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 ); }

590 591
    for (int i = 0; i < vnodes; i++) {
      char name[1024];
Chad Barb's avatar
Chad Barb committed
592
      char pname[1024];
593
      gets( line );
Chad Barb's avatar
Chad Barb committed
594 595
      if (sscanf( line, "%s %s", name, pname ) == 2) {
	map< string, int >::iterator it = reversePNodeNames.find( string( pname ) );
596
	if (it == reversePNodeNames.end()) {
Chad Barb's avatar
Chad Barb committed
597 598
	  fprintf(stderr,"pnode '%s' does not exist; can't fix.\n", pname );
	  exit(3);
599
	}
Chad Barb's avatar
Chad Barb committed
600 601
	if (verbose > 1) { 
	  printf("Fixing assignment from vnode %s to pnode %s.\n", name, pname );
602
	}
Chad Barb's avatar
Chad Barb committed
603 604
	fixed[i] = reversePNodeNames[ string( pname ) ];
	fixedNodeCount++;
605 606 607
      } else {
	fixed[i] = -1;
      }
Chad Barb's avatar
Chad Barb committed
608
      vnodeNames[i] = string( name );
609 610
    }

Chad Barb's avatar
Chad Barb committed
611
    for (int z = 0; z < dimensions; z++) {
Chad Barb's avatar
Chad Barb committed
612
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
613 614
	printf("Enter %ix%i grid o' desired %s (-1 is don't care.)\n", vnodes, vnodes, 
	       (z == 0) ? "latency" : "bandwidth");
615
      }
Chad Barb's avatar
Chad Barb committed
616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632
      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++; }
	}
      }
    } 
  }
633

Chad Barb's avatar
Chad Barb committed
634 635
  if (fixedNodeCount < vnodes) {
    if (verbose) { printf("Now running...\n"); }
636

Chad Barb's avatar
Chad Barb committed
637 638 639 640 641
    {
      for (int i = 0; i < SOLUTIONS; i++) {
	generateRandomSolution( &(pool[i]) );
      }
      sortByError();
642 643 644 645
    }

    int highestFoundRound = 0;
    float last = pool[0].error;
Chad Barb's avatar
Chad Barb committed
646 647
    for (int i = 0; i != maxrounds && (i < minrounds || i < highestFoundRound * 3); i++) {
      if (verbose && !(i % (minrounds / 10))) {
648 649
	printf("Round %i. (best %4.3f)\n", i, pool[0].error);
      }
Chad Barb's avatar
Chad Barb committed
650
      
651
      if (pool[0].error < last) {
Chad Barb's avatar
Chad Barb committed
652 653
	if (verbose) {
	  printf("Better solution found in round %i (error %4.3f)\n", 
Chad Barb's avatar
Chad Barb committed
654
		 i, pool[0].error);
Chad Barb's avatar
Chad Barb committed
655
	}
656 657 658
	last = pool[0].error;
	highestFoundRound = i;
      }
Chad Barb's avatar
Chad Barb committed
659
      
660 661 662 663 664 665 666 667
      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()]) ); 
      }
      sortByError();
      if (pool[0].error < EPSILON) { 
Chad Barb's avatar
Chad Barb committed
668
	if (verbose > 1) { printf("Found perfect solution.\n"); }
669 670 671
	break;
      }
    }
Chad Barb's avatar
Chad Barb committed
672 673
  } else {
    if (verbose) { printf("No non-fixed vnodes (or no vnodes at all,) so nothing to be done!\n"); }
674 675 676
  }

  {
Chad Barb's avatar
Chad Barb committed
677
    if (verbose) { printf("\nYour solution is as follows:\n"); }
678
    for (int x = 0; x < vnodes; x++) {
Chad Barb's avatar
Chad Barb committed
679 680 681 682 683 684
      if (pnodeNames.find( pool[0].vnode_mapping[x] ) == pnodeNames.end()) {
	pnodeNames[ pool[0].vnode_mapping[x] ] = "CRAP";
      }
      printf("%s mapsTo %s\n", 
	     vnodeNames[x].c_str(),
	     pnodeNames[pool[0].vnode_mapping[x]].c_str() );
685
    }
686

687 688 689
    printf("\n");

    // dump a detailed report of the returned solution's errors.
Chad Barb's avatar
Chad Barb committed
690
    if (verbose > 1) { calcError<true>( &(pool[0]) ); }
691 692
  }

Chad Barb's avatar
Chad Barb committed
693
  if (verbose > 1) { printf("Bye now.\n"); }
694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709
  return 0;
}