We discuss Inverse Spacefilling Partitioning (ISP), a partitioning strategy for non-uniform scientific computations running on distributed memory MIMD parallel computers. We consider the case of a dynamic workload distributed on a uniform mesh, and compare ISP against Orthogonal Recursive Bisection (ORB) and a Median of Medians variant of ORB, ORB-MM. We present two results. First, ISP and ORB-MM are superior to ORB in rendering balanced workloads---because they are more fine-grained---and incur communication overheads that are comparable to ORB. Second, ISP is more attractive than ORB-MM from a software engineering standpoint because it avoids elaborate bookkeeping. Whereas ISP partitionings can be described succinctly as logically contiguous segments of the line, ORB-MM's partitionings are inherently unstructured. We describe the general d-dimensional ISP algorithm and report empirical results with two- and three-dimensional, non-hierarchical particle methods.
Balanced partitioning of non-uniform data in a high dimensional space is much more difficult than partitioning the non-uniform data projected onto a line. For dynamic problems which require many such partitions, this partitioning time difference may be critical. For this reason, Recursive Coordinate Bisection (RCB) has grown in popularity since it repeatedly collapses d-1 dimensions onto 1 dimension. As an alternative method, we introduce the Inverse Spacefilling Partition (ISP) which maps the higher dimensional space to a line in more fine-g rained units. ISP is faster than RCB, and yields a more even load balance at the cost of slightly higher communication and irregularly partitioned regions. The general d-dimensional ISP algorithm is described, then analytical and empirical comparisons are made between ISP and RCB.
This document describes blobs, an interactive visualization program
for certain classes of particle methods running on distributed memory MIMD
multiprocessors. The blobs tool allows programmers to interactively
visualize various parallelization tradeoffs. This paper describes the
particle calculations and partitioning strategies modeled by
blobs,
the blobs display window and user interface,
and the blobs source distribution package.
VIPP is a trace-driven interactive performance visualization tool for exploring complex tradeoffs in load balancing various particle methods running on distributed memory MIMD multiprocessors. VIPP enables the user to experiment with diverse partitioning strategies, to vary partitioning frequency, granularity, numbers of processors, and to make varying assumptions about communication hardware performance. VIPP estimates and displays domain partitioning, workload balance, interprocessor communication, running time, and parallel efficiency. Since VIPP is trace-driven, it require neither a parallelized program nor even running hardware. It offers a solution which enables programmers to analyze the implementation of scientific applications, educates students about various trade-offs in implementing parallel applications, and allows the testing of new partitioning techniques. With on-line performance tools or low-level simulation, a programmer would need to modify code, recompile, and rerun to compare alternative implementations. By comparison, VIPP accomplishes this goal through a simulation of the calculation.
We evaluate three approaches to partitioning particle calculations on MIMD multiprocessor architectures: recursive bisection, interleaved or scattered decomposition, and processor self-scheduling. We explore the tradeoffs between load sharing capability and overhead costs and discuss computational results from a two-dimensional vortex dynamics calculation running on various commercial multiprocessor architectures.
*Not available on line, contact Scott Baden at baden@cs.ucsd.edu
Maintained by Scott B. Baden. Last modified: October 28, 2000 13:56:18 Disclaimer