GitLab

to accept new solutions, so that we don't give violtions any special
treatment.

This can greatly reduce 'thrasing' at low scores, allowing assign to
converge on a solution much faster. For example, in the 1000-node
topology used for the virtualization paper, assign's runtime dropped
from nearly two hours to just over half an hour, with no degredation
in scores found.

You can get the old accept behavior by enabling the
SPECIAL_VIOLATION_TREATMENT #define, which is on right now (hence, we
are not using this change yet.)

Here are the pertinent comments from the code:

#ifdef SPECIAL_VIOLATION_TREATMENT
         /*
          * In this ifdef, we always accept new solutions that have fewer
          * violations than the old solution, and when we're trying to
          * determine whether or not to accept a new solution with a higher
          * score, we don't take violations into the account.
          *
          * The problem with this shows up at low temperatures. What can often
          * happen is that we accept a solution with worse violations but a
          * better (or similar) score. Then, if we were to try, say the first
          * solution (or a score-equivalent one) again, we'd accept it again.
          *
          * What this leads to is 'thrashing', where we have a whole lot of
          * variation of scores over time, but are not making any real
          * progress. This prevents the cooling schedule from converging for
          * much, much longer than it should really take.
          */
#else // no SPECIAL_VIOLATION_TREATMENT
         /*
          * In this branch of the ifdef, we give violations no special
          * treatment when it comes to accepting new solution - we just add
          * them into the score. This makes assign behave in a more 'classic'
          * simulated annealing manner.
          *
          * One consequence, though, is that we have to be more careful with
          * scores. We do not want to be able to get into a situation where
          * adding a violation results in a _lower_ score than a solution with
          * fewer violations.
          */

local features/desires - turns out, we are using them in a manner
similar to types, so can save ourselves from looking at a lot of
bad solutions by being careful about going too far over on local
features.

more than one vnode; not much point if a one-to-one mapping is all we
can do.

combined with non-multiplexed nodes.

Also clear up the sense of the 'is_fixed' parameter to add_node() -
it was being handled correctly, but was confusing because it was non-
intuitive.

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().

again.

One of the fixes changes the way in which we iterate through pclasses
in find_pnode(). We used to treat the vector like a ring buffer, and
start (randomly) someplace in the middle. This turns out to give some
bad statistical properties when doing dynamic pclasses, since long
chains of disabled pclasses will cause some pclasses to be selected
more often. My old hack of just hopping around randomly in the
disabled-pclass case was bad, because it's hard to tell when you've
actually tried all the pclasses - so, we were getting false negatives
where it was looking like there was no place available where we could
map a vnode, which turned out to have worse effects than I had
thought.

So, now, we make a list of all the indices and randomize the order,
then just iterate through that list.

We also now count the number of pclasses that are enabled at every
temperature step, and adjust the neighborhood size to remove them.
This makes dynamic pclasses quite a bit faster - it cuts the time
by 30% - 50% for my test case.

Cleaned up find_pnode() by removing some #ifdef's that we don't use,
and probably will never want to again - this makes the function almost
readable!

In the top file, you can provide a 'node-hint', which is similar to a
'fix-node' in that it specifies a starting mapping for the virtual
node. Unlike a fixed node, however, assign is allowed to move hinted
nodes around all it wants.

Add a '-t' option to assign that allows you to give a starting
temperature, instead of going through the usual melting process.

Together, these may be helpful with the pre-pass we're planning on
incorporating into assign. During that pass, assign will be working
on a coarsened version of the virtual graph, so there may be some
places where decisions are made poorly due to the reduced information.
After one run has been done with the coarsened version, we can run
assign again with the full version of the graph, but with 'node-hints'
that start virtual nodes where the first run decided. This will allow
assign to fine-tune the results of the first mapping.

Of course, we don't want this second run to take too long, so we'll
want to start it with a low initial temperature (so that it basically
just does hill-climbing), and probably use a fractional '-H' argument
to prevent it from spending too long on large topologies.

'slot'. In the top file, you can how give' the virtual node's type as
type:count - sim:5, for example. If you give no count, it defaults to
one.

The idea here is to allow a pre-pass to assign to 'coarsen' the
virtual graph. This pre-pass could, for example, combine several
virtual or simulated nodes into one so that assign has a simpler
virtual graph to work with.

Fix a bug with limited trivial link bandwidth. It used to be the case
that we penalized solutions that over-used the trivial bandwidth based
on the number of links that were over it. Turns out this was a
problem, if you had links of differing bandwidths, and were near the
limit. Certain orderings were possible where you would remove two
trivial links in a different order than you added them, which might
result in more (or fewer) violations being scored then when you did
them originally. The fix for this is to penalize these based on
bandwidth, which is what assign now does.

Added a '-g' flag, which does greedy link selection - assign normally
does random link selection until the very end, when it does one pass
with greedy selection. This flag makes it do this all the time. This
is useful for debugging, because it cuts out a call to random(). Turns
out, it doesn't seem to make assign much slower. I might consider
making it the default.

Better output when the selftest (-T) fails.

they mean.

everything else goes to stdout. This will hopefully make things a bit
simpler by avoiding funny buffering issues for programs like
assign_wrapper that want to redirect assign's stdout.

when mapping fixed nodes.

sure they're within some tolerance of each other. Use this so that
cumulative float point errors don't cause us to spit out scary
looking false positive warnings.

circumstances with vnodes, but I managed to run into it.

top and ptop files, you can put
subnode_of:nodename
Any vnode that is a subnode must be mapped to a pnode that is a a
subnode of the pnode the vnode's parent is mapped to. Read that a few
times slowly, I swear it makes sense.

really working this time.

I will not check things in without running the testsuite
I will not check things in without running the testsuite
I will not check things in without running the testsuite
I will not check things in without running the testsuite
I will not check things in without running the testsuite
I will not check things in without running the testsuite
I will not check things in without running the testsuite
I will not check things in without running the testsuite
I will not check things in without running the testsuite
I will not check things in without running the testsuite

Split the function that determines if a vnode can be mapped to a given pnode
out of find_pnode, so that I can spread it out and make it more comprehensible.
In doing so, fixed a bug in which static types were not getting handled
correctly - a static type would only be found if no vnodes with dynamic types
were allocated to the pnode.

Fixed a bug in which, on allocation of a dynamic ptype, nodes where being
removed from their static type lists in the type_table.

Fixed a bug when there is a combination of fixed and un-fixed vnodes in the top
file.

I have more on the way, but this seemed like a good checkpoint.

nodes that there were in the top file.

was sooo wrong you wonder how it worked in the first place... Took
me days to find this one!

Also added a new switch, '-o', that lets assign try out solutions
that over-load a pnode. This helps a lot with topologies where the
optimal solution is a best-fit onto multiplexed pnodes.

The end result is that Mike's snake maps much better - it used to get
an essentially random mapping, but now it gets something acceptible.

a floating point number that, roughly, scales the runtime.

since we don't un-assign them when reverting to the best solution.

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.

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.