1. 20 May, 2009 1 commit
  2. 01 May, 2009 1 commit
  3. 20 Dec, 2007 1 commit
  4. 17 Dec, 2007 1 commit
    • Robert Ricci's avatar
      Fix for fixed interfaces: move the code that filters interfaces whose · 43333bb7
      Robert Ricci authored
      name's don't match from resolve_link() to find_best_link() - the latter
      returns only one link of each type, so it's too late to find the right
      interface by the time we get back out to resolve_link(). Also fixed
      a built-in assmption about the 'direction' that physical links go in.
      The old code (explicity) assumed that links to from node to switch - now
      we flip around our comparison if the directions of the links do not
      match.
      
      This was a bugger, even though it didn't involve much code, since the
      'flipping' involves a 'parity' issue - it's really easy to mess up the
      parity in several places and get it to work under *some* circumstances.
      
      As a side effect, added some more information to the plink strucutre.
      This turned out to not be necessary for the solution I finally came
      up with - it was part of an earlier, abandoned one. But, it's probably
      good information to have around in the future.
      43333bb7
  5. 01 Mar, 2007 1 commit
  6. 25 Jan, 2006 1 commit
    • Robert Ricci's avatar
      Merge in changes from the assign-devel branch. This includes: · ed3cbc13
      Robert Ricci authored
      Ripping out crope and replacing (almost) all cropes, char*s and
      strings with fstring
      
      Beginnings of XML parser support (not built by default yet).
      
      Significant re-org of code.
      
      Should now compile with the latest gcc.
      
      Putting link information in stored solutions.
      
      Support for fixing interfaces.
      ed3cbc13
  7. 13 Sep, 2005 1 commit
  8. 10 May, 2005 1 commit
  9. 19 Jan, 2005 1 commit
    • Robert Ricci's avatar
      Add support for the set-type-limit command in the ptop file. · 8eaec842
      Robert Ricci authored
      It looks like this:
      set-type-limit <type> <count>
      
      This can be placed anywhere in the ptop file.  It limits the number of
      physical nodes of a given type that an experimenter is allowed to use.
      
      For example, we may limit a user to 10 PCs, or 5 pc850s. In the latter
      case, if the experimenter had simply asked for 10 generic PCs, then we
      will try to find them some mapping of nodes that uses types of PCs
      other than pc850s.
      
      Added a precheck to tell the user up-front if they asked for more
      nodes than they are allowed to use of a given type.
      8eaec842
  10. 11 Aug, 2004 1 commit
  11. 08 Jun, 2004 1 commit
  12. 07 Jun, 2004 1 commit
  13. 03 Jun, 2004 1 commit
    • Robert Ricci's avatar
      'port' assign to compile under gcc 3 (specifically tested with 3.3.1). · f05e1008
      Robert Ricci authored
      This mostly required messing with the STL #includes.
      
      Still builds under gcc 2.95, and won't be built with 3.3 by default
      until I've spent more time testing it.
      
      One reason for doing this is that gcc 3.3 seems to generate faster
      code from templated functions. Tests so far show that the
      gcc3-compiled binary shaves 15-30% off of assign's runtime.
      
      The other reason for doing this is forward-looking. When we end up
      getting boss running on FreeBSD 5 or a recent Linux distro, the
      compiler is likely to be from the gcc 3 branch.
      f05e1008
  14. 02 Jun, 2004 1 commit
  15. 26 Apr, 2004 1 commit
    • Robert Ricci's avatar
      Some big changes to assign, and some related changes to assign_wrapper · 238dce73
      Robert Ricci authored
      and ptopgen.
      
      Add link typing to assign. Each virtual link is given a single type.
      Each physical link is given one or more types. A virtual link will
      only be mapped to a physical link which can satisfy its type. In both
      the top and ptop files, the link types are now mandatory, and they
      fall at the end of the mandatory link arguments.
      
      This differers from the 'regular' type system in two ways. First, a
      plink is not constrained to filling only one type at a time. If we are
      using emulated links, a plink could satisfy, say, an 'ethernet' link
      and an 'fxp' link at the same time. This seems to more naturally match
      the way we'll use link types.  Second, there are no counts assoicated
      with link types, as there are for node types. ie. a link is not an
      'ethernet:1' link, it's an 'ethernet' link. Presumably, when
      multiplexing virtual links onto a physical one, it's bandwidth that's
      the factor that limits the multiplexing.
      
      The link type is now taken into account when constructing pclasses,
      and in the mapping precheck.
      
      As a side-effect of these changes, the silly 'count' argument on the
      end of link lines in the ptop file, which was used for the fake LAN
      nodes, is no longer supported.
      
      The implementation could be a bit more efficient, but that would mean
      tossing more of the stuff we do with boost's graph library. I think
      this should happen, but today is not the day.
      
      Modify assign_wrapper and ptopgen to spit out top and ptop files in
      the new format.
      
      Changed the constant LINK_UKNOWN to LINK_UNMAPPED - the new name more
      accurately reflects the way this constant is used.
      
      Add a new '-n' flag that tells assign not to do annealing, just exit
      after the type precheck.
      
      Clarify the usage message for the -c flag.
      
      Removed some dead code for dealing with LAN nodes.
      238dce73
  16. 15 Apr, 2004 1 commit
  17. 09 Mar, 2004 1 commit
  18. 30 Jan, 2004 1 commit
  19. 28 Jan, 2004 1 commit
    • Robert Ricci's avatar
      Bugfix for 'loopback' links. · b8546d9b
      Robert Ricci authored
      Do some scoring, not just violations, for stateful features and
      desires - this does a better job of nudging assign towards good
      solutions.
      b8546d9b
  20. 14 Jan, 2004 1 commit
  21. 12 Jan, 2004 1 commit
    • Robert Ricci's avatar
      Several changes, mostly targeted at jail and simulation-type · 3a345f8e
      Robert Ricci authored
      topologies.
      
      First, added a new 'summary' of the solution, when the '-u' option is
      given. It's a view of things from the physical side - prints out how
      many vnodes were mapped to each pnode, as well as how much bandwidth
      (trivial and non-trivial) was used on each node. For 'normal' nodes,
      we also print out all links used and how much bandwidth was used on
      each of them. For switches, we print only inter-switch links. This is
      amazingly helpful in getting an intuitive feel for how well assign is
      doing.
      
      Added a SIGINFO handler for the impatient (like me) to see things such
      as the current temperature, and current and best scores, while assign
      is running.
      
      Fixed a bug in which emulated links could get over-subscribed, as well
      as a few other misc. bugfixes.
      
      Changed the way assign goes through the list of a node's pclasses in
      random order - there were problems with the old way in which you could
      end up with a situation in which some pnodes were chosen with a much
      higher probability than others. Now, rather than treating the list as
      a ring and starting at a random place, we make a randomly-ordered list
      of the pclasseses, and go through it from start to finish.
      
      Did some work on dynamic pclasses so that we adjust the estimate of
      the neighborhood size to account for disabled pclasses (ie. pnodes
      that have nothing mapped to them yet.)
      
      Changed the way that find_link_to_switch() decides on the best link to
      use - the old method was doing very poorly at bin-packing emulated
      links into plinks. I now use a simple first-fit algorithm. This made a
      pretty big difference. I may try some other fast bin-packing
      approximation algorithm, but my main fear is that all of the good ones
      (such as the 'sort from largest to smallest, then do first-fit'
      algorithm) may require re-mapping other links. This might be slow,
      and/or it might make it difficult, if not impossible, to keep
      add_node() and remove_node() symmetric.
      
      Combinded direct_link() and find_link_to_switch() into
      find_best_link(), since they really do the same thing.
      
      Standardized on std::random() to get random numbers - previosuly, some
      calls were using std::rand().
      
      The big one: I added a find_pnode_connected() function that finds a
      random pnode that one of the vnode's neighbors in the virtual graph is
      assigned to. Then, with a random probability (given with the -c option
      on the command line), we try that function to find a pnode first (if
      it fails, we still call find_pnode() ). Of course, this is only really
      applicable when you have a reasonable degree of vnode-to-pnode
      multiplexing. In the test case I'm using, this managed to get 3x as
      much bandwidth into trivial links as just using find_pnode().
      3a345f8e
  22. 06 Jan, 2004 1 commit
    • Robert Ricci's avatar
      Fix dynamic pclasses, and make them the default for virtual nodes · c7e2d29e
      Robert Ricci authored
      again.
      
      One of the fixes changes the way in which we iterate through pclasses
      in find_pnode(). We used to treat the vector like a ring buffer, and
      start (randomly) someplace in the middle. This turns out to give some
      bad statistical properties when doing dynamic pclasses, since long
      chains of disabled pclasses will cause some pclasses to be selected
      more often. My old hack of just hopping around randomly in the
      disabled-pclass case was bad, because it's hard to tell when you've
      actually tried all the pclasses - so, we were getting false negatives
      where it was looking like there was no place available where we could
      map a vnode, which turned out to have worse effects than I had
      thought.
      
      So, now, we make a list of all the indices and randomize the order,
      then just iterate through that list.
      
      We also now count the number of pclasses that are enabled at every
      temperature step, and adjust the neighborhood size to remove them.
      This makes dynamic pclasses quite a bit faster - it cuts the time
      by 30% - 50% for my test case.
      
      Cleaned up find_pnode() by removing some #ifdef's that we don't use,
      and probably will never want to again - this makes the function almost
      readable!
      c7e2d29e
  23. 17 Dec, 2003 1 commit
    • Robert Ricci's avatar
      Add the ability to have vritual nodes that consume more than one · 13c6d59f
      Robert Ricci authored
      'slot'. In the top file, you can how give' the virtual node's type as
      type:count - sim:5, for example. If you give no count, it defaults to
      one.
      
      The idea here is to allow a pre-pass to assign to 'coarsen' the
      virtual graph. This pre-pass could, for example, combine several
      virtual or simulated nodes into one so that assign has a simpler
      virtual graph to work with.
      13c6d59f
  24. 08 Dec, 2003 1 commit
    • Robert Ricci's avatar
      Add 'local' features and desires. As opposed to 'global' fds, these · 18d05233
      Robert Ricci authored
      effect a single node, but are different from 'class' fds in that they
      are stateful - ie. the socre you get depends on all other vnodes
      currently mapped to the pnodes. These are identified by prefixing
      them with a '?'. ('*' for global, mnemoic 'matches all'; '?' for
      local, mnemonic 'matches one')
      
      The currently implemented local fd is the additive one, or '?+'. We
      add the desire weight for all vnodes on the pnode together, and if
      this number is greater than the pnode's weight for the feature, a
      violation is flagged.
      
      The idea here is that we can give a pnode a feature like: ?+memory:256
      and vnodes desires like ?+memory:16 or ?+memory:64 to pack vnodes
      onto pnodes in a manner that appropriately reflects their resource
      usage.
      18d05233
  25. 13 Nov, 2003 1 commit
  26. 12 Nov, 2003 1 commit
    • Robert Ricci's avatar
      A few fixes for 'loopback' links in the virtual topology (links that · 227346c3
      Robert Ricci authored
      connect a vnode to itself):
      
      Move up the point at which we consider a vnode to be assigned - we
      want to do this before we look for link resolutions, or the 'other
      end' of a loopback link appears to be unassigned, which is not true.
      
      Add a mecahism to watch out for scoring lookpback links twice. The
      edge iterator for an undirected graph sees each vlink twice (there
      are two 'out' edges from the vnode). So, we have to avoid scoring it
      the second time.
      
      Note that we still only allow loopback links if they are 'trivial_ok'.
      227346c3
  27. 22 Oct, 2003 1 commit
    • Robert Ricci's avatar
      A few improvements: · b058ef64
      Robert Ricci authored
      Fix a bug with limited trivial link bandwidth. It used to be the case
      that we penalized solutions that over-used the trivial bandwidth based
      on the number of links that were over it. Turns out this was a
      problem, if you had links of differing bandwidths, and were near the
      limit. Certain orderings were possible where you would remove two
      trivial links in a different order than you added them, which might
      result in more (or fewer) violations being scored then when you did
      them originally. The fix for this is to penalize these based on
      bandwidth, which is what assign now does.
      
      Added a '-g' flag, which does greedy link selection - assign normally
      does random link selection until the very end, when it does one pass
      with greedy selection. This flag makes it do this all the time. This
      is useful for debugging, because it cuts out a call to random(). Turns
      out, it doesn't seem to make assign much slower. I might consider
      making it the default.
      
      Better output when the selftest (-T) fails.
      b058ef64
  28. 10 Oct, 2003 1 commit
  29. 29 Sep, 2003 1 commit
  30. 19 Sep, 2003 1 commit
  31. 18 Sep, 2003 1 commit
    • Robert Ricci's avatar
      Add some new ways to treat features. · 46a52a04
      Robert Ricci authored
      Features that begin with a '*' have some kind of global scope. Since
      that, by itself, doesn't mean much, the second character of the
      feature name must tell us what type of global feature it is. The two
      currently supported are:
      
      '&' - 'one is okay' - don't penalize the first pnode that has this
          feature, but penalize subsequent ones. Will be used to prefer
          not to give people multiple nodes at the sime widearea site.
      '!' - 'more than one is okay' - penalize the first pnode that has
          this feature, but not subsequent ones. This could be used to let
          assign pick experiments to swap out in order to let the current
          experiment map. The idea being that once you've decided that one
          of the experiment's nodes is getting stolen, you might as well
          swap the whole thing.
      
      For now, these global features should not have corresponding desires,
      because it's not clear what the right thing to do would be. But, we may
      decide to add these semantics someday.
      46a52a04
  32. 15 Sep, 2003 1 commit
    • Robert Ricci's avatar
      Some fixes aimed at vnodes: · 7848e357
      Robert Ricci authored
      Don't allow intraswitch links to vnodes on switches - they'll get
      scored as direct links. Since LANs are now directly on switches, there
      were situations where we could have scored the same link as either
      direct or intraswitch, which results in two different scores. This can
      cause those 'contact calfeld' warnings, and might have caused some
      strange scoring fluxuations as assign ran.
      
      When picking a link to a switch, for emulated links, pick the least
      loaded link, not the one with the fewest users. This helps in situations
      where the link bandwidths are heterogenous.
      7848e357
  33. 11 Sep, 2003 2 commits
  34. 04 Sep, 2003 2 commits
  35. 18 Jul, 2003 1 commit
  36. 10 Jul, 2003 1 commit
    • Robert Ricci's avatar
      Fix a major bug in dynamic pclasses. One of thse little things that · bc6c6a54
      Robert Ricci authored
      was sooo wrong you wonder how it worked in the first place... Took
      me days to find this one!
      
      Also added a new switch, '-o', that lets assign try out solutions
      that over-load a pnode. This helps a lot with topologies where the
      optimal solution is a best-fit onto multiplexed pnodes.
      
      The end result is that Mike's snake maps much better - it used to get
      an essentially random mapping, but now it gets something acceptible.
      bc6c6a54
  37. 01 Jul, 2003 1 commit
    • Robert Ricci's avatar
      Give assign the ability to make dynamic pclasses. Here's how it works: · fbcd6752
      Robert Ricci authored
      After building the set of pclasses normally, we make another pass
      through the vnodes. The goal to create a pclass for each individual
      node. We disable the node's 'own' pclass to begin with. Then, the
      _first_ time it gets a vnode mapped to it, we remove it from the
      'regular' pclass it belongs to, and enable it's own pclass. Then, if
      it goes empty, we put it back in its regular pclass and disable it's
      own.
      
      The point of this is to replace -p for use with multiplexed nodes.
      Instead of disabling pclasses altogheter, which has serious
      performance implications, we can instead be smart about which pnodes
      remain equivalent (because nothing's been mapped to them), and which
      are now different. The result is that on my test topoloy, the time to
      get a good mapping has gone from over 3 minutes to about 6 seconds.
      
      This feature is enabled with the -d option, and the -P option is
      pretty much mandatory when using it, since it greatly exacerbates the
      problem of cruft in the ptop file.
      
      This satisfies #14 from the todo file:
      14.  do dynamic pclasses
      
      Also bumped up the minimum neighborhood size from 500 to 1000. In some
      tests I was doing, this resulted in better solutions.
      fbcd6752
  38. 26 Jun, 2003 1 commit