wanlinksolve.cc 22 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
#include <math.h>
95 96 97
#include <sys/types.h>
#include <sys/time.h>
#include <sys/resource.h>
98 99 100 101 102

// To keep things lightweight, 
// structures are statically sized to
// accommodate up to MAX_NODES nodes.
// These could be changed to STL vectors in the future.
103
#define MAX_NODES 32
Chad Barb's avatar
Chad Barb committed
104 105
#define MAX_DIMENSIONS 2

106 107
// default rounds to keep going without finding a better solution.
#define DEFAULT_ROUNDS 512
108 109

// The size of our "population."
Chad Barb's avatar
Chad Barb committed
110
// (number of phenotypes)
111
#define SOLUTIONS 400
112

Chad Barb's avatar
Chad Barb committed
113
// The probability a given child will mutate (out of 1000)
114 115
//#define MUTATE_PROB 40
#define MUTATE_PROB 10
116

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

// A score below Epsilon means we've found a perfect solution,
// so stop immediately.
#define EPSILON 0.0001f

// lets STL it up a notch.
#include <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
134
// some code to enable when the solver wedges and we don't know why.
Chad Barb's avatar
Chad Barb committed
135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
#ifdef DEBUG
int wedgecount;
static inline void BEGIN_LOOP() { wedgecount = 0; } 
static inline void IN_LOOP_hlp( int line ) 
{ 
  ++wedgecount;
  if (wedgecount == 66666) { 
    printf( "possibly wedged in line %i.\n", line );
    assert(false);
  }
}
#define IN_LOOP() IN_LOOP_hlp(__LINE__)
#else

#define BEGIN_LOOP()
#define IN_LOOP()

#endif

154 155
// keep track of user names for nodes.
static map< int, string > pnodeNames;
156
static map< string, int > reversePNodeNames;
157 158 159 160
static map< int, string > vnodeNames;

static int pnodes, vnodes;

Chad Barb's avatar
Chad Barb committed
161 162 163
static int pLatency[MAX_DIMENSIONS][MAX_NODES][MAX_NODES];
static int vDesiredLatency[MAX_DIMENSIONS][MAX_NODES][MAX_NODES];

164
static float plexPenalty = 0.0f;
165 166 167 168 169
static int maxplex[MAX_NODES];
static int userSpecifiedMultiplex = 0;

static int fixed[MAX_NODES];

Chad Barb's avatar
Chad Barb committed
170 171 172 173 174 175
static int dimensions;
static float d2weight;

static int verbose = 0;

static int minrounds, maxrounds;
176

177 178
static bool himutate = false;

179 180 181
class Solution
{
public:
182
  int vnode_mapping[MAX_NODES];
183 184 185 186 187 188

  // Keep around a list of how many times each physical node is used
  // in this solution, rather than recomputing it each time it is needed
  // (which is often.)
  unsigned char pnode_uses[MAX_NODES];

189
  float error;
190
  unsigned int prob;
191 192
};

Chad Barb's avatar
Chad Barb committed
193 194 195
// the population pool.
// at any one time, one of these is the "current" pool (where the parents come from)
// and one is the "next" pool (where the children go)
196
static Solution pool[SOLUTIONS];
197
static Solution pool2[SOLUTIONS];
198

Chad Barb's avatar
Chad Barb committed
199
// determines probabilities of selecting each solution.
200
static inline void prepick( Solution * currentPool )
201
{
202 203 204 205 206 207 208
  float totalFitness = 0.0f;
  int i;

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

209
  unsigned int probsofar = 0;
210
  for (i = 0; i < SOLUTIONS; i++) {
211 212
    probsofar += (unsigned int)(((float)0xFFFFFFFF / currentPool[i].error) / totalFitness);
    currentPool[i].prob = probsofar;
213
  }
214 215

  currentPool[SOLUTIONS - 1].prob = 0xFFFFFFFF;
216 217
}

218 219
// optimized to 1. not use fp 2. use a binary search, rather than a linear one.
// win: according to gprof, was taking 75% of the total time, now takes 17%.
220 221
static inline int pickABest( Solution * currentPool )
{
222 223 224 225 226 227 228 229 230 231 232 233 234 235 236
  unsigned int x = rand();

  int lo = 0;
  int hi = SOLUTIONS;
  int mid;

  while (1) {
    mid = (hi + lo) / 2;
    if (x <= currentPool[mid].prob) { 
      if (mid == 0 || x > currentPool[mid - 1].prob) break; 
      hi = mid; 
    } else { 
      lo = mid; 
    }
  } 
237

238 239
  return mid;
  /*
240 241
  int i = 0;
  while (1) { 
242
    if (x < currentPool[i].prob) break;
243
    i++;
244
    if (i == SOLUTIONS) { printf("Ick.\n"); i = 0; break;}
245 246
  }
  return i - 1;
247
  */
248 249
}

250

251
// uses a template to avoid massive numbers
252 253 254 255 256 257 258 259 260 261 262
// of "if" choices.. compiler should generate two versions,
// one with dump and one without.
template <bool verbose>
static inline void calcError( Solution * t )
{ 
  float err = 0.0f;

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

263 264 265 266 267 268 269 270 271 272 273 274 275 276 277
  if (userSpecifiedMultiplex) {
    for (int x = 0; x < pnodes; x++) {
      if (t->pnode_uses[x] > 1) { 
	float errDelta = (float)(t->pnode_uses[x] - 1) * plexPenalty;
	if (verbose) {
	  printf("%i nodes multiplexed on physical node %s, (err [(vnodes - 1) * plexPenalty] %4.3f)\n",
		 t->pnode_uses[x],
		 pnodeNames[x].c_str(),
		 errDelta );
	}
	err += errDelta;
      }
    }
  }

278
  {
Chad Barb's avatar
Chad Barb committed
279 280 281 282 283
    for (int z = 0; z < dimensions; z++) {
      for (int x = 0; x < vnodes; x++) {
	for (int y = 0; y < vnodes; y++) {
	  int should = vDesiredLatency[z][x][y];
	  if (should != -1) {
284
	    int is     = pLatency[z][ t->vnode_mapping[x] ][ t->vnode_mapping[y] ];
285 286 287 288 289 290 291
	    if (is == -1) {
	      if (verbose) {
		printf("%s -> %s link nonexistant! Super-icky penality of 10000 assessed.\n",
		       vnodeNames[x].c_str(), vnodeNames[y].c_str() ); 
	      }
	      err += 10000.0f;
	    } else if (should != is) { 
Chad Barb's avatar
Chad Barb committed
292 293 294 295 296 297
	      float errDelta;

	      if (z == 0) {
		errDelta = sqrtf((float)(abs(should - is)));
	      } else {
		errDelta = d2weight * (float)(abs(should - is));
298
		if (should < is) { errDelta *= 0.5f; }
Chad Barb's avatar
Chad Barb committed
299 300 301 302 303 304 305 306
	      }

	      if (verbose) {
		if (z == 0) {
		  printf("%s -> %s latency (ms) should be %i; is %i (err [sqrt |a-b|] %4.3f)\n", 
			 vnodeNames[x].c_str(), vnodeNames[y].c_str(), 
			 should, is, errDelta );
		} else {
307
		  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
308 309 310
			 vnodeNames[x].c_str(), vnodeNames[y].c_str(), 
			 (int)expf((float)should / 1000.0f), 
			 (int)expf((float)is / 1000.0f),
311
			 (should < is) ? "* 0.5 " : "",
Chad Barb's avatar
Chad Barb committed
312 313 314 315
			 errDelta );
		}
	      }
	      err += errDelta;
316 317 318 319 320 321 322
	    }
	  }
	}
      }
    }
  }

Chad Barb's avatar
Chad Barb committed
323
  if (verbose) { printf("error of %4.3f\n", err ); }
324 325 326 327 328 329 330 331 332 333 334 335 336
  t->error = err;
} 

static int compar( const void * a , const void * b )
{
  Solution * sa = (Solution *)a;
  Solution * sb = (Solution *)b;

  if (sa->error > sb->error) { return  1; } else
  if (sa->error < sb->error) { return -1; } else
  { return 0; }
}

337
static inline void sortByError( Solution * t )
338 339
{
  // Ahh.. sweet, sweet qsort.
340
  qsort( t, SOLUTIONS, sizeof( Solution ), compar );
341 342 343 344 345 346 347
}

// "Mutating" is swapping what vnode a pnode maps to in
// the solution with what vnode a different pnode maps to.
// (if both are -1, e.g. not mapped to vnodes, nothing happens.)
static inline void mutate( Solution * t )
{
Chad Barb's avatar
Chad Barb committed
348
  BEGIN_LOOP();
349
  while(1) {
Chad Barb's avatar
Chad Barb committed
350
    IN_LOOP();
351
    // forecast calls for a 1% chance of mutation...
352
    if ((rand() % 1000) > (himutate ? 500 : MUTATE_PROB)) { break; }
353 354 355 356
    
    if ((rand() % 3)) {
      // swap mutation. 
      int a, b;
Chad Barb's avatar
Chad Barb committed
357 358

      BEGIN_LOOP();
359
      do {
Chad Barb's avatar
Chad Barb committed
360
	IN_LOOP();
361
	a = rand() % vnodes;
Chad Barb's avatar
Chad Barb committed
362 363 364 365 366
      } while (fixed[a] != -1);

      BEGIN_LOOP();
      do {
	IN_LOOP();
367
	b = rand() % vnodes;
Chad Barb's avatar
Chad Barb committed
368 369 370 371 372 373 374
      } while (fixed[b] != -1);

      if (a != b) {
	int temp = t->vnode_mapping[a];
	t->vnode_mapping[a] = t->vnode_mapping[b];
	t->vnode_mapping[b] = temp;
      }
375 376 377 378 379 380 381 382 383 384 385 386 387 388
    } else {
      // reassign mutation
      /*
      int pnode_uses[MAX_NODES];

      bzero( pnode_uses, sizeof( pnode_uses ) );

      for (int i = 0; i < vnodes; i++) {
	++pnode_uses[ t->vnode_mapping[i] ];
      }
      */

      int a, b;
      // find which vnode to remap
Chad Barb's avatar
Chad Barb committed
389
      BEGIN_LOOP();
390
      do {
Chad Barb's avatar
Chad Barb committed
391
	IN_LOOP();
392 393 394 395 396 397 398
	a = rand() % vnodes;
      } while (fixed[a] != -1);

      // de-map it.
      --t->pnode_uses[ t->vnode_mapping[a] ];

      // now find a suitable physical node.
Chad Barb's avatar
Chad Barb committed
399
      BEGIN_LOOP();
400
      do {
Chad Barb's avatar
Chad Barb committed
401
	IN_LOOP();
402 403 404 405 406 407 408
	b = rand() % pnodes;
      } while (t->pnode_uses[b] >= maxplex[b]);

      // now map it.
      t->vnode_mapping[a] = b;
      ++t->pnode_uses[b];
    }
409 410 411 412 413 414 415 416
  }
}

// TODO: make sure that failed matings don't happen too
// often for difficult graphs.
// (perhaps have a limited retry)
static inline void splice( Solution * t, Solution * a, Solution * b)
{
Chad Barb's avatar
Chad Barb committed
417 418 419 420 421 422 423 424 425 426 427 428 429 430 431
  if ((rand() % 1000) > CROSSOVER_PROB) {
    if (rand() % 2) {
      for (int x = 0; x < vnodes; x++) {
	t->vnode_mapping[x] = a->vnode_mapping[x];
      }
      for (int y = 0; y < vnodes; y++) {
	t->pnode_uses[y] = a->pnode_uses[y];
      }
    } else {
      for (int x = 0; x < vnodes; x++) {
	t->vnode_mapping[x] = b->vnode_mapping[x];
      }
      for (int y = 0; y < vnodes; y++) {
	t->pnode_uses[y] = b->pnode_uses[y];
      }
432
    }
Chad Barb's avatar
Chad Barb committed
433
  } else {
434

Chad Barb's avatar
Chad Barb committed
435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459
    bzero( t->pnode_uses, sizeof( t->pnode_uses ) );
    
    for (int i = 0; i < vnodes; i++) {
      if (fixed[i] != -1) {
	t->vnode_mapping[i] = fixed[i];
	++t->pnode_uses[ fixed[i] ];
      }
    }
    
    // go through each mapping, and pick randomly
    // which one of the two parents' mappings the child
    // will inherit.
    // Inherit the one that makes sense if the other would
    // conflict with a previously chosen mapping.
    // If both would conflict with a previously chosen mapping.
    // its a failed mating, and we return.
    
    int pos = rand() % vnodes;
    for (int i = 0; i < vnodes; i++) {
      pos = (pos + 1) % vnodes;
      if (fixed[pos] != -1) continue;
      if (rand() % 2) {
	if (t->pnode_uses[ a->vnode_mapping[pos] ] < maxplex[ a->vnode_mapping[pos] ]) {
	  t->vnode_mapping[pos] = a->vnode_mapping[pos];
	  ++t->pnode_uses[ a->vnode_mapping[pos] ];
460
	} else {
Chad Barb's avatar
Chad Barb committed
461 462 463 464 465 466 467 468 469 470 471 472
	  if (t->pnode_uses[ b->vnode_mapping[pos] ] < maxplex[ b->vnode_mapping[pos] ]) {
	    t->vnode_mapping[pos] = b->vnode_mapping[pos];
	    ++t->pnode_uses[ b->vnode_mapping[pos] ];
	  } else {
	    // failed mating (asexually clone a parent)
	    for (int x = 0; x < vnodes; x++) {
	      t->vnode_mapping[x] = a->vnode_mapping[x];
	    }
	    for (int y = 0; y < vnodes; y++) {
	      t->pnode_uses[y] = a->pnode_uses[y];
	    }
	    break;
473
	  }
474 475
	}
      } else {
Chad Barb's avatar
Chad Barb committed
476 477 478
	if (t->pnode_uses[ b->vnode_mapping[pos] ] < maxplex[ b->vnode_mapping[pos] ]) {
	  t->vnode_mapping[pos] = b->vnode_mapping[pos];
	  ++t->pnode_uses[ b->vnode_mapping[pos] ];
479
	} else {
Chad Barb's avatar
Chad Barb committed
480 481 482 483 484 485 486 487 488 489 490 491
	  if (t->pnode_uses[ a->vnode_mapping[pos] ] < maxplex[ a->vnode_mapping[pos] ]) {
	    t->vnode_mapping[pos] = a->vnode_mapping[pos];
	    ++t->pnode_uses[ a->vnode_mapping[pos] ];
	  } else {
	    // failed mating (asexually clone a parent)
	    for (int x = 0; x < vnodes; x++) {
	      t->vnode_mapping[x] = b->vnode_mapping[x];
	    }
	    for (int y = 0; y < vnodes; y++) {
	      t->pnode_uses[y] = b->pnode_uses[y];
	    }
	    break;
492
	  }
493 494 495 496 497 498 499 500 501 502 503 504 505
	}
      }
    }
  }

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

// Generate a random solution 
// for the initial population.
static inline void generateRandomSolution( Solution * t )
{
506 507
  //int pnode_uses[MAX_NODES];
  bzero( t->pnode_uses, sizeof( t->pnode_uses ) );
508 509 510 511

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] != -1) {
      t->vnode_mapping[i] = fixed[i];
512
      ++t->pnode_uses[ fixed[i] ];
513 514
    }
  }
515 516 517 518

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] == -1) {
      int x;
Chad Barb's avatar
Chad Barb committed
519
      BEGIN_LOOP();
520
      do {
Chad Barb's avatar
Chad Barb committed
521
	IN_LOOP();
522
	x = rand() % pnodes;
523 524
      } while( t->pnode_uses[x] >= maxplex[x] );
      ++t->pnode_uses[x];
525 526 527 528
      t->vnode_mapping[i] = x;
    }
  }

529 530 531
  calcError<false>( t );
}

Chad Barb's avatar
Chad Barb committed
532
void usage( char * appname )
533
{
Chad Barb's avatar
Chad Barb committed
534 535 536 537
  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
538
	  "  -v -v           jumbo verbosity\n"
539 540
	  "  -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
541 542
	  "  -2 <weight>     enable solving for bandwidth;\n"
	  "                  multiply bandwidth penalties by <weight>.\n"
Chad Barb's avatar
Chad Barb committed
543
	  "  -r <minrounds>  number of rounds to go without a solution before stopping\n"
Chad Barb's avatar
Chad Barb committed
544 545 546
	  "                  default: %i\n"
	  "  -R <maxrounds>  set maximum rounds\n"
	  "                  default: infinite (-1)\n\n", appname, DEFAULT_ROUNDS );
Chad Barb's avatar
Chad Barb committed
547
  exit(1);
Chad Barb's avatar
Chad Barb committed
548 549
}

550 551 552 553 554 555 556 557 558 559
unsigned int msecscpu()
{
  struct rusage r;

  getrusage( 0, &r );

  return r.ru_utime.tv_sec * 1000 + 
         r.ru_utime.tv_usec / 1000;
}

Chad Barb's avatar
Chad Barb committed
560 561
int main( int argc, char ** argv )
{
Chad Barb's avatar
Chad Barb committed
562 563
  int available = 0;
  int fixedNodeCount = 0;
564
  unsigned int bestSpeed = 0;
Chad Barb's avatar
Chad Barb committed
565

Chad Barb's avatar
Chad Barb committed
566 567 568 569 570 571 572 573 574
  verbose = 0;
  dimensions = 1;
  d2weight = 1.0f / 1000.0f;

  minrounds = DEFAULT_ROUNDS;
  maxrounds = -1;

  int ch;

575
  while ((ch = getopt(argc, argv, "v2:r:R:s:m:")) != -1) {
Chad Barb's avatar
Chad Barb committed
576
    switch (ch) {
577 578 579
    case 's':
      srand( atoi( optarg ) );
      break;
Chad Barb's avatar
Chad Barb committed
580 581 582
    case 'v': 
      verbose++; 
      break;
583
    case 'm':
584
      plexPenalty = atof( optarg );
585 586
      userSpecifiedMultiplex++;
      break;
Chad Barb's avatar
Chad Barb committed
587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602
    case '2': 
      dimensions = 2;
      d2weight = atof( optarg ) / 1000.0f; 
      break;
    case 'r':
      minrounds = atoi( optarg );
      break;
    case 'R':
      maxrounds = atoi( optarg );
      break;
    default: 
      usage( argv[0] );
    }
  }


603
  char line[4096];
604 605

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

Chad Barb's avatar
Chad Barb committed
610
    if (verbose > 1) { printf("Okay, enter %i names for the physical nodes, one per line.\n", pnodes ); }
611 612 613 614 615
    for (int i = 0; i < pnodes; i++) {
      char name[1024];
      gets( line );
      sscanf( line, "%s", name );
      pnodeNames[i] = string( name );
616 617 618 619
      reversePNodeNames[string(name)] = i;
    }

    if (userSpecifiedMultiplex) {
Chad Barb's avatar
Chad Barb committed
620
      if (verbose > 1) { printf("Enter %i numbers, one per line, indicating the"
621 622 623 624 625
			    " maximum number of virtual nodes allowed on each"
			    " physical node.\n", pnodes ); }
      for (int i = 0; i < pnodes; i++) {
	gets( line );
	sscanf( line, "%i", &(maxplex[i]));
Chad Barb's avatar
Chad Barb committed
626
	available += maxplex[i];
627 628 629 630
      }
    } else {
      for (int i = 0; i < pnodes; i++) {
	maxplex[i] = 1;
Chad Barb's avatar
Chad Barb committed
631
	++available;
632
      }
633 634
    }

Chad Barb's avatar
Chad Barb committed
635
    for (int z = 0; z < dimensions; z++) {
Chad Barb's avatar
Chad Barb committed
636
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
637 638 639 640 641 642 643 644 645
	printf("Enter %ix%i grid o' actual %s.\n", pnodes, pnodes, 
	     (z == 0) ? "latency" : "bandwidth");
      }
      for (int y = 0; y < pnodes; y++) {
	char * linePos = line;
	gets( line );
	while (*linePos == ' ') { linePos++; } // skip leading whitespace
	for (int x = 0; x < pnodes; x++) {
	  sscanf( linePos, "%i", &pLatency[z][x][y] );
646 647 648 649 650
	  if (z == 1) { 
	    if (pLatency[z][x][y] != -1) {
	      pLatency[z][x][y] = (int)( logf(pLatency[z][x][y]) * 1000.0f ); 
	    }
	  }
Chad Barb's avatar
Chad Barb committed
651 652 653
	  while (*linePos != ' ' && *linePos != '\n') { linePos++; }
	  while (*linePos == ' ') { linePos++; }
	}
654 655 656 657 658
      }
    }
  } 

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

Chad Barb's avatar
Chad Barb committed
663 664 665 666 667 668 669 670 671 672 673
    if (vnodes > available) {
      fprintf(stderr, 
	      "More nodes required (%i) than can be mapped (%i).\n", 
	      vnodes, available );
      exit(2);
    }

    if (verbose > 1) { printf("Okay, enter %i names for the virtual nodes, one per line.\n"
			      "to fix a node, suffix a space then the name of the physical node.\n", 
			      vnodes ); }

674 675
    for (int i = 0; i < vnodes; i++) {
      char name[1024];
Chad Barb's avatar
Chad Barb committed
676
      char pname[1024];
677
      gets( line );
Chad Barb's avatar
Chad Barb committed
678 679
      if (sscanf( line, "%s %s", name, pname ) == 2) {
	map< string, int >::iterator it = reversePNodeNames.find( string( pname ) );
680
	if (it == reversePNodeNames.end()) {
Chad Barb's avatar
Chad Barb committed
681 682
	  fprintf(stderr,"pnode '%s' does not exist; can't fix.\n", pname );
	  exit(3);
683
	}
Chad Barb's avatar
Chad Barb committed
684 685
	if (verbose > 1) { 
	  printf("Fixing assignment from vnode %s to pnode %s.\n", name, pname );
686
	}
Chad Barb's avatar
Chad Barb committed
687 688
	fixed[i] = reversePNodeNames[ string( pname ) ];
	fixedNodeCount++;
689 690 691
      } else {
	fixed[i] = -1;
      }
Chad Barb's avatar
Chad Barb committed
692
      vnodeNames[i] = string( name );
693 694
    }

Chad Barb's avatar
Chad Barb committed
695
    for (int z = 0; z < dimensions; z++) {
Chad Barb's avatar
Chad Barb committed
696
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
697 698
	printf("Enter %ix%i grid o' desired %s (-1 is don't care.)\n", vnodes, vnodes, 
	       (z == 0) ? "latency" : "bandwidth");
699
      }
Chad Barb's avatar
Chad Barb committed
700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716
      for (int y = 0; y < vnodes; y++) {
	char * linePos = line;
	gets( line );
	while (*linePos == ' ') { linePos++; } // skip leading whitespace
	for (int x = 0; x < vnodes; x++) {
	  sscanf( linePos, "%i", &vDesiredLatency[z][x][y] );
	  if (z == 1) { 
	    if (vDesiredLatency[z][x][y] != -1) {
	      vDesiredLatency[z][x][y] = (int)(logf(vDesiredLatency[z][x][y]) * 1000.0f); 
	    }
	  }
	  while (*linePos != ' ' && *linePos != '\n') { linePos++; }
	  while (*linePos == ' ') { linePos++; }
	}
      }
    } 
  }
717

718 719 720
  Solution * currentPool = pool;
  Solution * nextPool = pool2;

Chad Barb's avatar
Chad Barb committed
721 722
  if (fixedNodeCount < vnodes) {
    if (verbose) { printf("Now running...\n"); }
723

Chad Barb's avatar
Chad Barb committed
724 725
    {
      for (int i = 0; i < SOLUTIONS; i++) {
726
	generateRandomSolution( &(currentPool[i]) );
Chad Barb's avatar
Chad Barb committed
727
      }
728
      sortByError( currentPool );
729 730 731
    }

    int highestFoundRound = 0;
732 733
    float last = currentPool[0].error;

734
    himutate = false;
Chad Barb's avatar
Chad Barb committed
735
    for (int i = 0; i != maxrounds && i < (highestFoundRound + minrounds); i++) {
736
      /*
737

738
      */
739 740 741 742 743 744 745 746 747 748 749 750
     
      float avg = 0.0f;
      int xy;
      for (xy = 0; xy < SOLUTIONS; xy++) { avg += currentPool[xy].error; }
      avg /= (float)SOLUTIONS;
      
      float stddev = 0.0f;
      for (xy = 0; xy < SOLUTIONS; xy++) { 
	float diff = currentPool[xy].error - avg;
	stddev += diff * diff;
      }
      stddev = sqrtf(stddev / (float)(SOLUTIONS - 1));
751
      
752
      if (verbose && !(i % 100)) {
753
	printf("Round %i. (best %4.3f; avg %4.3f; sdev %4.3f)\n", i, currentPool[0].error, avg, stddev);
754
      }
Chad Barb's avatar
Chad Barb committed
755
      
756
      if (currentPool[0].error < last) {
Chad Barb's avatar
Chad Barb committed
757 758
	if (verbose) {
	  printf("Better solution found in round %i (error %4.3f)\n", 
759
		 i, currentPool[0].error);
Chad Barb's avatar
Chad Barb committed
760
	}
761
	bestSpeed = msecscpu();
762
	last = currentPool[0].error;
763 764
	highestFoundRound = i;
      }
765

Chad Barb's avatar
Chad Barb committed
766 767
      // this is "elitism" -- the best solution is guaranteed to survive.
      // (otherwise, a good solution may be found, but may be lost by the next generation.)
768 769 770 771 772
      memcpy( &(nextPool[0]), &(currentPool[0]), sizeof( Solution ) );
      prepick( currentPool );

      int j;

773 774 775 776 777 778
      // if there is not enough variety, more mutation!
      if (stddev < (avg / 10.0f)) { 
	himutate = true;
      }

      for (j = 1; j < SOLUTIONS; j++) {
779 780 781 782 783
	splice( &(nextPool[j]),
		&(currentPool[pickABest( currentPool )]),
		&(currentPool[pickABest( currentPool )]) );
      }

784 785
      if (stddev < 0.1f) {
	himutate = false;
786
      }
787 788 789 790 791 792 793
      /*
	printf("NUKE!\n");
	for (j = SOLUTIONS - 10; j != SOLUTIONS; j++) {
	  generateRandomSolution( &(nextPool[j]) );	
	}
      }
      */
794
      /*      
795 796 797 798 799 800
      for (int j = 0; j < CHILDREN_PER_ROUND; j++) {
	// Overwrite a "bad" solution with the child of two "good" ones.
	splice( &(pool[pickAWorst()]), 
		&(pool[pickABest()]), 
		&(pool[pickABest()]) ); 
      }
801 802 803 804 805 806 807 808
      */
      sortByError( nextPool );

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

      if (currentPool[0].error < EPSILON) { 
Chad Barb's avatar
Chad Barb committed
809
	if (verbose > 1) { printf("Found perfect solution.\n"); }
810 811 812
	break;
      }
    }
Chad Barb's avatar
Chad Barb committed
813 814
  } else {
    if (verbose) { printf("No non-fixed vnodes (or no vnodes at all,) so nothing to be done!\n"); }
815 816 817
  }

  {
Chad Barb's avatar
Chad Barb committed
818
    if (verbose) { printf("\nYour solution is as follows:\n"); }
819
    for (int x = 0; x < vnodes; x++) {
820 821
      if (pnodeNames.find( currentPool[0].vnode_mapping[x] ) == pnodeNames.end()) {
	pnodeNames[ currentPool[0].vnode_mapping[x] ] = "CRAP";
Chad Barb's avatar
Chad Barb committed
822 823 824
      }
      printf("%s mapsTo %s\n", 
	     vnodeNames[x].c_str(),
825
	     pnodeNames[currentPool[0].vnode_mapping[x]].c_str() );
826
    }
827

828 829 830
    printf("\n");

    // dump a detailed report of the returned solution's errors.
831 832 833 834
    if (verbose > 1) { 
      calcError<true>( &(currentPool[0]) ); 
      printf("Found in %i msecs\n", bestSpeed );
    }
835 836
  }

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