assign.cc 17.7 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <LEDA/graph_alg.h>
#include <LEDA/graphwin.h>
#include <LEDA/dictionary.h>
#include <LEDA/map.h>
#include <LEDA/graph_iterator.h>
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/time.h>
#include <string.h>

#include "testbed.h"

16
17
18
#include "phys.h"
topology *topo = NULL;

19
20
21
22
23
/* How can we chop things up? */
#define PARTITION_BY_ANNEALING 0

int nparts = 3;     /* DEFAULTS */
int intercap = 2;
David G Andersen's avatar
David G Andersen committed
24
int *nodecap = NULL;
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int better_heuristic = 0;
int accepts = 0;
int nnodes = 0;
int partition_mechanism;
int on_line = 0;

float sensitivity = .1;

static const int initial_temperature = 100;
static const int temp_prob = 130;

int refreshed = 0;

tbgraph G(1, 1);
node_array<int> bestnodes, absnodes;
float                       bestscore, absbest;

float *interlinks;
43
int *numnodes;
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

/*
 * Basic simulated annealing parameters:
 *
 * Make changes proportional to T
 * Accept worse solution with p = e^(change/Temperature*sensitivity)
 *
 */

inline int accept(float change, float temperature)
{
	float p;
	int r;

	if (change == 0) {
		p = 1000 * temperature / temp_prob;
	} else {
		p = expf(change/(temperature*sensitivity)) * 1000;
	}
	r = random() % 1000;
	if (r < p) {
		accepts++;
		return 1;
	}
	return 0;
}

David G Andersen's avatar
David G Andersen committed
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/*
 * score performs two functions at the moment.  First, it actually
 * performs an assignment of the virtual nodes in a switch to
 * physical nodes in that switch.  Then it returns a numeric evaluation
 * of the current mapping.
 *
 * There are several problems it solves:
 *
 *  a)  Assigning generic vnodes to nodes.
 *
 *      This is performed by searching a list of the nodes and assigning
 *      the virtual node to a node with the minimum necessary number
 *      of interfaces.
 *
 *  b)  Assigning delay vnodes to delay nodes:
 *
 *      Since a delay node may support many delay vnodes, this is a
 *      unit weight knapsack problem.  I take the easy out here
 *      by simply assigning the delay vnodes to nodes as they
 *      come along in the list.  This works for finding a feasible
 *      solution, but does not optimize the use of physical nodes.
 *
 *  c)  Scoring
 *
 *      Scoring is handled by:
 *       i)  add 1 for each unassigned node (excess nodes or too many
 *           interfaces
 *      ii)  Add 1 for each link across switches in excess of the
 *           capacity
 *     iii)  Add .1 for each switch used to try to minimize the number
 *           of switches involved
 *      iv)  Add .1 for each unit of bandwidth between switches to try
 *           to minimize interswitch bandwidth consumption
 *
 *
 *  The score function is the big bottleneck of the program right
 *  now.  Unlike the earlier versions in which only changed nodes
 *  were updated, score recomputes the entire solution each time
 *  it's called.  This is very inefficient and should be fixed
 *  by having the scupdate function update only the parts of the
 *  topology which changed.  This needs to be looked at more,
 *  but should probably be delayed until the rest of the features
 *  have been added.
 */

116
117
118
119
120
121
float score()
{

	float sc = 0;

	for (int i = 0; i < nparts; i++) {
David G Andersen's avatar
David G Andersen committed
122
		/* Have we violated bandwidth between switches? */
123
124
125
		if (interlinks[i] > intercap) {
			sc += (interlinks[i]-intercap);
		}
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
		/* XXX:  THIS MUST BE OPTIMIZED */
		
		/* Experimental:  Collapse delay nodes together
		 * and handle node fanout restrictions */

		/* Mark all nodes unused */
		for (int j = 0; j < topo->switches[i]->numnodes(); j++) {
			topo->switches[i]->nodes[j].used = 0;
		}
		
		int numdelays = 0;
		int assigned = 0;
		node n;
		forall_nodes(n, G) {
		    if (G[n].partition() == i) {
		        if (G[n].type() == testnode::TYPE_DELAY) {
				numdelays++;
			} else {
			    assigned = 0;
			    /* Assign to an available node */
			    for (int j = 0;
				 j < topo->switches[i]->numnodes();
				 j++) {
				    if (topo->switches[i]->nodes[j].used == 0 && (topo->switches[i]->nodes[j].ints >= G.degree(n))) {
					    topo->switches[i]->nodes[j].used = 1;
					    assigned = 1;
					    break;
				    }
			    }
			    if (!assigned) {
				    sc += 1;
			    }
			}
		    }
		}
		int numn = numnodes[i];

		numn -= numdelays;
		/* Now turn normal nodes into delay nodes as needed */
		/* XXX:  THIS IS NOT OPTIMAL.  We should improve on this
		 * so it uses the right size nodes a bit... but oh well */
		int maxnodes = topo->switches[i]->numnodes();
		int j = 0;
		while (numdelays > 0 && j < maxnodes) {
170
			if (topo->switches[i]->nodes[j].used) { j++; continue; }
171
172
173
174
175
176
177
178
179
180
			numdelays -= topo->switches[i]->nodes[j].ints/2;
			topo->switches[i]->nodes[j].used = 1;
			j++;
		}

		/* Add in the unsatisfied delay nodes */
		if (numdelays > 0) {
			sc += numdelays;
		}

David G Andersen's avatar
David G Andersen committed
181
182
183
184
185
186
187
188
189
		/* Try to minimize the number of switches used */
		/* This is likely NOT an effective way to do it! */
		if (numnodes[i] > 0) {
			sc += .1;
		}
		/* Try to minimize the bandwidth used... also probably
		   not effective */
		if (interlinks[i] > 0) {
			sc += .1 * interlinks[i];
190
191
192
193
194
		}
	}
	return sc;
}

David G Andersen's avatar
David G Andersen committed
195
196
197
198
199
200
201
202
203
204
205
206
207
208
/*
 * This is a completely bogus function.  It's a straight copy of the
 * score() function, but instead of incrementing a score counter,
 * it prints out a list of the constraints which are violated.
 *
 * In the future, this function should return something allowing us
 * to determine if a critical resource (nodes, interfaces, etc.) is
 * violated, or if a non-critical resource (interswitch bandwidth)
 * has been violated, so we can allow the user to proceed with a
 * potentially bad configuration if they so desire.
 *
 * ... and the "coding by copy" junk should be eliminated.  Jeez. :)
 */

209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
void violated()
{
	for (int i = 0; i < nparts; i++) {
		/* Have we violated bandwidth between switches? */
		if (interlinks[i] > intercap) {
			cout << "violated:  switch " << i << " bandwidth"
			     << endl;
		}
		for (int j = 0; j < topo->switches[i]->numnodes(); j++) {
			topo->switches[i]->nodes[j].used = 0;
		}
		
		int numdelays = 0;
		int assigned = 0;
		int unassigned = 0;
		node n;
		forall_nodes(n, G) {
		    if (G[n].partition() == i) {
		        if (G[n].type() == testnode::TYPE_DELAY) {
				numdelays++;
			} else {
			    /* Assign to an available node */
			    assigned = 0;
			    for (int j = 0;
				 j < topo->switches[i]->numnodes();
				 j++) {
				    if ((topo->switches[i]->nodes[j].used == 0) && (topo->switches[i]->nodes[j].ints >= G.degree(n))) {
					    topo->switches[i]->nodes[j].used = 1;
					    assigned = 1;
					    break;
				    }
			    }
			    if (!assigned) {
				    unassigned++;
			    }
			}
		    }
		}
		if (unassigned > 0) {
			cout << "violated:  switch " << i << " had "
			     << unassigned << " unassigned nodes" << endl;
		}
		int numn = numnodes[i];

		numn -= numdelays;
		/* Now turn normal nodes into delay nodes as needed */
		/* XXX:  THIS IS NOT OPTIMAL.  We should improve on this
		 * so it uses the right size nodes a bit... but oh well */
		int maxnodes = topo->switches[i]->numnodes();
		int j = 0;
		while (numdelays > 0 && j < maxnodes) {
260
			if (topo->switches[i]->nodes[j].used) { j++; continue; }
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
			numdelays -= topo->switches[i]->nodes[j].ints/2;
			topo->switches[i]->nodes[j].used = 1;
			j++;
		}

		/* Add in the unsatisfied delay nodes */
		if (numdelays > 0) {
			cout << "violated:  switch " << i << " had "
			     << numdelays << " unassigned delay nodes"
			     << endl;
		}
	}
}


David G Andersen's avatar
David G Andersen committed
276
277
278
279
280
/*
 * Reset the interlinks and numnodes arrays to an accurate
 * value.  Requires an inspection of all nodes and edges.
 */

281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
void screset() {
	edge e;
	node n;
	for (int i = 0; i < nparts; i++) {
		interlinks[i] = numnodes[i] = 0;
	}
    
	forall_nodes(n, G) {
		numnodes[G[n].partition()]++;
	}
	forall_edges(e, G) {
		node v = G.source(e);
		node w = G.target(e);
	
		if (G[v].partition() != G[w].partition()) {
			interlinks[G[v].partition()]++;
			interlinks[G[w].partition()]++;
		}
	}
}

David G Andersen's avatar
David G Andersen committed
302
303
304
305
306
307
308
309
310
311
312
/*
 * Move a node 'n' from its current switch to a new one, indicated by
 * newpos.
 *
 * Right now, this function performs the update logic to change the
 * node counts and the interswitch bandwidth, but does not cope
 * with the rest of the score.  In the future, it should perform
 * the incremental score update.  See the comments for the score()
 * function for more details.
 */

313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
void scupdate(node n, int newpos)
{
	int prevpos;

	AdjIt it(G, n);
	prevpos = G[n].partition();
	if (newpos == prevpos) return;

	numnodes[prevpos]--;
	numnodes[newpos]++;

	while (it.eol() == false) {
		edge e = it.get_edge();
		node n1 = G.source(e);
		node n2 = G.target(e);
		/* Ensure that n2 points to the stationary node */
		if (n2 == n) n2 = n1;

		/* They were not in the same bucket to start with */
		/* So both contributed to their interlinks */
		if (G[n2].partition() != prevpos) {
			interlinks[prevpos]--;

			/* If they're together now, there's no interlink */
			if (G[n2].partition() == newpos) {
				interlinks[G[n2].partition()]--;
			} else { /* Otherwise, move the interlink */
				interlinks[newpos]++;
			}
		}
		else /* They were in the same bucket.  They aren't anymore,
		      * or we would have exited earlier */
		{
			interlinks[G[n2].partition()]++;
			interlinks[newpos]++;
		}
		++it;
	}

	G[n].partition(newpos);
}

David G Andersen's avatar
David G Andersen committed
355
356
357
358
359
360
361
362
363
364
365
366
367
368
/*
 * The workhorse of our program.
 *
 * Assign performs an assignment of the virtual nodes (vnodes) to
 * nodes in the physical topology.
 *
 * The input virtual topology is the graph G (global)
 * the input physical topology is the topology topo (global).
 *
 * The simulated annealing logic is contained herein,
 * except for the "accept a bad change" computation,
 * which is performed in accept().
 */

369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
int assign()
{
	float newscore, bestscore, absbest;
	node n;
	int iters = 0;

	float timestart = used_time();
	float timeend;
	float scorediff;

	nnodes = G.number_of_nodes();
 
	float cycles = 120.0*(float)(nnodes + G.number_of_edges());

	int mintrans = (int)cycles;
	int trans;
	int naccepts = 40*nnodes;
	int accepts = 0;
	int oldpos;

	float temp = initial_temperature;
  
	/* Set up the initial counts */
	screset();

	bestscore = score();
	absbest = bestscore;

	if (bestscore == 0) {
#ifdef VERBOSE
		cout << "Problem started optimal\n";
#endif
		return 1;
	}
  
	while (temp >= 2) {
#ifdef VERBOSE
		cout << "Temperature:  " << temp << endl;
#endif
		trans = 0;
		accepts = 0;
      
		while (trans < mintrans && accepts < naccepts) {
			int newpos;
			trans++;
			iters++;
			n = G.choose_node();
			oldpos = G[n].partition();

			newpos = oldpos;
			/* XXX:  Room for improvement. :-) */
			while (newpos == oldpos)
				newpos = random() % nparts;
			scupdate(n, newpos);
			newscore = score();
			if (newscore < 0.1f) {
				timeend = used_time(timestart);
				cout << "OPTIMAL (0.0) in "
				     << iters << " iters, "
				     << timeend << " seconds" << endl;
				return 1;
			}
			/* So it's negative if bad */
			scorediff = bestscore - newscore;

			if (newscore < bestscore || accept(scorediff, temp)) {
				bestnodes[n] = G[n].partition();
				bestscore = newscore;
				accepts++;
				if (newscore < absbest) {
					node n2;
					forall_nodes(n2, G) {
						absnodes[n2] = G[n2].partition();
					}
					absbest = newscore;
				}
			} else { /* Reject this change */
				scupdate(n, oldpos);
			}
		}
      
		temp *= .9;
	}
	forall_nodes(n, G) {
		bestnodes[n] = absnodes[n];
	}
	bestscore = absbest;

	forall_nodes(n, G) {
		G[n].partition(absnodes[n]);
	}
	timeend = used_time(timestart);
	cout << "   BEST SCORE:  " << score() << " in "
	     << iters << " iters and " << timeend << " seconds" << endl;
	cout << "With " << accepts << " accepts of increases\n";
464
#if 0
465
	for (int i = 0; i < nparts; i++) {
David G Andersen's avatar
David G Andersen committed
466
		if (numnodes[i] > nodecap[i]) {
467
468
469
470
471
472
473
474
475
476
477
478
479
			cout << "node " << i << " has "
			     << numnodes[i] << " nodes" << endl;
		}
		if (interlinks[i] > intercap) {
			cout << "node " << i << " has "
			     << interlinks[i] << " links" << endl;
		}
	}
	if (score() < 0.0001) {
		return 1; /* Optimal enough */
	} else {
		return 0;
	}
480
481
#endif
	return 0;
482
483
}

David G Andersen's avatar
David G Andersen committed
484
485
486
487
488
489
490
491
/*
 * A legacy function from a less general version of the program.
 *
 * Now simply resets the node assignment, performs a new assignment,
 * and prints out the results.
 *
 */

492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
void loopassign()
{
	node_array<int> nodestorage;
	int optimal = 0;
	int orig_nparts;
	int orig_cap;
	float timestart = used_time();
	float totaltime;

	nodestorage.init(G, 0);
	bestnodes.init(G, 0);
	absnodes.init(G, 0);
    
	nnodes = G.number_of_nodes();
	optimal = assign();
	totaltime = used_time(timestart);
508
	violated();
509
510
	cout << "Total time to find solution "
	     << totaltime << " seconds" << endl;
511
	node n;
512
513
}

David G Andersen's avatar
David G Andersen committed
514
515
516
517
518
/*
 * If we have more ways of partitioning the graph other than just
 * simulated annealing, throw them in here.
 */

519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
void chopgraph(GraphWin& gw) {
	node n;
	forall_nodes(n, G) {
		G[n].partition(0);
	}
	switch(partition_mechanism) {
	case PARTITION_BY_ANNEALING:
		loopassign();
		break;
	default:
		cerr << "Unknown partition mechanism.  eeeek." << endl;
		exit(-1);
	}
}

David G Andersen's avatar
David G Andersen committed
534
535
536
537
538
539
540
541
/*
 * Something in the graph has changed!  Better redisplay.
 *
 * Performs the color assignment for whichever switch the
 * node belongs to and shows the inter-switch links as
 * dashed lines.
 */

542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
void display_scc(GraphWin& gw)
{
	edge e;
	node n;
	
	if (!refreshed) {
		forall_nodes(n, G) {
			G[n].partition(0);
		}
		if (on_line)
			chopgraph(gw);
	}
	
	refreshed = 0;
	
	/* Now color them according to their partition */
	forall_nodes(n, G) {
		switch(G[n].partition()) {
		case 0:
			gw.set_color(n, black);
			break;
		case 1:
			gw.set_color(n, blue);
			break;
		case 2:
			gw.set_color(n, green);
			break;
		case 3:
			gw.set_color(n, red);
			break;
		case 4:
			gw.set_color(n, yellow);
			break;
		case 5:
			gw.set_color(n, violet);
			break;
		case 6:
			gw.set_color(n, cyan);
			break;
		case 7:
			gw.set_color(n, brown);
			break;
		case 8:
			gw.set_color(n, pink);
			break;
		case 9:
			gw.set_color(n, orange);
			break;
		case 10:
			gw.set_color(n, grey1);
			break;
		case 11:
			gw.set_color(n, grey3);
			break;
		}
	}
	
	forall_edges(e, G) {
		node v = G.source(e);
		node w = G.target(e);
		if (G[v].partition() == G[w].partition()) {
			gw.set_style(e, solid_edge);
		} else {
			gw.set_style(e, dashed_edge);
		}
	}
	gw.redraw();
}

David G Andersen's avatar
David G Andersen committed
611
612
613
614
615
/*
 * Someone clicked on the "reassign" button.
 * Reset and redisplay.
 */

616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
void reassign(GraphWin& gw)
{
	node n;
	forall_nodes(n, G) {
		G[n].partition(0);
	}
	bestnodes.init(G, 0);
	absnodes.init(G, 0);
	chopgraph(gw);
	refreshed = 1;
	display_scc(gw);
}


void new_edge_handler(GraphWin& gw, edge)  { display_scc(gw); }
void del_edge_handler(GraphWin& gw)        { display_scc(gw); }
void new_node_handler(GraphWin& gw, node)  { display_scc(gw); }
void del_node_handler(GraphWin& gw)        { display_scc(gw); }

void usage() {
	fprintf(stderr,
637
		"usage:  assign [-h] [-ao] [-s <switches>] [-n nodes/switch] [-c cap] [file]\n"
638
639
640
641
642
643
644
		"           -h ...... brief help listing\n"
		"           -s #  ... number of switches in cluster\n"
		"           -n #  ... number of nodes per switch\n"
		"           -c #  ... inter-switch capacity (bw)\n"
		"                 (# of links which can go between switches\n"
		"           -a ...... Use simulated annealing (default)\n"
		"           -o ...... Update on-line (vs batch, default)\n"
645
		"           -t <file> Input topology desc. from <file>\n"
646
647
648
649
650
651
652
653
		);
}

int main(int argc, char **argv)
{
	int h_menu;
	extern char *optarg;
	extern int optind;
654
	char *topofile = NULL;
655
656
657
658
659
    
	int ch;

	partition_mechanism = PARTITION_BY_ANNEALING;
    
660
	while ((ch = getopt(argc, argv, "oas:n:c:t:h")) != -1)
661
662
663
664
665
666
		switch(ch) {
		case 'h': usage(); exit(0);
		case 's': nparts = atoi(optarg); break;
		case 'c': intercap = atoi(optarg); break;
		case 'a': partition_mechanism = PARTITION_BY_ANNEALING; break;
		case 'o': on_line = 1; break;
667
		case 't': topofile = optarg; break;
668
669
670
671
672
673
674
		default: usage(); exit(-1);
		}

	argc -= optind;
	argv += optind;
    
	interlinks = new float[nparts];
675
	numnodes = new int[nparts];
676
677
678
679
680
681
	for (int i = 0; i < nparts; i++) {
		interlinks[i] = 0;
		numnodes[i] = 0;
	}
    
	srandom(time(NULL) + getpid());
David G Andersen's avatar
David G Andersen committed
682
683
684
685
686
687
688

	/*
	 * Set up the LEDA graph window environment.  Whenever
	 * the user does anything to the graph, call the
	 * proper handler.
	 */
	
689
690
691
692
693
694
695
696
697
698
699
	GraphWin gw(G, "Flux Testbed:  Simulated Annealing");
    
	gw.set_init_graph_handler(del_edge_handler);
	gw.set_new_edge_handler(new_edge_handler);
	gw.set_del_edge_handler(del_edge_handler);
	gw.set_new_node_handler(new_node_handler);
	gw.set_del_node_handler(del_node_handler);
    
	gw.set_node_width(24);
	gw.set_node_height(24);
    
David G Andersen's avatar
David G Andersen committed
700
701
702
703
	/*
	 * Allow the user to specify a topology in ".top" format.
	 */

704
705
706
	if (argc == 1) {
		ifstream infile;
		infile.open(argv[0]);
707
		if (!infile || !infile.good()) {
708
709
710
		  cerr << "Error opening file: " << argv[0] << "\n";
		  exit(1);
		}
711
712
713
714
		parse_top(G, infile);
		gw.update_graph();
		node n;
		forall_nodes(n, G) {
David G Andersen's avatar
David G Andersen committed
715
716
717
			if (G[n].name() == NULL) {
				G[n].name("");
			}
718
719
720
721
722
			gw.set_label(n, G[n].name());
			gw.set_position(n,
					point(random() % 200, random() % 200));
		}
	}
723

David G Andersen's avatar
David G Andersen committed
724
725
726
727
728
729
	/*
	 * Allow the user to specify a physical topology
	 * in .phys format.  Fills in the "topo" global variable.
	 * Make no mistake:  This is actually mandatory now.
	 */
	
730
	if (topofile != NULL) {
David G Andersen's avatar
David G Andersen committed
731
		cout << "Parsing phys\n";
732
733
734
735
736
737
738
		topo = parse_phys(topofile);
		if (!topo) {
			cerr << "Could not read in topofile "
			     << topofile << endl;
			exit(-1);
		}
		nparts = topo->switchcount;
David G Andersen's avatar
David G Andersen committed
739
740
741
742
743
		cout << "Nparts: " << nparts << endl;
		nodecap = new int[nparts];
		for (int i = 0; i < nparts; i++) {
			nodecap[i] = topo->switches[i]->numnodes();
		}
744
		topo->print_topo();
745
	}
746
747
748
749
750
751
752
753
754
755
    
	gw.display();
    
	gw.set_directed(false);
    
	gw.set_node_shape(circle_node);
	gw.set_node_label_type(user_label);
    
	h_menu = gw.get_menu("Layout");
	gw_add_simple_call(gw, reassign, "Reassign", h_menu);
David G Andersen's avatar
David G Andersen committed
756
757
758
759

	/* Run until the user quits.  Everything is handled by callbacks
	 * from LEDA's event loop from here on.                           */
	
760
761
762
763
	gw.edit();
    
	return 0;
}