-
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