Shen uses elementary heuristic techniques to perform a mapping from an arbitrary logical task graph (showing all required intermodule communications) to an arbitrary torus.

An initial phase groups tasks to match the target number of processors, groups tasks with neighbors where their degree is greater than that of the target network, and balances computation and communication requirements across task groups. A placement module then maps these logical processes to processors so as to minimize the total length of physical paths between neighbors.

The heuristics used involve the assignment of weights to paths so as to reflect the number of bends (changes of dimension), and preassign of an order in which to realize routings (but what basis is used is not revealed). The routing algorithm finds the first route, takes it away, updates the heuristics, and repeats.

The self-adjusting aspect of the mapping is essentially backtracking: to other reasonable placements; or failing that to alternate groupings. This is shown to have an order quadratic in the size of the input task graph, but involving the fifth power of the size of the target processor graph (whereas the previous phases are at worst quadratic in the target size).

In summary, the paper provides an adequate, but not particularly exciting solution, and many details are omitted. An unfortunate irritation is that in a paper on “routing,” this word is consistently misspelled throughout the paper, and indeed there are other errors of English usage that should have been picked up by the editors.