notes on oview_layout

algorithms

the basic strategy is:
while (unbound routers)

ie, oview_layout currently makes two kinds of decisions both of these stages need some work.

the choice of the next router to place (top_router) may need a little tweaking, but the main problem lies in the area of placement.

large number of routers

oview_layout doesn't cope well with large numbers of routers. there seem to be two interrelated factors here:

most connected router

the most-connected router is currently chosen on the basis of

best point

old vert

OLD_VERT has a fixed set of verticies, and tries seeding the algorithm with the top_router() bound to each vertex in turn. the least-cost solution is then used. OLD_VERT maintains information about its fixed set of verticies and their relationships with each other, which is used in deciding which vertex to bind to next (top_vertex()).

OLD_VERT is ok for small numbers of routers, but:

new vert

the NEW_VERT algorithm (new_vertex()) creates a vertex whenever it is needed. it looks at all verticies 1-distant from those already used, evaluates the cost of placing the top_router there (eval_pos()), and chooses the cheapest. a free vertex 1-distant from more than one router will be evaluated more than once (BUG).

NEW_VERT is ok for small numbers of routers, but:

backtrack

there are points in NEW_VERT at which one of a number of equal-cost solutions is chosen essentially at random. this may happen in top_router() and in new_vertex(). in top_router(), the equal-cost choices are essentially equal-cost, however in new_vertex(), equal-cost placements will have different cost ramifications for subsequent placements -- our cost function isn't good enough.

the BACKTRACK algorithm (descend() / choose_vertex()) is based on NEW_VERT, but branches at each vertex placement where there is more than one equal-cost solution. it backs out as soon as the cost is greater than the best-cost so far. the assumption here (valid?) is that a better-cost choice at any stage will lead to a better-cost solution. if this ain't true, we have to exhaustively search the solution space. it does badly enough already: it is O(x^N), where N is (about) the number of routers, and speed rapidly declines after about N==10.

BACKTRACK ignores the CLING_COC hint.

BACKTRACK is ok for small numbers of routers, but:

cost function

different cost functions (penalise()) can be chosen for NEW_VERT/BACKTRACK using the -V option, making the addition of different kinds of links more or less costly.

OLD_VERT uses the config_cost() function, a sum of squares of distances (ie we don't sqrt() things).

secondary cost

a secondary cost function (CLING_COC) invoked in eval_pos() for NEW_VERT makes the penalty slightly greater for verticies further away from the "centre of connectedness" -- the average position of all the bound routers that the unbound routers the router is connected to are connected to. this seems to improve choices, but it is unclear whether it is a uniformly benificial heuristic. for want of something better, we use it.

suggested approach

the current approach works well for small numbers of routers. the suggested approach is to alternate between the placement of routers, and the placement of meta-routers, and to proceed on a subset-by-subset basis. the routers are broken up into local 'networks' interconnected by meta-routers. each collection of routers or metarouters tends to be a cube.

this algorithm essentially partitions our placement problem, making it tractable. the issue of missing/inactive (meta/normal) routers may complicate things, but shouldn't detract from the basic approach.

representation

desirable layout / representation

moderately large

we consider here the 6-metarouter case (with say 128 cpus) (try oview -c 128ortho2.topology, and oview -c 192ortho2.topology). the 128 cpu topology seems to be the limit of the current approach -- the 192 cpu layout works spatially (we can do it), but is simply appallingly cluttered.

given the need for many extended links which will lead to increased clutter, some minor representational changes should be made, even if this is only to turn the link tubes into lines... this will also improve rendering speed. the intersection of these extended links should still be avoided, although the 192 cpu layout may force us to use some.

we are assuming that the basic heuristic currently being used for layout is still valid for configurations of this size... ie we assume that the most closely packed layout is the best one.

truly large

for truly large numbers of routers (in systems with >6 metarouters), a different representation and layout is almost certainly needed, possibly allowing drill-down to the current model

some possibilities