Faithin Omaha eBook Collection

Download or read book Scalable Graph and Mesh Algorithms on Distributed-memory Systems written by Thap Panitanarak and published by . This book was released on 2017 with total page pages. Available in PDF, EPUB and Kindle. Book excerpt: Big datasets are now becoming a standard quantity in large-scale data analysis; they involve social and information network, and scientific mesh computations. These datasets are commonly stored and processed across multiple machines due to limited capabilities (such as memory and CPU) of single machines. However, many available analysis tools are still lacking in terms of an ability to fully utilize existing distributed-memory architectures. As these datasets are usually processed and analyzed in the form of graphs or meshes, we propose scalable and efficient approaches for graph and mesh computations for distributed-memory systems in this dissertation. Although graph and mesh computations are closely related regarding their parallelization approaches, some of their unique characteristics still need to be addressed separately. Thus, we organize the dissertation into two parts. The first part is for distributed graph computations, and the second part is for distributed mesh computations.In the first part of the dissertation, we focus on graph computations. First, we study a problem of Single-Source Shortest Path (SSSP) by analyzing and evaluating three well-known SSSP algorithms, i.e, Dijkstra's, Bellman-Ford, and $\Delta$-stepping algorithms. We implement these algorithms to run on distributed-memory systems based on a bulk synchronous parallel model. Their performances are evaluated and compared. Next, we propose our SSSP algorithm by combining advantages of these SSSP algorithms and utilizing a two-dimensional (2D) graph layout for our graph data structures. Then, we extend our study of the 2D graph data structures and optimization approaches to other well-known graph algorithms including breadth-first search, approximate diameter, connected components, and PageRank on various real-world graphs. Our objective is to implement an efficient graph framework for distributed-memory systems that works efficiently for many graph algorithms on various graph types. Finally, we propose graph coloring algorithms that are scalable and can be efficiently used for both graph and mesh applications.In the second part of the dissertation, we focus on parallel mesh computations on distributed-memory systems. First, we propose a domain decomposition method for 2D parallel mesh generation based on the MeTis partitioner with angle improvements. Our method is fast and gives good subdomain quality in terms of subdomain angles and mesh quality. Next, we propose a general-purpose parallel mesh warping method based on a parallel formulation of a sequential, log barrier-based mesh warping algorithm called LBWARP. Our parallel algorithm utilizes a modified distributed graph data structure with a vertex ghosting technique resulting in an efficient mesh warping algorithm which employs minimal communication. Since the algorithm needs to solve a sparse linear system with three right-hand sides (for 3D meshes), i.e., are each for the final $x$-, $y$- and $z$-coordinates in the deformed meshes, we also provide three parallel sparse linear solvers that support multiple right-hand sides for users to choose from based on the size of the problem and the number of available cores. These solvers further improve the overall performance of the algorithm, especially when a sequence of multiple deformations is required.