Scotch Brand 5.1.10 - Manual (Page 31)

Program amk hy outputs the target architecture file of a hypercube graph
of dimension dim. Vertices are labeled according to the decimal value of
their binary representation. The decomposition-defined target architectures
computed by amk hy do not exactly give the same results as the built-in
hypercube targets because distances are not computed in the same manner,
although the two recursive bipartitionings are identical.
To achieve best
performance and save space, use the built-in architecture.
Program amk p2 outputs the target architecture file of a weighted path graph
with two vertices, the weights of which are given as parameters.
This simple target topology is used to bipartition a source graph into two
weighted parts with as few cut edges as possible. In particular, it is used
to compute independent partitions of the processors of a multi-user parallel
machine. As a matter of fact, if the yet unallocated part of the machine is
represented by a source graph with n vertices, and n
′ processors are requested
by a user in order to run a job (with n ′ ≤ n), mapping the source graph onto
the weighted path graph with two vertices of weights n ′ and n − n ′ leads to
a partition of the machine in which the allocated n ′ processors should be as
densely connected as possible (see Figure 13).
a. Construction of a partition with 13
vertices (in black) on a 8 × 8 bidimen-
sional mesh architecture. b. Construction of a partition with
17 vertices (in black) on the remaining
architecture.
Figure 13: Construction of partitions on a bidimensional 8 × 8 mesh architecture
by weighted bipartitioning.
Options
-h Display the program synopsis.
-mmethod
Select the bipartitioning method (for amk m2 only).
n Nested dissection.
o Dimension-per-dimension one-way dissection. This is less efficient
than nested dissection, and this feature exists only for benchmarking
purposes.
-V Print the program version and copyright.
31