Parametric Binary Dissection

Abstract: "Binary dissection is widely used to partition non- uniform domains over parallel computers. This algorithm does not consider the perimeter, surface area, or aspect ratio of the regions being generated and can yield decompositions that have poor communication to computation ratio. Parametric Binary Dissection (PBD) is a new algorithm in which each cut is chosen to minimize load + [lambda]X(shape). In a 2 (or 3) dimensional problem, load is the amount of computation to be performed in a subregion and shape could refer to the perimeter (respectively surface) of that subregion. Shape is a measure of communication overhead and the parameter [lambda] permits us to trade off load imbalance against communication overhead. When [lambda] is zero, the algorithm reduces to plain binary dissection. This algorithm can be used to partition graphs embedded in 2 or 3-d. Here load is the number of nodes in a subregion, shape the number of edges that leave that subregion, and [lambda] the ratio of time to communicate over an edge to the time to compute at a node. We present an algorithm that finds the depth d parametric dissection of an embedded graph with n vertices and e edges in O(max[n log n, de]) time, which is an improvement over the O(dn log n) time of plain binary dissection. We also present parallel versions of this algorithm; the best of these requires O((n/p) log3 p) time on a p processor hypercube, assuming graphs of bounded degree. We describe how PBD is applied to 3-d unstructured meshes and yields partitions that are better than those obtained by plain dissection. We also discuss its application to the color image quantization problem, in which samples in high-resolution color space are mapped onto a lower resolution space in a way that minimizes the color error."