GitLab

In addition to assign, assign_wrapper and ptopgen have been modified
to output the new formats used by assign.

links.

with other emulated links.  Also added a trivial link type for virtual
links between vnodes in the same pnode.

make-vclass A 0.5 pc600 pc850

in the top file.  And then have nodes of type A.  Assign will try to put
them all as either pc600 or pc850.

Still need to write all the pre-assign stuff.

pclasses.  This involved removing the heuristics, which, for the most
part, were not worth the cycles they consumed, and scaled badly.

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.

problems.

fixing a bug in the debugging output.

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.

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.

Small changes done while working on the genetic algorithm. Added some debugging output options, cleaned up the make file a bit...

Added a basic README

Added two tests for features/desires.

around a second in most cases) but insures that we use a minimal number
of delay nodes.

Previously on the rare occasion that a run scored an integer score
assign_wrapper would break.

direct_link scores that pop up.

Also added the cycles_to_best performance monitoring

(now supply the total number of nodes).  Internal representation changed
to a linear list.  Scoring now assigns nodes to appropriate spots
in their switch and tries to match interface constraints.
Delay node coalescing now occurs.

todo:  Currently there's no way to set a node type via the GUI.
We should add this if we get time.

1)  Ripped out the optimizing loop
2)  Added in to the scoring bits designed to optimize by scoring not by
    constraining
3)  Now uses the topology description to determine the available
    physical network.

It doesn't produce feasible solutions as consistently as the old mechanism
did, but I suspect this just means I need to be a bit smarter with the
scoring, and also look for a global feasible solution and record it
instead of just the best score.  But perhaps the score tweaks will get it.

Updated help output.