×

Two-constraint domain decomposition with space filling curves. (English) Zbl 1216.68317

Summary: In scientific computing, space filling curves are a widely used tool for one-constraint domain decomposition. They provide a mechanism to sort multi-dimensional data in a locality preserving way, and, in this way, a (one dimensional) list of mesh elements is established which is subsequently split into 3 partitions under consideration of the constraint. This procedure has a runtime of \(O(N\log N) (N\) is the number of mesh elements) while nearly perfect load balancing can be established with reasonable partition surface sizes.
In this work, we discuss the extensibility of this procedure to two-constraint settings which is desirable, since the methodology is extremely fast. Here, the splitting operation is subject to two constraints, and, unlike to the one-constraint case, obtaining near perfect balancing is often hard to establish, and is, even more as in the one-constraint case, in conflict with the induced surface sizes (or edge-cuts). We discuss multiple strategies to tackle the splitting, and we present a fast, \(O(N\log N)\) splitting heuristic algorithm which provides an integer \(\sigma \) that allows to trade off between balancing and surface sizes which results in a \(O(N\log N)\) two-constraint decomposition method. Results are compared to the multi-constraint domain decomposition abilities implemented in the Metis software package, and show that the method produces higher surface sizes, but is orders of magnitudes faster which makes the method superior for certain applications.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68P10 Searching and sorting
90C59 Approximation methods and heuristics in mathematical programming

Software:

METIS; SFCGen
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bokhari, S. H.: Partitioning problems in parallel, pipeline, and distributed computing, IEEE trans. Comput. 37, No. 1, 48-57 (1988)
[2] Butz, A. R.: Alternative algorithm for Hilbert’s space-filling curve, IEEE trans. Comput. 20, No. 4, 424-426 (1971) · Zbl 0223.68018 · doi:10.1109/T-C.1971.223258
[3] Carmona, E. A.; Chandler, L. J.: On parallel PIC versatility and the structure of parallel PIC approaches, Concurr. pract. Exp. 9, No. 12, 1377-1405 (1997)
[4] , Lecture notes in computer science 1279 (1997)
[5] Gotsman, C.; Lindenbaum, M.: The metric properties of discrete space-filling curves, IEEE trans. Image process. 5, No. 5, 794-797 (1996)
[6] Griebel, Michael; Zumbusch, Gerhard: Parallel multigrid in an adaptive PDE solver based on hashing and space-filling curves, Parallel comput. 25, No. 7, 827-843 (1999) · Zbl 0945.65138 · doi:10.1016/S0167-8191(99)00020-4
[7] Hatzky, R.: Domain cloning for a particle-in-cell (pic) code on a cluster of symmetric-multiprocessor (smp) computers, Parallel comput. 32, No. 4, 325-330 (2006)
[8] Hendrickson, B.; Pothen, A.: Combinatorial scientific computing: the enabling power of discrete algorithms in computational science, Lecture notes in computer science 4395, 260-280 (2006) · Zbl 1177.65208 · doi:10.1007/978-3-540-71351-7_21
[9] R.W. Hockney, J.W. Eastwood, Computer Simulation Using Particles, 1981.
[10] Jin, G.; Mellor-Crummey, J.: Sfcgen: a framework for efficient generation of multi-dimensional space-filling curves by recursion, ACM trans. Math. softw. 31, No. 1, 120-148 (2005) · Zbl 1073.65017 · doi:10.1145/1055531.1055537
[11] N. Karmarkar, R.M. Karp, The differencing method of set partitioning, Technical Report UCB/CSD-83-113, University of California, Berkeley 1983.
[12] Karp, R. M.: Reducibility among combinatorial problems, Complexity of computer computations, 85-103 (1972) · Zbl 0366.68041
[13] G. Karypis, V. Kumar, Multilevel algorithms for multi-constraint graph partitioning, Technical report, University of Minnesota, Department of Computer Science, 1998. <http://glaros.dtc.umn.edu/gkhome/node/90>.
[14] Sanjeev Khanna, S. Muthukrishnan, Steven Skiena, Efficient array partitioning, in: ICALP’97: Proceedings of the 24th International Colloquium on Automata, Languages and Programming, London, UK, Springer-Verlag, 1997, pp. 616 – 626. · Zbl 1401.68354
[15] J. Lawder, Calculation of mappings between one and n-dimensional values using the Hilbert space-filling curve, Technical Report jl1/00, 2000.
[16] Lanteri, S.; Bernacki, M.; Fezoui, L.; Piperno, S.: Parallel discontinuous Galerkin unstructured mesh solvers for the calculation of three-dimensional wave propagation problems, Appl. math. Model. 30, 744-763 (2006) · Zbl 1101.78009 · doi:10.1016/j.apm.2005.06.015
[17] Mcmanus, K.; Cross, M.; Walshaw, C.; Johnson, Steve; Leggett, P. F.: A scalable strategy for the parallelization of multiphysics unstructured mesh-iterative codes on distributed-memory systems, Int. J. High perform. Comput. appl. 14, 137-174 (2000)
[18] Hiroshi Nakashima, Yohei Miyake, Hideyuki Usui, Yoshiharu Omura, Ohhelp: a scalable domain-decomposing dynamic load balancing for particle-in-cell simulations, in: ICS, 2009, pp. 90 – 99.
[19] Pinar, Ali; Aykanat, Cevdet: Fast optimal load balancing algorithms for 1d partitioning, J. parallel distrib. Comput. 64, No. 8, 974-996 (2004) · Zbl 1068.68038 · doi:10.1016/j.jpdc.2004.05.003
[20] Chaco Project. <http://www.sandia.gov/bahendr/chaco.html>.
[21] Jostle Project. <http://staffweb.cms.gre.ac.uk/wc06/jostle>.
[22] Metis Project. <http://glaros.dtc.umn.edu/gkhome/views/metis>.
[23] Scotch Project. <http://www.labri.fr/perso/pelegrin/scotch>.
[24] S. Schamberger, J.-M. Wierum, Graph partitioning in scientific simulations: multilevel schemes versus space-filling curves, in: PaCT, 2003, pp. 165 – 179.
[25] Vay, J. L.; Colella, P.; Kwan, J. W.; Mccorquodale, P.; Serafini, D. B.; Friedman, A.; Grote, D. P.; Westenskow, G.; Adam, J. C.; Héron, A.; Haber, I.: Application of adaptive mesh refinement to particle-in-cell simulations of plasmas and beams, Aip 11, 2928-2934 (2004)
[26] Walshaw, C.; Cross, M.; Mcmanus, K.: Multiphase mesh partitioning, Appl. math. Model. 25, No. 2, 123-140 (2000) · Zbl 1076.65538 · doi:10.1016/S0307-904X(00)00041-X
[27] Wu, J. -S.; Tseng, K. -C.: Parallel DSMC method using dynamic domain decomposition, Int. J. Numer. methods eng., 37-76 (2005) · Zbl 1140.76436 · doi:10.1002/nme.1232
[28] Walshaw, C.; Cross, M.; Mcmanus, K.: Multiphase mesh partitioning, Appl. math. Model. 25, No. 2, 123-140 (2000) · Zbl 1076.65538 · doi:10.1016/S0307-904X(00)00041-X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.