wanlinksolve.cc 25.2 KB
Newer Older
Leigh Stoller's avatar
Leigh Stoller committed
1
/*
2
 * Copyright (c) 2000-2003 University of Utah and the Flux Group.
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
 * 
 * {{{EMULAB-LICENSE
 * 
 * This file is part of the Emulab network testbed software.
 * 
 * This file is free software: you can redistribute it and/or modify it
 * under the terms of the GNU Affero General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or (at
 * your option) any later version.
 * 
 * This file is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Affero General Public
 * License for more details.
 * 
 * You should have received a copy of the GNU Affero General Public License
 * along with this file.  If not, see <http://www.gnu.org/licenses/>.
 * 
 * }}}
Leigh Stoller's avatar
Leigh Stoller committed
22 23
 */

24 25
/**** 
 wanlinksolve - 
Chad Barb's avatar
Chad Barb committed
26 27 28
 Resilient Overlay Network 
 Reasonably Effective Algorithm for Genetically Assigning Nodes.

29 30
 Chad Barb, May 3, 2002

Chad Barb's avatar
Chad Barb committed
31
 Applies a standard genetic algorithm (with crossover and elitism)
32 33 34 35
 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
36
 The penalty function is the sum of error square roots (for the first dimension).
37 38 39 40

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

Chad Barb's avatar
Chad Barb committed
41
 switches: 
42 43
   -v     Extra verbosity
   -v -v  Jumbo verbosity 
Chad Barb's avatar
Chad Barb committed
44

Chad Barb's avatar
Chad Barb committed
45 46 47 48
   -1 <weight>
       Multiply penalty for latency by <weight>.
       (optional, default weight is 1.0)

Chad Barb's avatar
Chad Barb committed
49
   -2 <weight>
50
       Solve for 2nd (bandwidth) dimension;
Chad Barb's avatar
Chad Barb committed
51 52 53 54 55
       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
56 57 58 59 60 61
   -3 <weight>
       Solve for 3rd (loss) dimension
       Penalty for error is difference of %% (10 * percent) loss,
       multiplied by <weight>.
       -2 must be specified first.

62 63 64
   -m <plexpenalty>
       Handle multiple virtual->physical mapping.
       For each vnode beyond 1 assigned to a pnode, <plexpenalty> will be assessed.
65 66 67
       Asks for 'p' lines of input, with the maximum number of virtual
       nodes allowed on a given physical node, per line (See below)

68 69 70
   -s <seed>
       Use a specific random seed.

Chad Barb's avatar
Chad Barb committed
71 72
   -r <roundswobetter>
       Specify the number of rounds to continue going without a better solution.
Chad Barb's avatar
Chad Barb committed
73 74 75 76 77
       default: DEFAULT_ROUNDS

   -R <maxrounds>
       Specify the absolute maximum number of rounds.
       default: -1 (infinite)
78 79 80 81 82 83 84

 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
85 86
 ? 'p' lines containing the maximum number of virtual nodes each 
       physical node can accommodate. ('-m' switch only)
87 88 89
 * '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
90
 ? 'p' lines, a P x P matrix of actual bandwidth ('-2' switch only)
Chad Barb's avatar
Chad Barb committed
91
 ? 'p' lines, a P x P matrix of actual loss ('-3' switch only)
Chad Barb's avatar
Chad Barb committed
92

93 94

 * One line containing a single number 'v'-- the number of virtual nodes.
95
 * 'v' lines containing the name of each virtual node.
96 97
       appending a space then the name of a physical node will permanently
       "fix" the mapping of this vnode to the named pnode.
98 99 100 101 102 103
 * '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
104
 ? 'v' lines, a V x V matrix of desired bandwidth ('-2' switch only)
Chad Barb's avatar
Chad Barb committed
105
 ? 'v' lines, a V x V matrix of desired loss ('-3' switch only)
106 107 108 109

 output format:
 
 Easily inferred. Note that the perl regexp:
110
 /(\S+)\smapsTo\s(\S+)/
111
 will grab vnode to pnode mappings (in $1 and $2, respectively.)
Chad Barb's avatar
Chad Barb committed
112 113 114 115 116 117 118 119 120 121


 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.

122 123 124 125 126
 
****/

#include <stdio.h>
#include <stdlib.h>
Chad Barb's avatar
Chad Barb committed
127 128
#include <stdarg.h>
#include <unistd.h>
129
#include <assert.h>
130
#include <math.h>
131 132 133
#include <sys/types.h>
#include <sys/time.h>
#include <sys/resource.h>
134 135 136 137 138

// 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.
139 140
#define MAX_PNODES 256
#define MAX_VNODES 64
Chad Barb's avatar
Chad Barb committed
141
#define MAX_DIMENSIONS 3
Chad Barb's avatar
Chad Barb committed
142

143 144
// default rounds to keep going without finding a better solution.
#define DEFAULT_ROUNDS 512
145 146

// The size of our "population."
Chad Barb's avatar
Chad Barb committed
147
// (number of phenotypes)
148
#define SOLUTIONS 400
149

Chad Barb's avatar
Chad Barb committed
150
// The probability a given child will mutate (out of 1000)
151 152
//#define MUTATE_PROB 40
#define MUTATE_PROB 10
153

Chad Barb's avatar
Chad Barb committed
154 155
// probability crossover will happen (out of 1000)
#define CROSSOVER_PROB 700
156 157 158 159 160 161 162 163 164 165 166 167

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

Chad Barb's avatar
Chad Barb committed
168
// some code to enable when the solver wedges and we don't know why.
169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
#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

188 189
// keep track of user names for nodes.
static map< int, string > pnodeNames;
190
static map< string, int > reversePNodeNames;
191 192 193 194
static map< int, string > vnodeNames;

static int pnodes, vnodes;

195 196
static int pLatency[MAX_DIMENSIONS][MAX_PNODES][MAX_PNODES];
static int vDesiredLatency[MAX_DIMENSIONS][MAX_VNODES][MAX_VNODES];
Chad Barb's avatar
Chad Barb committed
197

198
static float plexPenalty = 0.0f;
199
static int maxplex[MAX_PNODES];
200 201
static int userSpecifiedMultiplex = 0;

202
static int fixed[MAX_VNODES];
203

Chad Barb's avatar
Chad Barb committed
204
static int dimensions;
Chad Barb's avatar
Chad Barb committed
205
static float d1weight, d2weight, d3weight;
Chad Barb's avatar
Chad Barb committed
206 207 208 209

static int verbose = 0;

static int minrounds, maxrounds;
210

211 212
static bool himutate = false;

213 214 215
class Solution
{
public:
Chad Barb's avatar
Chad Barb committed
216
  // the beef, as it were.
217
  int vnode_mapping[MAX_VNODES];
218 219 220 221

  // 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.)
222
  unsigned char pnode_uses[MAX_PNODES];
223

Chad Barb's avatar
Chad Barb committed
224
  // calculated penalty
225
  float error;
Chad Barb's avatar
Chad Barb committed
226 227 228

  // probability of selecting this particular one (or any before it)
  // out of MAXINT
229
  unsigned int prob;
230 231
};

Chad Barb's avatar
Chad Barb committed
232 233 234
// 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)
235
static Solution pool[SOLUTIONS];
236
static Solution pool2[SOLUTIONS];
237

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

Chad Barb's avatar
Chad Barb committed
240
// determines probabilities of selecting each solution.
241
static inline void prepick( Solution * currentPool )
242
{
243 244 245 246 247 248 249
  float totalFitness = 0.0f;
  int i;

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

250
  unsigned int probsofar = 0;
251
  for (i = 0; i < SOLUTIONS; i++) {
252 253
    probsofar += (unsigned int)(((float)0xFFFFFFFF / currentPool[i].error) / totalFitness);
    currentPool[i].prob = probsofar;
254
  }
255 256

  currentPool[SOLUTIONS - 1].prob = 0xFFFFFFFF;
257 258
}

259 260
// 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%.
261 262
static inline int pickABest( Solution * currentPool )
{
263 264 265 266 267 268 269 270 271 272 273 274 275 276 277
  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; 
    }
  } 
278

279 280
  return mid;
  /*
281 282
  int i = 0;
  while (1) { 
283
    if (x < currentPool[i].prob) break;
284
    i++;
285
    if (i == SOLUTIONS) { printf("Ick.\n"); i = 0; break;}
286 287
  }
  return i - 1;
288
  */
289 290
}

291

292
// uses a template to avoid massive numbers
293 294
// of "if" choices.. compiler should generate two versions,
// one with dump and one without.
295 296 297
// returns 'true' if solution is free of invalidities 
// (e.g. no unusable links are used,)
// 'false' if invalid.
298
template <bool verbose>
299
static inline bool calcError( Solution * t )
300
{ 
301
  bool valid = true;
302 303 304 305 306 307
  float err = 0.0f;

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

308 309 310 311 312 313 314 315 316 317 318 319 320 321 322
  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;
      }
    }
  }

323
  {
Chad Barb's avatar
Chad Barb committed
324 325 326 327 328
    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) {
329
	    int is     = pLatency[z][ t->vnode_mapping[x] ][ t->vnode_mapping[y] ];
330 331
	    if (is == -1) {
	      if (verbose) {
332
		printf("%s -> %s link nonexistant! Super-icky penality of 100000 assessed.\n",
333 334
		       vnodeNames[x].c_str(), vnodeNames[y].c_str() ); 
	      }
335 336
	      err += 100000.0f;
	      valid = false;
337
	    } else if (should != is) { 
Chad Barb's avatar
Chad Barb committed
338 339 340
	      float errDelta;

	      if (z == 0) {
Chad Barb's avatar
Chad Barb committed
341 342
		errDelta = d1weight * sqrtf((float)(abs(should - is)));
	      } else if (z == 1) {
Chad Barb's avatar
Chad Barb committed
343
		errDelta = d2weight * (float)(abs(should - is));
344
		if (should < is) { errDelta *= 0.5f; }
Chad Barb's avatar
Chad Barb committed
345 346
	      } else {
		errDelta = d3weight * (float)(abs( should - is ));
Chad Barb's avatar
Chad Barb committed
347 348 349 350
	      }

	      if (verbose) {
		if (z == 0) {
Chad Barb's avatar
Chad Barb committed
351
		  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
352 353
			 vnodeNames[x].c_str(), vnodeNames[y].c_str(), 
			 should, is, errDelta );
Chad Barb's avatar
Chad Barb committed
354
		} else if (z == 1) {
355
		  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
356 357 358
			 vnodeNames[x].c_str(), vnodeNames[y].c_str(), 
			 (int)expf((float)should / 1000.0f), 
			 (int)expf((float)is / 1000.0f),
359
			 (should < is) ? "* 0.5 " : "",
Chad Barb's avatar
Chad Barb committed
360
			 errDelta );
Chad Barb's avatar
Chad Barb committed
361 362 363 364 365 366
		} 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
367 368 369
		}
	      }
	      err += errDelta;
370 371 372 373 374 375 376
	    }
	  }
	}
      }
    }
  }

Chad Barb's avatar
Chad Barb committed
377
  if (verbose) { printf("error of %4.3f\n", err ); }
378
  t->error = err;
379 380

  return valid;
381 382 383 384 385 386 387 388 389 390 391 392
} 

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; }
}

393
static inline void sortByError( Solution * t )
394 395
{
  // Ahh.. sweet, sweet qsort.
396
  qsort( t, SOLUTIONS, sizeof( Solution ), compar );
397 398 399 400 401 402 403
}

// "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 )
{
404
  BEGIN_LOOP();
405
  while(1) {
406
    IN_LOOP();
407
    // forecast calls for a 1% chance of mutation...
408
    if ((rand() % 1000) > (himutate ? 500 : MUTATE_PROB)) { break; }
409 410 411 412
    
    if ((rand() % 3)) {
      // swap mutation. 
      int a, b;
413 414

      BEGIN_LOOP();
415
      do {
416
	IN_LOOP();
417
	a = rand() % vnodes;
418 419 420 421 422
      } while (fixed[a] != -1);

      BEGIN_LOOP();
      do {
	IN_LOOP();
423
	b = rand() % vnodes;
424 425 426 427 428 429 430
      } 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;
      }
431 432 433 434 435
    } else {
      // reassign mutation

      int a, b;
      // find which vnode to remap
436
      BEGIN_LOOP();
437
      do {
438
	IN_LOOP();
439 440 441 442 443 444 445
	a = rand() % vnodes;
      } while (fixed[a] != -1);

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

      // now find a suitable physical node.
446
      BEGIN_LOOP();
447
      do {
448
	IN_LOOP();
449 450 451 452 453 454 455
	b = rand() % pnodes;
      } while (t->pnode_uses[b] >= maxplex[b]);

      // now map it.
      t->vnode_mapping[a] = b;
      ++t->pnode_uses[b];
    }
456 457 458 459 460 461 462 463
  }
}

// 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
464 465 466 467 468 469 470 471 472 473 474 475 476 477 478
  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];
      }
479
    }
Chad Barb's avatar
Chad Barb committed
480
  } else {
481

Chad Barb's avatar
Chad Barb committed
482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506
    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] ];
507
	} else {
Chad Barb's avatar
Chad Barb committed
508 509 510 511 512 513 514 515 516 517 518 519
	  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;
520
	  }
521 522
	}
      } else {
Chad Barb's avatar
Chad Barb committed
523 524 525
	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] ];
526
	} else {
Chad Barb's avatar
Chad Barb committed
527 528 529 530 531 532 533 534 535 536 537 538
	  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;
539
	  }
540 541 542 543 544 545 546 547 548 549 550 551 552
	}
      }
    }
  }

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

// Generate a random solution 
// for the initial population.
static inline void generateRandomSolution( Solution * t )
{
553
  bzero( t->pnode_uses, sizeof( t->pnode_uses ) );
554 555 556 557

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] != -1) {
      t->vnode_mapping[i] = fixed[i];
558
      ++t->pnode_uses[ fixed[i] ];
559 560
    }
  }
561 562 563 564

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] == -1) {
      int x;
565
      BEGIN_LOOP();
566
      do {
567
	IN_LOOP();
568
	x = rand() % pnodes;
569 570
      } while( t->pnode_uses[x] >= maxplex[x] );
      ++t->pnode_uses[x];
571 572 573 574
      t->vnode_mapping[i] = x;
    }
  }

575 576 577
  calcError<false>( t );
}

Chad Barb's avatar
Chad Barb committed
578
void usage( char * appname )
579
{
Chad Barb's avatar
Chad Barb committed
580 581
  fprintf(stderr,
	  "Usage:\n"
Chad Barb's avatar
Chad Barb committed
582 583
	  "%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
584
	  "  -v              extra verbosity\n"
585
	  "  -v -v           jumbo verbosity\n"
586 587
	  "  -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
588
	  "  -1 <weight>     assign weight to latency penalty (optional; default 1.0)\n"
Chad Barb's avatar
Chad Barb committed
589 590
	  "  -2 <weight>     enable solving for bandwidth;\n"
	  "                  multiply bandwidth penalties by <weight>.\n"
Chad Barb's avatar
Chad Barb committed
591 592
	  "  -3 <weight>     enable solving for loss.\n"
	  "                  (must specify -2 first)\n"
Chad Barb's avatar
Chad Barb committed
593
	  "  -r <minrounds>  number of rounds to go without a solution before stopping\n"
Chad Barb's avatar
Chad Barb committed
594 595 596
	  "                  default: %i\n"
	  "  -R <maxrounds>  set maximum rounds\n"
	  "                  default: infinite (-1)\n\n", appname, DEFAULT_ROUNDS );
597
  exit(1);
Chad Barb's avatar
Chad Barb committed
598 599
}

600 601 602 603 604 605 606 607 608 609
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
610 611
int main( int argc, char ** argv )
{
Chad Barb's avatar
Chad Barb committed
612
  unsigned int seed = 1;
613 614
  int available = 0;
  int fixedNodeCount = 0;
615
  unsigned int bestSpeed = 0;
616

Chad Barb's avatar
Chad Barb committed
617 618
  verbose = 0;
  dimensions = 1;
Chad Barb's avatar
Chad Barb committed
619
  d1weight = 1.0f;
Chad Barb's avatar
Chad Barb committed
620
  d2weight = 1.0f / 1000.0f;
Chad Barb's avatar
Chad Barb committed
621
  d3weight = 1.0f / 65536.0f;
Chad Barb's avatar
Chad Barb committed
622 623 624 625 626 627

  minrounds = DEFAULT_ROUNDS;
  maxrounds = -1;

  int ch;

Chad Barb's avatar
Chad Barb committed
628 629 630 631 632 633 634
  { 
    struct timeval tp;
    if ( 0 == gettimeofday( &tp, NULL )) {
      seed = ((unsigned int)tp.tv_sec << 6) + (unsigned int)tp.tv_usec;
    }
  }

Chad Barb's avatar
Chad Barb committed
635
  while ((ch = getopt(argc, argv, "v1:2:3:r:R:s:m:")) != -1) {
Chad Barb's avatar
Chad Barb committed
636
    switch (ch) {
637
    case 's':
Chad Barb's avatar
Chad Barb committed
638
      seed = atoi( optarg );
639
      break;
Chad Barb's avatar
Chad Barb committed
640 641 642
    case 'v': 
      verbose++; 
      break;
643
    case 'm':
644
      plexPenalty = atof( optarg );
645 646
      userSpecifiedMultiplex++;
      break;
Chad Barb's avatar
Chad Barb committed
647 648 649
    case '1':
      d1weight = atof( optarg );
      break;
Chad Barb's avatar
Chad Barb committed
650 651 652 653
    case '2': 
      dimensions = 2;
      d2weight = atof( optarg ) / 1000.0f; 
      break;
Chad Barb's avatar
Chad Barb committed
654 655 656 657 658 659 660 661 662
    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
663 664 665 666 667 668 669 670
    case 'r':
      minrounds = atoi( optarg );
      break;
    case 'R':
      maxrounds = atoi( optarg );
      break;
    default: 
      usage( argv[0] );
Chad Barb's avatar
Chad Barb committed
671
      break;
Chad Barb's avatar
Chad Barb committed
672 673 674
    }
  }

675 676 677 678 679 680 681 682 683 684
  if (minrounds < 0 ) { minrounds = 0; }
  if (maxrounds < 0 ) { maxrounds = -1; }

  if (d1weight < 0.0f || d2weight < 0.0f || d3weight < 0.0f /* || plexPenalty < 0.0f */) {
    fprintf(stderr, 
	    "The '-1','-2' and '-3' switches each require\n"
	    "a positive argument, or zero.\n"
	    "Negative weights are silly.\n" );
    exit(1);
  }
Chad Barb's avatar
Chad Barb committed
685

Chad Barb's avatar
Chad Barb committed
686 687 688
  srand( seed );
  if (verbose) { printf("Using random seed %u\n", seed ); }

689
  char line[4096];
690 691

  {
692
    if (verbose > 1) { printf("How many physical nodes?\n"); }
Chad Barb's avatar
Chad Barb committed
693
    fgets( line, sizeof( line ), stdin );
694 695
    sscanf( line, "%i", &pnodes );

696 697 698 699 700
    if (pnodes > MAX_PNODES) {
      fprintf(stderr, "Too many nodes. Increase MAX_PNODES!\n");
      exit(1);
    }

701
    if (verbose > 1) { printf("Okay, enter %i names for the physical nodes, one per line.\n", pnodes ); }
702 703
    for (int i = 0; i < pnodes; i++) {
      char name[1024];
Chad Barb's avatar
Chad Barb committed
704
      fgets( line, sizeof( line ), stdin );
705 706
      sscanf( line, "%s", name );
      pnodeNames[i] = string( name );
707 708 709 710
      reversePNodeNames[string(name)] = i;
    }

    if (userSpecifiedMultiplex) {
711
      if (verbose > 1) { printf("Enter %i numbers, one per line, indicating the"
712 713 714
			    " maximum number of virtual nodes allowed on each"
			    " physical node.\n", pnodes ); }
      for (int i = 0; i < pnodes; i++) {
Chad Barb's avatar
Chad Barb committed
715
	fgets( line, sizeof( line ), stdin );
716
	sscanf( line, "%i", &(maxplex[i]));
717
	available += maxplex[i];
718 719 720 721
      }
    } else {
      for (int i = 0; i < pnodes; i++) {
	maxplex[i] = 1;
722
	++available;
723
      }
724 725
    }

Chad Barb's avatar
Chad Barb committed
726
    for (int z = 0; z < dimensions; z++) {
727
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
728
	printf("Enter %ix%i grid o' actual %s.\n", pnodes, pnodes, dimName[z]);
Chad Barb's avatar
Chad Barb committed
729 730 731
      }
      for (int y = 0; y < pnodes; y++) {
	char * linePos = line;
Chad Barb's avatar
Chad Barb committed
732
	fgets( line, sizeof( line ), stdin );
Chad Barb's avatar
Chad Barb committed
733 734
	while (*linePos == ' ') { linePos++; } // skip leading whitespace
	for (int x = 0; x < pnodes; x++) {
Chad Barb's avatar
Chad Barb committed
735
	  float temp;
Chad Barb's avatar
Chad Barb committed
736
	  sscanf( linePos, "%i", &pLatency[z][x][y] );
Chad Barb's avatar
Chad Barb committed
737
	  sscanf( linePos, "%f", &temp );
738
	    if (pLatency[z][x][y] != -1) {
Chad Barb's avatar
Chad Barb committed
739 740 741 742 743
	      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);
	      }
744
	  }
Chad Barb's avatar
Chad Barb committed
745 746 747
	  while (*linePos != ' ' && *linePos != '\n') { linePos++; }
	  while (*linePos == ' ') { linePos++; }
	}
748 749 750 751 752
      }
    }
  } 

  {
753
    if (verbose > 1) { printf("How many virtual nodes?\n"); }
Chad Barb's avatar
Chad Barb committed
754
    fgets( line, sizeof( line ), stdin );
755 756
    sscanf( line, "%i", &vnodes );

757 758 759 760 761
    if (vnodes > MAX_VNODES) {
      fprintf(stderr, "Too many vnodes. Increase MAX_VNODES!\n");
      exit(1);
    }

762 763 764 765 766 767 768 769 770 771 772
    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 ); }

773 774
    for (int i = 0; i < vnodes; i++) {
      char name[1024];
775
      char pname[1024];
Chad Barb's avatar
Chad Barb committed
776
      fgets( line, sizeof( line ), stdin );
777 778
      if (sscanf( line, "%s %s", name, pname ) == 2) {
	map< string, int >::iterator it = reversePNodeNames.find( string( pname ) );
779
	if (it == reversePNodeNames.end()) {
780 781
	  fprintf(stderr,"pnode '%s' does not exist; can't fix.\n", pname );
	  exit(3);
782
	}
783 784
	if (verbose > 1) { 
	  printf("Fixing assignment from vnode %s to pnode %s.\n", name, pname );
785
	}
786 787
	fixed[i] = reversePNodeNames[ string( pname ) ];
	fixedNodeCount++;
788 789 790
      } else {
	fixed[i] = -1;
      }
791
      vnodeNames[i] = string( name );
792 793
    }

Chad Barb's avatar
Chad Barb committed
794
    for (int z = 0; z < dimensions; z++) {
795
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
796
	printf("Enter %ix%i grid o' desired %s (-1 is don't care.)\n", vnodes, vnodes, 
Chad Barb's avatar
Chad Barb committed
797
	       dimName[z]);
798
      }
Chad Barb's avatar
Chad Barb committed
799 800
      for (int y = 0; y < vnodes; y++) {
	char * linePos = line;
Chad Barb's avatar
Chad Barb committed
801
	fgets( line, sizeof( line ), stdin );
Chad Barb's avatar
Chad Barb committed
802 803
	while (*linePos == ' ') { linePos++; } // skip leading whitespace
	for (int x = 0; x < vnodes; x++) {
Chad Barb's avatar
Chad Barb committed
804
	  float temp;
Chad Barb's avatar
Chad Barb committed
805
	  sscanf( linePos, "%i", &vDesiredLatency[z][x][y] );
Chad Barb's avatar
Chad Barb committed
806 807 808
	  sscanf( linePos, "%f", &temp );
	  if (vDesiredLatency[z][x][y] != -1) {
	    if (z == 1) { 
Chad Barb's avatar
Chad Barb committed
809
	      vDesiredLatency[z][x][y] = (int)(logf(vDesiredLatency[z][x][y]) * 1000.0f); 
Chad Barb's avatar
Chad Barb committed
810 811
	    } else if (z == 2) {
	      vDesiredLatency[z][x][y] = (int)(temp * 65536.0f);
Chad Barb's avatar
Chad Barb committed
812 813 814 815 816 817 818 819
	    }
	  }
	  while (*linePos != ' ' && *linePos != '\n') { linePos++; }
	  while (*linePos == ' ') { linePos++; }
	}
      }
    } 
  }
820

821 822 823
  Solution * currentPool = pool;
  Solution * nextPool = pool2;

824 825
  if (fixedNodeCount < vnodes) {
    if (verbose) { printf("Now running...\n"); }
826

827 828
    {
      for (int i = 0; i < SOLUTIONS; i++) {
829
	generateRandomSolution( &(currentPool[i]) );
830
      }
831
      sortByError( currentPool );
832 833 834
    }

    int highestFoundRound = 0;
835 836
    float last = currentPool[0].error;

837
    himutate = false;
Chad Barb's avatar
Chad Barb committed
838
    for (int i = 0; i != maxrounds && i < (highestFoundRound + minrounds); i++) {
839 840 841 842 843 844 845 846 847 848 849 850
     
      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));
851
      
852
      if (verbose && !(i % 100)) {
853
	printf("Round %i. (best %4.3f; avg %4.3f; sdev %4.3f)\n", i, currentPool[0].error, avg, stddev);
854
      }
855
      
856
      if (currentPool[0].error < last) {
Chad Barb's avatar
Chad Barb committed
857 858
	if (verbose) {
	  printf("Better solution found in round %i (error %4.3f)\n", 
859
		 i, currentPool[0].error);
Chad Barb's avatar
Chad Barb committed
860
	}
861
	bestSpeed = msecscpu();
862
	last = currentPool[0].error;
863 864
	highestFoundRound = i;
      }
865

Chad Barb's avatar
Chad Barb committed
866 867
      // 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.)
868 869 870 871 872
      memcpy( &(nextPool[0]), &(currentPool[0]), sizeof( Solution ) );
      prepick( currentPool );

      int j;

873 874 875 876 877 878
      // if there is not enough variety, more mutation!
      if (stddev < (avg / 10.0f)) { 
	himutate = true;
      }

      for (j = 1; j < SOLUTIONS; j++) {
879 880 881 882 883
	splice( &(nextPool[j]),
		&(currentPool[pickABest( currentPool )]),
		&(currentPool[pickABest( currentPool )]) );
      }

Chad Barb's avatar
Chad Barb committed
884 885 886
      //if (stddev < (avg / 10.0f))) {
      himutate = false;
      //}
Chad Barb's avatar
Chad Barb committed
887

888 889 890 891 892 893 894
      sortByError( nextPool );

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

      if (currentPool[0].error < EPSILON) { 
895
	if (verbose > 1) { printf("Found perfect solution.\n"); }
896 897 898
	break;
      }
    }
899 900
  } else {
    if (verbose) { printf("No non-fixed vnodes (or no vnodes at all,) so nothing to be done!\n"); }
901 902 903
  }

  {
Chad Barb's avatar
Chad Barb committed
904
    if (verbose) { printf("\nYour solution is as follows:\n"); }
905
    for (int x = 0; x < vnodes; x++) {
906 907
      if (pnodeNames.find( currentPool[0].vnode_mapping[x] ) == pnodeNames.end()) {
	pnodeNames[ currentPool[0].vnode_mapping[x] ] = "CRAP";
Chad Barb's avatar
Chad Barb committed
908 909 910
      }
      printf("%s mapsTo %s\n", 
	     vnodeNames[x].c_str(),
911
	     pnodeNames[currentPool[0].vnode_mapping[x]].c_str() );
912
    }
913

914 915 916
    printf("\n");

    // dump a detailed report of the returned solution's errors.
917
    if (verbose > 1) { 
918 919 920 921 922 923
      if (calcError<true>( &(currentPool[0]) )) {
	printf("Found in %i msecs (cpu time)\n", bestSpeed );
      } else {
	fprintf( stderr, "Solution is invalid, since it uses unavailable links.");
	exit(6);
      }
924
    }
925 926
  }

927
  if (verbose > 1) { printf("Bye now.\n"); }
928 929
  return 0;
}