1. 15 Apr, 2004 1 commit
  2. 09 Mar, 2004 1 commit
  3. 08 Mar, 2004 1 commit
    • Robert Ricci's avatar
      A faily fundamental change in assign - change the criteria we use · 5a72226d
      Robert Ricci authored
      to accept new solutions, so that we don't give violtions any special
      treatment.
      
      This can greatly reduce 'thrasing' at low scores, allowing assign to
      converge on a solution much faster. For example, in the 1000-node
      topology used for the virtualization paper, assign's runtime dropped
      from nearly two hours to just over half an hour, with no degredation
      in scores found.
      
      You can get the old accept behavior by enabling the
      SPECIAL_VIOLATION_TREATMENT #define, which is on right now (hence, we
      are not using this change yet.)
      
      Here are the pertinent comments from the code:
      
      #ifdef SPECIAL_VIOLATION_TREATMENT
               /*
                * In this ifdef, we always accept new solutions that have fewer
                * violations than the old solution, and when we're trying to
                * determine whether or not to accept a new solution with a higher
                * score, we don't take violations into the account.
                *
                * The problem with this shows up at low temperatures. What can often
                * happen is that we accept a solution with worse violations but a
                * better (or similar) score. Then, if we were to try, say the first
                * solution (or a score-equivalent one) again, we'd accept it again.
                *
                * What this leads to is 'thrashing', where we have a whole lot of
                * variation of scores over time, but are not making any real
                * progress. This prevents the cooling schedule from converging for
                * much, much longer than it should really take.
                */
      #else // no SPECIAL_VIOLATION_TREATMENT
               /*
                * In this branch of the ifdef, we give violations no special
                * treatment when it comes to accepting new solution - we just add
                * them into the score. This makes assign behave in a more 'classic'
                * simulated annealing manner.
                *
                * One consequence, though, is that we have to be more careful with
                * scores. We do not want to be able to get into a situation where
                * adding a violation results in a _lower_ score than a solution with
                * fewer violations.
                */
      5a72226d
  4. 28 Jan, 2004 1 commit
  5. 25 Jan, 2004 1 commit
  6. 14 Jan, 2004 1 commit
  7. 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
  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. 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
  12. 10 Oct, 2003 1 commit
  13. 29 Sep, 2003 1 commit
  14. 19 Sep, 2003 1 commit
  15. 15 Sep, 2003 2 commits
  16. 12 Sep, 2003 2 commits
  17. 04 Sep, 2003 1 commit
  18. 20 Aug, 2003 1 commit
    • Robert Ricci's avatar
      Okay, add back some of my static nodes/multiplexing changes, · da47400b
      Robert Ricci authored
      really working this time.
      
      I will not check things in without running the testsuite
      I will not check things in without running the testsuite
      I will not check things in without running the testsuite
      I will not check things in without running the testsuite
      I will not check things in without running the testsuite
      I will not check things in without running the testsuite
      I will not check things in without running the testsuite
      I will not check things in without running the testsuite
      I will not check things in without running the testsuite
      I will not check things in without running the testsuite
      da47400b
  19. 08 Aug, 2003 1 commit
  20. 07 Aug, 2003 1 commit
    • Robert Ricci's avatar
      A lot of bugfixes relating, primarily, to multiplexed nodes: · 821107fc
      Robert Ricci authored
      Split the function that determines if a vnode can be mapped to a given pnode
      out of find_pnode, so that I can spread it out and make it more comprehensible.
      In doing so, fixed a bug in which static types were not getting handled
      correctly - a static type would only be found if no vnodes with dynamic types
      were allocated to the pnode.
      
      Fixed a bug in which, on allocation of a dynamic ptype, nodes where being
      removed from their static type lists in the type_table.
      
      Fixed a bug when there is a combination of fixed and un-fixed vnodes in the top
      file.
      
      I have more on the way, but this seemed like a good checkpoint.
      821107fc
  21. 30 Jul, 2003 2 commits
  22. 10 Jul, 2003 2 commits
  23. 09 Jul, 2003 1 commit
  24. 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
  25. 26 Jun, 2003 1 commit
    • Robert Ricci's avatar
      Major changes to the way assign handles LAN nodes. · 83cfa8ec
      Robert Ricci authored
      LAN nodes are no longer treated specially. Instead, I've introduced
      the idea of 'static' types (old-style types retroactively become
      'dynamic' types). While a pnode can only satisfy one dynamic type at a
      time, it can always satisfy its static types (assuming it has enough
      capacity left.) Static types are flagged by prepending them with a '*'
      in the ptop file. So, for example, you may give switches the
      '*lan:10000' type so that they can satisfy virtual LAN nodes. Of
      course, other pnodes can have this type too, so that we can get
      'trivial LANs'.
      
      Actually, removing special treatment for LANs cleans up a lot of code.
      However, it may have some negative impacts on solutions, since we're
      not as smart about where to place LAN nodes as we used to be (they get
      annealed along with everything else, and not migrated.) I haven't seen
      any evidence of this yet, however.
      
      This leaves us with a single type of special pnode, a switch.
      
      Also added a new bit of syntax in ptop files - when '*' is given as a
      the maxiumum load for a type, the node is allowed to take on an
      infinite (well, actually, just a really big number of) vnodes of that
      type.
      
      ptopgen was modified to always report switches as being capable of
      hosting LANs, and assign_wrapper now understands direct links to LANs,
      which is what we get when the LAN is hosted directly on a switch.
      
      Fixed a bug in scoring direct links, in which the penatly was being
      added once when a direct link was mapped, but subtracted only once
      when it was freed.
      
      Added a '-T' option for doing simple self-testing. When adding a node
      to the solution, assign records the score, adds the node, removes it
      again, and checks to make sure that the resulting score is the same as
      the original score. The usefulness of this feature in debugging
      scoring problems cannot be understated...
      83cfa8ec
  26. 20 Jun, 2003 1 commit