Cache net bounding boxes to improve performance for high-fan-out nets

[mossblaser]

Builds on #4 and should be merged afterwards.

Rather than recomputing the bounding box of every impacted net twice on every swap in order to compute the cost of the net, store the bounding box and only recompute it when it changes. For simplicity this implementation is rather conservative and actually regenerates the bounding box more often than strictly necessary.

For low-fan-out nets this has little performance impact. For nets with really silly fan-outs, I've seen algorithm execution times 2-4x quicker.

A work-in-progress experiment for my thesis takes 16,384 vertices in a 128x128 2D grid interconnected by nets with a simple 2D gaussian connectivity pattern. The pink/purple line in the plot below shows the runtime of the SA algorithm as the fan-out of the nets is ramped up (NB: log-log plot). The black dots show the runtime of the old version on the same graph. Note that I got bored once the runtime reached an hour or so...

The plot below shows how the 'quality' of the placement decreases with fan out. Quality here is measured as the routing congestion as a proportion of the congestion produced by a manual placement. 1.0 means as-good-as-manual, higher values are better!

[mundya]

LGTM!

[mossblaser]

Whoops... The torus bites again!

This bounding box caching technique is actually broken!

For example, consider the following bounding box around four points in a torus:

Lets say we move the third vertex a little to the right. The new bounding box should now look like this:

In this instance, the bounding box must be recomputed (since it will now wrap-around) however the test which decides whether to update the bounding box will not trigger this because the vertex that moved stayed within the old bounding box and wasn't originally on the edge of the bounding box.

Sadly I can't see a straight-forward way to fix this problem so I think for now I'm going to close the PR and keep the branch for future consideration...