assign.cc 24.1 KB
Newer Older
Robert Ricci's avatar
Robert Ricci committed
1 2 3 4 5 6
/*
 * EMULAB-COPYRIGHT
 * Copyright (c) 2000-2003 University of Utah and the Flux Group.
 * All rights reserved.
 */

7 8 9 10 11 12 13 14
#include "port.h"

#include <boost/config.hpp>
#include <boost/utility.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
15
#ifdef GRAPHVIZ_SUPPORT
16
#include <boost/graph/graphviz.hpp>
17
#endif
18 19

#include <fstream.h>
20
#include <iostream.h>
21
#include <time.h>
22
#include <stdlib.h>
23
#include <math.h>
24 25
#include <sys/types.h>
#include <sys/time.h>
26
#include <sys/resource.h>
27 28
#include <signal.h>
#include <sys/signal.h>
29
#include <queue>
30 31

using namespace boost;
32 33

#include "common.h"
34
#include "delay.h"
35
#include "physical.h"
36
#include "virtual.h"
37
#include "vclass.h"
38
#include "pclass.h"
39
#include "score.h"
40 41 42
#include "solution.h"
#include "maps.h"
#include "anneal.h"
43 44 45

// Here we set up all our graphs.  Need to create the graphs
// themselves and then setup the property maps.
46
tb_pgraph PG;
47 48 49 50 51 52 53 54 55 56
tb_pgraph_vertex_pmap pvertex_pmap = get(vertex_data, PG);
tb_pgraph_edge_pmap pedge_pmap = get(edge_data, PG);
tb_sgraph SG;
tb_sgraph_vertex_pmap svertex_pmap = get(vertex_data, SG);
tb_sgraph_edge_pmap sedge_pmap = get(edge_data, SG);
tb_vgraph VG;
tb_vgraph_vertex_pmap vvertex_pmap = get(vertex_data, VG);
tb_vgraph_edge_pmap vedge_pmap = get(edge_data, VG);

// A simple list of physical types.
57
name_count_map ptypes;
58 59

// List of virtual types by name.
60
name_count_map vtypes;
61
name_list_map vclasses;
62 63

// A list of all pclasses.
64
pclass_list pclasses;
65 66 67
 	
// Map from a pnode* to the the corresponding pvertex.
pnode_pvertex_map pnode2vertex;
68 69 70

// Map of a type to a tt_entry, a vector of pclasses and the size of
// the vector.
71
pclass_types type_table;
72 73 74
#ifdef PER_VNODE_TT
pclass_types vnode_type_table;
#endif
75

76 77 78 79 80
// This datastructure contains all the information needed to calculate
// the shortest path between any two switches.  Indexed by svertex,
// the value will be a predicate map (indexed by svertex as well) of
// the shortest paths for the given vertex.
switch_pred_map_map switch_preds;
81

82 83
// Same, but for distances 
switch_dist_map_map switch_dist;
84

85 86
// Time started, finished, and the time limit
double timestart, timeend, timelimit, timetarget;
87

88 89 90
// An amount to scale the neighborhood size by
double scale_neighborhood = 1.0;

91 92 93 94 95
#ifdef GNUPLOT_OUTPUT
FILE *scoresout, *tempout, *deltaout;
#endif
// Whether or not assign is allowed to generate trivial links
bool allow_trivial_links = true;
96

97
// Whether or not assign should use pclasses
98
bool disable_pclasses = false;
99

100 101 102
// Whether or not assign should prune out pclasses that it knows can
// never be used
bool prune_pclasses = false;
103 104 105

// Whether or not we should use the experimental support for dynamic pclasses
bool dynamic_pclasses = false;
106 107 108

// Whether or not to allow assign to temporarily over-subscribe pnodes
bool allow_overload = false;
Robert Ricci's avatar
Robert Ricci committed
109 110 111 112

// Forces assign to do greedy link assignment, by chosing the first link in its
// list, which is usually the lowest-cost
bool greedy_link_assignment = false;
113 114 115 116 117

// Forces assign to skip melting, and, instead, use the temperature given as
// the initial temperature
bool no_melting = false;
double initial_temperature = 0.0f;
118 119 120 121 122 123

// Print out a summary of the solution in addition to the solution itself
bool print_summary = false;

// Use the 'connected' find algorithm
double use_connected_pnode_find = 0.0f;
124 125 126 127
  
// XXX - shouldn't be in this file
double absbest;
int absbestviolated, iters, iters_to_best;
128

129 130 131
/*
 * Internal functions
 */
132

133
// Return the CPU time (in seconds) used by this process
134 135 136 137 138 139 140 141
float used_time()
{
  struct rusage ru;
  getrusage(RUSAGE_SELF,&ru);
  return ru.ru_utime.tv_sec+ru.ru_utime.tv_usec/1000000.0+
    ru.ru_stime.tv_sec+ru.ru_stime.tv_usec/1000000.0;
}

142
// Read in the .ptop file
143 144 145 146
void read_physical_topology(char *filename)
{
  ifstream ptopfile;
  ptopfile.open(filename);
147
  if (!ptopfile.is_open()) {
148
      cout << "Unable to open ptop file " << filename << endl;
149
      exit(EXIT_FATAL);
150
  }
151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
  cout << "Physical Graph: " << parse_ptop(PG,SG,ptopfile) << endl;

#ifdef DUMP_GRAPH
  {
    cout << "Physical Graph:" << endl;
    
    pvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(PG);
    
    for (;vit != vendit;vit++) {
      tb_pnode *p = get(pvertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
    
    pedge_iterator eit,eendit;
    tie(eit,eendit) = edges(PG);

    for (;eit != eendit;eit++) {
      tb_plink *p = get(pedge_pmap,*eit);
      cout << *eit << " (" << source(*eit,PG) << " <-> " <<
	target(*eit,PG) << ")\t" << *p;
    }
  }
174
#endif // DUMP_GRAPH
175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197

#ifdef GRAPH_DEBUG
  {
    cout << "Switch Graph:" << endl;
    

    svertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(SG);
    
    for (;vit != vendit;vit++) {
      tb_switch *p = get(svertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
    
    sedge_iterator eit,eendit;
    tie(eit,eendit) = edges(SG);

    for (;eit != eendit;eit++) {
      tb_slink *p = get(sedge_pmap,*eit);
      cout << *eit << " (" << source(*eit,SG) << " <-> " <<
	target(*eit,SG) << ")\t" << *p;
    }
  }
198
#endif // GRAPH_DEBUG
199

200 201
  // Set up pnode2vertex - a mapping between vertices in the physical graph and
  // the pnodes that we just read in from the ptop file
202 203 204 205 206 207 208 209
  pvertex_iterator pvit,pvendit;
  tie(pvit,pvendit) = vertices(PG);
  for (;pvit != pvendit;pvit++) {
    pnode2vertex[get(pvertex_pmap,*pvit)]=*pvit;
  }

}

210 211
// Calculate the minimum spanning tree for the switches - we only consider one
// potential path between each pair of switches.
212
void calculate_switch_MST()
213
{
214
  cout << "Calculating shortest paths on switch fabric." << endl;
215 216

  // Set up the weight map for Dijkstra's
217 218 219 220 221 222 223 224 225 226
  tb_sgraph_weight_pmap sweight_pmap = get(edge_weight, SG);
  sedge_iterator seit,seendit;
  tie(seit,seendit) = edges(SG);
  for (;seit != seendit;seit++) {
    tb_slink *slink = get(sedge_pmap,*seit);
    // XXX should we make this more complicated depending on
    // latency/loss as well?
    put(sweight_pmap,*seit,
	100000000-get(pedge_pmap,slink->mate)->delay_info.bandwidth);
  }
227

228
  // Let boost do the Disjktra's for us, from each switch
229 230 231 232 233 234 235 236
  svertex_iterator svit,svendit;
  tie(svit,svendit) = vertices(SG);
  for (;svit != svendit;svit++) {
    switch_preds[*svit] = new switch_pred_map(num_vertices(SG));
    switch_dist[*svit] = new switch_dist_map(num_vertices(SG));
    dijkstra_shortest_paths(SG,*svit,
    			    predecessor_map(&((*switch_preds[*svit])[0])).
			    distance_map(&((*switch_dist[*svit])[0])));
237 238
  }

239 240 241 242 243 244 245 246 247
#ifdef GRAPH_DEBUG
  cout << "Shortest paths" << endl;
  tie(svit,svendit) = vertices(SG);
  for (;svit != svendit;svit++) {
    cout << *svit << ":" << endl;
    for (unsigned int i = 0;i<num_vertices(SG);++i) {
      cout << i << " " << (*switch_dist[*svit])[i] << endl;
    }
  }
248
#endif // GRAPH_DEBUG
249 250
}

251
// Read in the .top file
252 253 254 255
void read_virtual_topology(char *filename)
{
  ifstream topfile;
  topfile.open(filename);
256
  if (!topfile.is_open()) {
257
      cout << "Unable to open top file " << filename << endl;
258
      exit(EXIT_FATAL);
259
  }
260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285
  cout << "Virtual Graph: " << parse_top(VG,topfile) << endl;

#ifdef DUMP_GRAPH
  {
    cout << "Virtual Graph:" << endl;
    

    vvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(VG);
    
    for (;vit != vendit;vit++) {
      tb_vnode *p = get(vvertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
    
    vedge_iterator eit,eendit;
    tie(eit,eendit) = edges(VG);

    for (;eit != eendit;eit++) {
      tb_vlink *p = get(vedge_pmap,*eit);
      cout << *eit << " (" << source(*eit,VG) << " <-> " <<
	target(*eit,VG) << ")\t" << *p;
    }
  }  
#endif
}
286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311
/*
 * Make a pass through the pclasses, looking for ones that no node can use, and
 * nuking them.
 */
void prune_unusable_pclasses() {
    cout << "Pruning pclasses." << endl;
    int pruned = 0;
    pclass_list::iterator pclass_iterator = pclasses.begin();
    while (pclass_iterator != pclasses.end()) {
	if ((*pclass_iterator)->refcount == 0) {
	    pclass_list::iterator nukeme = pclass_iterator;
	    pclass_iterator++;
#ifdef PCLASS_DEBUG
	    cout << "Pruning " << (*nukeme)->name << endl;
#endif
	    pruned++;
	    delete *nukeme;
	    pclasses.erase(nukeme);
	} else {
	    pclass_iterator++;
	}
    }
    cout << "pclass pruning complete: removed " << pruned << " pclasses, " <<
	pclasses.size() << " remain." << endl;
}

312
void print_help()
313
{
314 315
  cout << "assign [options] ptopfile topfile [config params]" << endl;
  cout << "Options: " << endl;
316
#ifdef TIME_TERMINATE
317
  cout << "  -l <time>   - Limit runtime." << endl;
318
#endif
319
  cout << "  -s <seed>   - Set the seed." << endl;
320
#ifdef GRAPHVIZ_SUPPORT
321
  cout << "  -v <viz>    - Produce graphviz files with given prefix." <<
322
    endl;
323
#endif
324 325 326
  cout << "  -r          - Don't allow trivial links." << endl;
  cout << "  -p          - Disable pclasses." << endl;
  cout << "  -d          - Enable dynamic pclasses." << endl;
327
#ifdef PER_VNODE_TT
328
  cout << "  -P          - Prune unusable pclasses." << endl;
329
#endif
330 331 332
  cout << "  -T          - Doing some scoring self-testing." << endl;
  cout << "  -H <float>  - Try <float> times harder." << endl;
  cout << "  -o          - Allow overloaded pnodes to be considered." << endl;
333 334
  cout << "  -t <float>  - Start the temperature at <float> instead of melting."
      << endl;
335 336
  cout << "  -u          - Print a summary of the solution." << endl;
  cout << "  -c <float>  - Use the 'connected' pnode finding algorithm " <<
337 338
      "<float>*100% of the time." << endl;
  cout << "  -n          - Don't anneal - just do the prechecks." << endl;
339
  exit(EXIT_FATAL);
340 341 342 343 344 345 346
}
 
// Perfrom a pre-cehck to make sure that there are enough free nodes of the
// proper types. Returns 1 if the proper types exist, 0 if they do not.
// TODO - move away from using global variables
int type_precheck() {
    cout << "Type precheck:" << endl;
347

348
    bool ok = true;
349

350
    // First, check the regular types
351 352 353 354 355 356
    for (name_count_map::iterator vtype_it=vtypes.begin();
	    vtype_it != vtypes.end();++vtype_it) {
    
	// Check to see if there were any pnodes of the type at all
	name_count_map::iterator ptype_it = ptypes.find(vtype_it->first);
	if (ptype_it == ptypes.end()) {
357
	    cout << "  *** No physical nodes of type " << vtype_it->first
358 359
		<< " found" << endl;
	    ok = false;
360
	} else {
361 362
	    // Okay, there are some - are there enough?
	    if (ptype_it->second < vtype_it->second) {
363
		cout << "  *** " << vtype_it->second << " nodes of type " <<
364 365 366 367
		    vtype_it->first << " requested, but only "
		    << ptype_it->second << " found" << endl;
		ok = false;
	    }
368
	}
369
    }
370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389

    // Check the vclasses, too
    for (name_list_map::iterator vclass_it = vclasses.begin();
	    vclass_it != vclasses.end(); ++vclass_it) {
	bool found_match = false;
	for (vector<crope>::iterator vtype_it = vclass_it->second.begin();
		vtype_it != vclass_it->second.end(); vtype_it++) {
	    if (ptypes.find(*vtype_it) != ptypes.end()) {
		found_match = true;
		break;
	    }
	}

	if (!found_match) {
	    cout << "  *** No physical nodes can satisfy vclass " <<
		vclass_it->first << endl;
	    ok = false;
	}
    }

390
    if (ok) {
391
      cout << "Type precheck passed." << endl;
392 393 394 395 396 397
      return 1;
    } else {
      cout << "Type precheck failed!" << endl;
      return 0;
    }
}
398

399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414
// Perfrom a pre-cehck to make sure that every vnode has at least one possible
// mapping.  Returns 1 if this is the case, 0 if not.
// TODO - move away from using global variables
int mapping_precheck() {
#ifdef PER_VNODE_TT
    cout << "Node mapping precheck:" << endl;
    /*
     * Build up an entry in the type table for each vnode, by first looking at
     * the type table entry for the vnode's type, then checking each entry to
     * make sure that it:
     * (1) Has enough interfaces
     * (2) Has enough total bandwidth (for emulated links)
     * (3) Meets any 1.0-weight features and/or desires
     */
    vvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(VG);
415

416 417 418 419
    /*
     * Indicates whether all nodes have potential matches or not
     */
    bool ok = true;
420

421 422
    for (;vit != vendit;vit++) {
	tb_vnode *v = get(vvertex_pmap,*vit);
423

424 425 426 427 428 429 430 431 432 433
	pclass_vector *vec = new pclass_vector();
	vnode_type_table[v->name] = tt_entry(0,vec);

	// This constitutes a list of the number of ptypes that matched the
	// criteria. We use to guess what's wrong with the vnode.
	int matched_bw = 0;
	// Keep track of desires had how many 'hits', so that we can tell
	// if any simply were not matched
	tb_vnode::desires_count_map matched_desires;

434 435 436 437 438
	// Keep track of which link types had how many 'hits', so that we can
	// tell which type(s) caused this node to fail
	tb_vnode::link_counts_map matched_link_counts;
	map<crope,bool> matched_links;

439 440 441 442
	tb_vclass *vclass = v->vclass;
	tb_vclass::members_map::iterator mit;
	if (vclass) {
	    mit = vclass->members.begin();
443
	}
444 445 446 447 448 449 450 451 452
	for (;;) {
	    // Loop over all types this node can take on, which might be only
	    // one, if it's not part of a vclass
	    crope this_type;
	    if (vclass) {
		this_type = mit->first;
	    } else {
		this_type = v->type;
	    }
453

454 455
	    for (pclass_vector::iterator it = type_table[this_type].second->begin();
		    it != type_table[this_type].second->end(); it++) {
456

457 458 459
		bool potential_match = true;
		// Grab the first node of the pclass as a representative sample
		tb_pnode *pnode = *((*it)->members[this_type]->L.begin());
460

461
#if 0
462 463 464 465 466
		// Check the number of interfaces - if the pnode is a switch,
		// for now, we don't check this, since it can end up with more
		// 'interfaces' due to the fact that it can have interswitch
		// links
		if ((pnode->total_interfaces >= v->num_links) ||
467
			(!pnode->current_type.compare("switch"))) {
468 469 470 471
		    matched_links++;
		} else {
		    potential_match = false;
		}
472 473 474 475
#endif

		// Check to see if any of the link that this pnode has are of
		// the correct type for the virtual node
476

477 478 479 480 481 482
		// Check bandwidth on emulated links
		if (pnode->total_bandwidth >= v->total_bandwidth) {
		    matched_bw++;
		} else {
		    potential_match = false;
		}
483

484 485 486 487 488 489 490 491 492 493 494 495
		// Check to see if if the pnode has enough slots of the
		// appropriate type available
		tb_pnode::types_map::iterator mit = pnode->types.find(v->type);
		if (mit == pnode->types.end()) {
		    // Must have been a vtype to get here - ignore it
		} else {
		    if (v->typecount > mit->second->max_load) {
			// Nope, this vnode is too demanding
			potential_match = false;
		    }
		}

496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520
		//
		// Check features and desires
		//

		// Desires first
		for (tb_vnode::desires_map::iterator desire_it = v->desires.begin();
			desire_it != v->desires.end();
			desire_it++) {
		    crope name = (*desire_it).first;
		    float value = (*desire_it).second;
		    // Only check for desires that would result in a violation if
		    // unsatisfied
		    if (value >= FD_VIOLATION_WEIGHT) {
			if (matched_desires.find(name) == matched_desires.end()) {
			    matched_desires[name] = 0;
			}
			tb_pnode::features_map::iterator feature_it =
			    pnode->features.find(name);
			if (feature_it != pnode->features.end()) {
			    matched_desires[name]++;
			} else {
			    potential_match = false;
			}
		    }
		}
521

522 523 524 525 526
		// Next, features
		for (tb_pnode::features_map::iterator feature_it = pnode->features.begin();
			feature_it != pnode->features.end(); feature_it++) {
		    crope name = (*feature_it).first;
		    float value = (*feature_it).second;
527 528 529 530
		    // Skip 'local' and 'global' features
		    if (name[0] == '*' || name[0] == '?') {
			continue;
		    }
531 532 533 534 535 536 537 538 539 540
		    // Only check for feature that would result in a violation if
		    // undesired
		    if (value >= FD_VIOLATION_WEIGHT) {
			tb_vnode::desires_map::iterator desire_it =
			    v->desires.find(name);
			if (desire_it == v->desires.end()) {
			    potential_match = false;
			}
		    }
		}
541

542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561
		// Check link types
		tb_vnode::link_counts_map::iterator vit;
		for (vit = v->link_counts.begin(); vit != v->link_counts.end();
		    vit++) {
		  crope type = vit->first;
		  int count = vit->second;
		  if (pnode->link_counts.find(type) !=
			pnode->link_counts.end()) {
		    // Found at least one link of this type
		    matched_links[type] = true;
		    if (pnode->link_counts[type] >= count) {
		      // Great, there are enough, too
		      matched_link_counts[type]++;
		    } else {
		      potential_match = false;
		    }
		  } else {
		    potential_match = false;
		  }
		}
562

563 564 565 566 567 568
		if (potential_match) {
		    vec->push_back(*it);
		    vnode_type_table[v->name].first++;
		    (*it)->refcount++;
#ifdef PCLASS_DEBUG
		    cerr << v->name << " can map to " << (*it)->name << endl;
569
#endif
570 571
		}
	    }
572

573 574 575 576 577 578 579 580 581
	    if (vclass) { 
		mit++;
		if (mit == vclass->members.end()) {
		    break;
		}
	    } else {
		// If not a vtype, we only had to do this once
		break;
	    }
582
	}
583

584
	if (vnode_type_table[v->name].first == 0) {
585
	    cout << "  *** No possible mapping for " << v->name << endl;
586
	    // Make an attempt to figure out why it didn't match
587 588 589 590 591 592 593 594 595 596 597 598 599 600
	    
	    // Check all of its link types
	    tb_vnode::link_counts_map::iterator lit;
	    for (lit = v->link_counts.begin(); lit != v->link_counts.end();
		lit++) {
	      crope type = lit->first;
	      if (!matched_links[type]) {
		cout << "      No links of type " << type << " found!" << endl;
	      } else {
		if (!matched_link_counts[type]) {
		  cout << "      Too many links of type " << type << "!"
		    << endl;
		}
	      }
601
	    }
602

603
	    if (!matched_bw) {
604
		cout << "      Too much bandwidth on emulated links!" << endl;
605
	    }
606

607 608 609 610
	    for (tb_vnode::desires_count_map::iterator dit = matched_desires.begin();
		    dit != matched_desires.end();
		    dit++) {
		if (dit->second == 0) {
611
		    cout << "      No physical nodes have feature " << dit->first
612 613
			<< "!" << endl;
		}
614
	    }
615
	    ok = false;
616
	}
617 618 619
#ifdef PCLASS_DEBUG
	cerr << v->name << " can map to " << vnode_type_table[v->name].first << " pclasses"
	    << endl;
620
#endif
621

622
    }
623

624 625 626
    if (ok) {
	cout << "Node mapping precheck succeeded" << endl;
	return 1;
627
    } else {
628 629
	cout << "Node mapping precheck failed!" << endl;
	return 0;
630 631
    }

632 633 634
#else // PER_VNODE_TT
    // PER_VNODE_TT is required for this check, just pretend it's OK.
    return 1;
635
#endif
636
}
637

638 639 640
// Signal handler - add a convneint way to kill assign and make it return an
// unretryable error
void exit_unretryable(int signal) {
641 642 643 644 645 646 647 648 649 650
  cout << "Killed with signal " << signal << " - exiting!" << endl;
  _exit(EXIT_UNRETRYABLE);
}

// Singal handler - add a way for a user to get some status information
extern double temp;
void status_report(int signal) {
  cout << "I: " << iters << " T: " << temp << " S: " << get_score() << " V: "
    << violated << " (Best S: " << absbest << " V:" << absbestviolated << ")"
    << endl;
651 652
}

653 654 655
int main(int argc,char **argv)
{
  int seed = 0;
656
#ifdef GRAPHVIZ_SUPPORT
657
  crope viz_prefix;
658
#endif
659
  bool scoring_selftest = false;
660
  bool prechecks_only = false;
661 662 663 664 665
  
  // Handle command line
  char ch;
  timelimit = 0.0;
  timetarget = 0.0;
666
  while ((ch = getopt(argc,argv,"s:v:l:t:rpPTdH:oguc:n")) != -1) {
667 668 669 670
    switch (ch) {
    case 's':
      if (sscanf(optarg,"%d",&seed) != 1) {
	print_help();
671
      }
672
      break;
673
#ifdef GRAPHVIZ_SUPPORT
674 675 676
    case 'v':
      viz_prefix = optarg;
      break;
677
#endif
678 679 680 681 682 683 684 685 686 687 688 689 690
#ifdef TIME_TERMINATE
    case 'l':
      if (sscanf(optarg,"%lf",&timelimit) != 1) {
	print_help();
      }
      break;
#endif
#ifdef TIME_TARGET
    case 't':
      if (sscanf(optarg,"%lf",&timetarget) != 1) {
	print_help();
      }
      break;
691
#endif
692 693 694
    case 'r':
      allow_trivial_links = false; break;
    case 'p':
695
      disable_pclasses = true; break;
696 697 698 699
#ifdef PER_VNODE_TT
    case 'P':
      prune_pclasses = true; break;
#endif
700 701
    case 'T':
      scoring_selftest = true; break;
702 703
    case 'd':
      dynamic_pclasses = true; break;
704 705 706 707 708
    case 'H':
      if (sscanf(optarg,"%lf",&scale_neighborhood) != 1) {
	print_help();
      }
      break;
709 710
    case 'o':
      allow_overload = true; break;
Robert Ricci's avatar
Robert Ricci committed
711 712
    case 'g':
      greedy_link_assignment = true; break;
713 714 715 716 717
    case 't':
      if (sscanf(optarg,"%lf",&initial_temperature) != 1) {
	print_help();
      }
      no_melting = true; break;
718 719 720 721 722 723 724
    case 'u':
      print_summary = true; break;
    case 'c':
      if (sscanf(optarg,"%lf",&use_connected_pnode_find) != 1) {
	print_help();
      }
      break;
725 726 727 728
    case 'n':
      prechecks_only = true;
      cout << "Doing only prechecks, exiting early" << endl;
      break;
729 730
    default:
      print_help();
731
    }
732
  }
733 734 735 736 737 738 739 740 741
  argc -= optind;
  argv += optind;
  
  if (seed == 0) {
    if (getenv("ASSIGN_SEED") != NULL) {
      sscanf(getenv("ASSIGN_SEED"),"%d",&seed);
    } else {
      seed = time(NULL)+getpid();
    }
742
  }
743

744
#ifdef GRAPHVIZ_SUPPORT
745 746 747
  if (viz_prefix.size() == 0) {
    if (getenv("ASSIGN_GRAPHVIZ") != NULL) {
      viz_prefix = getenv("ASSIGN_GRAPHVIZ");
748
    }
749
  }
750
#endif
751

752 753 754 755
  if (argc == 0) {
    print_help();
  }

756 757 758 759 760 761 762

  // Set up a signal handler for USR1 that exits with an unretryable error
  struct sigaction action;
  action.sa_handler = exit_unretryable;
  sigemptyset(&action.sa_mask);
  action.sa_flags = 0;
  sigaction(SIGUSR1,&action,NULL);
763
  sigaction(SIGINT,&action,NULL);
764

765 766 767 768 769 770 771
  // Set up a signal handler for control+T
  struct sigaction action2;
  action2.sa_handler = status_report;
  sigemptyset(&action2.sa_mask);
  action2.sa_flags = 0;
  sigaction(SIGINFO,&action2,NULL);

772 773 774 775 776 777 778 779 780 781 782 783 784
  // Convert options to the common.h parameters.
  parse_options(argv, options, noptions);
#ifdef SCORE_DEBUG
  dump_options("Configuration options:", options, noptions);
#endif

#ifdef GNUPLOT_OUTPUT
  scoresout = fopen("scores.out","w");
  tempout = fopen("temp.out","w");
  deltaout = fopen("delta.out","w");
#endif

  cout << "seed = " << seed << endl;
785
  srandom(seed);
786 787 788 789 790

  read_physical_topology(argv[0]);
  calculate_switch_MST();
  
  cout << "Generating physical equivalence classes:";
791
  generate_pclasses(PG,disable_pclasses,dynamic_pclasses);
792
  cout << pclasses.size() << endl;
793

794 795 796
#ifdef PCLASS_DEBUG
  pclass_debug();
#endif
797 798

  read_virtual_topology(argv[1]);
799

800 801
  // Run the type precheck
  if (!type_precheck()) {
802
      exit(EXIT_UNRETRYABLE);
803
  }
804

805 806
  // Run the mapping precheck
  if (!mapping_precheck()) {
807
      exit(EXIT_UNRETRYABLE);
808
  }
809

810 811 812 813 814
  // Bomb out early if we're only doing the prechecks
  if (prechecks_only) {
      exit(EXIT_SUCCESS);
  }

815
#ifdef PER_VNODE_TT
816 817 818
  if (prune_pclasses) {
      prune_unusable_pclasses();
  }
819 820 821
#endif

  // Output graphviz if necessary
822
#ifdef GRAPHVIZ_SUPPORT
823 824 825 826 827 828 829 830 831 832 833 834 835 836 837
  if (viz_prefix.size() != 0) {
    crope vviz = viz_prefix + "_virtual.viz";
    crope pviz = viz_prefix + "_physical.viz";
    crope sviz = viz_prefix + "_switch.viz";
    ofstream vfile,pfile,sfile;
    vfile.open(vviz.c_str());
    write_graphviz(vfile,VG,vvertex_writer(),vedge_writer(),graph_writer());
    vfile.close();
    pfile.open(pviz.c_str());
    write_graphviz(pfile,PG,pvertex_writer(),pedge_writer(),graph_writer());
    pfile.close();
    sfile.open(sviz.c_str());
    write_graphviz(sfile,SG,svertex_writer(),sedge_writer(),graph_writer());
    sfile.close();
  }
838
#endif
839 840 841 842 843 844 845 846 847

  // Handle the initial temperature, if one was given - a NULL initial temp.
  // means that we should start with the normal melting procedure
  double *initial_temperature_pointer;
  if (no_melting) {
    initial_temperature_pointer = &initial_temperature;
  } else {
    initial_temperature_pointer = NULL;
  }
848 849
 
  timestart = used_time();
850 851
  anneal(scoring_selftest, scale_neighborhood, initial_temperature_pointer,
      use_connected_pnode_find);
852
  timeend = used_time();
853

854 855 856 857 858 859
#ifdef GNUPLOT_OUTPUT
  fclose(scoresout);
  fclose(tempout);
  fclose(deltaout);
#endif

860
  if ((!compare_scores(get_score(),absbest)) || (violated > absbestviolated)) {
861 862
    cout << "Internal error: Invalid migration assumptions." << endl;
    cout << "score:" << get_score() << " absbest:" << absbest <<
863 864
      " violated:" << violated << " absbestviolated:" <<
      absbestviolated << endl;
865
    cout << "  Contact calfeld" << endl;
866
  }
867
  
868
  cout << "   BEST SCORE:  " << get_score() << " in " << iters <<
869 870 871 872
    " iters and " << timeend-timestart << " seconds" << endl;
  cout << "With " << violated << " violations" << endl;
  cout << "Iters to find best score:  " << iters_to_best << endl;
  cout << "Violations: " << violated << endl;
873
  cout << vinfo;
874

875
  print_solution();
876

877 878 879 880
  if (print_summary) {
    print_solution_summary();
  }

881
#ifdef GRAPHVIZ_SUPPORT
882 883 884 885 886 887 888 889
  if (viz_prefix.size() != 0) {
    crope aviz = viz_prefix + "_solution.viz";
    ofstream afile;
    afile.open(aviz.c_str());
    write_graphviz(afile,VG,solution_vertex_writer(),
		   solution_edge_writer(),graph_writer());
    afile.close();
  }
890
#endif
891
  
Robert Ricci's avatar
Robert Ricci committed
892
  if (violated != 0) {
893
      exit(EXIT_RETRYABLE);
894
  } else {
895
      exit(EXIT_SUCCESS);
896
  }
897
}
898