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 A 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 the 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 (maxn 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)log3p) 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.