Effective domain decomposition methods for adaptive unstructured grids applied to high performance computing for problems in computational aerodynamics
Modern domain decomposition methods in high performance aerodynamics simulations are investigated. Effective decomposition algorithms for adaptive unstructured grids based on geometric and graph representations are implemented. Geometric techniques (such as recursive coordinate bisection, recursive inertial bisection and space-filling curve methods), combinatorial approaches (which include levelized nested dissection, Kernighan-Lin and Fiduccia-Mattheyses algorithm), spectral methods, multilevel schemes are considered. A set of quality criteria for optimal mesh decomposition like load balancing, number of edges cut, the provision of connectivity of the subdomains, run time, the degree of parallelizability are discussed. Some test cases are considered to examine of the quantitative and qualitative characteristics of the traditional domain decomposition techniques and combined schemes.
high performance computing, numerical simulation, computational aerodynamics, software systems, unstructured mesh, multiprocessor simulation, graph decomposition, data decomposition
Проведено исследование современных методов декомпозиции неструктурированных адаптивных сеток для организации параллельных вычислений на многопроцессорных системах при решении актуальных задач газовой динамики и аэродинамики. Изучены и реализованы эффективные алгоритмы оптимального разбиения расчетных сеток, строящиеся на основе геометрических и графовых моделей. Рассматриваются геометрические способы декомпозиции, которые используют принципы координатной или моментной рекурсивной бисекции, либо применяют заполняющие пространство кривые; комбинаторные подходы, такие как метод деления с учетом связности, алгоритм Кернигана-Лина и Фидуччи-Маттейсеса; класс спектральных методов; многоуровневые (иерархические) технологии. Обсуждается ряд критериев разбиения: сбалансированность, количество коммуникационных связей между доменами, обеспечение связности каждой из подобластей, время выполнения алгоритмов, способность к распараллеливанию. Проведена качественная и количественная оценка эффективности исследованных классических технологий декомпозиции, а также комбинированных методов на ряде тестовых задач.
1. Schloegel K., Karypis G., Kumar V. Graph partitioning for high performance scientific simulations / In J. Dongarra, I. Foster, G. Fox, K. Kennedy, and A. White, editors, CRPC Parallel Computing Handbook, Morgan Kaufmann, 2001. 2. Berger M.J., Bokhari S. A partitioning strategy for nonuniform problems on multiprocessors // IEEE Trans. Comp. Vol. 36. 1987. P. 570–580. 3. Heath M.T., Raghavan P. A Cartesian parallel nested dissection algorithm // SIAM Journal of Matrix Analysis and Applications. Vol. 16, № 1, 1995. P. 235–253. 4. Nour-Omid B., Raefsky A., Lyzenga G. Solving finite element equations on concurrent computers. / In A.K. Noor, editor, Parallel Computations and Their Impact on Mechanics, ASME, 1986. P. 209–227. 5. Patra A., Kim D.W. Efficient mesh partitioning for adaptive hp finite element methods / In International Conference on Domain Decomposition Methods, 1998. 6. Pilkington J.R., Baden S.B. Partitioning with spacefilling curves / Technical Report CS94-349, Dept. of Computer Science and Engineering, Univ. of California, 1994. 7. Raghavan P. Line and plane separators / Technical Report UIUCDCS-R-93-1794, Dept. of Computer Science, Univ. of Illinois, 1993. 8. Mandelbrot B.B. The Fractal Geometry of Nature / New York: W. H. Freeman and Co., 1982. 9. Alauzet F., Loseille A. On the use of space filling curves for parallel anisotropic mesh adaptation // Proc. in 18th International Meshing Roundtable, Springer-Verlag, 2009. P. 337–357. 10. Schamberger S., Wierum J.M. A locality preserving graph ordering approach for implicit partitioning: Graph-filling curves // Proc. 17th Intl. Conf. on Parallel and Distributed Computing Systems, PDCS 2004, ISCA, 2004. P. 51–57. 11. Ashcraft C., Liu J.W.H. A partition improvement algorithm for generalized nested dissection / Technical Report BCSTECH-94-020, Dept. of Computer Science, York Univ., 1994. 12. Ashcraft C., Liu J.W.H. Using domain decomposition to find graph bisectors / Technical report CS-95-08, Dept. of Computer Science, York Univ., 1995. 13. Fiduccia C.M., Mattheyses R.M. A linear time heuristic for improving network partitions // Proc. 19th IEEE Design Automation Conference, 1982. P. 175–181. 14. George A., Liu J.W. Computer Solution of Large Sparse Positive Definite Systems / Prentice-Hall, Englewood Cliffs, NJ, 1981. 15. Goehring T., Saad Y. Heuristic algorithms for automatic graph partitioning / Technical Report UMSI-94-29, University of Minnesota Supercomputing Institute, 1994. 16. Hager W.W., Park S.C., Davis T.A. Block exchange in graph partitioning / In P.M. Pardalos, editor, Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems. Kluwer Academic Publishers, 2000. P. 299-307. 17. Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs // The Bell System Technical Journal. Vol. 49, №2, 1970. P. 291–307. 18. Писсанецки, С. Технология разреженных матриц / С. Писсанецки. - М.: Мир, 1988. 19. Chung Y.-C., Ranka S. Mapping finite element graphs on hypercubes // Journal of Supercomputing. Vol. 6, 1992. P. 257 – 282. 20. Sadayappan P., Ercal F. Mapping of finite element graphs onto processor meshes // IEEE Transactions on Computers. Vol. C-36, 1987. P. 1408 – 1424. 21. Diekmann R., Monien B., Preis R. Using helpful sets to improve graph bisections / In D. Hsu, A. Rosenberg, D. Sotteau, editors, Interconnection Networks and Mapping and Scheduling Parallel Computations. AMS Publications, DIMACS Volume Series. Vol. 21, 1995. P. 57–73. 22. Simon H.D. Partitioning of unstructured problems for parallel processing // Comput. Syst. Eng. Vol. 2, 1991. P. 135–148. 23. Williams R.D. Performance of dynamic load balancing algorithms for unstructured mesh calculations / Technical Report, California Institute of Technology, 1990 24. Chan T.F., Resasco D.C. A framework for the analysis and construction of domain decomposition preconditioners / Technical Report CAM-87-09, University of California, Los Angeles, 1987. 25. Chan T.F., Smith B. Domain decomposition and multigrid algorithms for elliptic problems on unstructured meshes // Contemp. Math, 1993. P. 1–14. 26. Hendrickson B., Leland R. An improved spectral graph partitioning algorithm for mapping parallel computations // SIAM J. Sci. Comput. Vol. 16, №2, 1995. P. 452–469. 27. Pothen A., Simon H.D., Liou K.-P. Partitioning sparse matrices with eigenvectors of graphs // SIAM Journal of Matrix Analysis and Applications. Vol. 11, № 3, 1990. P. 430–452. 28. Pothen A., Simon H.D., Wang L., Barnard S.T. Towards a fast implementation of spectral nested dissection // Supercomputing '92 Proceedings, 1992. P. 42–51. 29. Spielman D.A., Teng S.-H. Spectral partitioning works: Planar graphs and finite element meshes // Linear Algebra and its Applications. Vol. 421, 2007. P. 284–305. 30. Ильин В. А., Позняк Э. Г. Линейная алгебра: Учебник для вузов. — 6-е изд., стер. — М.: ФИЗМАТЛИТ, 2004. – 280 с. 31. Chung F. R. K. Spectral Graph Theory / CBMS regional conference series in mathematics Conference Series in Mathematics. Vol.92, 1997. 32. Mohar B. The Laplacian spectrum of graphs / In Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk , editors, Graph Theory, Combinatorics, and Applications. Vol. 2, Wiley, New York, 1991. P. 871–898. 33. Fiedler M. Algebraic connectivity of graphs // Czech. Math. J. Vol 23, №98, 1973. P. 298–305 34. Fiedler M. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory // Czech. Math. J. Vol. 25, №100, 1975. P. 619–633. 35. Data and Graph Partitioning. [Электронный ресурс] / Lecture notes. Indiana University. URL: http://www.cs.indiana.edu/classes/b673/notes/GraphPartitioning.pdf 36. Bui T. N., Jones C. A heuristic for reducing fill in sparse matrix factorization // 6th SIAM Conf. Parallel Processing for Scientific Computing, 1993. P. 445 – 452. 37. Cong J., Smith M. A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design / Proc. ACM/IEEE Design Automation Conference, 1993. P. 755–760. 38. Gupta A. Fast and effective algorithms for graph partitioning and sparse matrix reordering // IBM Journal of Research and Development. Vol. 41, 1996. P. 171–183. 39. Hauck S., Borriello G. An evaluation of bipartitioning techniques // IEEE Transactions on Computer-Aided Design. Vol. 16, № 8, 1997. P. 849–866. 40. Hendrickson B., Leland R. A multilevel algorithm for partitioning graphs / Technical Report SAND 93-1301, Sandia National Laboratories, 1993. 41. Karypis G., Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs // SIAM Journal on Scientific Computing. Vol. 20, №1, 1998. P. 359–392. 42. Karypis G., Kumar V. Multilevel k-way partitioning scheme for irregular graphs // Journal of Parallel and Distributed Computing. Vol. 48, № 1, 1998. P. 96–129. 43. Monien B., Preis R., Diekmann R. Quality matching and local improvement for multilevel graph-partitioning / Technical report, University of Paderborn, 1999. 44. Chevalier C., Safro I. Comparison of coarsening schemes for multi-level graph partitioning / Proc. Learning and Intelligent Optimization, 2009. P. 191–205. 45. Karypis G., Kumar V. MeTiS 4.0: Unstructured graph partitioning and sparse matrix ordering system / Technical report, Dept. of Computer Science and Engineering, Univ. of Minnesota, 1998. 46. Pellegrini F., Roman J. SCOTCH: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs // Proc. HPCN’96, 1996. P. 493–498. 47. Hendrickson B., Leland R. The Chaco user's guide: Version 2.0 / Technical Report SAND94-2692, Sandia National Laboratories, 1994. 48. Walshaw C. The Parallel JOSTLE Library User's Guide, Version 3.0. / University of Greenwich, 1998. 49. Preis R., Diekmann R. PARTY – a software library for graph partitioning / Technical report, University of Paderborn, 1997. 50. Якобовский М.В. Инкрементный алгоритм декомпозиции графов // Вестник Нижего-родского университета им. Н.И. Лобачевского. Серия «Математическое моделирование и оптимальное управление». Издательство ННГУ. № 1(28), 2005. С. 243–250. 51. Головченко Е.Н. Параллельный пакет декомпозиции больших сеток // Матем. модели-рование. T. 23, № 10, 2011. C. 3–18. 52. Головченко Е.Н. Разбиение больших сеток // Вестник Нижегородского университета им. Н.И. Лобачевского. Серия «Информационные технологии». Издательство ННГУ. № 5(2), 2012. С. 309–315. 53. Головченко Е.Н., Якобовский М.В. Пакет параллельной декомпозиции больших сеток GridSpiderPar // Вычислительные методы и программирование: Новые вычислительные технологии (Электронный научный журнал). Т. 16, № 4, 2015. С. 507–517. 54. MATLAB. http://www.mathworks.com/products/matlab/ 55. Rantakokko J. A local refinement algorithm for data partitioning / Proc. of PARA2000, T. Sorevik et.al, editors, New Paradigms for HPC in Industry and Academia, 5th International Workshop, PARA2000, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2001. P. 140–148. 56. Barnard S.T. PMRSB: Parallel multilevel recursive spectral bisection / Proc. ACM/IEEE Conference on Supercomputing (on CD-ROM), 1995. 57. Gilbert J. R., Zmijewski E. A parallel graph partitioning algorithm for a message-passing multiprocessor // International Journal of Parallel Programming. Vol.16, 1987. P. 498–513. 58. Karypis G., Kumar V. A parallel algorithm for multilevel graph partitioning and sparse matrix ordering // Journal of Parallel and Distributed Computing. Vol.48, №1, 1988. 48(1). P. 71–95. 59. Karypis G., Kumar V. Parallel multilevel k-way partitioning scheme for irregular graphs / Siam Review. Vol.42, №2, 1999. P. 278 – 300. 60. Karypis G., Schloegel K., Kumar V. ParMeTiS: Parallel graph partitioning and sparse matrix ordering library / Technical report, Dept. of Computer Science and Engineering, Univ. of Minnesota, 1997. 61. Cross M., Walshaw C. Parallel optimization algorithms for multilevel mesh partitioning / Techical Report 99/IM/44, Uviversity of Greenwich, 1999.
