Binary Dissection: Variants & Applications
Abstract
Partitioning is an important issue in a variety of applications. Two examples are domain decomposition for parallel computing and color image quantization. In the former we need to partition a computational task over many processors; in the latter we need to partition a high resolution color space into a small number of representative colors. In both cases, partitioning must be done in a manner that yields good results as defined by an application specific metric. Binary dissection is a technique that has been widely used to partition non-uniform domains over parallel computers. It proceeds by recursively partitioning the given domain into two parts, such that each part has approximately equal computational load. The basic dissection algorithm does not consider the perimeter, surface area or aspect ratio of the two sub-regions generated at each step and can thus yield decompositions that have poor communication to computation ratios. We have developed and implemented several variants of the binary dissection approach that attempt to remedy this limitation, are faster than the basic algorithm, can be applied to a variety of problems, and are amenable to parallelization. The Parametric Binary Dissection (PBD) algorithm tries to minimize the difference between volume + lambda x (surface) for each of the two sub-regions it generates at each step. When applied to parallel computing, volume represents the amount of computation required while surface is proportional to interprocessor communication. The parameter lambda permits us to trade off load imbalance against communication overhead. When lambda is zero, the algorithm reduces to simple binary dissection. The Fast Adaptive Dissection (FAD) algorithm is used for color image quantization, where samples in a high resolution color space are mapped into a lower resolution space in a way that minimizes color error.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1997
- Accession Number
- ADA329502
Entities
People
- David M. Nicol
- Shahid H. Bokhari
- Thomas W. Crockett