Scotch Brand 5.1.10 - Manual (Page 10)

calls a graph bipartitioning algorithm to split the subset of processes associated with
the domain across the two subdomains, as sketched in the following.
mapping (D, P)
Set_Of_Processors
D;
Set_Of_Processes P;
{
Set_Of_Processors D0, D1;
Set_Of_Processes P0, P1;
if (|P| == 0) return; /* If nothing to do. */
if (|D| == 1) { /* If one processor in D */
result (D, P); /* P is mapped onto it. */
return;
}
(D0, D1) = processor_bipartition (D);
(P0, P1) = process_bipartition
(P, D0, D1);
mapping (D0, P0); /* Perform recursion. */
mapping (D1, P1);
}
The association of a subdomain with every process defines a partial mapping of the
process graph. As bipartitionings are performed, the subdomain sizes decrease, up
to give a complete mapping when all subdomains are of size one.
The above algorithm lies on the ability to define five main objects:
• a domain structure, which represents a set of processors in the target archi-
tecture;
• a domain bipartitioning function, which, given a domain, bipartitions it in two
disjoint subdomains;
• a domain distance function, which gives, in the target graph, a measure of the
distance between two disjoint domains. Since domains may not be convex nor
connected, this distance may be estimated. However, it must respect certain
homogeneity properties, such as giving more accurate results as domain sizes
decrease. The domain distance function is used by the graph bipartitioning
algorithms to compute the communication function to minimize, since it allows
the mapper to estimate the dilation of the edges that link vertices which belong
to different domains. Using such a distance function amounts to considering
that all routings will use shortest paths on the target architecture, which
is how most parallel machines actually do. We have thus chosen that our
program would not provide routings for the communication channels, leaving
their handling to the communication system of the target machine;
• a process subgraph structure, which represents the subgraph induced by a
subset of the vertex set of the original source graph;
• a process subgraph bipartitioning function, which bipartitions subgraphs in
two disjoint pieces to be mapped onto the two subdomains computed by the
domain bipartitioning function.
All these routines are seen as black boxes by the mapping program, which can thus
accept any kind of target architecture and process bipartitioning functions.
10