wanlinksolve.cc 21.6 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 400
109

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

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

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

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

static int pnodes, vnodes;

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

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

static int fixed[MAX_NODES];

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

static int verbose = 0;

static int minrounds, maxrounds;
173

174 175
static bool himutate = false;

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

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

186
  float error;
187
  unsigned int prob;
188 189
};

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

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

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

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

  currentPool[SOLUTIONS - 1].prob = 0xFFFFFFFF;
213 214
}

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

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

247

248
// uses a template to avoid massive numbers
249 250 251 252 253 254 255 256 257 258 259
// 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");
  }

260 261 262 263 264 265 266 267 268 269 270 271 272 273 274
  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;
      }
    }
  }

275
  {
Chad Barb's avatar
Chad Barb committed
276 277 278 279 280
    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) {
281
	    int is     = pLatency[z][ t->vnode_mapping[x] ][ t->vnode_mapping[y] ];
282 283 284 285 286 287 288
	    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
289 290 291 292 293 294
	      float errDelta;

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

	      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 {
304
		  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
305 306 307
			 vnodeNames[x].c_str(), vnodeNames[y].c_str(), 
			 (int)expf((float)should / 1000.0f), 
			 (int)expf((float)is / 1000.0f),
308
			 (should < is) ? "* 0.5 " : "",
Chad Barb's avatar
Chad Barb committed
309 310 311 312
			 errDelta );
		}
	      }
	      err += errDelta;
313 314 315 316 317 318 319
	    }
	  }
	}
      }
    }
  }

Chad Barb's avatar
Chad Barb committed
320
  if (verbose) { printf("error of %4.3f\n", err ); }
321 322 323 324 325 326 327 328 329 330 331 332 333
  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; }
}

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

// "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
345
  BEGIN_LOOP();
346
  while(1) {
Chad Barb's avatar
Chad Barb committed
347
    IN_LOOP();
348
    // forecast calls for a 1% chance of mutation...
349
    if ((rand() % 1000) > (himutate ? 500 : MUTATE_PROB)) { break; }
350 351 352 353
    
    if ((rand() % 3)) {
      // swap mutation. 
      int a, b;
Chad Barb's avatar
Chad Barb committed
354 355

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

      BEGIN_LOOP();
      do {
	IN_LOOP();
364
	b = rand() % vnodes;
Chad Barb's avatar
Chad Barb committed
365 366 367 368 369 370 371
      } 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;
      }
372 373 374 375 376 377 378 379 380 381 382 383 384 385
    } 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
386
      BEGIN_LOOP();
387
      do {
Chad Barb's avatar
Chad Barb committed
388
	IN_LOOP();
389 390 391 392 393 394 395
	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
396
      BEGIN_LOOP();
397
      do {
Chad Barb's avatar
Chad Barb committed
398
	IN_LOOP();
399 400 401 402 403 404 405
	b = rand() % pnodes;
      } while (t->pnode_uses[b] >= maxplex[b]);

      // now map it.
      t->vnode_mapping[a] = b;
      ++t->pnode_uses[b];
    }
406 407 408 409 410 411 412 413
  }
}

// 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
414 415 416 417 418 419 420 421 422 423 424 425 426 427 428
  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];
      }
429
    }
Chad Barb's avatar
Chad Barb committed
430
  } else {
431

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

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

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

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

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

526 527 528
  calcError<false>( t );
}

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

int main( int argc, char ** argv )
{
Chad Barb's avatar
Chad Barb committed
549 550 551
  int available = 0;
  int fixedNodeCount = 0;

Chad Barb's avatar
Chad Barb committed
552 553 554 555 556 557 558 559 560
  verbose = 0;
  dimensions = 1;
  d2weight = 1.0f / 1000.0f;

  minrounds = DEFAULT_ROUNDS;
  maxrounds = -1;

  int ch;

561
  while ((ch = getopt(argc, argv, "v2:r:R:s:m:")) != -1) {
Chad Barb's avatar
Chad Barb committed
562
    switch (ch) {
563 564 565
    case 's':
      srand( atoi( optarg ) );
      break;
Chad Barb's avatar
Chad Barb committed
566 567 568
    case 'v': 
      verbose++; 
      break;
569
    case 'm':
570
      plexPenalty = atof( optarg );
571 572
      userSpecifiedMultiplex++;
      break;
Chad Barb's avatar
Chad Barb committed
573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588
    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] );
    }
  }


589 590 591
  char line[1024];

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

Chad Barb's avatar
Chad Barb committed
596
    if (verbose > 1) { printf("Okay, enter %i names for the physical nodes, one per line.\n", pnodes ); }
597 598 599 600 601
    for (int i = 0; i < pnodes; i++) {
      char name[1024];
      gets( line );
      sscanf( line, "%s", name );
      pnodeNames[i] = string( name );
602 603 604 605
      reversePNodeNames[string(name)] = i;
    }

    if (userSpecifiedMultiplex) {
Chad Barb's avatar
Chad Barb committed
606
      if (verbose > 1) { printf("Enter %i numbers, one per line, indicating the"
607 608 609 610 611
			    " 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
612
	available += maxplex[i];
613 614 615 616
      }
    } else {
      for (int i = 0; i < pnodes; i++) {
	maxplex[i] = 1;
Chad Barb's avatar
Chad Barb committed
617
	++available;
618
      }
619 620
    }

Chad Barb's avatar
Chad Barb committed
621
    for (int z = 0; z < dimensions; z++) {
Chad Barb's avatar
Chad Barb committed
622
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
623 624 625 626 627 628 629 630 631
	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] );
632 633 634 635 636
	  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
637 638 639
	  while (*linePos != ' ' && *linePos != '\n') { linePos++; }
	  while (*linePos == ' ') { linePos++; }
	}
640 641 642 643 644
      }
    }
  } 

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

Chad Barb's avatar
Chad Barb committed
649 650 651 652 653 654 655 656 657 658 659
    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 ); }

660 661
    for (int i = 0; i < vnodes; i++) {
      char name[1024];
Chad Barb's avatar
Chad Barb committed
662
      char pname[1024];
663
      gets( line );
Chad Barb's avatar
Chad Barb committed
664 665
      if (sscanf( line, "%s %s", name, pname ) == 2) {
	map< string, int >::iterator it = reversePNodeNames.find( string( pname ) );
666
	if (it == reversePNodeNames.end()) {
Chad Barb's avatar
Chad Barb committed
667 668
	  fprintf(stderr,"pnode '%s' does not exist; can't fix.\n", pname );
	  exit(3);
669
	}
Chad Barb's avatar
Chad Barb committed
670 671
	if (verbose > 1) { 
	  printf("Fixing assignment from vnode %s to pnode %s.\n", name, pname );
672
	}
Chad Barb's avatar
Chad Barb committed
673 674
	fixed[i] = reversePNodeNames[ string( pname ) ];
	fixedNodeCount++;
675 676 677
      } else {
	fixed[i] = -1;
      }
Chad Barb's avatar
Chad Barb committed
678
      vnodeNames[i] = string( name );
679 680
    }

Chad Barb's avatar
Chad Barb committed
681
    for (int z = 0; z < dimensions; z++) {
Chad Barb's avatar
Chad Barb committed
682
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
683 684
	printf("Enter %ix%i grid o' desired %s (-1 is don't care.)\n", vnodes, vnodes, 
	       (z == 0) ? "latency" : "bandwidth");
685
      }
Chad Barb's avatar
Chad Barb committed
686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702
      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++; }
	}
      }
    } 
  }
703

704 705 706
  Solution * currentPool = pool;
  Solution * nextPool = pool2;

Chad Barb's avatar
Chad Barb committed
707 708
  if (fixedNodeCount < vnodes) {
    if (verbose) { printf("Now running...\n"); }
709

Chad Barb's avatar
Chad Barb committed
710 711
    {
      for (int i = 0; i < SOLUTIONS; i++) {
712
	generateRandomSolution( &(currentPool[i]) );
Chad Barb's avatar
Chad Barb committed
713
      }
714
      sortByError( currentPool );
715 716 717
    }

    int highestFoundRound = 0;
718 719
    float last = currentPool[0].error;

720
    himutate = false;
Chad Barb's avatar
Chad Barb committed
721
    for (int i = 0; i != maxrounds && i < (highestFoundRound + minrounds); i++) {
722
      /*
723

724
      */
725 726 727 728 729 730 731 732 733 734 735 736
     
      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));
737
      
738
      if (verbose && !(i % 100)) {
739
	printf("Round %i. (best %4.3f; avg %4.3f; sdev %4.3f)\n", i, currentPool[0].error, avg, stddev);
740
      }
Chad Barb's avatar
Chad Barb committed
741
      
742
      if (currentPool[0].error < last) {
Chad Barb's avatar
Chad Barb committed
743 744
	if (verbose) {
	  printf("Better solution found in round %i (error %4.3f)\n", 
745
		 i, currentPool[0].error);
Chad Barb's avatar
Chad Barb committed
746
	}
747
	last = currentPool[0].error;
748 749
	highestFoundRound = i;
      }
750

Chad Barb's avatar
Chad Barb committed
751 752
      // 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.)
753 754 755 756 757
      memcpy( &(nextPool[0]), &(currentPool[0]), sizeof( Solution ) );
      prepick( currentPool );

      int j;

758 759 760 761 762 763
      // if there is not enough variety, more mutation!
      if (stddev < (avg / 10.0f)) { 
	himutate = true;
      }

      for (j = 1; j < SOLUTIONS; j++) {
764 765 766 767 768
	splice( &(nextPool[j]),
		&(currentPool[pickABest( currentPool )]),
		&(currentPool[pickABest( currentPool )]) );
      }

769 770
      if (stddev < 0.1f) {
	himutate = false;
771
      }
772 773 774 775 776 777 778
      /*
	printf("NUKE!\n");
	for (j = SOLUTIONS - 10; j != SOLUTIONS; j++) {
	  generateRandomSolution( &(nextPool[j]) );	
	}
      }
      */
779
      /*      
780 781 782 783 784 785
      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()]) ); 
      }
786 787 788 789 790 791 792 793
      */
      sortByError( nextPool );

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

      if (currentPool[0].error < EPSILON) { 
Chad Barb's avatar
Chad Barb committed
794
	if (verbose > 1) { printf("Found perfect solution.\n"); }
795 796 797
	break;
      }
    }
Chad Barb's avatar
Chad Barb committed
798 799
  } else {
    if (verbose) { printf("No non-fixed vnodes (or no vnodes at all,) so nothing to be done!\n"); }
800 801 802
  }

  {
Chad Barb's avatar
Chad Barb committed
803
    if (verbose) { printf("\nYour solution is as follows:\n"); }
804
    for (int x = 0; x < vnodes; x++) {
805 806
      if (pnodeNames.find( currentPool[0].vnode_mapping[x] ) == pnodeNames.end()) {
	pnodeNames[ currentPool[0].vnode_mapping[x] ] = "CRAP";
Chad Barb's avatar
Chad Barb committed
807 808 809
      }
      printf("%s mapsTo %s\n", 
	     vnodeNames[x].c_str(),
810
	     pnodeNames[currentPool[0].vnode_mapping[x]].c_str() );
811
    }
812

813 814 815
    printf("\n");

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

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