1. 28 May, 2003 1 commit
    • Robert Ricci's avatar
      Added the TRIVIAL_LINK_BW option, which allows, in the ptop file, · 5c67bf1f
      Robert Ricci authored
      specification of how much bandwidth can be used on the node for
      trivial links. Clearly, there will be some limit to loopback
      transfers, and this makes assign aware of it.
      
      While I was in there, cleaned up and commented some of the code I was
      working on.
      
      Also fixed a bug with the type pre-check and emulated links that are
      trivial_ok - we can't add these into the total for a vnode, because
      they could end up being satisified with trivial links.
      5c67bf1f
  2. 17 Apr, 2003 2 commits
    • Robert Ricci's avatar
    • Robert Ricci's avatar
      Several changes to assign: · 1003657e
      Robert Ricci authored
      Add features and desires to the PER_VNODE_TT restrictions. For
      desires, we can tell the user which ones can't be satisfied, but for
      features, we don't even try to figure out which one(s) keep us from
      mapping. From the assign_todo file, this is:
      9.   add features/desires to PER_VNODE_TT restrictions
      
      Add a new -P switch, when PER_VNODE_TT is in use. This casues it to
      prune out pclasses that no vnode can map to - this can lead to _huge_
      time savings, particularly since we put things like wide-area nodes
      into the ptop file. I've seen a 98% reduction in time when using both
      -p and -P! But, it's not the default yet, because I need to do more
      testing to make sure that this isn't hurting solution quality
      significantly.  todo item:
      8.   prune pclasses when using PER_VNODE_TT
      
      Standardize the exit values from assign:
      On success, returns 0
      On failures that are not retryable (ie. this top can never be mapped
          to this ptop), returns 2
      If SA fails to find a solution (ie., we might consider retrying),
          returns 1
      
      Fix a bug that has annoyed me for a very, very long time - if the
      input files don't exist, exit instead of hanging forever!
      
      Make the weight at which a feature/desire is considered 'hard' (ie. it
      generates a violation if unsatisifed or undesired) a variable, so that
      we'll be able to change it from 1.0 if we want.
      
      Put some more messages that should appear inline in the mail to stderr
      instead of stdout.
      1003657e
  3. 16 Apr, 2003 1 commit
    • Robert Ricci's avatar
      Fix PER_VNODE_TT to work with vclasses and emulated links. Now, we can turn it · 690ec56d
      Robert Ricci authored
      on in production!
      
      PER_VNODE_TT handles emulated links by simply adding up the total bandwidth
      consumed by a vnode, and the total bandwidth available on each pnode. Of
      course, this can lead to false positives (knapsack problem), but that's okay,
      because it just means we won't bail up front - we'll have to do the full
      annealing pass before we decide it's unmappable.
      
      PER_VNODE_TT now also tries to figure out why a vnode is not mappable - if
      there are _no_ pclasses that match one of the restrictions, it will print out
      something like:
        *** No possible mapping for nodeA
            Too many links!
        *** No possible mapping for nodeB
            Too much bandwidth on emulated links!
      
      This completes the following two items from assign_todo.txt:
      
      6.   fix PER_VNODE_TT and vclasses
      7.   fix PER_VNODE_TT and emulated vlinks
      690ec56d
  4. 15 Apr, 2003 1 commit
  5. 10 Mar, 2003 1 commit
  6. 05 Mar, 2003 1 commit
  7. 10 Feb, 2003 1 commit
  8. 05 Feb, 2003 1 commit
  9. 04 Feb, 2003 1 commit
  10. 29 Jan, 2003 1 commit
  11. 03 Jul, 2002 1 commit
  12. 29 May, 2002 1 commit
  13. 14 Jan, 2002 1 commit
  14. 08 Jan, 2002 2 commits
  15. 07 Jan, 2002 1 commit
  16. 03 Jan, 2002 1 commit
  17. 02 Jan, 2002 1 commit
    • Christopher Alfeld's avatar
      · 1eb1e1d9
      Christopher Alfeld authored
      This check-in consists of 7 modifications to assign.
      
      1. Equivalence Classes
      
      Defined an equivalence relation on the physical nodes and applied it
      to the physical topology to get the resulting quotient topology (abuse
      of terminology).  So instead of searching among all possible physical
      nodes to make a map, assign only searches among all possible
      equivalence classes of nodes.  This tremendously reduces the search
      space.  At the time of this writing it reduces the physical topology
      from 252 nodes to 13 nodes.  The equivalence classes are generated
      automatically from the ptop file.
      
      2. Scoring based on equivalence classes.
      
      Each equivalence class used comes with a significant cost.  This
      strongly encourages assign to use equivalence machines when possible.
      The result is that an experiment that does not otherwise specify will
      almost definitely get machines of the same type.  If this needs to be
      reduced in the future it is the SCORE_PCLASS constant.
      
      3. Heuristics
      
      Added a bunch of heuristics for choosing which equivalence class to
      use.  This was less successful than I hoped.  A good solution is now
      found in record time but it still continues searching.  When OPTIMAL
      is turned on these heuristics help a lot.  When off they make little
      difference.  I may turn this into a compile time option in the future
      since the heuristics do take non-trivial CPU cycles.
      
      4. Fixed the very-very-big-and-evil disconnected-switches bug.
      
      Assign wasn't cleaning up after itself in certain cases.  Disconnected
      graphs are now merely a minor, easily ignored, bump rather than the
      towering cliffs they use to be.
      
      5. Fixed the not-yet-noticed not-enough-nodes bug.
      
      Found a bug that probably has never come up before because we have
      checks that avoid those circumstances.
      
      6. Modified constants.
      
      I was tired of waiting so long for results so, I lowered CYCLES and
      reduced the constant for naccepts (Mac, you probably want to add that
      inconspicuous number to your configurable constants; look for
      "naccepts =").  The results is roughly a speedup of 2.  It works great
      currently but we may want to change these numbers up again if we get
      problems with features and desires.
      
      7. General clean up.
      
      Associated with the other changes was a lot of restructuring and some
      cleanup.  Specifically to the assign loop and scoring code.
      1eb1e1d9
  18. 29 Nov, 2001 1 commit
  19. 25 Jul, 2001 1 commit
  20. 24 Jul, 2001 1 commit
    • Christopher Alfeld's avatar
      This commit contains two signifcant changes: · 210aa1ec
      Christopher Alfeld authored
      1. 'tb-set-hardware ... shark' and 'tb-set-hardware ... dnard' are now
      functionally identical.  Previously only the former worked but both passed
      the parser.
      
      2. Assign will now exit very quickly in the case that, for a given virtual
      nodes, there are no physical nodes that could match in type.  This should
      never happen as the parser and assign_wrapper have checks that usually
      prevent this.  However, in the case of problems in the code (such as #1)
      this'll make it easier to debug.  In addition, as we add more types of
      nodes and our estimates becoming increasingly inaccurate cases where this
      might occur could slip in.  All calling code treats this identically to an
      'insufficient resources' failure.
      210aa1ec
  21. 20 Jul, 2001 1 commit
    • Christopher Alfeld's avatar
      This is a nearly complete rewrite of the assign interswitch code. Assign · 8078740b
      Christopher Alfeld authored
      now precomputers the shortest path between all pairs of switches and uses
      this to computer paths through the switch fabric.  In the process of
      writing this I also removed the limitations of two switch hops.  Packets
      can now travel through any number of switches to reach their destination.
      Of course, the longer the path the more it costs so assign will prefer
      shorter paths.
      
      Also did various other tweaks in the process.  We now use strings almost
      everywhere instead of char*'s and the makefile is cleaner.
      8078740b
  22. 03 May, 2001 1 commit
  23. 24 Apr, 2001 1 commit
  24. 23 Mar, 2001 2 commits
  25. 21 Mar, 2001 1 commit
  26. 14 Mar, 2001 1 commit
  27. 13 Mar, 2001 1 commit
  28. 01 Mar, 2001 1 commit
  29. 26 Dec, 2000 1 commit
  30. 25 Aug, 2000 1 commit
  31. 03 Jul, 2000 1 commit
  32. 29 Mar, 2000 1 commit
  33. 05 Jan, 2000 4 commits
  34. 02 Jan, 2000 1 commit