Non-Stationary Acceleration Strategies for PageRank Computing

Empreu sempre aquest identificador per citar o enllaçar aquest ítem http://hdl.handle.net/10045/97000
Información del item - Informació de l'item - Item information
Títol: Non-Stationary Acceleration Strategies for PageRank Computing
Autors: Migallón Gomis, Héctor | Migallón, Violeta | Penadés, Jose
Grups d'investigació o GITE: Computación de Altas Prestaciones y Paralelismo (gCAPyP)
Centre, Departament o Servei: Universidad de Alicante. Departamento de Ciencia de la Computación e Inteligencia Artificial
Paraules clau: PageRank | Power method | Non-stationary iterations | Parallel processing | Distributed shared memory | Hybrid MPI/OpenMP
Àrees de coneixement: Ciencia de la Computación e Inteligencia Artificial
Data de publicació: 1-d’octubre-2019
Editor: MDPI
Citació bibliogràfica: Migallón H, Migallón V, Penadés J. Non-Stationary Acceleration Strategies for PageRank Computing. Mathematics. 2019; 7(10):911. doi:10.3390/math7100911
Resum: In this work, a non-stationary technique based on the Power method for accelerating the parallel computation of the PageRank vector is proposed and its theoretical convergence analyzed. This iterative non-stationary model, which uses the eigenvector formulation of the PageRank problem, reduces the needed computations for obtaining the PageRank vector by eliminating synchronization points among processes, in such a way that, at each iteration of the Power method, the block of iterate vector assigned to each process can be locally updated more than once, before performing a global synchronization. The parallel implementation of several strategies combining this novel non-stationary approach and the extrapolation methods has been developed using hybrid MPI/OpenMP programming. The experiments have been carried out on a cluster made up of 12 nodes, each one equipped with two Intel Xeon hexacore processors. The behaviour of the proposed parallel algorithms has been studied with realistic datasets, highlighting their performance compared with other parallel techniques for solving the PageRank problem. Concretely, the experimental results show a time reduction of up to 58.4% in relation to the parallel Power method, when a small number of local updates is performed before each global synchronization, outperforming both the two-stage algorithms and the extrapolation algorithms, more sharply as the number of processes increases.
Patrocinadors: This research was supported by the Spanish Ministry of Science, Innovation and Universities Grant RTI2018-098156-B-C54, co-financed by the European Commission (FEDER funds).
URI: http://hdl.handle.net/10045/97000
ISSN: 2227-7390
DOI: 10.3390/math7100911
Idioma: eng
Tipus: info:eu-repo/semantics/article
Drets: © 2019 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
Revisió científica: si
Versió de l'editor: https://doi.org/10.3390/math7100911
Apareix a la col·lecció: INV - gCAPyP - Artículos de Revistas

Arxius per aquest ítem:
Arxius per aquest ítem:
Arxiu Descripció Tamany Format  
Thumbnail2019_Migallon_etal_Mathematics.pdf890,99 kBAdobe PDFObrir Vista prèvia


Aquest ítem està subjecte a una llicència de Creative Commons Llicència Creative Commons Creative Commons