Экспериментальное сравнение алгоритмов в параллельном методе вложенных сечений

Анна Юрьевна Пирова, Никита Юрьевич Кудрявцев, Иосиф Борисович Мееров

Аннотация


В прямых методах решения больших разреженных систем линейных алгебраических уравнений применяется процедура переупорядочения строк и столбцов исходной матрицы. Целью данной процедуры является сокращение числа ненулевых элементов в процессе последующей численной факторизации. Нахождение перестановки, минимизирующей число ненулевых элементов в факторе, является NP-полной задачей. Для решения этой задачи применяются эвристические методы. Результаты применения данных методов могут быть оценены как с точки зрения качества получаемых перестановок (заполнение фактора матрицы после переупорядочения), так и с точки зрения временных затрат на построение перестановок. Многоуровневый метод вложенных сечений, показывающий достаточно хорошие результаты по обоим критериям, является одним из наиболее распространенных методов переупорядочения. Метод имеет определенные ресурсы внутреннего параллелизма, активно используемые в ряде реализаций (ParMETIS, mtMETIS, PT-SCOTCH, PMORSy). Вместе с тем, низкая арифметическая интенсивность, нерегулярный доступ к памяти, дисбаланс вычислительной нагрузки и необходимость поиска компромисса между временем работы и качеством перестановок мотивируют дальнейшие исследования метода.

В данной работе выполняется сравнение ряда алгоритмов, применяемых на разных этапах метода вложенных сечений, с точки зрения их влияния на заполнение фактора и время работы в параллельном случае. Реализация алгоритмов и эксперименты выполнены в рамках ранее разработанной параллельной библиотеки переупорядочения матриц PMORSy, опережающей аналоги на ряде матриц коллекции университета Флориды. В результате выполненной работы удалось выделить наиболее перспективную комбинацию алгоритмов и улучшить качество перестановок и время работы PMORSy.


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


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

Полный текст:

PDF

Литература


Bui T., Jones C. A Heuristic for Reducing Fill in Sparse Matrix Factorization // 6th SIAM Conference Parallel Processing for Scientific Computing. 1993. P. 445–452.

Chevalier C., Pellegrini F. PT-Scotch: A Tool for Efficient Parallel Graph Ordering // Parallel Computing. 2008. Vol. 34, No. 6. P. 318–331. DOI: 10.1016/j.parco.2007.12.001.

Davis T. A., Hu Y. The University of Florida Sparse Matrix Collection // ACM Transactions on Mathematical Software (TOMS). 2011. Vol. 38, No. 1. P. 1. DOI: 10.1145/2049662.2049663.

George A. et al. Sparse Cholesky Factorization on a Local-memory Multiprocessor //SIAM J. on Scientific and Statistical Computing. 1988. Vol. 9, No. 2. P. 327–340. DOI: 10.1016/0167-8191(92)90014-x.

George A. Nested Dissection of a Regular Finite Element Mesh // SIAM J. on Numerical Analysis. 1973. Vol. 10, No. 2. P. 345–363. DOI: 10.1137/0710032.

George A., Liu J.W.H. An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems // SIAM J. on Numerical Analysis. 1978. Vol. 15, No. 5. P. 1053–1069. DOI: 10.1137/0715069.

Karypis G., Kumar V. ParMetis: Parallel Graph Partitioning and Sparse Matrix Ordering Library. Tech. Rep. TR 97-060, University Of Minnesota, Department Of Computer Science. 1997.

Karypis G., Kumar V. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs // SIAM J. on Scientific Computing. 1998. Vol. 20, No. 1. P. 359–392. DOI: 10.1137/s1064827595287997.

Karypis G., Kumar V. Analysis of Multilevel Graph Partitioning // Proceedings of the 1995 ACM/IEEE conference on Supercomputing. ACM, 1995. P. 29.

Karypis G., Kumar V. METIS. A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-reducing Orderings of Sparse Matrices. Technical Report University of Minnesota, Department of Computer Science and Engineering. 1998.

LaSalle D., Karypis G. Efficient Nested Dissection for Multicore Architectures // Euro-Par 2015: Parallel Processing. 2015, Springer Berlin Heidelberg. P. 467–478.

Pellegrini F. Scotch and libScotch 6.0 User’s Guide. Technical Report LaBRI, 2012.

Pellegrini F. Shared Memory Parallel Algorithms in Scotch 6 // MUMPS User Group Meeting. 2013. URL: http://graal.ens-lyon.fr/mumps/doc/ud_2013/pellegrini.pdf (дата обращения: 01.12.2016)

Pirova A., Meyerov I. MORSy — a New Tool for Sparse Matrix Reordering // An International Conference on Engineering and Applied Sciences Optimization M. Papadrakakis, M.G. Karlaftis, N.D. Lagaros (eds.) (Kos Island, Greece, 4-6 June 2014). P. 1952–1964.

Pirova A., Meyerov I., Kozinov E., Lebedev S. PMORSy: Parallel Sparse Matrix Ordering Software for Fill-in Minimization // Optimization Methods and Software. 2017. Vol. 32, No. 2. P. 274–289. DOI: 10.1080/10556788.2016.1193177.

Pothen A. Graph Partitioning Algorithms with Applications to Scientific Computing // Parallel Numerical Algorithms. Springer Netherlands, 1997. P. 323–368. DOI: 10.1007/978-94-011-5412-3_12.

Tinney W., Walker J. Direct Solutions of Sparse Network Equations by Optimally Ordered Triangular Factorization // Proceedings of the IEEE. 1967. Vol. 55, No. 11. P. 1801–1809. DOI: 10.1109/proc.1967.6011.

Yannakakis M. Computing the Minimum Fill-in is NP-complete // SIAM J. on Algebraic and Discrete Methods. 1981. Vol. 2, No. 1. P. 77–79. DOI: 10.1137/0602010.

Пирова A.Ю., Мееров И.Б., Козинов Е.А., Лебедев С.А. Параллельный алгоритм многоуровневого метода вложенных сечений для вычислительных систем с общей памятью // Вычислительные методы и программирование. 2015. Т. 16. № 3.

C. 407–420.

Старостин Н.В. Многоуровневый итерационный алгоритм декомпозиции графа. // Системы управления и информационные технологии. 2015. Т. 61. № 3.

С. 27–30.




DOI: http://dx.doi.org/10.14529/cmse170103