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

7 8
#include "port.h"

Christopher Alfeld's avatar
 
Christopher Alfeld committed
9
#include <stdlib.h>
10 11

#include <queue>
12
#include <list>
13 14
#include <algorithm>

15 16 17 18 19 20 21 22 23 24 25
/*
 * We have to do these includes differently depending on which version of gcc
 * we're compiling with
 */
#if __GNUC__ == 3 && __GNUC_MINOR__ > 0
#include <ext/hash_map>
using namespace __gnu_cxx;
#else
#include <hash_map>
#endif

26 27 28 29 30 31 32
#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
33 34

#include "common.h"
35
#include "delay.h"
Christopher Alfeld's avatar
 
Christopher Alfeld committed
36 37 38 39
#include "physical.h"
#include "virtual.h"
#include "pclass.h"

40 41 42 43 44 45 46

// 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.

47 48
// Used to catch cumulative floating point errors
static double ITTY_BITTY = 0.00000001;
49 50 51 52

extern pnode_pvertex_map pnode2vertex;

// pclasses - A list of all pclasses.
Christopher Alfeld's avatar
 
Christopher Alfeld committed
53
extern pclass_list pclasses;
54

55
// type_table - Maps a type (fstring) to a tt_entry.  A tt_entry
56 57
// consists of an array of pclasses that satisfy that type, and the
// length of the array.
58
extern pclass_types type_table;
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 67
#ifdef PCLASS_DEBUG_MORE
  cerr << "pclass_equiv: a=" << a->name << " b=" << b->name << endl;
#endif
68 69 70
  // 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.
71
  // don't prefer one just because it's the same pclass over another that, in
72 73
  // reality, is very different.
  if (a->unique || b->unique) {
74 75 76
#ifdef PCLASS_DEBUG_MORE
      cerr << "    no, unique" << endl;
#endif
77 78
      return 0;
  }
79
  
Christopher Alfeld's avatar
 
Christopher Alfeld committed
80
  // check type information
81 82
  for (tb_pnode::types_map::iterator it=a->types.begin();
       it!=a->types.end();++it) {
83
    const fstring &a_type = (*it).first;
84
    tb_pnode::type_record *a_type_record = (*it).second;
85 86
    
    tb_pnode::types_map::iterator bit = b->types.find(a_type);
87 88 89 90
    if ((bit == b->types.end()) || ! ( *(*bit).second == *a_type_record) ) {
#ifdef PCLASS_DEBUG_MORE
      cerr << "    no, a has type " << a_type << endl;
#endif
Christopher Alfeld's avatar
 
Christopher Alfeld committed
91
      return 0;
92
    }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
93
  }
94 95 96 97
  // 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) {
98
    const fstring &b_type = (*it).first;
99 100 101
    tb_pnode::type_record *b_type_record = (*it).second;
    
    tb_pnode::types_map::iterator bit = a->types.find(b_type);
102 103 104 105
    if ((bit == a->types.end()) || ! ( *(*bit).second == *b_type_record) ) {
#ifdef PCLASS_DEBUG_MORE
      cerr << "    no, b has type " << b_type << endl;
#endif
106
      return 0;
107
    }
108
  }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
109

110 111
  // check subnode information
  if (a->subnode_of != b->subnode_of) {
112 113 114
#ifdef PCLASS_DEBUG_MORE
      cerr << "    no, parent nodes difer" << endl;
#endif
115 116 117
      return 0;
  }
  if (a->has_subnode || b->has_subnode) {
118 119 120
#ifdef PCLASS_DEBUG_MORE
      cerr << "    no, subnodes nodes difer" << endl;
#endif
121 122 123
      return 0;
  }

Christopher Alfeld's avatar
 
Christopher Alfeld committed
124
  // check features
125 126 127 128 129 130 131 132
  tb_featuredesire_set_iterator fdit(a->features.begin(),a->features.end(),
	  b->features.begin(),b->features.end());

  while (!fdit.done()) {
      if (fdit.membership() == tb_featuredesire_set_iterator::BOTH) {
	  // Great, we've got a feature that's in both, just make sure that
	  // the two are equivalent (score, etc.)
	  if (!fdit.both_equiv()) {
133 134 135
#ifdef PCLASS_DEBUG_MORE
              cerr << "    no, different weights for feature " << fdit->name() << endl;
#endif
136 137 138 139
	      return 0;
	  }
      } else {
	  // Got a feature that's in one but not the other
140 141 142
#ifdef PCLASS_DEBUG_MORE
              cerr << "    no, only one has " << fdit->name() << endl;
#endif
143 144 145 146
	  return 0;
      }

      fdit++;
147 148
  }

149
  // Check links
150 151
  pvertex an = pnode2vertex[a];
  pvertex bn = pnode2vertex[b];
152

153 154 155
  // Make a list of all links for node b
  typedef list<pedge> link_list;
  link_list b_links;
156 157 158 159 160

  poedge_iterator eit,eendit;
  tie(eit,eendit) = out_edges(bn,PG);
  for (;eit != eendit;++eit) {
    pvertex dst = target(*eit,PG);
161
    b_links.push_back(*eit);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
162
  }
163 164 165
  
  // 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
166 167
  tie(eit,eendit) = out_edges(an,PG);
  for (;eit != eendit;++eit) {
168 169 170 171 172 173 174 175 176 177 178 179 180 181 182
    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)) {
183 184 185
#ifdef PCLASS_DEBUG_TONS
        cerr << "    mached link " << plink_a->name << endl;
#endif
186 187 188 189 190 191
	b_links.erase(bit);
	break;
      }
    }
    // If we never found a match, these nodes aren't equivalent
    if (bit == b_links.end()) {
192 193 194
#ifdef PCLASS_DEBUG_MORE
              cerr << "    no, a has unmached link " << plink_a->name << endl;
#endif
195 196
      return 0;
    }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
197
  }
198 199

  // Make sure node b has no extra links
200 201 202 203 204 205 206 207 208
  if (b_links.size() != 0) {
#ifdef PCLASS_DEBUG_MORE
              cerr << "    no, b has unmached link " << endl;
#endif
      return 0;
  }
#ifdef PCLASS_DEBUG_MORE
              cerr << "    yes" << endl;
#endif
Christopher Alfeld's avatar
 
Christopher Alfeld committed
209 210 211
  return 1;
}

212
/* This function takes a physical graph and generates the set of
Christopher Alfeld's avatar
 
Christopher Alfeld committed
213 214 215 216
   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. */
217 218
int generate_pclasses(tb_pgraph &PG, bool pclass_for_each_pnode,
    bool dynamic_pclasses) {
219
  typedef hash_map<tb_pclass*,tb_pnode*,hashptr<tb_pclass*> > pclass_pnode_map;
220
  typedef hash_map<fstring,pclass_list*> name_pclass_list_map;
221 222 223 224 225 226 227 228

  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
229
    bool found_class = 0;
230
    tb_pnode *curP = get(pvertex_pmap,cur);
231 232 233 234 235 236 237 238 239 240 241 242
    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;
243
	  curclass->add_member(curP,false);
244 245 246
	  break;
	} 
      }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
247
    }
248

Christopher Alfeld's avatar
 
Christopher Alfeld committed
249 250 251 252
    if (found_class == 0) {
      // new class
      tb_pclass *n = new tb_pclass;
      pclasses.push_back(n);
253
      canonical_members[n]=curP;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
254
      n->name = curP->name;
255
      n->add_member(curP,false);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
256 257 258
    }
  }

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
  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";
285
      n->add_member(pnode,true);
286 287 288 289
      n->disabled = true;
    }
  }

290 291 292 293 294 295 296 297 298 299
  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
300
      }
301
      pre_type_table[(*dit).first]->push_back(cur);
302 303 304 305 306
    }
  }

  // now we convert the lists in pre_type_table into arrays for
  // faster access.
307 308 309 310 311
  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());
312 313
    int i=0;
    
314 315 316 317 318
    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
319
    }
320
    delete L;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
321 322 323 324
  }
  return 0;
}

325
int tb_pclass::add_member(tb_pnode *p, bool is_own_class)
Christopher Alfeld's avatar
 
Christopher Alfeld committed
326
{
327 328
  tb_pnode::types_map::iterator it;
  for (it=p->types.begin();it!=p->types.end();++it) {
329
    fstring type = (*it).first;
330 331
    if (members.find(type) == members.end()) {
      members[type]=new tb_pnodelist;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
332
    }
333
    members[type]->push_back(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
334 335
  }
  size++;
336 337 338 339 340
  if (is_own_class) {
      p->my_own_class=this;
  } else {
      p->my_class=this;
  }
Christopher Alfeld's avatar
 
Christopher Alfeld committed
341 342 343
  return 0;
}

344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373
// 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();
  }
374 375 376 377 378
  if (!own_class && !other_class) {
    cerr << "In neither class!" << endl;
    pclass_debug();
    abort();
  }
379 380
}

Christopher Alfeld's avatar
 
Christopher Alfeld committed
381
// should be called after add_node
382
int pclass_set(tb_vnode *v,tb_pnode *p)
Christopher Alfeld's avatar
 
Christopher Alfeld committed
383
{
384
  tb_pclass *c = p->my_class;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
385 386
  
  // remove p node from correct lists in equivalence class.
387 388 389
  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
390
      // same class - only remove if node is full
391 392 393
      if ((p->current_type_record->current_load ==
	      p->current_type_record->max_load) ||
	      p->my_own_class) {
394
	(*dit).second->remove(p);
395 396 397
	if (p->my_own_class) {
	  p->my_own_class->disabled = false;
	}
Christopher Alfeld's avatar
 
Christopher Alfeld committed
398 399
      }
    } else {
400 401 402 403 404
      // 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
405
    }
406 407 408 409 410 411 412 413 414 415 416
#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
417
  }
418

419
  c->used_members++;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
420
  
421
  //assert_own_class_invariant(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
422 423 424
  return 0;
}

425
int pclass_unset(tb_pnode *p)
Christopher Alfeld's avatar
 
Christopher Alfeld committed
426 427
{
  // add pnode to all lists in equivalence class.
428 429 430 431 432
  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
433 434 435
      // 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.
436
      if (! (*dit).second->exists(p)) {
437
	assert(p->current_type_record->current_load > 0);
438 439 440 441
#ifdef PNODE_ALWAYS_FRONT
	(*dit).second->push_front(p);
#else
#ifdef PNODE_SWITCH_LOAD
442
	if (p->current_type_record->current_load == 0) {
443 444 445 446
#else
	if (p->current_load == 1) {
#endif
	  (*dit).second->push_back(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
447
	} else {
448
	  (*dit).second->push_front(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
449
	}
450
#endif
Christopher Alfeld's avatar
 
Christopher Alfeld committed
451 452
      }
    }
453 454 455 456

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

459
  if (p->my_own_class && (p->total_load == 1)) {
460 461
    p->my_own_class->disabled = true;
  }
462

463
  c->used_members--;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
464
  
465
  //assert_own_class_invariant(p);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
466 467 468 469 470 471
  return 0;
}

void pclass_debug()
{
  cout << "PClasses:\n";
472 473 474
  pclass_list::iterator it;
  for (it=pclasses.begin();it != pclasses.end();++it) {
    cout << *(*it);
Christopher Alfeld's avatar
 
Christopher Alfeld committed
475 476 477 478
  }

  cout << "\n";
  cout << "Type Table:\n";
479
  pclass_types::iterator dit;
480 481
  extern pclass_types vnode_type_table; // from assign.cc
  for (dit=vnode_type_table.begin();dit!=vnode_type_table.end();++dit) {
482 483 484
    cout << (*dit).first << ":";
    int n = (*dit).second.first;
    pclass_vector &A = *((*dit).second.second);
485
    for (int i = 0; i < n ; ++i) {
486
      cout << " " << A[i]->name;
Christopher Alfeld's avatar
 
Christopher Alfeld committed
487 488 489 490 491
    }
    cout << "\n";
  }
}

492 493 494 495 496 497 498 499 500 501 502 503 504
/* 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;
}