wanlinksolve.cc 23.2 KB
Newer Older
1 2
/**** 
 wanlinksolve - 
Chad Barb's avatar
Chad Barb committed
3 4 5
 Resilient Overlay Network 
 Reasonably Effective Algorithm for Genetically Assigning Nodes.

6 7
 Chad Barb, May 3, 2002

Chad Barb's avatar
Chad Barb committed
8
 Applies a standard genetic algorithm (with crossover and elitism)
9 10 11 12
 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.

Chad Barb's avatar
Chad Barb committed
13
 The penalty function is the sum of error square roots (for the first dimension).
14 15 16 17

 For the application this was designed for,
 "weights" are values of latency time in milliseconds.

Chad Barb's avatar
Chad Barb committed
18
 switches: 
Chad Barb's avatar
Chad Barb committed
19 20
   -v     Extra verbosity
   -v -v  Jumbo verbosity 
Chad Barb's avatar
Chad Barb committed
21

Chad Barb's avatar
Chad Barb committed
22 23 24 25
   -1 <weight>
       Multiply penalty for latency by <weight>.
       (optional, default weight is 1.0)

Chad Barb's avatar
Chad Barb committed
26
   -2 <weight>
27
       Solve for 2nd (bandwidth) dimension;
Chad Barb's avatar
Chad Barb committed
28 29 30 31 32
       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.

Chad Barb's avatar
Chad Barb committed
33 34 35 36 37 38
   -3 <weight>
       Solve for 3rd (loss) dimension
       Penalty for error is difference of %% (10 * percent) loss,
       multiplied by <weight>.
       -2 must be specified first.

39 40 41
   -m <plexpenalty>
       Handle multiple virtual->physical mapping.
       For each vnode beyond 1 assigned to a pnode, <plexpenalty> will be assessed.
42 43 44
       Asks for 'p' lines of input, with the maximum number of virtual
       nodes allowed on a given physical node, per line (See below)

45 46 47
   -s <seed>
       Use a specific random seed.

Chad Barb's avatar
Chad Barb committed
48 49
   -r <roundswobetter>
       Specify the number of rounds to continue going without a better solution.
Chad Barb's avatar
Chad Barb committed
50 51 52 53 54
       default: DEFAULT_ROUNDS

   -R <maxrounds>
       Specify the absolute maximum number of rounds.
       default: -1 (infinite)
55 56 57 58 59 60 61

 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
62 63
 ? 'p' lines containing the maximum number of virtual nodes each 
       physical node can accommodate. ('-m' switch only)
64 65 66
 * '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
67
 ? 'p' lines, a P x P matrix of actual bandwidth ('-2' switch only)
Chad Barb's avatar
Chad Barb committed
68
 ? 'p' lines, a P x P matrix of actual loss ('-3' switch only)
Chad Barb's avatar
Chad Barb committed
69

70 71

 * One line containing a single number 'v'-- the number of virtual nodes.
72
 * 'v' lines containing the name of each virtual node.
Chad Barb's avatar
Chad Barb committed
73 74
       appending a space then the name of a physical node will permanently
       "fix" the mapping of this vnode to the named pnode.
75 76 77 78 79 80
 * '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
81
 ? 'v' lines, a V x V matrix of desired bandwidth ('-2' switch only)
Chad Barb's avatar
Chad Barb committed
82
 ? 'v' lines, a V x V matrix of desired loss ('-3' switch only)
83 84 85 86

 output format:
 
 Easily inferred. Note that the perl regexp:
87
 /(\S+)\smapsTo\s(\S+)/
88
 will grab vnode to pnode mappings (in $1 and $2, respectively.)
Chad Barb's avatar
Chad Barb committed
89 90 91 92 93 94 95 96 97 98


 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.

99 100 101 102 103
 
****/

#include <stdio.h>
#include <stdlib.h>
Chad Barb's avatar
Chad Barb committed
104 105
#include <stdarg.h>
#include <unistd.h>
Chad Barb's avatar
Chad Barb committed
106
#include <assert.h>
107
#include <math.h>
108 109 110
#include <sys/types.h>
#include <sys/time.h>
#include <sys/resource.h>
111 112 113 114 115

// 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.
116
#define MAX_NODES 32
Chad Barb's avatar
Chad Barb committed
117
#define MAX_DIMENSIONS 3
Chad Barb's avatar
Chad Barb committed
118

119 120
// default rounds to keep going without finding a better solution.
#define DEFAULT_ROUNDS 512
121 122

// The size of our "population."
Chad Barb's avatar
Chad Barb committed
123
// (number of phenotypes)
124
#define SOLUTIONS 400
125

Chad Barb's avatar
Chad Barb committed
126
// The probability a given child will mutate (out of 1000)
127 128
//#define MUTATE_PROB 40
#define MUTATE_PROB 10
129

Chad Barb's avatar
Chad Barb committed
130 131
// probability crossover will happen (out of 1000)
#define CROSSOVER_PROB 700
132 133 134 135 136 137 138 139 140 141 142 143 144 145 146

// 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
147
// some code to enable when the solver wedges and we don't know why.
Chad Barb's avatar
Chad Barb committed
148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166
#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

167 168
// keep track of user names for nodes.
static map< int, string > pnodeNames;
169
static map< string, int > reversePNodeNames;
170 171 172 173
static map< int, string > vnodeNames;

static int pnodes, vnodes;

Chad Barb's avatar
Chad Barb committed
174 175 176
static int pLatency[MAX_DIMENSIONS][MAX_NODES][MAX_NODES];
static int vDesiredLatency[MAX_DIMENSIONS][MAX_NODES][MAX_NODES];

177
static float plexPenalty = 0.0f;
178 179 180 181 182
static int maxplex[MAX_NODES];
static int userSpecifiedMultiplex = 0;

static int fixed[MAX_NODES];

Chad Barb's avatar
Chad Barb committed
183
static int dimensions;
Chad Barb's avatar
Chad Barb committed
184
static float d1weight, d2weight, d3weight;
Chad Barb's avatar
Chad Barb committed
185 186 187 188

static int verbose = 0;

static int minrounds, maxrounds;
189

190 191
static bool himutate = false;

192 193 194
class Solution
{
public:
Chad Barb's avatar
Chad Barb committed
195
  // the beef, as it were.
196
  int vnode_mapping[MAX_NODES];
197 198 199 200 201 202

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

Chad Barb's avatar
Chad Barb committed
203
  // calculated penalty
204
  float error;
Chad Barb's avatar
Chad Barb committed
205 206 207

  // probability of selecting this particular one (or any before it)
  // out of MAXINT
208
  unsigned int prob;
209 210
};

Chad Barb's avatar
Chad Barb committed
211 212 213
// 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)
214
static Solution pool[SOLUTIONS];
215
static Solution pool2[SOLUTIONS];
216

Chad Barb's avatar
Chad Barb committed
217 218
const char dimName[3][12] = { "latency", "bandwidth", "loss" };

Chad Barb's avatar
Chad Barb committed
219
// determines probabilities of selecting each solution.
220
static inline void prepick( Solution * currentPool )
221
{
222 223 224 225 226 227 228
  float totalFitness = 0.0f;
  int i;

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

229
  unsigned int probsofar = 0;
230
  for (i = 0; i < SOLUTIONS; i++) {
231 232
    probsofar += (unsigned int)(((float)0xFFFFFFFF / currentPool[i].error) / totalFitness);
    currentPool[i].prob = probsofar;
233
  }
234 235

  currentPool[SOLUTIONS - 1].prob = 0xFFFFFFFF;
236 237
}

238 239
// 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%.
240 241
static inline int pickABest( Solution * currentPool )
{
242 243 244 245 246 247 248 249 250 251 252 253 254 255 256
  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; 
    }
  } 
257

258 259
  return mid;
  /*
260 261
  int i = 0;
  while (1) { 
262
    if (x < currentPool[i].prob) break;
263
    i++;
264
    if (i == SOLUTIONS) { printf("Ick.\n"); i = 0; break;}
265 266
  }
  return i - 1;
267
  */
268 269
}

270

271
// uses a template to avoid massive numbers
272 273 274 275 276 277 278 279 280 281 282
// 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");
  }

283 284 285 286 287 288 289 290 291 292 293 294 295 296 297
  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;
      }
    }
  }

298
  {
Chad Barb's avatar
Chad Barb committed
299 300 301 302 303
    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) {
304
	    int is     = pLatency[z][ t->vnode_mapping[x] ][ t->vnode_mapping[y] ];
305 306 307 308 309 310 311
	    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
312 313 314
	      float errDelta;

	      if (z == 0) {
Chad Barb's avatar
Chad Barb committed
315 316
		errDelta = d1weight * sqrtf((float)(abs(should - is)));
	      } else if (z == 1) {
Chad Barb's avatar
Chad Barb committed
317
		errDelta = d2weight * (float)(abs(should - is));
318
		if (should < is) { errDelta *= 0.5f; }
Chad Barb's avatar
Chad Barb committed
319 320
	      } else {
		errDelta = d3weight * (float)(abs( should - is ));
Chad Barb's avatar
Chad Barb committed
321 322 323 324
	      }

	      if (verbose) {
		if (z == 0) {
Chad Barb's avatar
Chad Barb committed
325
		  printf("%s -> %s latency (ms) should be %i; is %i (err [wt * sqrt |a-b|] %4.3f)\n", 
Chad Barb's avatar
Chad Barb committed
326 327
			 vnodeNames[x].c_str(), vnodeNames[y].c_str(), 
			 should, is, errDelta );
Chad Barb's avatar
Chad Barb committed
328
		} else if (z == 1) {
329
		  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
330 331 332
			 vnodeNames[x].c_str(), vnodeNames[y].c_str(), 
			 (int)expf((float)should / 1000.0f), 
			 (int)expf((float)is / 1000.0f),
333
			 (should < is) ? "* 0.5 " : "",
Chad Barb's avatar
Chad Barb committed
334
			 errDelta );
Chad Barb's avatar
Chad Barb committed
335 336 337 338 339 340
		} else {
		  printf("%s -> %s loss should be %1.4f; is %1.4f (err [wt * |a-b|] %4.3f)\n",
			 vnodeNames[x].c_str(), vnodeNames[y].c_str(), 			 
			 (float)should / 65536.0f,
			 (float)is / 65536.0f,
			 errDelta );
Chad Barb's avatar
Chad Barb committed
341 342 343
		}
	      }
	      err += errDelta;
344 345 346 347 348 349 350
	    }
	  }
	}
      }
    }
  }

Chad Barb's avatar
Chad Barb committed
351
  if (verbose) { printf("error of %4.3f\n", err ); }
352 353 354 355 356 357 358 359 360 361 362 363 364
  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; }
}

365
static inline void sortByError( Solution * t )
366 367
{
  // Ahh.. sweet, sweet qsort.
368
  qsort( t, SOLUTIONS, sizeof( Solution ), compar );
369 370 371 372 373 374 375
}

// "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
376
  BEGIN_LOOP();
377
  while(1) {
Chad Barb's avatar
Chad Barb committed
378
    IN_LOOP();
379
    // forecast calls for a 1% chance of mutation...
380
    if ((rand() % 1000) > (himutate ? 500 : MUTATE_PROB)) { break; }
381 382 383 384
    
    if ((rand() % 3)) {
      // swap mutation. 
      int a, b;
Chad Barb's avatar
Chad Barb committed
385 386

      BEGIN_LOOP();
387
      do {
Chad Barb's avatar
Chad Barb committed
388
	IN_LOOP();
389
	a = rand() % vnodes;
Chad Barb's avatar
Chad Barb committed
390 391 392 393 394
      } while (fixed[a] != -1);

      BEGIN_LOOP();
      do {
	IN_LOOP();
395
	b = rand() % vnodes;
Chad Barb's avatar
Chad Barb committed
396 397 398 399 400 401 402
      } 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;
      }
403 404 405 406 407
    } else {
      // reassign mutation

      int a, b;
      // find which vnode to remap
Chad Barb's avatar
Chad Barb committed
408
      BEGIN_LOOP();
409
      do {
Chad Barb's avatar
Chad Barb committed
410
	IN_LOOP();
411 412 413 414 415 416 417
	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
418
      BEGIN_LOOP();
419
      do {
Chad Barb's avatar
Chad Barb committed
420
	IN_LOOP();
421 422 423 424 425 426 427
	b = rand() % pnodes;
      } while (t->pnode_uses[b] >= maxplex[b]);

      // now map it.
      t->vnode_mapping[a] = b;
      ++t->pnode_uses[b];
    }
428 429 430 431 432 433 434 435
  }
}

// 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
436 437 438 439 440 441 442 443 444 445 446 447 448 449 450
  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];
      }
451
    }
Chad Barb's avatar
Chad Barb committed
452
  } else {
453

Chad Barb's avatar
Chad Barb committed
454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478
    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] ];
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[ 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;
492
	  }
493 494
	}
      } else {
Chad Barb's avatar
Chad Barb committed
495 496 497
	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] ];
498
	} else {
Chad Barb's avatar
Chad Barb committed
499 500 501 502 503 504 505 506 507 508 509 510
	  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;
511
	  }
512 513 514 515 516 517 518 519 520 521 522 523 524
	}
      }
    }
  }

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

// Generate a random solution 
// for the initial population.
static inline void generateRandomSolution( Solution * t )
{
525 526
  //int pnode_uses[MAX_NODES];
  bzero( t->pnode_uses, sizeof( t->pnode_uses ) );
527 528 529 530

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] != -1) {
      t->vnode_mapping[i] = fixed[i];
531
      ++t->pnode_uses[ fixed[i] ];
532 533
    }
  }
534 535 536 537

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] == -1) {
      int x;
Chad Barb's avatar
Chad Barb committed
538
      BEGIN_LOOP();
539
      do {
Chad Barb's avatar
Chad Barb committed
540
	IN_LOOP();
541
	x = rand() % pnodes;
542 543
      } while( t->pnode_uses[x] >= maxplex[x] );
      ++t->pnode_uses[x];
544 545 546 547
      t->vnode_mapping[i] = x;
    }
  }

548 549 550
  calcError<false>( t );
}

Chad Barb's avatar
Chad Barb committed
551
void usage( char * appname )
552
{
Chad Barb's avatar
Chad Barb committed
553 554
  fprintf(stderr,
	  "Usage:\n"
Chad Barb's avatar
Chad Barb committed
555 556
	  "%s [-v [-v]] [-m <penalty>] [-s <seed>] [-1 <weight>]\n"
	  "\t[-2 <weight> [-3 <weight>]] [-r <minrounds>] [-R <maxrounds>]\n\n"
Chad Barb's avatar
Chad Barb committed
557
	  "  -v              extra verbosity\n"
Chad Barb's avatar
Chad Barb committed
558
	  "  -v -v           jumbo verbosity\n"
559 560
	  "  -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
561
	  "  -1 <weight>     assign weight to latency penalty (optional; default 1.0)\n"
Chad Barb's avatar
Chad Barb committed
562 563
	  "  -2 <weight>     enable solving for bandwidth;\n"
	  "                  multiply bandwidth penalties by <weight>.\n"
Chad Barb's avatar
Chad Barb committed
564 565
	  "  -3 <weight>     enable solving for loss.\n"
	  "                  (must specify -2 first)\n"
Chad Barb's avatar
Chad Barb committed
566
	  "  -r <minrounds>  number of rounds to go without a solution before stopping\n"
Chad Barb's avatar
Chad Barb committed
567 568 569
	  "                  default: %i\n"
	  "  -R <maxrounds>  set maximum rounds\n"
	  "                  default: infinite (-1)\n\n", appname, DEFAULT_ROUNDS );
Chad Barb's avatar
Chad Barb committed
570
  exit(1);
Chad Barb's avatar
Chad Barb committed
571 572
}

573 574 575 576 577 578 579 580 581 582
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
583 584
int main( int argc, char ** argv )
{
Chad Barb's avatar
Chad Barb committed
585 586
  int available = 0;
  int fixedNodeCount = 0;
587
  unsigned int bestSpeed = 0;
Chad Barb's avatar
Chad Barb committed
588

Chad Barb's avatar
Chad Barb committed
589 590
  verbose = 0;
  dimensions = 1;
Chad Barb's avatar
Chad Barb committed
591
  d1weight = 1.0f;
Chad Barb's avatar
Chad Barb committed
592
  d2weight = 1.0f / 1000.0f;
Chad Barb's avatar
Chad Barb committed
593
  d3weight = 1.0f / 65536.0f;
Chad Barb's avatar
Chad Barb committed
594 595 596 597 598 599

  minrounds = DEFAULT_ROUNDS;
  maxrounds = -1;

  int ch;

Chad Barb's avatar
Chad Barb committed
600
  while ((ch = getopt(argc, argv, "v1:2:3:r:R:s:m:")) != -1) {
Chad Barb's avatar
Chad Barb committed
601
    switch (ch) {
602 603 604
    case 's':
      srand( atoi( optarg ) );
      break;
Chad Barb's avatar
Chad Barb committed
605 606 607
    case 'v': 
      verbose++; 
      break;
608
    case 'm':
609
      plexPenalty = atof( optarg );
610 611
      userSpecifiedMultiplex++;
      break;
Chad Barb's avatar
Chad Barb committed
612 613 614
    case '1':
      d1weight = atof( optarg );
      break;
Chad Barb's avatar
Chad Barb committed
615 616 617 618
    case '2': 
      dimensions = 2;
      d2weight = atof( optarg ) / 1000.0f; 
      break;
Chad Barb's avatar
Chad Barb committed
619 620 621 622 623 624 625 626 627
    case '3':
      if (dimensions != 2) {
	fprintf(stderr, "Must specify -2 option first when using -3.\n");
	exit(1);
      } else {
	dimensions = 3;
	d3weight = atof( optarg ) / 65536.0f;
      }
      break;
Chad Barb's avatar
Chad Barb committed
628 629 630 631 632 633 634 635
    case 'r':
      minrounds = atoi( optarg );
      break;
    case 'R':
      maxrounds = atoi( optarg );
      break;
    default: 
      usage( argv[0] );
Chad Barb's avatar
Chad Barb committed
636
      break;
Chad Barb's avatar
Chad Barb committed
637 638 639 640
    }
  }


641
  char line[4096];
642 643

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

Chad Barb's avatar
Chad Barb committed
648
    if (verbose > 1) { printf("Okay, enter %i names for the physical nodes, one per line.\n", pnodes ); }
649 650 651 652 653
    for (int i = 0; i < pnodes; i++) {
      char name[1024];
      gets( line );
      sscanf( line, "%s", name );
      pnodeNames[i] = string( name );
654 655 656 657
      reversePNodeNames[string(name)] = i;
    }

    if (userSpecifiedMultiplex) {
Chad Barb's avatar
Chad Barb committed
658
      if (verbose > 1) { printf("Enter %i numbers, one per line, indicating the"
659 660 661 662 663
			    " 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
664
	available += maxplex[i];
665 666 667 668
      }
    } else {
      for (int i = 0; i < pnodes; i++) {
	maxplex[i] = 1;
Chad Barb's avatar
Chad Barb committed
669
	++available;
670
      }
671 672
    }

Chad Barb's avatar
Chad Barb committed
673
    for (int z = 0; z < dimensions; z++) {
Chad Barb's avatar
Chad Barb committed
674
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
675
	printf("Enter %ix%i grid o' actual %s.\n", pnodes, pnodes, dimName[z]);
Chad Barb's avatar
Chad Barb committed
676 677 678 679 680 681
      }
      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++) {
Chad Barb's avatar
Chad Barb committed
682
	  float temp;
Chad Barb's avatar
Chad Barb committed
683
	  sscanf( linePos, "%i", &pLatency[z][x][y] );
Chad Barb's avatar
Chad Barb committed
684
	  sscanf( linePos, "%f", &temp );
685
	    if (pLatency[z][x][y] != -1) {
Chad Barb's avatar
Chad Barb committed
686 687 688 689 690
	      if (z == 1) { 
		pLatency[z][x][y] = (int)( logf(pLatency[z][x][y]) * 1000.0f ); 
	      } else if (z == 2) {
		pLatency[z][x][y] = (int)(temp * 65536.0f);
	      }
691
	  }
Chad Barb's avatar
Chad Barb committed
692 693 694
	  while (*linePos != ' ' && *linePos != '\n') { linePos++; }
	  while (*linePos == ' ') { linePos++; }
	}
695 696 697 698 699
      }
    }
  } 

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

Chad Barb's avatar
Chad Barb committed
704 705 706 707 708 709 710 711 712 713 714
    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 ); }

715 716
    for (int i = 0; i < vnodes; i++) {
      char name[1024];
Chad Barb's avatar
Chad Barb committed
717
      char pname[1024];
718
      gets( line );
Chad Barb's avatar
Chad Barb committed
719 720
      if (sscanf( line, "%s %s", name, pname ) == 2) {
	map< string, int >::iterator it = reversePNodeNames.find( string( pname ) );
721
	if (it == reversePNodeNames.end()) {
Chad Barb's avatar
Chad Barb committed
722 723
	  fprintf(stderr,"pnode '%s' does not exist; can't fix.\n", pname );
	  exit(3);
724
	}
Chad Barb's avatar
Chad Barb committed
725 726
	if (verbose > 1) { 
	  printf("Fixing assignment from vnode %s to pnode %s.\n", name, pname );
727
	}
Chad Barb's avatar
Chad Barb committed
728 729
	fixed[i] = reversePNodeNames[ string( pname ) ];
	fixedNodeCount++;
730 731 732
      } else {
	fixed[i] = -1;
      }
Chad Barb's avatar
Chad Barb committed
733
      vnodeNames[i] = string( name );
734 735
    }

Chad Barb's avatar
Chad Barb committed
736
    for (int z = 0; z < dimensions; z++) {
Chad Barb's avatar
Chad Barb committed
737
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
738
	printf("Enter %ix%i grid o' desired %s (-1 is don't care.)\n", vnodes, vnodes, 
Chad Barb's avatar
Chad Barb committed
739
	       dimName[z]);
740
      }
Chad Barb's avatar
Chad Barb committed
741 742 743 744 745
      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++) {
Chad Barb's avatar
Chad Barb committed
746
	  float temp;
Chad Barb's avatar
Chad Barb committed
747
	  sscanf( linePos, "%i", &vDesiredLatency[z][x][y] );
Chad Barb's avatar
Chad Barb committed
748 749 750
	  sscanf( linePos, "%f", &temp );
	  if (vDesiredLatency[z][x][y] != -1) {
	    if (z == 1) { 
Chad Barb's avatar
Chad Barb committed
751
	      vDesiredLatency[z][x][y] = (int)(logf(vDesiredLatency[z][x][y]) * 1000.0f); 
Chad Barb's avatar
Chad Barb committed
752 753
	    } else if (z == 2) {
	      vDesiredLatency[z][x][y] = (int)(temp * 65536.0f);
Chad Barb's avatar
Chad Barb committed
754 755 756 757 758 759 760 761
	    }
	  }
	  while (*linePos != ' ' && *linePos != '\n') { linePos++; }
	  while (*linePos == ' ') { linePos++; }
	}
      }
    } 
  }
762

763 764 765
  Solution * currentPool = pool;
  Solution * nextPool = pool2;

Chad Barb's avatar
Chad Barb committed
766 767
  if (fixedNodeCount < vnodes) {
    if (verbose) { printf("Now running...\n"); }
768

Chad Barb's avatar
Chad Barb committed
769 770
    {
      for (int i = 0; i < SOLUTIONS; i++) {
771
	generateRandomSolution( &(currentPool[i]) );
Chad Barb's avatar
Chad Barb committed
772
      }
773
      sortByError( currentPool );
774 775 776
    }

    int highestFoundRound = 0;
777 778
    float last = currentPool[0].error;

779
    himutate = false;
Chad Barb's avatar
Chad Barb committed
780
    for (int i = 0; i != maxrounds && i < (highestFoundRound + minrounds); i++) {
781 782 783 784 785 786 787 788 789 790 791 792
     
      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));
793
      
794
      if (verbose && !(i % 100)) {
795
	printf("Round %i. (best %4.3f; avg %4.3f; sdev %4.3f)\n", i, currentPool[0].error, avg, stddev);
796
      }
Chad Barb's avatar
Chad Barb committed
797
      
798
      if (currentPool[0].error < last) {
Chad Barb's avatar
Chad Barb committed
799 800
	if (verbose) {
	  printf("Better solution found in round %i (error %4.3f)\n", 
801
		 i, currentPool[0].error);
Chad Barb's avatar
Chad Barb committed
802
	}
803
	bestSpeed = msecscpu();
804
	last = currentPool[0].error;
805 806
	highestFoundRound = i;
      }
807

Chad Barb's avatar
Chad Barb committed
808 809
      // 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.)
810 811 812 813 814
      memcpy( &(nextPool[0]), &(currentPool[0]), sizeof( Solution ) );
      prepick( currentPool );

      int j;

815 816 817 818 819 820
      // if there is not enough variety, more mutation!
      if (stddev < (avg / 10.0f)) { 
	himutate = true;
      }

      for (j = 1; j < SOLUTIONS; j++) {
821 822 823 824 825
	splice( &(nextPool[j]),
		&(currentPool[pickABest( currentPool )]),
		&(currentPool[pickABest( currentPool )]) );
      }

826 827
      if (stddev < 0.1f) {
	himutate = false;
828
      }
Chad Barb's avatar
Chad Barb committed
829

830 831 832 833 834 835 836
      sortByError( nextPool );

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

      if (currentPool[0].error < EPSILON) { 
Chad Barb's avatar
Chad Barb committed
837
	if (verbose > 1) { printf("Found perfect solution.\n"); }
838 839 840
	break;
      }
    }
Chad Barb's avatar
Chad Barb committed
841 842
  } else {
    if (verbose) { printf("No non-fixed vnodes (or no vnodes at all,) so nothing to be done!\n"); }
843 844 845
  }

  {
Chad Barb's avatar
Chad Barb committed
846
    if (verbose) { printf("\nYour solution is as follows:\n"); }
847
    for (int x = 0; x < vnodes; x++) {
848 849
      if (pnodeNames.find( currentPool[0].vnode_mapping[x] ) == pnodeNames.end()) {
	pnodeNames[ currentPool[0].vnode_mapping[x] ] = "CRAP";
Chad Barb's avatar
Chad Barb committed
850 851 852
      }
      printf("%s mapsTo %s\n", 
	     vnodeNames[x].c_str(),
853
	     pnodeNames[currentPool[0].vnode_mapping[x]].c_str() );
854
    }
855

856 857 858
    printf("\n");

    // dump a detailed report of the returned solution's errors.
859 860 861 862
    if (verbose > 1) { 
      calcError<true>( &(currentPool[0]) ); 
      printf("Found in %i msecs\n", bestSpeed );
    }
863 864
  }

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