wanlinksolve.cc 20.8 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

103 104
// default rounds to keep going without finding a better solution.
#define DEFAULT_ROUNDS 512
105 106

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

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

Chad Barb's avatar
Chad Barb committed
113 114
// probability crossover will happen (out of 1000)
#define CROSSOVER_PROB 700
115 116 117 118 119 120 121 122 123 124 125 126 127 128 129

// 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
130
// some code to enable when the solver wedges and we don't know why.
Chad Barb's avatar
Chad Barb committed
131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149
#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

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

static int pnodes, vnodes;

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

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

static int fixed[MAX_NODES];

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

static int verbose = 0;

static int minrounds, maxrounds;
172 173 174 175

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

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

183
  float error;
184
  unsigned int prob;
185 186
};

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

Chad Barb's avatar
Chad Barb committed
193
// determines probabilities of selecting each solution.
194
static inline void prepick( Solution * currentPool )
195
{
196 197 198 199 200 201 202
  float totalFitness = 0.0f;
  int i;

  for (i = 0; i < SOLUTIONS; i++) {
    totalFitness += 1.0f / currentPool[i].error;
  }

203
  unsigned int probsofar = 0;
204
  for (i = 0; i < SOLUTIONS; i++) {
205 206
    probsofar += (unsigned int)(((float)0xFFFFFFFF / currentPool[i].error) / totalFitness);
    currentPool[i].prob = probsofar;
207
  }
208 209

  currentPool[SOLUTIONS - 1].prob = 0xFFFFFFFF;
210 211
}

212 213
// 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%.
214 215
static inline int pickABest( Solution * currentPool )
{
216 217 218 219 220 221 222 223 224 225 226 227 228 229 230
  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; 
    }
  } 
231

232 233
  return mid;
  /*
234 235
  int i = 0;
  while (1) { 
236
    if (x < currentPool[i].prob) break;
237
    i++;
238
    if (i == SOLUTIONS) { printf("Ick.\n"); i = 0; break;}
239 240
  }
  return i - 1;
241
  */
242 243
}

244
// uses a template to avoid massive numbers
245 246 247 248 249 250 251 252 253 254 255
// 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");
  }

256 257 258 259 260 261 262 263 264 265 266 267 268 269 270
  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;
      }
    }
  }

271
  {
Chad Barb's avatar
Chad Barb committed
272 273 274 275 276
    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) {
277
	    int is     = pLatency[z][ t->vnode_mapping[x] ][ t->vnode_mapping[y] ];
Chad Barb's avatar
Chad Barb committed
278 279 280 281 282 283 284
	    if (should != is) { 
	      float errDelta;

	      if (z == 0) {
		errDelta = sqrtf((float)(abs(should - is)));
	      } else {
		errDelta = d2weight * (float)(abs(should - is));
285
		if (should < is) { errDelta *= 0.5f; }
Chad Barb's avatar
Chad Barb committed
286 287 288 289 290 291 292 293
	      }

	      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 {
294
		  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
295 296 297
			 vnodeNames[x].c_str(), vnodeNames[y].c_str(), 
			 (int)expf((float)should / 1000.0f), 
			 (int)expf((float)is / 1000.0f),
298
			 (should < is) ? "* 0.5 " : "",
Chad Barb's avatar
Chad Barb committed
299 300 301 302
			 errDelta );
		}
	      }
	      err += errDelta;
303 304 305 306 307 308 309
	    }
	  }
	}
      }
    }
  }

Chad Barb's avatar
Chad Barb committed
310
  if (verbose) { printf("error of %4.3f\n", err ); }
311 312 313 314 315 316 317 318 319 320 321 322 323
  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; }
}

324
static inline void sortByError( Solution * t )
325 326
{
  // Ahh.. sweet, sweet qsort.
327
  qsort( t, SOLUTIONS, sizeof( Solution ), compar );
328 329 330 331 332 333 334
}

// "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
335
  BEGIN_LOOP();
336
  while(1) {
Chad Barb's avatar
Chad Barb committed
337
    IN_LOOP();
338
    // forecast calls for a 1% chance of mutation...
Chad Barb's avatar
Chad Barb committed
339
    if ((rand() % 1000) > MUTATE_PROB) { break; }
340 341 342 343
    
    if ((rand() % 3)) {
      // swap mutation. 
      int a, b;
Chad Barb's avatar
Chad Barb committed
344 345

      BEGIN_LOOP();
346
      do {
Chad Barb's avatar
Chad Barb committed
347
	IN_LOOP();
348
	a = rand() % vnodes;
Chad Barb's avatar
Chad Barb committed
349 350 351 352 353
      } while (fixed[a] != -1);

      BEGIN_LOOP();
      do {
	IN_LOOP();
354
	b = rand() % vnodes;
Chad Barb's avatar
Chad Barb committed
355 356 357 358 359 360 361
      } 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;
      }
362 363 364 365 366 367 368 369 370 371 372 373 374 375
    } 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
376
      BEGIN_LOOP();
377
      do {
Chad Barb's avatar
Chad Barb committed
378
	IN_LOOP();
379 380 381 382 383 384 385
	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
386
      BEGIN_LOOP();
387
      do {
Chad Barb's avatar
Chad Barb committed
388
	IN_LOOP();
389 390 391 392 393 394 395
	b = rand() % pnodes;
      } while (t->pnode_uses[b] >= maxplex[b]);

      // now map it.
      t->vnode_mapping[a] = b;
      ++t->pnode_uses[b];
    }
396 397 398 399 400 401 402 403
  }
}

// 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
404 405 406 407 408 409 410 411 412 413 414 415 416 417 418
  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];
      }
419
    }
Chad Barb's avatar
Chad Barb committed
420
  } else {
421

Chad Barb's avatar
Chad Barb committed
422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446
    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] ];
447
	} else {
Chad Barb's avatar
Chad Barb committed
448 449 450 451 452 453 454 455 456 457 458 459
	  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;
460
	  }
461 462
	}
      } else {
Chad Barb's avatar
Chad Barb committed
463 464 465
	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] ];
466
	} else {
Chad Barb's avatar
Chad Barb committed
467 468 469 470 471 472 473 474 475 476 477 478
	  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;
479
	  }
480 481 482 483 484 485 486 487 488 489 490 491 492
	}
      }
    }
  }

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

// Generate a random solution 
// for the initial population.
static inline void generateRandomSolution( Solution * t )
{
493 494
  //int pnode_uses[MAX_NODES];
  bzero( t->pnode_uses, sizeof( t->pnode_uses ) );
495 496 497 498

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] != -1) {
      t->vnode_mapping[i] = fixed[i];
499
      ++t->pnode_uses[ fixed[i] ];
500 501
    }
  }
502 503 504 505

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] == -1) {
      int x;
Chad Barb's avatar
Chad Barb committed
506
      BEGIN_LOOP();
507
      do {
Chad Barb's avatar
Chad Barb committed
508
	IN_LOOP();
509
	x = rand() % pnodes;
510 511
      } while( t->pnode_uses[x] >= maxplex[x] );
      ++t->pnode_uses[x];
512 513 514 515
      t->vnode_mapping[i] = x;
    }
  }

516 517 518
  calcError<false>( t );
}

Chad Barb's avatar
Chad Barb committed
519
void usage( char * appname )
520
{
Chad Barb's avatar
Chad Barb committed
521 522 523 524
  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
525
	  "  -v -v           jumbo verbosity\n"
526 527
	  "  -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
528 529
	  "  -2 <weight>     enable solving for bandwidth;\n"
	  "                  multiply bandwidth penalties by <weight>.\n"
Chad Barb's avatar
Chad Barb committed
530
	  "  -r <minrounds>  number of rounds to go without a solution before stopping\n"
Chad Barb's avatar
Chad Barb committed
531 532 533
	  "                  default: %i\n"
	  "  -R <maxrounds>  set maximum rounds\n"
	  "                  default: infinite (-1)\n\n", appname, DEFAULT_ROUNDS );
Chad Barb's avatar
Chad Barb committed
534
  exit(1);
Chad Barb's avatar
Chad Barb committed
535 536 537 538
}

int main( int argc, char ** argv )
{
Chad Barb's avatar
Chad Barb committed
539 540 541
  int available = 0;
  int fixedNodeCount = 0;

Chad Barb's avatar
Chad Barb committed
542 543 544 545 546 547 548 549 550
  verbose = 0;
  dimensions = 1;
  d2weight = 1.0f / 1000.0f;

  minrounds = DEFAULT_ROUNDS;
  maxrounds = -1;

  int ch;

551
  while ((ch = getopt(argc, argv, "v2:r:R:s:m:")) != -1) {
Chad Barb's avatar
Chad Barb committed
552
    switch (ch) {
553 554 555
    case 's':
      srand( atoi( optarg ) );
      break;
Chad Barb's avatar
Chad Barb committed
556 557 558
    case 'v': 
      verbose++; 
      break;
559
    case 'm':
560
      plexPenalty = atof( optarg );
561 562
      userSpecifiedMultiplex++;
      break;
Chad Barb's avatar
Chad Barb committed
563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578
    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] );
    }
  }


579 580 581
  char line[1024];

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

Chad Barb's avatar
Chad Barb committed
586
    if (verbose > 1) { printf("Okay, enter %i names for the physical nodes, one per line.\n", pnodes ); }
587 588 589 590 591
    for (int i = 0; i < pnodes; i++) {
      char name[1024];
      gets( line );
      sscanf( line, "%s", name );
      pnodeNames[i] = string( name );
592 593 594 595
      reversePNodeNames[string(name)] = i;
    }

    if (userSpecifiedMultiplex) {
Chad Barb's avatar
Chad Barb committed
596
      if (verbose > 1) { printf("Enter %i numbers, one per line, indicating the"
597 598 599 600 601
			    " 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
602
	available += maxplex[i];
603 604 605 606
      }
    } else {
      for (int i = 0; i < pnodes; i++) {
	maxplex[i] = 1;
Chad Barb's avatar
Chad Barb committed
607
	++available;
608
      }
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 615 616 617 618 619 620 621 622 623 624 625
	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++; }
	}
626 627 628 629 630
      }
    }
  } 

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

Chad Barb's avatar
Chad Barb committed
635 636 637 638 639 640 641 642 643 644 645
    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 ); }

646 647
    for (int i = 0; i < vnodes; i++) {
      char name[1024];
Chad Barb's avatar
Chad Barb committed
648
      char pname[1024];
649
      gets( line );
Chad Barb's avatar
Chad Barb committed
650 651
      if (sscanf( line, "%s %s", name, pname ) == 2) {
	map< string, int >::iterator it = reversePNodeNames.find( string( pname ) );
652
	if (it == reversePNodeNames.end()) {
Chad Barb's avatar
Chad Barb committed
653 654
	  fprintf(stderr,"pnode '%s' does not exist; can't fix.\n", pname );
	  exit(3);
655
	}
Chad Barb's avatar
Chad Barb committed
656 657
	if (verbose > 1) { 
	  printf("Fixing assignment from vnode %s to pnode %s.\n", name, pname );
658
	}
Chad Barb's avatar
Chad Barb committed
659 660
	fixed[i] = reversePNodeNames[ string( pname ) ];
	fixedNodeCount++;
661 662 663
      } else {
	fixed[i] = -1;
      }
Chad Barb's avatar
Chad Barb committed
664
      vnodeNames[i] = string( name );
665 666
    }

Chad Barb's avatar
Chad Barb committed
667
    for (int z = 0; z < dimensions; z++) {
Chad Barb's avatar
Chad Barb committed
668
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
669 670
	printf("Enter %ix%i grid o' desired %s (-1 is don't care.)\n", vnodes, vnodes, 
	       (z == 0) ? "latency" : "bandwidth");
671
      }
Chad Barb's avatar
Chad Barb committed
672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688
      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++; }
	}
      }
    } 
  }
689

690 691 692
  Solution * currentPool = pool;
  Solution * nextPool = pool2;

Chad Barb's avatar
Chad Barb committed
693 694
  if (fixedNodeCount < vnodes) {
    if (verbose) { printf("Now running...\n"); }
695

Chad Barb's avatar
Chad Barb committed
696 697
    {
      for (int i = 0; i < SOLUTIONS; i++) {
698
	generateRandomSolution( &(currentPool[i]) );
Chad Barb's avatar
Chad Barb committed
699
      }
700
      sortByError( currentPool );
701 702 703
    }

    int highestFoundRound = 0;
704 705
    float last = currentPool[0].error;

Chad Barb's avatar
Chad Barb committed
706
    for (int i = 0; i != maxrounds && i < (highestFoundRound + minrounds); i++) {
707 708 709 710 711 712 713 714
      /*
      {
	float blah = 0.0f;
	for (int xy = 0; xy < SOLUTIONS; xy++) { blah += currentPool[xy].error; }
	printf("Avg = %7.2f\n", (blah / (float)SOLUTIONS) );
      }
      */
      
715
      if (verbose && !(i % 100)) {
716
	printf("Round %i. (best %4.3f)\n", i, currentPool[0].error);
717
      }
Chad Barb's avatar
Chad Barb committed
718
      
719
      if (currentPool[0].error < last) {
Chad Barb's avatar
Chad Barb committed
720 721
	if (verbose) {
	  printf("Better solution found in round %i (error %4.3f)\n", 
722
		 i, currentPool[0].error);
Chad Barb's avatar
Chad Barb committed
723
	}
724
	last = currentPool[0].error;
725 726
	highestFoundRound = i;
      }
727

Chad Barb's avatar
Chad Barb committed
728 729
      // 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.)
730 731 732 733 734 735 736 737 738 739 740 741 742 743 744
      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]) );	
      }
      /*      
745 746 747 748 749 750
      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()]) ); 
      }
751 752 753 754 755 756 757 758
      */
      sortByError( nextPool );

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

      if (currentPool[0].error < EPSILON) { 
Chad Barb's avatar
Chad Barb committed
759
	if (verbose > 1) { printf("Found perfect solution.\n"); }
760 761 762
	break;
      }
    }
Chad Barb's avatar
Chad Barb committed
763 764
  } else {
    if (verbose) { printf("No non-fixed vnodes (or no vnodes at all,) so nothing to be done!\n"); }
765 766 767
  }

  {
Chad Barb's avatar
Chad Barb committed
768
    if (verbose) { printf("\nYour solution is as follows:\n"); }
769
    for (int x = 0; x < vnodes; x++) {
770 771
      if (pnodeNames.find( currentPool[0].vnode_mapping[x] ) == pnodeNames.end()) {
	pnodeNames[ currentPool[0].vnode_mapping[x] ] = "CRAP";
Chad Barb's avatar
Chad Barb committed
772 773 774
      }
      printf("%s mapsTo %s\n", 
	     vnodeNames[x].c_str(),
775
	     pnodeNames[currentPool[0].vnode_mapping[x]].c_str() );
776
    }
777

778 779 780
    printf("\n");

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

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