1. 30 Jan, 2004 1 commit
  2. 29 Jan, 2004 1 commit
  3. 28 Jan, 2004 3 commits
  4. 25 Jan, 2004 1 commit
  5. 23 Jan, 2004 1 commit
  6. 14 Jan, 2004 1 commit
  7. 12 Jan, 2004 2 commits
    • Robert Ricci's avatar
      Snapshot · 20770ea5
      Robert Ricci authored
      20770ea5
    • 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
  8. 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
  9. 18 Dec, 2003 1 commit
    • Robert Ricci's avatar
      Add two new features to assign: · 40ada0ba
      Robert Ricci authored
      In the top file, you can provide a 'node-hint', which is similar to a
      'fix-node' in that it specifies a starting mapping for the virtual
      node. Unlike a fixed node, however, assign is allowed to move hinted
      nodes around all it wants.
      
      Add a '-t' option to assign that allows you to give a starting
      temperature, instead of going through the usual melting process.
      
      Together, these may be helpful with the pre-pass we're planning on
      incorporating into assign. During that pass, assign will be working
      on a coarsened version of the virtual graph, so there may be some
      places where decisions are made poorly due to the reduced information.
      After one run has been done with the coarsened version, we can run
      assign again with the full version of the graph, but with 'node-hints'
      that start virtual nodes where the first run decided. This will allow
      assign to fine-tune the results of the first mapping.
      
      Of course, we don't want this second run to take too long, so we'll
      want to start it with a low initial temperature (so that it basically
      just does hill-climbing), and probably use a fractional '-H' argument
      to prevent it from spending too long on large topologies.
      40ada0ba
  10. 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
  11. 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
  12. 04 Dec, 2003 1 commit
  13. 13 Nov, 2003 1 commit
  14. 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
  15. 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
  16. 10 Oct, 2003 1 commit
  17. 06 Oct, 2003 1 commit
  18. 29 Sep, 2003 1 commit
  19. 19 Sep, 2003 1 commit
  20. 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
  21. 15 Sep, 2003 5 commits
  22. 12 Sep, 2003 3 commits
  23. 11 Sep, 2003 4 commits
  24. 10 Sep, 2003 1 commit
  25. 09 Sep, 2003 1 commit
  26. 08 Sep, 2003 2 commits
  27. 04 Sep, 2003 1 commit