DOI: https://doi.org/10.26089/NumMet.v16r339

Параллельный алгоритм многоуровневого метода вложенных сечений для вычислительных систем с общей памятью

Авторы

  • А.Ю. Пирова
  • И.Б. Мееров
  • Е.А. Козинов
  • С.А. Лебедев

Ключевые слова:

многоуровневый метод вложенных сечений
переупорядочение разреженной матрицы
разложение Холецкого
параллельные алгоритмы
вычислительные системы с общей памятью
высокопроизводительные вычисления

Аннотация

Рассматривается задача переупорядочения строк и столбцов симметричной положительно определенной разреженной матрицы с целью уменьшения числа ненулевых элементов в факторе Холецкого. %количества вновь появляющихся ненулевых элементов в процессе разложения %(факторизации) этой матрицы методом Холецкого. Данная задача является NP-полной. Для ее решения используются эвристические алгоритмы, основанные на применении методов теории графов. Предлагается параллельный алгоритм переупорядочения для вычислительных систем с общей памятью. В качестве базы для распараллеливания используется модификация многоуровневого метода вложенных сечений, ранее реализованная авторами в виде библиотеки с открытым исходным кодом MORSy. Основная идея распараллеливания заключается в организации и параллельной обработке очереди задач, которые могут быть решены независимо. В отличие от широко распространенных аналогов, применяющих MPI для организации параллелизма как на распределенной, так и на общей памяти, предложенный алгоритм использует возможности стандарта OpenMP 3.0. Вычислительные эксперименты выполнены на симметричных положительно определенных матрицах из коллекции университета Флориды. Показано, что параллельный код MORSy дает сходные или лучшие перестановки в сравнении с библиотекой ParMETIS для всех тестовых матриц, кроме одной, в большинстве случаев опережая ParMETIS по времени работы. Программная реализация выполнена в виде библиотеки с открытым исходным кодом и доступна для скачивания на сайте Приволжского научно-образовательного центра суперкомпьютерных технологий.

Новые вычислительные технологии

Загрузки

Опубликован

2015-07-26

Выпуск

Том 16 (2015): Выпуск 3.

Раздел

Раздел 1. Вычислительные методы и приложения

Авторы

А.Ю. Пирова

Нижегородский государственный университет им Н.И. Лобачевского
пр.Гагарина, 23, 603950, Нижний Новгород
• младший научный сотрудник

И.Б. Мееров

Нижегородский государственный университет им Н.И. Лобачевского
пр.Гагарина, 23, 603950, Нижний Новгород
• заместитель заведующего кафедрой

Е.А. Козинов

Нижегородский государственный университет им Н.И. Лобачевского
пр.Гагарина, 23, 603950, Нижний Новгород
• ассистент

С.А. Лебедев

Нижегородский государственный университет им Н.И. Лобачевского
пр.Гагарина, 23, 603950, Нижний Новгород
• программист

Библиографические ссылки

  1. M. Yannakakis, “Computing the Minimum Fill-In is NP-Complete,” SIAM J. Alg. Disc. Meth. 2 (1), 77-79 (1981).
  2. W. F. Tinney and J. W. Walker, “Direct Solutions of Sparse Network Equations by Optimally Ordered Triangular Factorization,” Proc. IEEE 55 (11), 1801-1809 (1967).
  3. A. George, “Nested Dissection of a Regular Finite Element Mesh,” SIAM J. Numer. Anal. 10 (2), 345-363 (1973).
  4. A. Pirova and I. Meyerov, “MORSy - A New Tool For Sparse Matrix Reordering,” in Proc. Int. Conf. on Engineering and Applied Sciences Optimization, Kos Island, Greece, June 4-6, 2014 (National Tech. Univ. of Athens, Athens, 2014), pp. 1952-1964.
  5. J. W. H. Liu, “Modification of the Minimum-Degree Algorithm by Multiple Elimination,” ACM Trans. Math. Softw. 11 (2), 141-153 (1985).
  6. P. R. Amestoy, T. A. Davis, and I. S. Duff, “An Approximate Minimum Degree Ordering Algorithm,” SIAM. J. Matrix Anal. Appl. 17 (4), 886-905 (1996).
  7. T. A. Davis, J. R. Gilbert, S. I. Larimore, and E. G. Ng, “A Column Approximate Minimum Degree Ordering Algorithm,” ACM Trans. Math. Soft. 30 (3), 353-376 (2004).
  8. R. J. Lipton, D. J. Rose, and R. E. Tarjan, “Generalized Nested Dissection,” SIAM J. Numer. Anal. 16 (2), 346-358 (1979).
  9. A. George and J. W. H. Liu, “An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems,” SIAM J. Numer. Anal. 15 (5), 1053-1069 (1978).
  10. A. Pothen, H. D. Simon, and L. Wang, Spectral Nested Dissection , Technical Report CS-92-01 (Pennsylvania State Univ., State College, 1992).
  11. M. T. Heath and P. Raghavan, “A Cartesian Parallel Nested Dissection Algorithm,” SIAM J. Matrix Anal. Appl. 16 (1), 235-253 (1995).
  12. G. L. Miller, S.-H. Teng, and S. A. Vavasis, “A Unified Geometric Approach to Graph Separators,” in Proc. 32nd Annual Symp. on Foundations of Computer Science, San Juan, USA, October 1-4, 1991 (IEEE Press, New York, 1991), pp. 538-547.
  13. T. N. Bui and C. Jones, “A Heuristic for Reducing Fill-In in Sparse Matrix Factorization,” in Proc. 6th SIAM Conf. on Parallel Processing for Scientific Computing, Norfolk, USA, March 22-24, 1993 (SIAM Press, Philadelphia, 1993), pp. 445-452.
  14. B. Hendrickson and R. Leland, A Multilevel Algorithm for Partitioning Graphs , Tech. Rep. SAND93-1301 (Sandia National Labs., Albuquerque, 1993).
  15. G. Karypis and V. Kumar, “A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs,” SIAM J. Sci. Comput. 20 (1), 359-392 (1998).
  16. B. Hendrickson and E. Rothberg, “Improving the Runtime and Quality of Nested Dissection Ordering,” SIAM J. Sci. Comput. 20 (2), 468-489 (1999).
  17. A. George, M. T. Heath, J. Liu, and E. Ng, “Sparse Cholesky Factorization on a Local-Memory Multiprocessor ,” SIAM J. Sci. Stat. Comput. 9 (2), 327-340 (1988).
  18. G. Karipis, METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices , Version 5.0 (University of Minnesota, Minneapolis, 2011).
  19. Intel Math Kernel Library Reference Manual.
    http://software.intel.com/sites/default/files/managed/9d/c8/mklman.pdf . Cited August 11, 2015.
  20. G. Karypis and V. Kumar, ParMetis: Parallel Graph Partitioning and Sparse Matrix Ordering Library , Technical Report 97-060 (University of Minnesota, Minneapolis, 1997).
  21. G. Karypis and V. Kumar, “A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering,” J. Parallel Distrib. Comput. 48 (1), 71-95 (1998).
  22. K. Schloegel, G. Karypis, and V. Kumar, “Parallel Multilevel Algorithms for Multi-Constraint Graph Partitioning,” in Lecture Notes in Computer Science (Springer, London, 2000), Vol. 1900, pp. 296-310.
  23. F. Pellegrini, Scotch and LibScotch 6.0 User’s Guide (Université Bordeaux, Bordeaux, 2012).
  24. F. Pellegrini, J. Roman, and P. Amestoy, “Hybridizing Nested Dissection and Halo Approximate Minimum Degree for Efficient Sparse Matrix Ordering,” Concurrency: Pract. Exper. 12 (2-3), 68-84 (2000).
  25. C. Chevalier and F. Pellegrini, “PT-Scotch: A Tool for Efficient Parallel Graph Ordering,” Parallel Comput. 34 (6-8), 318-331 (2008).
  26. D. Lasalle and G. Karypis, “Multi-Threaded Graph Partitioning,” in Proc. 27th Int. Symp. on Parallel and Distributed Processing, Boston, USA, May 20-24, 2013 (IEEE Press, New York, 2013), pp. 225-236.
  27. F. Pellegrini, “Shared Memory Parallel Algorithms in Scotch 6,”
    http://graal.ens-lyon.fr/MUMPS/doc/ud_2013/Pellegrini.pdf . Cited August 11, 2015.
  28. MORSy.
    http://hpc-education.unn.ru/research/overview/sparse-algebra/morsy . Cited August 11, 2015.
  29. B. W. Kernighan and S. Lin, “An Efficient Heuristic Procedure for Partitioning Graphs,” The Bell Syst. Tech. J. 49 (2), 291-307 (1970).
  30. C. M. Fiduccia and R. M. Mattheyses, “A Linear-Time Heuristic for Improving Network Partitions,” in Proc. 19th IEEE Design Automation Conf., Las Vegas, USA, June 14-16, 1982 (IEEE Press, Piscataway, 1982), pp. 175-181.
  31. C. Aschcraft and J. W. H. Liu, A Partition Improvement Algorithm for Generalized Nested Dissection , Technical Report BCSTECH-94-020 (Boeing Computer Services, Seattle, 1994).
  32. C. Aschcraft and J. W. H. Liu, “Using Domain Decomposition to Find Graph Bisectors,” BIT Numer. Math. 37 (3), 506-534 (1997).
  33. T. A. Davis and Y. Hu, “The University of Florida Sparse Matrix Collection,” ACM Trans. Math. Softw. 38 (2011).
    doi 10.1145/2049662.2049663
  34. G. Karipis and K. Schloegel, ParMETIS Manual. Parallel Graph Partitioning and Sparse Matrix Ordering Library , Version 4.0.
    http://glaros.dtc.umn.edu/gkhome/fetch/sw/parmetis/manual.pdf . Cited August 11, 2015.
  35. S. Lebedev, D. Akhmedzhanov, E. Kozinov, et al., “Dynamic Parallelization Strategies for Multifrontal Sparse Cholesky Factorization,” Lecture Notes in Computer Science (in press).
  36. Е. A. Kozinov, I. G. Lebedev, S. A. Lebedev, et al., “Novel Linear Equations Systems Solver for Sparse Symmetric Positive-Definite Matrix,” Vestn. Univ. Nizhni Novgorod 5 (2), 376-384 (2012).