To efficiently parallelize such adaptive irregular problems on distributed memory parallel computers, ... effective methods for domain partitioning ... must be addressed.
A simple one-dimensional domain partitioning method is implemented and compared with unstructured mesh partitioners such as recursive coordinate bisection and recursive inertial bisection.
(Click here to view the animation)
There have been several theoretical and experimental discussions of partitioning strategies based on spatial information for many years. Recursive coordinate bisection (RCB) is a well-known algorithm which bisects a problem domain into two pieces of equal work load recursively until the number of subdomains is equal to the number of processors.
(Click here
to view the animation)
Recursive inertial bisection (RIB) is similar to RCB in that it bisects a problem domain recursively based on spatial information, but RIB uses minimum moment of inertia when it selects bisectioning directions, whereas RCB selects bisectioning directions from x-, y-, or z-dimensions. In other words, RIB bisects a 3-dimensional domain with a plane at any angle with respect to the coordinate axes, whereas RCB does so only with a plane perpendicular to one of the x, y and z coordinate axes. Clearly the number of processors has to be a power of 2 to apply these algorithms on parallel computers.
(Click here to view the animation)
Chain partitioners decompose a chain-structured problem domain whose task graph is a chain of work units into a set of pieces which satisfies contiguity constraints -- each processor has a contiguous subdomain of work units assigned to it. That is, a problem domain has to be partitioned in such a way that work units i and i+1 are assigned to the same or to adjacent processors. Relatively simple algorithms for finding the optimal partition of a chain-structured problem have been suggested. While these algorithms are developed to optimize computation and communication costs at the same time, we have developed and used a new chain partitioning algorithm which considers computation cost only. This algorithm requires only one step of global communication and a few steps of local computation.
This goes back to the CHAOS home page
Questions about the system or webserver:
webmaster@cs.umd.edu
Problems with homepage:
wes@cs.umd.edu