Summary
In parallel simulations, partitioning and load-balancing algorithms compute the distribution of application data and work to processors. The effectiveness of this distribution greatly influences the performance of a parallel simulation. Decompositions that balance processor loads while keeping the application’s communication costs low are preferred. Although a wide variety of partitioning and load-balancing algorithms have been developed, their effectiveness depends on the characteristics of the application using them. In this chapter, we review several partitioning algorithms, along with their strengths and weaknesses for various PDE applications. We also discuss current efforts toward improving partitioning algorithms for future applications and architectures.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
S. Adjerid, J. E. Flaherty, P. Moore, and Y. Wang. High-order adaptive methods for parabolic systems. Physica-D, 60:94–111, 1992.
S. Aluru and F. Sevilgen. Parallel domain decomposition and load balancing using space-filling curves. In Proc. International Conference on High-Performance Computing, pages 230–235, 1997.
R. E. Bank and M. J. Holst. A new paradigm for parallel adaptive meshing algorithms. SIAM J. Scien. Comput., 22:1411–1443, 2000.
K. J. Barker and N. P. Chrisochoides. An evaluation of a framework for the dynamic load balancing of highly adaptive and irregular parallel applications. In Proc. Supercomputing 2003, Phoenix, 2003.
S. T. Barnard. PMRSB: parallel multilevel recursive spectral bisection. In F. Baker and J. Wehmer, editors, Proc. Supercomputing’ 95, San Diego, December 1995.
S. T. Barnard and H. D. Simon. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and Experience, 6(2):101–117, 1994.
J. J. Bartholdi and L. K. Platzman. An O(n log n) travelling salesman heuristic based on spacefilling curves. Operation Research Letters, 1(4):121–125, September 1982.
A. C. Bauer. Efficient Solution Procedures for Adaptive Finite Element Methods — Applications to Elliptic Problems. PhD thesis, State University of New York at Buffalo, 2002.
M. J. Berger and S. H. Bokhari. A partitioning strategy for nonuniform problems on multiprocessors. IEEE Trans. Computers, 36:570–580, 1987.
M. Berzins. A new metric for dynamic load balancing. Appl. Math. Modelling, 25:141–151, 2000.
T. Bially. Space-filling curves: their generation and their application to band reduction. IEEE Trans. Inform. Theory, IT-15:658–664, Nov. 1969.
E. Boman, K. Devine, R. Heaphy, B. Hendrickson, M. Heroux, and R. Preis. LDRD report: Parallel repartitioning for optimal solver performance. Technical Report SAND2004-0365, Sandia National Laboratories, Albuquerque, NM, February 2004.
E. Boman, K. Devine, R. Heaphy, B. Hendrickson, W. F. Mitchell, M. S. John, and C. Vaughan. Zoltan: Data-management services for parallel applications. URL: http://www.cs.sandia.gov/Zoltan.
C. L. Bottasso, J. E. Flaherty, C. Özturan, M. S. Shephard, B. K. Szymanski, J. D. Teresco, and L. H. Ziantz. The quality of partitions produced by an iterative load balancer. In B. K. Szymanski and B. Sinharoy, editors, Proc. Third Workshop on Languages, Compilers, and Runtime Systems, pages 265–277, Troy, 1996.
T. Bui and C. Jones. A heuristic for reducing fill in sparse matrix factorization”. In Proc. 6th SIAM Conf. Parallel Processing for Scientific Computing, pages 445–452. SIAM, 1993.
A. Caldwell, A. Kahng, and J. Markov. Design and implementation of move-based heuristics for VLSI partitioning. ACM J. Experimental Algs., 5, 2000.
P. M. Campbell, K. D. Devine, J. E. Flaherty, L. G. Gervasio, and J. D. Teresco. Dynamic octree load balancing using space-filling curves. Technical Report CS-03-01, Williams College Department of Computer Science, 2003.
F. Cao, J. R. Gilbert, and S.-H. Teng. Partitioning meshes with lines and planes. Technical Report CSL-96-01, Xerox PARC, 1996. ftp://parcftp.xerox.com/pub/gilbert/index.html.
U. Catalyurek and C. Aykanat. Decomposing irregularly sparse matrices for parallel matrix-vector multiplications. Lecture Notes in Computer Science, 1117:75–86, 1996.
U. Catalyurek and C. Aykanat. Hypergraph-partitioning based decomposition for parallel sparse-matrix vector multiplication. IEEE Trans. Parallel Dist. Systems, 10(7):673–693, 1999.
C. Chang, T. Kurc, A. Sussman, U. Catalyurek, and J. Saltz. A hypergraph-based workload partitioning strategy for parallel data aggregation. In Proc. of 11th SIAM Conf. Parallel Processing for Scientific Computing. SIAM, March 2001.
S. Chatterjee, A. R. Lebeck, P. K. Patnala, and M. Thottethodi. Recursive array layouts and fast parallel matrix multiplication. In ACM Symposium on Parallel Algorithms and Architectures, pages 222–231, 1999.
C.-K. Cheng and Y.-C. A. Wei. An improved two-way partitioning algorithm with stable performance. IEEE Trans. Computer Aided Design, 10(12):1502–1511, 1991.
G. Cybenko. Dynamic load balancing for distributed memory multiprocessors. J. Parallel Distrib. Comput., 7:279–301, 1989.
L. Dagum. Automatic partitioning of unstructured grids into connected components. In Proc. Supercomputing Conference 1993, pages 94–101, Los Alamitos, 1993. IEEE, Computer Society Press.
H. L. de Cougny, K. D. Devine, J. E. Flaherty, R. M. Loy, C. Özturan, and M. S. Shephard. Load balancing for the parallel adaptive solution of partial differential equations. Appl. Numer. Math., 16:157–182, 1994.
K. D. Devine, E. G. Boman, R. T. Heaphy, B. A. Hendrickson, J. D. Teresco, J. Faik, J. E. Flaherty, and L. G. Gervasio. New challenges in dynamic load balancing. Appl. Numer. Math., 52(2–3):133–152, 2005.
K. D. Devine and J. E. Flaherty. Parallel adaptive hp-refinement techniques for conservation laws. Appl. Numer. Math., 20:367–386, 1996.
K. D. Devine, B. A. Hendrickson, E. Boman, M. St. John, and C. Vaughan. Zoltan: A Dynamic Load Balancing Library for Parallel Applications; User’s Guide. Sandia National Laboratories, Albuquerque, NM, 1999. Tech. Report SAND99-1377. Opensource software distributed at http://www.cs.sandia.gov/Zoltan.
R. Diekmann, D. Meyer, and B. Monien. Parallel decomposition of unstructured femmeshes. In Proc. Parallel Algorithms for Irregularly Structured Problems, pages 199–216. Springer LNCS 980, 1995.
R. Diekmann, B. Monien, and R. Preis. Load balancing strategies for distributed memory machines. In B. Topping, editor, Parallel and Distributed Processing for Computational Mechanics: Systems and Tools, pages 124–157, Edinburgh, 1999. Saxe-Coburg.
R. Diekmann, R. Preis, F. Schlimbach, and C. Walshaw. Shape-optimized mesh partitioning and load balancing for parallel adaptive fem. Parallel Comput., 26(12):1555–1581, 2000.
H. C. Edwards. A Parallel Infrastructure for Scalable Adaptive Finite Element Methods and its Application to Least Squares C? Collocation. PhD thesis, The University of Texas at Austin, May 1997.
R. Enbody, R. Purdy, and C. Severance. Dynamic load balancing. In Proc. 7th SIAM Conference on Parallel Processing for Scientific Computing, pages 645–646. SIAM, February 1995.
J. Faik, L. G. Gervasio, J. E. Flaherty, J. Chang, J. D. Teresco, E. G. Boman, and K. D. Devine. A model for resource-aware load balancing on heterogeneous clusters. Technical Report CS-04-03, Williams College Department of Computer Science, 2004. Presented at Cluster’ 04.
C. Farhat. A simple and efficient automatic FEM domain decomposer. Computers and Structures, 28(5):579–602, 1988.
C. Farhat, S. Lanteri, and H. D. Simon. TOP/DOMDEC: a software tool for mesh partitioning and parallel processing. Comp. Sys. Engng., 6(1):13–26, 1995.
C. Farhat and M. Lesoinne. Automatic partitioning of unstructured meshes for the parallel solution of problems in computational mechanics. Int. J. Numer. Meth. Engng., 36:745–764, 1993.
C. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In Proc. 19th IEEE Design Automation Conference, pages 175–181. IEEE, 1982.
J. E. Flaherty, M. Dindar, R. M. Loy, M. S. Shephard, B. K. Szymanski, J. D. Teresco, and L. H. Ziantz. An adaptive and parallel framework for partial differential equations. In D. F. Griffiths, D. J. Higham, and G. A. Watson, editors, Numerical Analysis 1997 (Proc. 17th Dundee Biennial Conf.), number 380 in Pitman Research Notes in Mathematics Series, pages 74–90. Addison Wesley Longman, 1998.
J. E. Flaherty, R. M. Loy, C. Özturan, M. S. Shephard, B. K. Szymanski, J. D. Teresco, and L. H. Ziantz. Parallel structures and dynamic load balancing for adaptive finite element computation. Appl. Numer. Math., 26:241–263, 1998.
J. E. Flaherty, R. M. Loy, M. S. Shephard, B. K. Szymanski, J. D. Teresco, and L. H. Ziantz. Adaptive local refinement with octree load-balancing for the parallel solution of three-dimensional conservation laws. J. Parallel Distrib. Comput., 47:139–152, 1997.
J. E. Flaherty, R. M. Loy, M. S. Shephard, B. K. Szymanski, J. D. Teresco, and L. H. Ziantz. Predictive load balancing for parallel adaptive finite element computation. In H. R. Arabnia, editor, Proc. PDPTA’ 97, volume I, pages 460–469, 1997.
J. E. Flaherty, R. M. Loy, M. S. Shephard, and J. D. Teresco. Software for the parallel adaptive solution of conservation laws by discontinuous Galerkin methods. In B. Cockburn, G. Karniadakis, and S.-W. Shu, editors, Discontinous Galerkin Methods Theory, Computation and Applications, volume 11 of Lecture Notes in Compuational Science and Engineering, pages 113–124. Springer, 2000.
J. Garbers, H. J. Promel, and A. Steger. Finding clusters in VLSI circuits. In Proc. IEEE Intl. Conf. on Computer Aided Design, pages 520–523, 1990.
M. Garey, D. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237–267, 1976.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.
L. Hagen and A. Kahng. Fast spectral methofs for ratio cut partitioning and clustering. In Proc. IEEE Intl. Conf. on Computer Aided Design, pages 10–13, 1991.
L. Hagen and A. Kahng. A new approach to effective circuit clustering. In Proc. IEEE Intl. Conf. on Computer Aided Design, pages 422–427, 1992.
B. Hendrickson. Graph partitioning and parallel solvers: Has the emperor no clothes? In Proc. Irregular’98, volume 1457 of Lecture Notes in Computer Science, pages 218–225. Springer-Verlag, 1998.
B. Hendrickson and K. Devine. Dynamic load balancing in computational mechanics. Comput. Methods Appl. Mech. Engrg., 184(2–4):485–500, 2000.
B. Hendrickson and T. G. Kolda. Graph partitioning models for parallel computing. Parallel Comput., 26:1519–1534, 2000.
B. Hendrickson and R. Leland. The Chaco user’s guide, version 2.0. Technical Report SAND94-2692, Sandia National Laboratories, Albuquerque, 1994. Open-source software distributed at http://www.cs.sandia.gov/~bahendr/chaco.html.
B. Hendrickson and R. Leland. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. Scien. Comput., 16(2):452–469, 1995.
B. Hendrickson and R. Leland. A multilevel algorithm for partitioning graphs. In Proc. Supercomputing’ 95, 1995.
G. Horton. A multi-level diffusion method for dynamic load balancing. Parallel Comput., 19:209–218, 1993.
S.-H. Hsieh, G. H. Paulino, and J. F. Abel. Evaluation of automatic domain partitioning algorithms for parallel finite element analysis. Structural Engineering Report 94-2, School of Civil and Environmental Engineering, Cornell University, Ithaca, 1994.
Y. F. Hu and R. J. Blake. An optimal dynamic load balancing algorithm. Preprint DLP-95-011, Daresbury Laboratory, Warrington, WA4 4AD, UK, 1995.
Y. F. Hu, R. J. Blake, and D. R. Emerson. An optimal migration algorithm for dynamic load balancing. Concurrency: Practice and Experience, 10:467–483, 1998.
H. V. Jagadish. Linear clustering of objects with multiple attributes. In Proc. ACM SIGMOD, pages 332–342, 1990.
M. T. Jones and P. E. Plassmann. Computational results for parallel unstructured mesh computations. Comp. Sys. Engng., 5(4–6):297–309, 1994.
L. V. Kale and S. Krishnan. CHARM++: A portable concurrent object oriented system based on C++. ACM SIGPLAN notices, 28(10):91–128, 1993.
G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel hypergraph partitioning: application in VLSI domain. In Proc. 34th conf. Design automation, pages 526–529. ACM, 1997.
G. Karypis and V. Kumar. Metis: Unstructured graph partitioning and sparse matrix ordering system. Tech. Report, University of Minnesota, Department of Computer Science, Minneapolis, MN, 1995. Open-source software distributed at http://www-users.cs.umn.edu/~karypis/metis.
G. Karypis and V. Kumar. Multilevel algorithms for multiconstraint graph paritioning. Technical Report 98-019, Department of Computer Science, University of Minnesota, 1998.
G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Scien. Comput., 20(1), 1999.
G. Karypis and V. Kumar. Parallel multivelel k-way partitioning scheme for irregular graphs. SIAM Review, 41(2):278–300, 1999.
G. Karypis, K. Schloegel, and V. Kumar. ParMetis Parallel Graph Partitioning and Sparse Matrix Ordering Library, Version 3.1. University of Minnesota Department of Computer Science and Engineering, and Army HPC Research Center, Minneapolis, 2003. Open-source software distributed at http://www-users.cs.umn.edu/~karypis/metis.
B. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 29:291–307, 1970.
E. Leiss and H. Reddy. Distributed load balancing: design and performance analysis. W. M. Kuck Research Computation Laboratory, 5:205–270, 1989.
R. M. Loy. Adaptive Local Refinement with Octree Load-Balancing for the Parallel Solution of Three-Dimensional Conservation Laws. PhD thesis, Computer Science Dept., Rensselaer Polytechnic Institute, Troy, 1998.
B. Maerten, D. Roose, A. Basermann, J. Fingberg, and G. Lonsdale. DRAMA: A library for parallel dynamic load balancing of finite element applications. In Proc. Ninth SIAM Conference on Parallel Processing for Scientific Computing, San Antonio, 1999. Library distributed under license agreement from http://www.ccrl-nece.de/~drama/drama.html.
T. Minyard and Y. Kallinderis. Octree partitioning of hybrid grids for parallel adaptive viscous flow simulations. Int. J. Numer. Meth. Fluids, 26:57–78, 1998.
T. Minyard and Y. Kallinderis. Parallel load balancing for dynamic execution environments. Comput. Methods Appl. Mech. Engrg., 189(4):1295–1309, 2000.
T. Minyard, Y. Kallinderis, and K. Schulz. Parallel load balancing for dynamic execution environments. In Proc. 34th Aerospace Sciences Meeting and Exhibit, number 96-0295, Reno, 1996.
W. F. Mitchell. Refinement tree based partitioning for adaptive grids. In Proc. Seventh SIAM Conf. on Parallel Processing for Scientific Computing, pages 587–592. SIAM, 1995.
W. F. Mitchell. The full domain partition approach to distributing adaptive grids. Appl. Numer. Math., 26:265–275, 1998.
W. F. Mitchell. The refinement-tree partition for parallel solution of partial differential equations. NIST Journal of Research, 103(4):405–414, 1998.
B. Moon, H. V. Jagadish, C. Faloutsos, and J. H. Saltz. Analysis of the clustering properties of the Hilbert spacefilling curve. IEEE Trans. Knowledge and Data Engng., 13(1):124–141, January/February 2001.
G. M. Morton. A computer oriented geodetic data base and a new technique in file sequencing. Technical report, IBM Ltd., March 1966.
J. T. Oden, A. Patra, and Y. Feng. Domain decomposition for adaptive hp finite element methods. In Proc. Seventh Intl. Conf. Domain Decomposition Methods, State College, Pennsylvania, October 1993.
L. Oliker and R. Biswas. PLUM: Parallel load balancing for adaptive unstructured meshes. J. Parallel Distrib. Comput., 51(2):150–177, 1998.
L. Oliker, R. Biswas, and R. C. Strawn. Parallel implementaion of an adaptive scheme for 3D unstructured grids on the SP2. In Proc. 3rd International Workshop on Parallel Algorithms for Irregularly Structured Problems, Santa Barbara, 1996.
J. A. Orenstein. Spatial query processing in an object-oriented database system. In Proc. ACM SIGMOD, pages 326–336, May 1986.
M. Ozdal and C. Aykanat. Hypergraph models and algorithms for data-pattern based clustering. Data Mining and Knowledge Discovery, 9:29–57, 2004.
C. Özturan. Distributed Environment and Load Balancing for Adaptive Unstructured Meshes. PhD thesis, Computer Science Dept., Rensselaer Polytechnic Institute, Troy, 1995.
M. Parashar and J. C. Browne. On partitioning dynamic adaptive grid hierarchies. In Proc. 29th Annual Hawaii International Conference on System Sciences, volume 1, pages 604–613, Jan. 1996.
M. Parashar, J. C. Browne, C. Edwards, and K. Klimkowski. A common data management infrastructure for adaptive algorithms for PDE solutions. In Proc. SC97, San Jose, CA, 1997.
A. Patra and J. T. Oden. Problem decomposition for adaptive hp finite element methods. Comp. Sys. Engng., 6(2):97–109, 1995.
E. A. Patrick, D. R. Anderson, and F. K. Brechtel. Mapping multidimensional space to one dimension for computer output display. IEEE Trans. Computers, C-17(10):949–953, October 1968.
G. Peano. Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen, 36:157–160, 1890.
F. Pellegrini. SCOTCH 3.1 User’s guide. Technical Report 1137-96, LaBRI, Université Bordeaux I, August 1996. Library available at http://www.labri.fr/Perso/~pelegrin/scotch/.
F. Pellegrini and J. Roman. Experimental analysis of the dual recursive bipartitioning algorithm for static mapping. Technical Report 1038-96, Université Bordeaux I, 1996.
J. R. Pilkington and S. B. Baden. Dynamic partitioning of non-uniform structured workloads with spacefilling curves. IEEE Trans. on Parallel and Distributed Systems, 7(3):288–300, 1996.
A. Pinar and B. Hendrickson. Graph partitioning for complex objectives. In Proc. 15th Int’l Parallel and Distributed Processing Symp. (I PDPS), San Francisco, CA, April 2001.
S. Plimpton, S. Attaway, B. Hendrickson, J. Swegle, C. Vaughan, and D. Gardner. Transient dynamics simulations: Parallel algorithms for contact detection and smoothed particle hydrodynamics. J. Parallel Distrib. Comput., 50:104–122, 1998.
A. Pothen, H. Simon, and K.-P. Liou. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Mat. Anal. Appl., 11(3):430–452, 1990.
R. Preis and R. Diekmann. PARTY–a software library for graph partitioning. In B. Topping, editor, Advances in Computational Mechanics with Parallel and Distributed Processing, pages 63–71. CIVIL-COMP PRESS, 1997. Library distributed under free research and academic license at http://wwwcs.upb.de/fachbereich/AG/monien/RESEARCH/PART/party.html.
H. Sagan. Space-Filling Curves. Springer-Verlag, 1994.
K. Schloegel, G. Karypis, and V. Kumar. Multilevel diffusion schemes for repartitioning of adaptive meshes. J. Parallel Distrib. Comput., 47(2):109–124, 1997.
K. Schloegel, G. Karypis, and V. Kumar. A new algorithm for multi-objective graph partitioning. Tech. Report 99-003, University of Minnesota, Department of Computer Science and Army HPC Center, Minneapolis, 1999.
K. Schloegel, G. Karypis, and V. Kumar. A unified algorithm for load-balancing adaptive scientific simulations. In Proc. Supercomputing, Dallas, 2000.
K. Schloegel, G. Karypis, and V. Kumar. Wavefront diffusion and LMSR: Algorithms for dynamic repartitioning of adaptive meshes. IEEE Trans. Parallel Distrib. Syst., 12(5):451–466, 2001.
K. Schloegel, G. Karypis, and V. Kumar. Parallel static and dynamic multiconstraint graph partitioning. Concurrency and Computation — Practice and Experience, 14(3):219–240, 2002.
M. S. Shephard, S. Dey, and J. E. Flaherty. A straightforward structure to construct shape functions for variable p-order meshes. Comp. Meth. in Appl. Mech. and Engng., 147:209–233, 1997.
M._S. Shephard, J. E. Flaherty, H. L. de Cougny, C. Özturan, C. L. Bottasso, and M. W. Beall. Parallel automated adaptive procedures for unstructured meshes. In Parallel Computing in CFD, number R-807, pages 6.1–6.49. Agard, Neuilly-Sur-Seine, 1995.
H. D. Simon. Partitioning of unstructured problems for parallel processing. Comp. Sys. Engng., 2:135–148, 1991.
S. Sinha and M. Parashar. Adaptive system partitioning of AMR applications on heterogeneous clusters. Cluster Computing, 5(4):343–352, October 2002.
A. Sohn and H. Simon. S-HARP: A scalable parallel dynamic partitioner for adaptive mesh-based computations. In Proc. Supercomputing’ 98, Orlando, 1998.
J. Steensland. Vampire homepage. http://user.it.uu.se/~johans/research/vampire/vampire1.html, 2000. Open-source software distributed at http://user.it.uu.se/~johans/research/vampire/download.html.
J. Steensland, S. Chandra, and M. Parashar. An application-centric characterization of domain-based SFC partitioners for parallel SAMR. IEEE Trans. Parallel and Distrib. Syst., 13(12):1275–1289, 2002.
J. Steensland, S. Söderberg, and M. Thuné. A comparison of partitioning schemes for blockwise parallel SAMR algorithms. In Proc. 5th International Workshop on Applied Parallel Computing, New Paradigms for HPC in Industry and Academia, volume 1947 of Lecture Notes in Computer Science, pages 160–169, London, 2000. Springer-Verlag.
V. E. Taylor and B. Nour-Omid. A study of the factorization fill-in for a parallel implementation of the finite element method. Int. J. Numer. Meth. Engng., 37:3809–3823, 1994.
J. D. Teresco, J. Faik, and J. E. Flaherty. Hierarchical partitioning and dynamic load balancing for scientific computation. Technical Report CS-04-04, Williams College Department of Computer Science, 2004. To appear in the Proceedings of PARA’04.
J. D. Teresco and L. P. Ungar. A comparison of Zoltan dynamic load balancers for adaptive computation. Technical Report CS-03-02, Williams College Department of Computer Science, 2003. Presented at COMPLAS’ 03.
A. Trifunovic and W. J. Knottenbelt. Towards a parallel disk-based algorithm for multilevel k-way hypergraph partitioning. In Proc. 18th International Parallel and Distributed Processing Symposium (IPDPS’04), page 236b, Santa Fe, 2004.
R. Van Driessche and D. Roose. An improved spectral bisection algorithm and its application to dynamic load balancing. Parallel Comput., 21:29–48, 1995.
D. Vanderstraeten, C. Farhat, P. Chen, R. Keunings, and O. Ozone. A retrofit based methodology for the fast generation and optimization of large-scale mesh partitions: beyond the minimum interface size criterion. Comput. Methods Appl. Mech. Engrg., 133:25–45, 1996.
B. Vastenhouw and R. H. Bisseling. A two-dimensional data distribution method for parallel sparse matrix-vector multiplication. Preprint 1238, Dept. of Mathematics, Utrecht University, May 2002.
C. Walshaw. The Parallel JOSTLE Library User’s Guide, Version 3.0. University of Greenwich, London, UK, 2002. Library distributed under free research and academic license at http://staffweb.cms.gre.ac.uk/~c.walshaw/jostle/.
C. Walshaw and M. Cross. Multilevel Mesh Partitioning for Heterogeneous Communication Networks. Tech. Rep. 00/IM/57, Comp. Math. Sci., Univ. Greenwich, London SE10 9LS, UK, March 2000.
C. Walshaw and M. Cross. Multilevel Mesh Partitioning for Heterogeneous Communication Networks. Future Generation Comput. Syst., 17(5):601–623, 2001. (Originally published as Univ. Greenwich Tech. Rep. 00/IM/57).
C. Walshaw and M. Cross. Dynamic mesh partitioning and load-balancing for parallel computational mechanics codes. In B. H. V. Topping, editor, Computational Mechanics Using High Performance Computing, pages 79–94. Saxe-Coburg Publications, Stirling, 2002. (Invited Chapter, Proc. Parallel & Distributed Computing for Computational Mechanics, Weimar, Germany, 1999).
C. Walshaw, M. Cross, and M. Everett. A localized algorithm for optimizing unstructured mesh partitions. Intl. J. of Supercomputer Applications, 9(4):280–295, 1995.
C. Walshaw, M. Cross, and M. Everett. Parallel dynamic graph-partitioning for unstructured meshes. J. Parallel Distrib. Comput., 47(2):102–108, 1997.
C. Walshaw, M. Cross, and K. McManus. Multiphase mesh partitioning. Appl. Math. Modelling, 25(2):123–140, 2000. (Originally published as Univ. Greenwich Tech. Rep. 99/IM/51).
M._S. Warren and J. K. Salmon. A parallel hashed oct-tree n-body algorithm. In Proc. Supercomputing’ 93, pages 12–21. IEEE Computer Society, 1993.
J. Watts. A practical approach to dynamic load balancing. Master’s Thesis, October 1995.
J. Watts, M. Rieffel, and S. Taylor. A load balancing technique for multiphase computations. In Proc. High Performance Computing’ 97, pages 15–20. Society for Computer Simulation, 1997.
S. Wheat. A Fine Grained Data Migration Approach to Application Load Balancing on MP MIMD Machines. PhD thesis, University of New Mexico, Department of Computer Science, Albuquerque, 1992.
S. Wheat, K. Devine, and A. MacCabe. Experience with automatic, dynamic load balancing and adaptive finite element computation. In H. El-Rewini and B. Shriver, editors, Proc. 27th Hawaii International Conference on System Sciences, pages 463–472, Kihei, 1994.
M. Willebeek-LeMair and A. Reeves. Strategies for dynamic load balancing on highly parallel computers. IEEE Parallel and Distrib. Sys., 4(9):979–993, 1993.
R. Wolski, N. T. Spring, and J. Hayes. The Network Weather Service: A distributed resource performance forecasting service for metacomputing. Future Generation Comput. Syst., 15(5–6):757–768, October 1999.
C. Xu, F. Lau, and R. Diekmann. Decentralized remapping of data parallel applications in distributed memory multiprocessors. Tech. Rep. tr-rsfb-96-021, Dept. of Computer Science, University of Paderborn, Paderborn, Germany, Sept. 1996.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Teresco, J.D., Devine, K.D., Flaherty, J.E. (2006). Partitioning and Dynamic Load Balancing for the Numerical Solution of Partial Differential Equations. In: Bruaset, A.M., Tveito, A. (eds) Numerical Solution of Partial Differential Equations on Parallel Computers. Lecture Notes in Computational Science and Engineering, vol 51. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-31619-1_2
Download citation
DOI: https://doi.org/10.1007/3-540-31619-1_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29076-6
Online ISBN: 978-3-540-31619-0
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)