Impacto de estratégias combinatórias no precondicionador paralelo híbrido SPIKE
Resumo
Neste trabalho, utilizamos o algoritmo paralelo híbrido SPIKE como um precondicionador para um método iterativo não-estacionário combinando as arquiteturas de memória distribuída e compartilhada, MPI e OpenMP. A fim de obter um bom precondicionador, resolvemos um conjunto de problemas combinatórios como reordenamentos e particionamento de grafos. Apresentamos os resultados avaliando a influência de cada estratégia na convergência e tempo de CPU do método iterativo.
Referências
Barnard, S. T., Pothen, A., and Simon, H. D. (1993). A spectral algorithm for envelope reduction of sparse matrices. In Proceedings of the 1993 ACM/IEEE conference on Supercomputing, Supercomputing '93, pages 493–502, New York, NY, USA. ACM.
Davis, T. A. and Hu, Y. (2011). The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software, (1):1:1 – 1:25.
Duff, I. S. and Koster, J. (2000). On algorithms for permuting large entries to the diagonal of a sparse matrix. SIAM J. Matrix Anal. Appl., 22(4):973–996.
Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23:298–305.
Hogg, J. and Scott, J. (2015). On the use of suboptimal matchings for scaling and ordering sparse symmetric matrices. Numerical Linear Algebra with Applications.
Manguoglu, M., Koyutürk, M., Sameh, A. H., and Grama, A. (2010). Weighted matrix ordering and parallel banded preconditioners for iterative linear system solvers. SIAM J. Sci. Comput., 32(3):1201–1216.
Manguoglu, M., Sameh, A. H., and Schenk, O. (2009). PSPIKE: A parallel hybrid In Sips, H., Epema, D., and Lin, H.-X., editors, Eurosparse linear system solver. Par 2009 Parallel Processing, volume 5704 of LNCS, pages 797–808. Springer Berlin Heidelberg.
Manne, F. and Sørevik, T. (1995). Optimal partitioning of sequences. J. Algorithms, 19(2):235–249.
Pinar, A. and Aykanat, C. (2004). Fast optimal load balancing algorithms for 1d partitioning. J. Parallel Distrib. Comput., 64(8):974–996.
Polizzi, E. and Sameh, A. H. (2006). A parallel hybrid banded system solver: The SPIKE algorithm. Parallel Comput., 32(2):177–194.
Polizzi, E. and Sameh, A. H. (2007). SPIKE: A parallel environment for solving banded linear systems. Computers & Fluids, 36(1):113–120.
Sathe, M., Schenk, O., Uçar, B., and Sameh, A. (2012). A Scalable Hybrid Linear Solver Based on Combinatorial Algorithms. In Naumann, U. and Schenk, O., editors, Combinatorial Scientic Computing, Chapman-Hall/CRC Computational Science, pages 95–128. Taylor & Francis.
Davis, T. A. and Hu, Y. (2011). The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software, (1):1:1 – 1:25.
Duff, I. S. and Koster, J. (2000). On algorithms for permuting large entries to the diagonal of a sparse matrix. SIAM J. Matrix Anal. Appl., 22(4):973–996.
Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23:298–305.
Hogg, J. and Scott, J. (2015). On the use of suboptimal matchings for scaling and ordering sparse symmetric matrices. Numerical Linear Algebra with Applications.
Manguoglu, M., Koyutürk, M., Sameh, A. H., and Grama, A. (2010). Weighted matrix ordering and parallel banded preconditioners for iterative linear system solvers. SIAM J. Sci. Comput., 32(3):1201–1216.
Manguoglu, M., Sameh, A. H., and Schenk, O. (2009). PSPIKE: A parallel hybrid In Sips, H., Epema, D., and Lin, H.-X., editors, Eurosparse linear system solver. Par 2009 Parallel Processing, volume 5704 of LNCS, pages 797–808. Springer Berlin Heidelberg.
Manne, F. and Sørevik, T. (1995). Optimal partitioning of sequences. J. Algorithms, 19(2):235–249.
Pinar, A. and Aykanat, C. (2004). Fast optimal load balancing algorithms for 1d partitioning. J. Parallel Distrib. Comput., 64(8):974–996.
Polizzi, E. and Sameh, A. H. (2006). A parallel hybrid banded system solver: The SPIKE algorithm. Parallel Comput., 32(2):177–194.
Polizzi, E. and Sameh, A. H. (2007). SPIKE: A parallel environment for solving banded linear systems. Computers & Fluids, 36(1):113–120.
Sathe, M., Schenk, O., Uçar, B., and Sameh, A. (2012). A Scalable Hybrid Linear Solver Based on Combinatorial Algorithms. In Naumann, U. and Schenk, O., editors, Combinatorial Scientic Computing, Chapman-Hall/CRC Computational Science, pages 95–128. Taylor & Francis.
Publicado
18/10/2015
Como Citar
LUGON, Brenno; CATABRIGA, Lucia; RANGEL, Maria; DE LIMA, Leonardo.
Impacto de estratégias combinatórias no precondicionador paralelo híbrido SPIKE. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 16. , 2015, Florianópolis.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2015
.
p. 120-131.
DOI: https://doi.org/10.5753/wscad.2015.14277.
