• 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
solution.cc 8.62 KB