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

Chad Barb's avatar
Chad Barb committed
6
 Applies a standard genetic algorithm (with crossover and elitism)
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
   -r <roundswobetter>
       Specify the number of rounds to continue going without a better solution.
Chad Barb's avatar
Chad Barb committed
38 39 40 41 42
       default: DEFAULT_ROUNDS

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

57 58

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

 output format:
 
 Easily inferred. Note that the perl regexp:
73
 /(\S+)\smapsTo\s(\S+)/
74
 will grab vnode to pnode mappings (in $1 and $2, respectively.)
Chad Barb's avatar
Chad Barb committed
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.


86 87 88 89 90
 
****/

#include <stdio.h>
#include <stdlib.h>
Chad Barb's avatar
Chad Barb committed
91 92
#include <stdarg.h>
#include <unistd.h>
Chad Barb's avatar
Chad Barb committed
93
#include <assert.h>
94 95 96 97 98 99 100
#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
101 102
#define MAX_DIMENSIONS 2

Chad Barb's avatar
Chad Barb committed
103
#define DEFAULT_ROUNDS 256
104 105

// The size of our "population."
Chad Barb's avatar
Chad Barb committed
106
// (number of phenotypes)
107
#define SOLUTIONS 500
108

Chad Barb's avatar
Chad Barb committed
109 110
// The probability a given child will mutate (out of 1000)
#define MUTATE_PROB 40
111

Chad Barb's avatar
Chad Barb committed
112 113
// probability crossover will happen (out of 1000)
#define CROSSOVER_PROB 700
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 <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
129
// some code to enable when the solver wedges and we don't know why.
Chad Barb's avatar
Chad Barb committed
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148
#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

149 150
// keep track of user names for nodes.
static map< int, string > pnodeNames;
151
static map< string, int > reversePNodeNames;
152 153 154 155
static map< int, string > vnodeNames;

static int pnodes, vnodes;

Chad Barb's avatar
Chad Barb committed
156 157 158
static int pLatency[MAX_DIMENSIONS][MAX_NODES][MAX_NODES];
static int vDesiredLatency[MAX_DIMENSIONS][MAX_NODES][MAX_NODES];

159
static float plexPenalty = 0.0f;
160 161 162 163 164
static int maxplex[MAX_NODES];
static int userSpecifiedMultiplex = 0;

static int fixed[MAX_NODES];

Chad Barb's avatar
Chad Barb committed
165 166 167 168 169 170
static int dimensions;
static float d2weight;

static int verbose = 0;

static int minrounds, maxrounds;
171 172 173 174

class Solution
{
public:
175
  int vnode_mapping[MAX_NODES];
176 177 178 179 180 181

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

182
  float error;
183
  float prob;
184 185
};

Chad Barb's avatar
Chad Barb committed
186 187 188
// 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)
189
static Solution pool[SOLUTIONS];
190
static Solution pool2[SOLUTIONS];
191

Chad Barb's avatar
Chad Barb committed
192
// determines probabilities of selecting each solution.
193
static inline void prepick( Solution * currentPool )
194
{
195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220
  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;
}

221
// uses a template to avoid massive numbers
222 223 224 225 226 227 228 229 230 231 232
// 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");
  }

233 234 235 236 237 238 239 240 241 242 243 244 245 246 247
  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;
      }
    }
  }

248
  {
Chad Barb's avatar
Chad Barb committed
249 250 251 252 253
    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) {
254
	    int is     = pLatency[z][ t->vnode_mapping[x] ][ t->vnode_mapping[y] ];
Chad Barb's avatar
Chad Barb committed
255 256 257 258 259 260 261
	    if (should != is) { 
	      float errDelta;

	      if (z == 0) {
		errDelta = sqrtf((float)(abs(should - is)));
	      } else {
		errDelta = d2weight * (float)(abs(should - is));
262
		if (should < is) { errDelta *= 0.5f; }
Chad Barb's avatar
Chad Barb committed
263 264 265 266 267 268 269 270
	      }

	      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 {
271
		  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
272 273 274
			 vnodeNames[x].c_str(), vnodeNames[y].c_str(), 
			 (int)expf((float)should / 1000.0f), 
			 (int)expf((float)is / 1000.0f),
275
			 (should < is) ? "* 0.5 " : "",
Chad Barb's avatar
Chad Barb committed
276 277 278 279
			 errDelta );
		}
	      }
	      err += errDelta;
280 281 282 283 284 285 286
	    }
	  }
	}
      }
    }
  }

Chad Barb's avatar
Chad Barb committed
287
  if (verbose) { printf("error of %4.3f\n", err ); }
288 289 290 291 292 293 294 295 296 297 298 299 300
  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; }
}

301
static inline void sortByError( Solution * t )
302 303
{
  // Ahh.. sweet, sweet qsort.
304
  qsort( t, SOLUTIONS, sizeof( Solution ), compar );
305 306 307 308 309 310 311
}

// "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
312
  BEGIN_LOOP();
313
  while(1) {
Chad Barb's avatar
Chad Barb committed
314
    IN_LOOP();
315
    // forecast calls for a 1% chance of mutation...
Chad Barb's avatar
Chad Barb committed
316
    if ((rand() % 1000) > MUTATE_PROB) { break; }
317 318 319 320
    
    if ((rand() % 3)) {
      // swap mutation. 
      int a, b;
Chad Barb's avatar
Chad Barb committed
321 322

      BEGIN_LOOP();
323
      do {
Chad Barb's avatar
Chad Barb committed
324
	IN_LOOP();
325
	a = rand() % vnodes;
Chad Barb's avatar
Chad Barb committed
326 327 328 329 330
      } while (fixed[a] != -1);

      BEGIN_LOOP();
      do {
	IN_LOOP();
331
	b = rand() % vnodes;
Chad Barb's avatar
Chad Barb committed
332 333 334 335 336 337 338
      } 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;
      }
339 340 341 342 343 344 345 346 347 348 349 350 351 352
    } 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
353
      BEGIN_LOOP();
354
      do {
Chad Barb's avatar
Chad Barb committed
355
	IN_LOOP();
356 357 358 359 360 361 362
	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
363
      BEGIN_LOOP();
364
      do {
Chad Barb's avatar
Chad Barb committed
365
	IN_LOOP();
366 367 368 369 370 371 372
	b = rand() % pnodes;
      } while (t->pnode_uses[b] >= maxplex[b]);

      // now map it.
      t->vnode_mapping[a] = b;
      ++t->pnode_uses[b];
    }
373 374 375 376 377 378 379 380
  }
}

// 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's avatar
Chad Barb committed
381 382 383 384 385 386 387 388 389 390 391 392 393 394 395
  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];
      }
396
    }
Chad Barb's avatar
Chad Barb committed
397
  } else {
398

Chad Barb's avatar
Chad Barb committed
399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423
    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] ];
424
	} else {
Chad Barb's avatar
Chad Barb committed
425 426 427 428 429 430 431 432 433 434 435 436
	  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;
437
	  }
438 439
	}
      } else {
Chad Barb's avatar
Chad Barb committed
440 441 442
	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] ];
443
	} else {
Chad Barb's avatar
Chad Barb committed
444 445 446 447 448 449 450 451 452 453 454 455
	  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;
456
	  }
457 458 459 460 461 462 463 464 465 466 467 468 469
	}
      }
    }
  }

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

// Generate a random solution 
// for the initial population.
static inline void generateRandomSolution( Solution * t )
{
470 471
  //int pnode_uses[MAX_NODES];
  bzero( t->pnode_uses, sizeof( t->pnode_uses ) );
472 473 474 475

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] != -1) {
      t->vnode_mapping[i] = fixed[i];
476
      ++t->pnode_uses[ fixed[i] ];
477 478
    }
  }
479 480 481 482

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] == -1) {
      int x;
Chad Barb's avatar
Chad Barb committed
483
      BEGIN_LOOP();
484
      do {
Chad Barb's avatar
Chad Barb committed
485
	IN_LOOP();
486
	x = rand() % pnodes;
487 488
      } while( t->pnode_uses[x] >= maxplex[x] );
      ++t->pnode_uses[x];
489 490 491 492
      t->vnode_mapping[i] = x;
    }
  }

493 494 495
  calcError<false>( t );
}

Chad Barb's avatar
Chad Barb committed
496
void usage( char * appname )
497
{
Chad Barb's avatar
Chad Barb committed
498 499 500 501
  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
502
	  "  -v -v           jumbo verbosity\n"
503 504
	  "  -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
505 506
	  "  -2 <weight>     enable solving for bandwidth;\n"
	  "                  multiply bandwidth penalties by <weight>.\n"
Chad Barb's avatar
Chad Barb committed
507
	  "  -r <minrounds>  number of rounds to go without a solution before stopping\n"
Chad Barb's avatar
Chad Barb committed
508 509 510
	  "                  default: %i\n"
	  "  -R <maxrounds>  set maximum rounds\n"
	  "                  default: infinite (-1)\n\n", appname, DEFAULT_ROUNDS );
Chad Barb's avatar
Chad Barb committed
511
  exit(1);
Chad Barb's avatar
Chad Barb committed
512 513 514 515
}

int main( int argc, char ** argv )
{
Chad Barb's avatar
Chad Barb committed
516 517 518
  int available = 0;
  int fixedNodeCount = 0;

Chad Barb's avatar
Chad Barb committed
519 520 521 522 523 524 525 526 527
  verbose = 0;
  dimensions = 1;
  d2weight = 1.0f / 1000.0f;

  minrounds = DEFAULT_ROUNDS;
  maxrounds = -1;

  int ch;

528
  while ((ch = getopt(argc, argv, "v2:r:R:s:m:")) != -1) {
Chad Barb's avatar
Chad Barb committed
529
    switch (ch) {
530 531 532
    case 's':
      srand( atoi( optarg ) );
      break;
Chad Barb's avatar
Chad Barb committed
533 534 535
    case 'v': 
      verbose++; 
      break;
536
    case 'm':
537
      plexPenalty = atof( optarg );
538 539
      userSpecifiedMultiplex++;
      break;
Chad Barb's avatar
Chad Barb committed
540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555
    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] );
    }
  }


556 557 558
  char line[1024];

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

Chad Barb's avatar
Chad Barb committed
563
    if (verbose > 1) { printf("Okay, enter %i names for the physical nodes, one per line.\n", pnodes ); }
564 565 566 567 568
    for (int i = 0; i < pnodes; i++) {
      char name[1024];
      gets( line );
      sscanf( line, "%s", name );
      pnodeNames[i] = string( name );
569 570 571 572
      reversePNodeNames[string(name)] = i;
    }

    if (userSpecifiedMultiplex) {
Chad Barb's avatar
Chad Barb committed
573
      if (verbose > 1) { printf("Enter %i numbers, one per line, indicating the"
574 575 576 577 578
			    " 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
579
	available += maxplex[i];
580 581 582 583
      }
    } else {
      for (int i = 0; i < pnodes; i++) {
	maxplex[i] = 1;
Chad Barb's avatar
Chad Barb committed
584
	++available;
585
      }
586 587
    }

Chad Barb's avatar
Chad Barb committed
588
    for (int z = 0; z < dimensions; z++) {
Chad Barb's avatar
Chad Barb committed
589
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
590 591 592 593 594 595 596 597 598 599 600 601 602
	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++; }
	}
603 604 605 606 607
      }
    }
  } 

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

Chad Barb's avatar
Chad Barb committed
612 613 614 615 616 617 618 619 620 621 622
    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 ); }

623 624
    for (int i = 0; i < vnodes; i++) {
      char name[1024];
Chad Barb's avatar
Chad Barb committed
625
      char pname[1024];
626
      gets( line );
Chad Barb's avatar
Chad Barb committed
627 628
      if (sscanf( line, "%s %s", name, pname ) == 2) {
	map< string, int >::iterator it = reversePNodeNames.find( string( pname ) );
629
	if (it == reversePNodeNames.end()) {
Chad Barb's avatar
Chad Barb committed
630 631
	  fprintf(stderr,"pnode '%s' does not exist; can't fix.\n", pname );
	  exit(3);
632
	}
Chad Barb's avatar
Chad Barb committed
633 634
	if (verbose > 1) { 
	  printf("Fixing assignment from vnode %s to pnode %s.\n", name, pname );
635
	}
Chad Barb's avatar
Chad Barb committed
636 637
	fixed[i] = reversePNodeNames[ string( pname ) ];
	fixedNodeCount++;
638 639 640
      } else {
	fixed[i] = -1;
      }
Chad Barb's avatar
Chad Barb committed
641
      vnodeNames[i] = string( name );
642 643
    }

Chad Barb's avatar
Chad Barb committed
644
    for (int z = 0; z < dimensions; z++) {
Chad Barb's avatar
Chad Barb committed
645
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
646 647
	printf("Enter %ix%i grid o' desired %s (-1 is don't care.)\n", vnodes, vnodes, 
	       (z == 0) ? "latency" : "bandwidth");
648
      }
Chad Barb's avatar
Chad Barb committed
649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665
      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++; }
	}
      }
    } 
  }
666

667 668 669
  Solution * currentPool = pool;
  Solution * nextPool = pool2;

Chad Barb's avatar
Chad Barb committed
670 671
  if (fixedNodeCount < vnodes) {
    if (verbose) { printf("Now running...\n"); }
672

Chad Barb's avatar
Chad Barb committed
673 674
    {
      for (int i = 0; i < SOLUTIONS; i++) {
675
	generateRandomSolution( &(currentPool[i]) );
Chad Barb's avatar
Chad Barb committed
676
      }
677
      sortByError( currentPool );
678 679 680
    }

    int highestFoundRound = 0;
681 682
    float last = currentPool[0].error;

Chad Barb's avatar
Chad Barb committed
683
    for (int i = 0; i != maxrounds && i < (highestFoundRound + minrounds); i++) {
684 685 686 687 688 689 690 691 692 693
      /*
      {
	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);
694
      }
Chad Barb's avatar
Chad Barb committed
695
      
696
      if (currentPool[0].error < last) {
Chad Barb's avatar
Chad Barb committed
697 698
	if (verbose) {
	  printf("Better solution found in round %i (error %4.3f)\n", 
699
		 i, currentPool[0].error);
Chad Barb's avatar
Chad Barb committed
700
	}
701
	last = currentPool[0].error;
702 703
	highestFoundRound = i;
      }
704

Chad Barb's avatar
Chad Barb committed
705 706
      // 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.)
707 708 709 710 711 712 713 714 715 716 717 718 719 720 721
      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]) );	
      }
      /*      
722 723 724 725 726 727
      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()]) ); 
      }
728 729 730 731 732 733 734 735
      */
      sortByError( nextPool );

      Solution * temp = currentPool;
      currentPool = nextPool;
      nextPool = temp;

      if (currentPool[0].error < EPSILON) { 
Chad Barb's avatar
Chad Barb committed
736
	if (verbose > 1) { printf("Found perfect solution.\n"); }
737 738 739
	break;
      }
    }
Chad Barb's avatar
Chad Barb committed
740 741
  } else {
    if (verbose) { printf("No non-fixed vnodes (or no vnodes at all,) so nothing to be done!\n"); }
742 743 744
  }

  {
Chad Barb's avatar
Chad Barb committed
745
    if (verbose) { printf("\nYour solution is as follows:\n"); }
746
    for (int x = 0; x < vnodes; x++) {
747 748
      if (pnodeNames.find( currentPool[0].vnode_mapping[x] ) == pnodeNames.end()) {
	pnodeNames[ currentPool[0].vnode_mapping[x] ] = "CRAP";
Chad Barb's avatar
Chad Barb committed
749 750 751
      }
      printf("%s mapsTo %s\n", 
	     vnodeNames[x].c_str(),
752
	     pnodeNames[currentPool[0].vnode_mapping[x]].c_str() );
753
    }
754

755 756 757
    printf("\n");

    // dump a detailed report of the returned solution's errors.
758
    if (verbose > 1) { calcError<true>( &(currentPool[0]) ); }
759 760
  }

Chad Barb's avatar
Chad Barb committed
761
  if (verbose > 1) { printf("Bye now.\n"); }
762 763
  return 0;
}