assign.cc 24.5 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>
Mac Newbold's avatar
Mac Newbold committed
20
#include <iostream.h>
21
#include <time.h>
Mac Newbold's avatar
Mac Newbold committed
22
#include <stdlib.h>
23
#include <math.h>
Mac Newbold's avatar
Mac Newbold committed
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
#include <algorithm>
31
32

using namespace boost;
Mac Newbold's avatar
Mac Newbold committed
33
34

#include "common.h"
35
#include "delay.h"
Mac Newbold's avatar
Mac Newbold committed
36
#include "physical.h"
37
#include "virtual.h"
38
#include "vclass.h"
39
#include "pclass.h"
40
#include "score.h"
41
42
43
#include "solution.h"
#include "maps.h"
#include "anneal.h"
44
45
46

// Here we set up all our graphs.  Need to create the graphs
// themselves and then setup the property maps.
47
tb_pgraph PG;
48
49
50
51
52
53
54
55
56
57
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);

// List of virtual types by name.
58
name_count_map vtypes;
59
name_list_map vclasses;
60
61

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

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

74
75
76
77
78
// 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;
79

80
81
// Same, but for distances 
switch_dist_map_map switch_dist;
Christopher Alfeld's avatar
   
Christopher Alfeld committed
82

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

86
87
88
// An amount to scale the neighborhood size by
double scale_neighborhood = 1.0;

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

95
// Whether or not assign should use pclasses
96
bool disable_pclasses = false;
97

Robert Ricci's avatar
Robert Ricci committed
98
99
100
// Whether or not assign should prune out pclasses that it knows can
// never be used
bool prune_pclasses = false;
101
102
103

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

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

// 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;
Robert Ricci's avatar
Robert Ricci committed
111
112
113
114
115

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

// 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;
122
123
124
125
  
// XXX - shouldn't be in this file
double absbest;
int absbestviolated, iters, iters_to_best;
Robert Ricci's avatar
Robert Ricci committed
126

127
128
129
// Map of all physical types in use in the system
tb_ptype_map ptypes;

130
131
132
/*
 * Internal functions
 */
Mac Newbold's avatar
Mac Newbold committed
133

Robert Ricci's avatar
Robert Ricci committed
134
// Return the CPU time (in seconds) used by this process
135
136
137
138
139
140
141
142
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;
}

Robert Ricci's avatar
Robert Ricci committed
143
// Read in the .ptop file
144
145
146
147
void read_physical_topology(char *filename)
{
  ifstream ptopfile;
  ptopfile.open(filename);
Robert Ricci's avatar
Robert Ricci committed
148
  if (!ptopfile.is_open()) {
149
      cout << "*** Unable to open ptop file " << filename << endl;
150
      exit(EXIT_FATAL);
Robert Ricci's avatar
Robert Ricci committed
151
  }
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
  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;
    }
  }
Robert Ricci's avatar
Robert Ricci committed
175
#endif // DUMP_GRAPH
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

#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;
    }
  }
Robert Ricci's avatar
Robert Ricci committed
199
#endif // GRAPH_DEBUG
200

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

}

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

  // Set up the weight map for Dijkstra's
218
219
220
221
222
223
224
225
226
227
  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);
  }
Christopher Alfeld's avatar
   
Christopher Alfeld committed
228

Robert Ricci's avatar
Robert Ricci committed
229
  // Let boost do the Disjktra's for us, from each switch
230
231
232
233
234
235
236
237
  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])));
Christopher Alfeld's avatar
   
Christopher Alfeld committed
238
239
  }

240
241
242
243
244
245
246
247
248
#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;
    }
  }
Robert Ricci's avatar
Robert Ricci committed
249
#endif // GRAPH_DEBUG
250
251
}

Robert Ricci's avatar
Robert Ricci committed
252
// Read in the .top file
253
254
255
256
void read_virtual_topology(char *filename)
{
  ifstream topfile;
  topfile.open(filename);
Robert Ricci's avatar
Robert Ricci committed
257
  if (!topfile.is_open()) {
258
      cout << "*** Unable to open top file " << filename << endl;
259
      exit(EXIT_FATAL);
Robert Ricci's avatar
Robert Ricci committed
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
286
  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
}
Robert Ricci's avatar
Robert Ricci committed
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
312
/*
 * 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;
}

313
void print_help()
314
{
315
316
  cout << "assign [options] ptopfile topfile [config params]" << endl;
  cout << "Options: " << endl;
317
#ifdef TIME_TERMINATE
318
  cout << "  -l <time>   - Limit runtime." << endl;
Mac Newbold's avatar
Mac Newbold committed
319
#endif
320
  cout << "  -s <seed>   - Set the seed." << endl;
321
#ifdef GRAPHVIZ_SUPPORT
322
  cout << "  -v <viz>    - Produce graphviz files with given prefix." <<
323
    endl;
324
#endif
325
326
327
  cout << "  -r          - Don't allow trivial links." << endl;
  cout << "  -p          - Disable pclasses." << endl;
  cout << "  -d          - Enable dynamic pclasses." << endl;
328
#ifdef PER_VNODE_TT
329
  cout << "  -P          - Prune unusable pclasses." << endl;
330
#endif
331
332
333
  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;
Robert Ricci's avatar
Robert Ricci committed
334
335
  cout << "  -t <float>  - Start the temperature at <float> instead of melting."
      << endl;
336
337
  cout << "  -u          - Print a summary of the solution." << endl;
  cout << "  -c <float>  - Use the 'connected' pnode finding algorithm " <<
338
339
      "<float>*100% of the time." << endl;
  cout << "  -n          - Don't anneal - just do the prechecks." << endl;
340
  exit(EXIT_FATAL);
341
342
343
344
345
346
347
}
 
// 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;
348

349
    bool ok = true;
Mac Newbold's avatar
Mac Newbold committed
350

351
    // First, check the regular types
352
353
354
355
    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
356
	tb_ptype_map::iterator ptype_it = ptypes.find(vtype_it->first);
357
	if (ptype_it == ptypes.end()) {
358
	    cout << "  *** No physical nodes of type " << vtype_it->first
359
360
		<< " found" << endl;
	    ok = false;
361
	} else {
362
	    // Okay, there are some - are there enough?
363
	    if (ptype_it->second->pnode_slots() < vtype_it->second) {
364
		cout << "  *** " << vtype_it->second << " nodes of type " <<
365
		    vtype_it->first << " requested, but only "
366
367
368
369
370
371
372
373
374
		    << ptype_it->second->pnode_slots() << " found" << endl;
		ok = false;
	    }
	    // Okay, there are enough - but are we allowed to use them?
	    if (ptype_it->second->maxusers() &&
		    (ptype_it->second->maxusers() < vtype_it->second)) {
		cout << "  *** " << vtype_it->second << " nodes of type " <<
		    vtype_it->first << " requested, but you are only " <<
		    "allowed to use " << ptype_it->second->maxusers() << endl;
375
376
		ok = false;
	    }
377
	}
378
    }
379
380
381
382
383
384
385

    // 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++) {
386
387
	    tb_ptype_map::iterator mit = ptypes.find(*vtype_it);
	    if ((mit != ptypes.end()) && (mit->second->pnode_slots() != 0)) {
388
389
390
391
392
393
394
395
396
397
398
399
		found_match = true;
		break;
	    }
	}

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

400
    if (ok) {
401
      cout << "Type precheck passed." << endl;
402
403
      return 1;
    } else {
404
      cout << "*** Type precheck failed!" << endl;
405
406
407
      return 0;
    }
}
408

409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
// 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);
425

426
427
428
429
    /*
     * Indicates whether all nodes have potential matches or not
     */
    bool ok = true;
430

431
432
    for (;vit != vendit;vit++) {
	tb_vnode *v = get(vvertex_pmap,*vit);
433

434
435
436
437
438
439
440
441
	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
442
	map<crope,int> matched_desires;
443

444
445
446
447
448
	// 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;

449
450
451
452
	tb_vclass *vclass = v->vclass;
	tb_vclass::members_map::iterator mit;
	if (vclass) {
	    mit = vclass->members.begin();
453
	}
454
455
456
457
458
459
460
461
462
	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;
	    }
463

464
465
466
467
468
469
470
471
            // Check to make sure there are actually nodes of this type in the
            // physical topology
            if (type_table.find(this_type) == type_table.end()) {
                // Yes, I know, goto is evil. But I'm not gonna indent the next
                // 100 lines of code for this error case
                goto nosuchtype;
            }

472
473
	    for (pclass_vector::iterator it = type_table[this_type].second->begin();
		    it != type_table[this_type].second->end(); it++) {
474

475
476
		bool potential_match = true;
		// Grab the first node of the pclass as a representative sample
477
	 	tb_pnode *pnode = *((*it)->members[this_type]->L.begin());
478
479
480

		// Check to see if any of the link that this pnode has are of
		// the correct type for the virtual node
Mac Newbold's avatar
Mac Newbold committed
481

482
483
484
485
486
487
		// Check bandwidth on emulated links
		if (pnode->total_bandwidth >= v->total_bandwidth) {
		    matched_bw++;
		} else {
		    potential_match = false;
		}
Mac Newbold's avatar
Mac Newbold committed
488

489
490
491
492
493
494
495
496
497
498
499
500
		// 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;
		    }
		}

501
502
503
504
505
506
507
		/*
		 * Check features and desires
		*/
		tb_featuredesire_set_iterator
		    fdit(v->desires.begin(),v->desires.end(),
			 pnode->features.begin(),pnode->features.end());
		for (;!fdit.done();fdit++) {
508
		    // Skip 'local' and 'global' features
509
		    if (fdit->is_global() || fdit->is_local()) {
510
511
			continue;
		    }
512
513
514
		    // Only check for FDs that would result in a violation if
		    // unmatched.
		    if (fdit.either_violateable()) {
515
516
517
518
519
			if (fdit.membership() !=
				tb_featuredesire_set_iterator::BOTH) {
			    potential_match = false;
			}

520
521
			// We look for violateable desires on vnodes so that we
			// can report them to the user
522
523
524
525
526
527
528
529
530
			if ((fdit.membership() ==
				tb_featuredesire_set_iterator::FIRST_ONLY ||
			    fdit.membership() ==
				 tb_featuredesire_set_iterator::BOTH)
				&& fdit.first_iterator()->is_violateable()) {
			    if (matched_desires.find(fdit->name()) ==
				    matched_desires.end()) {
				matched_desires[fdit->name()] = 0;
			    }
531
532
533
534
			}
			if (fdit.membership() ==
				tb_featuredesire_set_iterator::BOTH) {
			    matched_desires[fdit->name()]++;
535
536
537
			}
		    }
		}
538
		
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
		// 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;
		  }
		}
Mac Newbold's avatar
Mac Newbold committed
559

560
561
562
563
564
565
		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;
566
#endif
567
568
		}
	    }
569

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

582
	if (vnode_type_table[v->name].first == 0) {
583
	    cout << "  *** No possible mapping for " << v->name << endl;
584
	    // Make an attempt to figure out why it didn't match
585
586
587
588
589
590
591
592
593
594
595
596
597
598
	    
	    // 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;
		}
	      }
599
	    }
600

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

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

620
    }
621

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

630
631
632
#else // PER_VNODE_TT
    // PER_VNODE_TT is required for this check, just pretend it's OK.
    return 1;
Robert Ricci's avatar
Robert Ricci committed
633
#endif
634
}
Christopher Alfeld's avatar
   
Christopher Alfeld committed
635

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

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

742
#ifdef GRAPHVIZ_SUPPORT
743
744
745
  if (viz_prefix.size() == 0) {
    if (getenv("ASSIGN_GRAPHVIZ") != NULL) {
      viz_prefix = getenv("ASSIGN_GRAPHVIZ");
746
    }
747
  }
748
#endif
Mac Newbold's avatar
Mac Newbold committed
749

750
751
752
753
  if (argc == 0) {
    print_help();
  }

754
755
756
757
758
759
760

  // 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);
761
  sigaction(SIGINT,&action,NULL);
762

763
764
765
766
767
768
769
  // 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);

770
771
772
773
774
775
776
777
778
779
780
781
782
  // 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;
783
  srandom(seed);
784
785
786

  read_physical_topology(argv[0]);
  calculate_switch_MST();
787
788
789
790
791

  read_virtual_topology(argv[1]);

  // Time while we make pclasses and do the type prechecks
  timestart = used_time();
792
793
  
  cout << "Generating physical equivalence classes:";
794
  generate_pclasses(PG,disable_pclasses,dynamic_pclasses);
795
  cout << pclasses.size() << endl;
796

797
798
799
#ifdef PCLASS_DEBUG
  pclass_debug();
#endif
800

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

806
807
  // Run the mapping precheck
  if (!mapping_precheck()) {
808
      exit(EXIT_UNRETRYABLE);
809
  }
Robert Ricci's avatar
Robert Ricci committed
810

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

816
#ifdef PER_VNODE_TT
Robert Ricci's avatar
Robert Ricci committed
817
818
819
  if (prune_pclasses) {
      prune_unusable_pclasses();
  }
820
821
822
#endif

  // Output graphviz if necessary
823
#ifdef GRAPHVIZ_SUPPORT
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
  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();
  }
839
#endif
Robert Ricci's avatar
Robert Ricci committed
840
841
842
843
844
845
846
847
848

  // 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;
  }
849
 
850
  // Note, time is started earlier now, up by where we make pclasses
851
852
  anneal(scoring_selftest, scale_neighborhood, initial_temperature_pointer,
      use_connected_pnode_find);
853
  timeend = used_time();
854

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

861
  if ((!compare_scores(get_score(),absbest)) || (violated > absbestviolated)) {
862
    cout << "WARNING: Internal scoring inconsistency." << endl;
863
    cout << "score:" << get_score() << " absbest:" << absbest <<
864
865
866
      " violated:" << violated << " absbestviolated:" <<
      absbestviolated << endl;
  }
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