(3M) Calculator User Manual

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 a ssociation of a subdomain with every process defines a partial mapping of the
process gr aph. As bipartitionings are performed, the subdomain sizes decrease, up
to give a complete mapping when all subdomains are of size one.
The above algor ithm 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 co mmunication function to minimize, since it allows
the mapper to estimate the dilation of the edges that link vertices which belong
to differe nt 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 chos e n 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 stru cture, which re presents 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 proc e ss bipartitioning functions.
10