New BSP/CGM algorithms for spanning trees. (May 2019)

• Record Type: Journal Article
• Authors: Vasconcellos, Jucele França de Alencar; Cáceres, Edson Norberto; Mongelli, Henrique; Song, Siang Wun; Dehne, Frank; Szwarcfiter, Jayme Luiz
• Other Names: Mencagli Gabriele guest-editor.; França Felipe MG guest-editor.; Bentes Cristiana Barbosa guest-editor.; Justen Marzulo Leandro Augusto guest-editor.; Lima Pilla Mauricio guest-editor.; Wyrzykowski Roman guest-editor.; Deelman Ewa guest-editor.
• Is Part Of: International journal of high performance computing applications. Volume 33:Number 3(2019)
• Page Start: 444
• Page End: 461
• Publication Date: 2019-05
• Subjects: Spanning tree -- minimum spanning tree -- parallel algorithm -- BSP/CGM model -- GPU; High performance computing -- Periodicals; Supercomputers -- Periodicals; 004.1105
• DOI: 10.1177/1094342018803672
• Languages: English
• ISSNs: 1094-3420

Abstract

Computing a spanning tree (ST) and a minimum ST (MST) of a graph are fundamental problems in graph theory and arise as a subproblem in many applications. In this article, we propose parallel algorithms to these problems. One of the steps of previous parallel MST algorithms relies on the heavy use of parallel list ranking which, though efficient in theory, is very time-consuming in practice. Using a different approach with a graph decomposition, we devised new parallel algorithms that do not make use of the list ranking procedure. We proved that our algorithms are correct, and for a graphG = ( V, E ), | V | = n, and| E | = m, the algorithms can be executed on a Bulk Synchronous Parallel/Coarse Grained Multicomputer (BSP/CGM) model usingO ( log p ) communications rounds withO ( n + m p ) computation time for each round. To show that our algorithms have good performance on real parallel machines, we have implemented them on graphics processing unit. The obtained speedups are competitive and showed that the BSP/CGM model is suitable for designing general purpose parallel algorithms.