• 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
physical.h 2.18 KB