Octant Approach
An application-centric characterization of partitioners
is obtained by first classifying the SAMR application state and identifying
the partitioning requirements of each application state. Then the partitioner(s)
is/are assigned to the application states based on the experimental evaluation.
The octant approach is used to classify the state
of the SAMR application. The octant approach is an extension to the quadrant
approach. According to the octant approach, application state is classified
with respect to
(a) the adaptation pattern (scattered or localized),
(b) whether run-time is dominated by computations
or communications,
(c) the activity dynamics in the solution, e.g.
adaptation pattern changes rapidly.
Applications may start off in one octant, then,
as solution progresses, migrate to any other.
In the "far part" of the cube, solutions have high
activity dynamics. This gives rise to increased need for data movement.
Furthermore, partitioning efficiency is crucial as there is a need for
frequent repartitioning. Techniques like pBD-ISP and even G-MISP+SP meet
these requirements. In the "close part" of the cube, there is more time
for computing the partitioning. Thus, schemes like G-MISP+SP are strong
candidates here. In the "upper part" of the cube, communication dominates
run-time. As a result, partitioners such as pBD-ISP that optimize this
metric are best suited. On the other hand, in the "lower part", computation
dominates, which suggests that schemes that optimize load balance (such
as G-MISP+SP or SP) are preferable. In the "right part" of the cube, adaptation
is scattered over the computational domain. This typically means more overhead.
Both ISP and pBD-ISP optimizes this metric well. Finally, in the "left
part" of the cube, adaptation is strongly localized and results in lesser
data movement and overheads. Moreover, load balance is harder to achieve,
indicating that techniques like G-MISP+SP, SP, or pBD-ISP are suitable.
The association of partitioning techniques to application state octants
using the experimental evaluation are summarized in the following table.
Mapping of partitioning techniques to application
state octants
Clearly, the two most successful schemes are pBD-ISP
and G-MISP+SP. Since G-MISP (variant of G-MISP+SP) is very much similar in
modus-operandi to SFC scheme from GrACE toolkit, partitioning schemes pBD-ISP,
G-MISP+SP, and SFC are the preferred partitioners, depending on the application
state.