GitLab

After building the set of pclasses normally, we make another pass
through the vnodes. The goal to create a pclass for each individual
node. We disable the node's 'own' pclass to begin with. Then, the
_first_ time it gets a vnode mapped to it, we remove it from the
'regular' pclass it belongs to, and enable it's own pclass. Then, if
it goes empty, we put it back in its regular pclass and disable it's
own.

The point of this is to replace -p for use with multiplexed nodes.
Instead of disabling pclasses altogheter, which has serious
performance implications, we can instead be smart about which pnodes
remain equivalent (because nothing's been mapped to them), and which
are now different. The result is that on my test topoloy, the time to
get a good mapping has gone from over 3 minutes to about 6 seconds.

This feature is enabled with the -d option, and the -P option is
pretty much mandatory when using it, since it greatly exacerbates the
problem of cruft in the ptop file.

This satisfies #14 from the todo file:
14.  do dynamic pclasses

Also bumped up the minimum neighborhood size from 500 to 1000. In some
tests I was doing, this resulted in better solutions.

turns out that getting iterators to the STL hash_* data structures is
really slow, so for some that won't be very big, use the non-hash
version.

Buys something like a 30% speedup for large topologies.

LAN nodes are no longer treated specially. Instead, I've introduced
the idea of 'static' types (old-style types retroactively become
'dynamic' types). While a pnode can only satisfy one dynamic type at a
time, it can always satisfy its static types (assuming it has enough
capacity left.) Static types are flagged by prepending them with a '*'
in the ptop file. So, for example, you may give switches the
'*lan:10000' type so that they can satisfy virtual LAN nodes. Of
course, other pnodes can have this type too, so that we can get
'trivial LANs'.

Actually, removing special treatment for LANs cleans up a lot of code.
However, it may have some negative impacts on solutions, since we're
not as smart about where to place LAN nodes as we used to be (they get
annealed along with everything else, and not migrated.) I haven't seen
any evidence of this yet, however.

This leaves us with a single type of special pnode, a switch.

Also added a new bit of syntax in ptop files - when '*' is given as a
the maxiumum load for a type, the node is allowed to take on an
infinite (well, actually, just a really big number of) vnodes of that
type.

ptopgen was modified to always report switches as being capable of
hosting LANs, and assign_wrapper now understands direct links to LANs,
which is what we get when the LAN is hosted directly on a switch.

Fixed a bug in scoring direct links, in which the penatly was being
added once when a direct link was mapped, but subtracted only once
when it was freed.

Added a '-T' option for doing simple self-testing. When adding a node
to the solution, assign records the score, adds the node, removes it
again, and checks to make sure that the resulting score is the same as
the original score. The usefulness of this feature in debugging
scoring problems cannot be understated...

some independant functionality off into new files, and reduce its
use of globals, which can be very confusing to follow.

I didn't get as far as I had hoped, but it's a good start.

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.

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.

when a new LAN is created, we make a new plink. Since assign is only
halfway OO, there is no constuctor for a plink to set the fixends
flag to something sensible.

Turned back on FIX_PLINK_ENDPOINTS, and 'touch' score.cc so that it
gets rebuilt.

First, don't select a plink for an emulated link that would cause us
to go over bandwidth.

Second, make FIX_PLINK_ENDPOINTS the default, and add a #define that
makes it the default (instead of having to specify it on each plink
line.)

go on the end of a link line in the top file, trivial_ok . This means
that it's okay to map the virtual link to a trivial link. By default,
it will not be permissible to use trivial links.

Right now, however, trivial links are OK by default, but that will
change once assign_wrapper flags all simulated links as trivial_ok .

endpoints in the same order they went in.

using the new assign, and captures Leigh's linkdelays work.

time to debug a delayed LAN problem.

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

links.

This fix is more complicated that the original changes that caused the
problem :|

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.

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.

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.

Added a basic README

Added two tests for features/desires.