pclass.cc 11.7 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
#include "port.h"

Christopher Alfeld's avatar
 
Christopher Alfeld committed
9
#include <stdlib.h>
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <hash_map>
#include <rope>
#include <queue>
#include <slist>
#include <algorithm>

#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>

using namespace boost;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
24
25

#include "common.h"
26
#include "delay.h"
Christopher Alfeld's avatar
 
Christopher Alfeld committed
27
28
29
30
#include "physical.h"
#include "virtual.h"
#include "pclass.h"

31
32
33
34
35
36
37

// The purpose of the code in s this file is to generate the physical
// equivalence classes and then maintain them during the simulated
// annealing process.  A function generate_pclasses is provided to
// fill out the pclass structure.  Then two routines pclass_set, and
// pclass_unset are used to maintaing the structure during annealing.

38
39
// Used to catch cumulative floating point errors
static double ITTY_BITTY = 0.00000001;
40
41
42
43

extern pnode_pvertex_map pnode2vertex;

// pclasses - A list of all pclasses.
Christopher Alfeld's avatar
 
Christopher Alfeld committed
44
extern pclass_list pclasses;
45
46
47
48

// type_table - Maps a type (crope) to a tt_entry.  A tt_entry
// consists of an array of pclasses that satisfy that type, and the
// length of the array.
49
extern pclass_types type_table;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
50

51
52
53
54
55
56
57
58
typedef pair<pvertex,int> link_info; // dst, bw

struct hashlinkinfo {
  size_t operator()(link_info const &A) const {
    hashptr<void *> ptrhash;
    return ptrhash(A.first)/2+A.second;
  }
};
Christopher Alfeld's avatar
 
Christopher Alfeld committed
59
60
61
62
63
64

// returns 1 if a and b are equivalent.  They are equivalent if the
// type and features information match and if there is a one-to-one
// mapping between links that preserves bw, and destination.
int pclass_equiv(tb_pgraph &PG, tb_pnode *a,tb_pnode *b)
{
65
66
  typedef hash_multiset<link_info,hashlinkinfo> link_set;
  
Christopher Alfeld's avatar
 
Christopher Alfeld committed
67
  // check type information
68
69
70
  for (tb_pnode::types_map::iterator it=a->types.begin();
       it!=a->types.end();++it) {
    const crope &a_type = (*it).first;
71
    tb_pnode::type_record *a_type_record = (*it).second;
72
73
    
    tb_pnode::types_map::iterator bit = b->types.find(a_type);
74
    if ((bit == b->types.end()) || ! ( *(*bit).second == *a_type_record) )
Christopher Alfeld's avatar
 
Christopher Alfeld committed
75
76
      return 0;
  }
77
78
79
80
81
82
83
84
85
86
87
  // We have to check in both directions, or b might have a type that a does
  // not
  for (tb_pnode::types_map::iterator it=b->types.begin();
       it!=b->types.end();++it) {
    const crope &b_type = (*it).first;
    tb_pnode::type_record *b_type_record = (*it).second;
    
    tb_pnode::types_map::iterator bit = a->types.find(b_type);
    if ((bit == a->types.end()) || ! ( *(*bit).second == *b_type_record) )
      return 0;
  }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
88

89
90
91
92
93
94
95
96
  // check subnode information
  if (a->subnode_of != b->subnode_of) {
      return 0;
  }
  if (a->has_subnode || b->has_subnode) {
      return 0;
  }

Christopher Alfeld's avatar
 
Christopher Alfeld committed
97
  // check features
98
99
100
101
102
103
104
105
  for (tb_pnode::features_map::iterator it=a->features.begin();
       it != a->features.end();++it) {
    const crope &a_feature = (*it).first;
    const double a_weight = (*it).second;
    
    tb_pnode::features_map::iterator bit;
    bit = b->features.find(a_feature);
    if ((bit == b->features.end()) || ((*bit).second != a_weight)) 
Christopher Alfeld's avatar
 
Christopher Alfeld committed
106
107
108
109
110
111
      return 0;
  }

  // check links - to do this we first create sets of every link in b.
  // we then loop through every link in a, find a match in the set, and
  // remove it from the set.
112
113
  pvertex an = pnode2vertex[a];
  pvertex bn = pnode2vertex[b];
114

115
116
117
118
119
120
  link_set b_links;

  poedge_iterator eit,eendit;
  tie(eit,eendit) = out_edges(bn,PG);
  for (;eit != eendit;++eit) {
    pvertex dst = target(*eit,PG);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
121
    if (dst == bn)
122
123
      dst = source(*eit,PG);
    b_links.insert(link_info(dst,get(pedge_pmap,*eit)->delay_info.bandwidth));
Christopher Alfeld's avatar
 
Christopher Alfeld committed
124
  }
125
126
127
  tie(eit,eendit) = out_edges(an,PG);
  for (;eit != eendit;++eit) {
    pvertex dst = target(*eit,PG);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
128
    if (dst == an)
129
130
131
132
133
134
      dst = source(*eit,PG);
    int bw = get(pedge_pmap,*eit)->delay_info.bandwidth;
    link_info tomatch = link_info(dst,bw);
    link_set::iterator found = b_links.find(tomatch);
    if (found == b_links.end()) return 0;
    else b_links.erase(found);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
135
  }
136
  if (b_links.size() != 0) return 0;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
137
138
139
  return 1;
}

140
/* This function takes a physical graph and generates the set of
Christopher Alfeld's avatar
 
Christopher Alfeld committed
141
142
143
144
   equivalence classes of physical nodes.  The globals pclasses (a
   list of all equivalence classes) and type_table (and table of
   physical type to list of classes that can satisfy that type) are
   set by this routine. */
145
146
int generate_pclasses(tb_pgraph &PG, bool pclass_for_each_pnode,
    bool dynamic_pclasses) {
147
148
149
150
151
152
153
154
155
156
  typedef hash_map<tb_pclass*,tb_pnode*,hashptr<tb_pclass*> > pclass_pnode_map;
  typedef hash_map<crope,pclass_list*> name_pclass_list_map;

  pvertex cur;
  pclass_pnode_map canonical_members;

  pvertex_iterator vit,vendit;
  tie(vit,vendit) = vertices(PG);
  for (;vit != vendit;++vit) {
    cur = *vit;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
157
    bool found_class = 0;
158
    tb_pnode *curP = get(pvertex_pmap,cur);
159
160
161
162
163
164
165
166
167
168
169
170
    tb_pclass *curclass;

    // If we're putting each pnode in its own pclass, don't bother to find
    // existing pclasses that it matches
    if (!pclass_for_each_pnode) {
      pclass_pnode_map::iterator dit;
      for (dit=canonical_members.begin();dit!=canonical_members.end();
	  ++dit) {
	curclass=(*dit).first;
	if (pclass_equiv(PG,curP,(*dit).second)) {
	  // found the right class
	  found_class=1;
171
	  curclass->add_member(curP,false);
172
173
174
	  break;
	} 
      }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
175
    }
176

Christopher Alfeld's avatar
 
Christopher Alfeld committed
177
178
179
180
    if (found_class == 0) {
      // new class
      tb_pclass *n = new tb_pclass;
      pclasses.push_back(n);
181
      canonical_members[n]=curP;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
182
      n->name = curP->name;
183
      n->add_member(curP,false);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
184
185
186
    }
  }

187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
  if (dynamic_pclasses) {
    // Make a pclass for each node, which starts out disabled. It will get
    // enabled later when something is assigned to the pnode
    pvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(PG);
    for (;vit != vendit;++vit) {
      tb_pnode *pnode = get(pvertex_pmap,*vit);
      // No point in doing this if the pnode is either: already in a pclass of
      // size one, or can only have a single vnode mapped to it anyway
      if (pnode->my_class->size == 1) {
	  continue;
      }
      bool multiplexed = false;
      tb_pnode::types_map::iterator it = pnode->types.begin();
      for (; it != pnode->types.end(); it++) {
	  if ((*it).second->max_load > 1) {
	      multiplexed = true;
	      break;
	  }
      }
      if (!multiplexed) {
	  continue;
      }
      tb_pclass *n = new tb_pclass;
      pclasses.push_back(n);
      n->name = pnode->name + "-own";
213
      n->add_member(pnode,true);
214
215
216
217
      n->disabled = true;
    }
  }

218
219
220
221
222
223
224
225
226
227
  name_pclass_list_map pre_type_table;

  pclass_list::iterator it;
  for (it=pclasses.begin();it!=pclasses.end();++it) {
    tb_pclass *cur = *it;
    tb_pclass::pclass_members_map::iterator dit;
    for (dit=cur->members.begin();dit!=cur->members.end();
	 ++dit) {
      if (pre_type_table.find((*dit).first) == pre_type_table.end()) {
	pre_type_table[(*dit).first]=new pclass_list;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
228
      }
229
      pre_type_table[(*dit).first]->push_back(cur);
230
231
232
233
234
    }
  }

  // now we convert the lists in pre_type_table into arrays for
  // faster access.
235
236
237
238
239
  name_pclass_list_map::iterator dit;
  for (dit=pre_type_table.begin();dit!=pre_type_table.end();
       ++dit) {
    pclass_list *L = (*dit).second;
    pclass_vector *A = new pclass_vector(L->size());
240
241
    int i=0;
    
242
243
244
245
246
    type_table[(*dit).first]=tt_entry(L->size(),A);

    pclass_list::iterator it;
    for (it=L->begin();it!=L->end();++it) {
      (*A)[i++] = *it;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
247
    }
248
    delete L;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
249
250
251
252
  }
  return 0;
}

253
int tb_pclass::add_member(tb_pnode *p, bool is_own_class)
Christopher Alfeld's avatar
 
Christopher Alfeld committed
254
{
255
256
257
258
259
  tb_pnode::types_map::iterator it;
  for (it=p->types.begin();it!=p->types.end();++it) {
    crope type = (*it).first;
    if (members.find(type) == members.end()) {
      members[type]=new tb_pnodelist;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
260
    }
261
    members[type]->push_back(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
262
263
  }
  size++;
264
265
266
267
268
  if (is_own_class) {
      p->my_own_class=this;
  } else {
      p->my_class=this;
  }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
269
270
271
  return 0;
}

272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
// Debugging function to check the invariant that a node is either in its
// dynamic pclass, a 'normal' pclass, but not both
void assert_own_class_invariant(tb_pnode *p) {
  cerr << "class_invariant: " << p->name << endl;
  bool own_class = false;
  bool other_class = false;
  pclass_list::iterator pit = pclasses.begin();
  for (;pit != pclasses.end(); pit++) {
    tb_pclass::pclass_members_map::iterator mit = (*pit)->members.begin();
    for (;mit != (*pit)->members.end(); mit++) {
      if (mit->second->exists(p)) {
	if (*pit == p->my_own_class) {
	  cerr << "In own pclass (" << (*pit)->name << "," << (*pit)->disabled
	    << ")" << endl;
	  if (!(*pit)->disabled) {
	    own_class = true;
	  }
	} else {
	  cerr << "In pclass " << (*pit)->name << " type " << mit->first <<
	    " size " << mit->second->size() << endl;
	  other_class = true;
	}
      }
    }
  }
  if (own_class && other_class) {
    cerr << "Uh oh, in own and other class!" << endl;
    pclass_debug();
    abort();
  }
302
303
304
305
306
  if (!own_class && !other_class) {
    cerr << "In neither class!" << endl;
    pclass_debug();
    abort();
  }
307
308
}

Christopher Alfeld's avatar
 
Christopher Alfeld committed
309
// should be called after add_node
310
int pclass_set(tb_vnode *v,tb_pnode *p)
Christopher Alfeld's avatar
 
Christopher Alfeld committed
311
{
312
  tb_pclass *c = p->my_class;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
313
314
  
  // remove p node from correct lists in equivalence class.
315
316
317
  tb_pclass::pclass_members_map::iterator dit;
  for (dit=c->members.begin();dit!=c->members.end();dit++) {
    if ((*dit).first == p->current_type) {
Christopher Alfeld's avatar
 
Christopher Alfeld committed
318
      // same class - only remove if node is full
319
320
321
      if ((p->current_type_record->current_load ==
	      p->current_type_record->max_load) ||
	      p->my_own_class) {
322
	(*dit).second->remove(p);
323
324
325
	if (p->my_own_class) {
	  p->my_own_class->disabled = false;
	}
Christopher Alfeld's avatar
 
Christopher Alfeld committed
326
327
      }
    } else {
328
329
330
331
332
      // XXX - should be made faster
      if (!p->types[dit->first]->is_static) {
	  // If it's not in the list then this fails quietly.
	  (*dit).second->remove(p);
      }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
333
    }
334
335
336
337
338
339
340
341
342
343
344
#ifdef SMART_UNMAP
    if (c->used_members.find((*dit).first) == c->used_members.end()) {
	c->used_members[(*dit).first] = new tb_pclass::tb_pnodeset;
    }

    // XXX: bogus? Maybe we're only supposed to insert if it was in the
    // other list?
    //if (find((*dit).second->L.begin(),(*dit).second->L.end(),p) != (*dit).second->L.end()) {
    c->used_members[(*dit).first]->insert(p);
    //}
#endif
Christopher Alfeld's avatar
 
Christopher Alfeld committed
345
  }
346

347
  c->used_members++;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
348
  
349
  //assert_own_class_invariant(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
350
351
352
  return 0;
}

353
int pclass_unset(tb_pnode *p)
Christopher Alfeld's avatar
 
Christopher Alfeld committed
354
355
{
  // add pnode to all lists in equivalence class.
356
357
358
359
360
  tb_pclass *c = p->my_class;

  tb_pclass::pclass_members_map::iterator dit;
  for (dit=c->members.begin();dit!=c->members.end();++dit) {
    if ((*dit).first == p->current_type) {
Christopher Alfeld's avatar
 
Christopher Alfeld committed
361
362
363
      // If it's not in the list then we need to add it to the back if it's
      // empty and the front if it's not.  Since unset is called before
      // remove_node empty means only one user.
364
      if (! (*dit).second->exists(p)) {
365
	assert(p->current_type_record->current_load > 0);
366
367
368
369
#ifdef PNODE_ALWAYS_FRONT
	(*dit).second->push_front(p);
#else
#ifdef PNODE_SWITCH_LOAD
370
	if (p->current_type_record->current_load == 0) {
371
372
373
374
#else
	if (p->current_load == 1) {
#endif
	  (*dit).second->push_back(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
375
	} else {
376
	  (*dit).second->push_front(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
377
	}
378
#endif
Christopher Alfeld's avatar
 
Christopher Alfeld committed
379
380
      }
    }
381
382
383
384

#ifdef SMART_UNMAP
      c->used_members[(*dit).first]->erase(p);
#endif
Christopher Alfeld's avatar
 
Christopher Alfeld committed
385
386
  }

387
  if (p->my_own_class && (p->total_load == 1)) {
388
389
    p->my_own_class->disabled = true;
  }
390

391
  c->used_members--;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
392
  
393
  //assert_own_class_invariant(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
394
395
396
397
398
399
  return 0;
}

void pclass_debug()
{
  cout << "PClasses:\n";
400
401
402
  pclass_list::iterator it;
  for (it=pclasses.begin();it != pclasses.end();++it) {
    cout << *(*it);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
403
404
405
406
  }

  cout << "\n";
  cout << "Type Table:\n";
407
  pclass_types::iterator dit;
408
409
  extern pclass_types vnode_type_table; // from assign.cc
  for (dit=vnode_type_table.begin();dit!=vnode_type_table.end();++dit) {
410
411
412
    cout << (*dit).first << ":";
    int n = (*dit).second.first;
    pclass_vector &A = *((*dit).second.second);
413
    for (int i = 0; i < n ; ++i) {
414
      cout << " " << A[i]->name;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
415
416
417
418
419
    }
    cout << "\n";
  }
}