pclass.cc 12.9 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

#include <hash_map>
#include <rope>
#include <queue>
14
#include <list>
15 16 17 18 19 20 21 22 23
#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

// 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)
{
56 57 58
  // The unique flag is used to signify that there is some reason that assign
  // is not aware of that the node is unique, and shouldn't be put into a
  // pclass. The usual reason for doing this is for scoring purposes - ie.
59
  // don't prefer one just because it's the same pclass over another that, in
60 61 62 63
  // reality, is very different.
  if (a->unique || b->unique) {
      return 0;
  }
64
  
Christopher Alfeld's avatar
 
Christopher Alfeld committed
65
  // check type information
66 67 68
  for (tb_pnode::types_map::iterator it=a->types.begin();
       it!=a->types.end();++it) {
    const crope &a_type = (*it).first;
69
    tb_pnode::type_record *a_type_record = (*it).second;
70 71
    
    tb_pnode::types_map::iterator bit = b->types.find(a_type);
72
    if ((bit == b->types.end()) || ! ( *(*bit).second == *a_type_record) )
Christopher Alfeld's avatar
 
Christopher Alfeld committed
73 74
      return 0;
  }
75 76 77 78 79 80 81 82 83 84 85
  // 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
86

87 88 89 90 91 92 93 94
  // 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
95
  // check features
96 97 98 99 100 101 102 103
  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
104 105 106
      return 0;
  }

107 108 109 110 111 112 113 114 115 116 117 118 119 120
  // have to go both ways in case the second node has a feature the first
  // doesn't
  for (tb_pnode::features_map::iterator it=b->features.begin();
       it != b->features.end();++it) {
    const crope &b_feature = (*it).first;
    const double b_weight = (*it).second;
    
    tb_pnode::features_map::iterator ait;
    ait = a->features.find(b_feature);
    if (ait == a->features.end()) {
      return 0;
    }
  }

121
  // Check links
122 123
  pvertex an = pnode2vertex[a];
  pvertex bn = pnode2vertex[b];
124

125 126 127
  // Make a list of all links for node b
  typedef list<pedge> link_list;
  link_list b_links;
128 129 130 131 132

  poedge_iterator eit,eendit;
  tie(eit,eendit) = out_edges(bn,PG);
  for (;eit != eendit;++eit) {
    pvertex dst = target(*eit,PG);
133
    b_links.push_back(*eit);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
134
  }
135 136 137
  
  // Go through all of a's links, trying to find matches on node b. If we find
  // a match, we remove it from the list
138 139
  tie(eit,eendit) = out_edges(an,PG);
  for (;eit != eendit;++eit) {
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162
    tb_plink *plink_a = get(pedge_pmap,*eit);
    pvertex dest_pv_a = target(*eit,PG);
    if (dest_pv_a == a)
      dest_pv_a = source(*eit,PG);

    link_list::iterator bit;
    for (bit = b_links.begin(); bit != b_links.end(); bit++) {
      tb_plink *plink_b = get(pedge_pmap,*bit);
      pvertex dest_pv_b = target(*bit,PG);
      if (dest_pv_b == b)
	dest_pv_b = source(*bit,PG);

      // If links are equivalent, remove this link in b from further
      // consideration, and go to the next link in a
      if ((dest_pv_a == dest_pv_b) && plink_a->is_equiv(*plink_b)) {
	b_links.erase(bit);
	break;
      }
    }
    // If we never found a match, these nodes aren't equivalent
    if (bit == b_links.end()) {
      return 0;
    }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
163
  }
164 165

  // Make sure node b has no extra links
166
  if (b_links.size() != 0) return 0;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
167 168 169
  return 1;
}

170
/* This function takes a physical graph and generates the set of
Christopher Alfeld's avatar
 
Christopher Alfeld committed
171 172 173 174
   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. */
175 176
int generate_pclasses(tb_pgraph &PG, bool pclass_for_each_pnode,
    bool dynamic_pclasses) {
177 178 179 180 181 182 183 184 185 186
  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
187
    bool found_class = 0;
188
    tb_pnode *curP = get(pvertex_pmap,cur);
189 190 191 192 193 194 195 196 197 198 199 200
    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;
201
	  curclass->add_member(curP,false);
202 203 204
	  break;
	} 
      }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
205
    }
206

Christopher Alfeld's avatar
 
Christopher Alfeld committed
207 208 209 210
    if (found_class == 0) {
      // new class
      tb_pclass *n = new tb_pclass;
      pclasses.push_back(n);
211
      canonical_members[n]=curP;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
212
      n->name = curP->name;
213
      n->add_member(curP,false);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
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
  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";
243
      n->add_member(pnode,true);
244 245 246 247
      n->disabled = true;
    }
  }

248 249 250 251 252 253 254 255 256 257
  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
258
      }
259
      pre_type_table[(*dit).first]->push_back(cur);
260 261 262 263 264
    }
  }

  // now we convert the lists in pre_type_table into arrays for
  // faster access.
265 266 267 268 269
  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());
270 271
    int i=0;
    
272 273 274 275 276
    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
277
    }
278
    delete L;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
279 280 281 282
  }
  return 0;
}

283
int tb_pclass::add_member(tb_pnode *p, bool is_own_class)
Christopher Alfeld's avatar
 
Christopher Alfeld committed
284
{
285 286 287 288 289
  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
290
    }
291
    members[type]->push_back(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
292 293
  }
  size++;
294 295 296 297 298
  if (is_own_class) {
      p->my_own_class=this;
  } else {
      p->my_class=this;
  }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
299 300 301
  return 0;
}

302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331
// 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();
  }
332 333 334 335 336
  if (!own_class && !other_class) {
    cerr << "In neither class!" << endl;
    pclass_debug();
    abort();
  }
337 338
}

Christopher Alfeld's avatar
 
Christopher Alfeld committed
339
// should be called after add_node
340
int pclass_set(tb_vnode *v,tb_pnode *p)
Christopher Alfeld's avatar
 
Christopher Alfeld committed
341
{
342
  tb_pclass *c = p->my_class;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
343 344
  
  // remove p node from correct lists in equivalence class.
345 346 347
  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
348
      // same class - only remove if node is full
349 350 351
      if ((p->current_type_record->current_load ==
	      p->current_type_record->max_load) ||
	      p->my_own_class) {
352
	(*dit).second->remove(p);
353 354 355
	if (p->my_own_class) {
	  p->my_own_class->disabled = false;
	}
Christopher Alfeld's avatar
 
Christopher Alfeld committed
356 357
      }
    } else {
358 359 360 361 362
      // 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
363
    }
364 365 366 367 368 369 370 371 372 373 374
#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
375
  }
376

377
  c->used_members++;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
378
  
379
  //assert_own_class_invariant(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
380 381 382
  return 0;
}

383
int pclass_unset(tb_pnode *p)
Christopher Alfeld's avatar
 
Christopher Alfeld committed
384 385
{
  // add pnode to all lists in equivalence class.
386 387 388 389 390
  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
391 392 393
      // 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.
394
      if (! (*dit).second->exists(p)) {
395
	assert(p->current_type_record->current_load > 0);
396 397 398 399
#ifdef PNODE_ALWAYS_FRONT
	(*dit).second->push_front(p);
#else
#ifdef PNODE_SWITCH_LOAD
400
	if (p->current_type_record->current_load == 0) {
401 402 403 404
#else
	if (p->current_load == 1) {
#endif
	  (*dit).second->push_back(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
405
	} else {
406
	  (*dit).second->push_front(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
407
	}
408
#endif
Christopher Alfeld's avatar
 
Christopher Alfeld committed
409 410
      }
    }
411 412 413 414

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

417
  if (p->my_own_class && (p->total_load == 1)) {
418 419
    p->my_own_class->disabled = true;
  }
420

421
  c->used_members--;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
422
  
423
  //assert_own_class_invariant(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
424 425 426 427 428 429
  return 0;
}

void pclass_debug()
{
  cout << "PClasses:\n";
430 431 432
  pclass_list::iterator it;
  for (it=pclasses.begin();it != pclasses.end();++it) {
    cout << *(*it);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
433 434 435 436
  }

  cout << "\n";
  cout << "Type Table:\n";
437
  pclass_types::iterator dit;
438 439
  extern pclass_types vnode_type_table; // from assign.cc
  for (dit=vnode_type_table.begin();dit!=vnode_type_table.end();++dit) {
440 441 442
    cout << (*dit).first << ":";
    int n = (*dit).second.first;
    pclass_vector &A = *((*dit).second.second);
443
    for (int i = 0; i < n ; ++i) {
444
      cout << " " << A[i]->name;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
445 446 447 448 449
    }
    cout << "\n";
  }
}

450 451 452 453 454 455 456 457 458 459 460 461 462
/* Count how many enabled, non-empty, pclasses there currently are. */
int count_enabled_pclasses()
{
  pclass_list::iterator it;
  int count = 0;
  for (it=pclasses.begin();it != pclasses.end();++it) {
      if ((*it)->disabled) { continue; }
      // XXX - skip empty pclasses
      count++;
  }

  return count;
}