Экспериментальное сравнение алгоритмов в параллельном методе вложенных сечений
Автор: Пирова Анна Юрьевна, Кудрявцев Никита Юрьевич, Мееров Иосиф Борисович
Рубрика: Вычислительная математика
Статья в выпуске: 1 т.6, 2017 года.
Бесплатный доступ
В прямых методах решения больших разреженных систем линейных алгебраических уравнений применяется процедура переупорядочения строк и столбцов исходной матрицы. Целью данной процедуры является сокращение числа ненулевых элементов в процессе последующей численной факторизации. Нахождение перестановки, минимизирующей число ненулевых элементов в факторе, является NP-полной задачей. Для решения этой задачи применяются эвристические методы. Результаты применения данных методов могут быть оценены как с точки зрения качества получаемых перестановок (заполнение фактора матрицы после переупорядочения), так и с точки зрения временных затрат на построение перестановок. Многоуровневый метод вложенных сечений, показывающий достаточно хорошие результаты по обоим критериям, является одним из наиболее распространенных методов переупорядочения. Метод имеет определенные ресурсы внутреннего параллелизма, активно используемые в ряде реализаций (ParMETIS, mtMETIS, PT-SCOTCH, PMORSy). Вместе с тем, низкая арифметическая интенсивность, нерегулярный доступ к памяти, дисбаланс вычислительной нагрузки и необходимость поиска компромисса между временем работы и качеством перестановок мотивируют дальнейшие исследования метода. В данной работе выполняется сравнение ряда алгоритмов, применяемых на разных этапах метода вложенных сечений, с точки зрения их влияния на заполнение фактора и время работы в параллельном случае. Реализация алгоритмов и эксперименты выполнены в рамках ранее разработанной параллельной библиотеки переупорядочения матриц PMORSy, опережающей аналоги на ряде матриц коллекции университета Флориды. В результате выполненной работы удалось выделить наиболее перспективную комбинацию алгоритмов и улучшить качество перестановок и время работы PMORSy.
Метод вложенных сечений, переупорядочение разреженных матриц, параллельный алгоритм
Короткий адрес: https://sciup.org/147160612
IDR: 147160612 | DOI: 10.14529/cmse170103
Список литературы Экспериментальное сравнение алгоритмов в параллельном методе вложенных сечений
- 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.
