Massively parallel | EPFL Graph Search

Massively parallel is the term for using a large number of computer processors (or separate computers) to simultaneously perform a set of coordinated computations in parallel. GPUs are massively parallel architecture with tens of thousands of threads. One approach is grid computing, where the processing power of many computers in distributed, diverse administrative domains is opportunistically used whenever a computer is available. An example is BOINC, a volunteer-based, opportunistic grid system, whereby the grid provides power only on a best effort basis. Another approach is grouping many processors in close proximity to each other, as in a computer cluster. In such a centralized system the speed and flexibility of the interconnect becomes very important, and modern supercomputers have used various approaches ranging from enhanced InfiniBand systems to three-dimensional torus interconnects. The term also applies to massively parallel processor arrays (MPPAs), a type of integrated

The LifeV library: engineering mathematics beyond the proof of concept

Simone Deparis, Luca Formaggia, Davide Forti

LifeV is a library for the finite element (FE) solution of partial differential equations in one, two, and three dimensions. It is written in C++ and designed to run on diverse parallel architectures, including cloud and high performance computing facilities. In spite of its academic research nature, meaning a library for the development and testing of new methods, one distinguishing feature of LifeV is its use on real world problems and it is intended to provide a tool for many engineering applications. It has been actually used in computational hemodynamics, including cardiac mechanics and fluid-structure interaction problems, in porous media, ice sheets dynamics for both forward and inverse problems. In this paper we give a short overview of the features of LifeV and its coding paradigms on simple problems. The main focus is on the parallel environment which is mainly driven by domain decomposition methods and based on external libraries such as MPI, the Trilinos project, HDF5 and ParMetis. Dedicated to the memory of Fausto Saleri.

2018

Round Compression for Parallel Matching Algorithms

Aleksander Madry, Slobodan Mitrovic

For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture the nature of large-scale computation. In particular, compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises in this context is though: can we leverage this additional power to obtain even faster parallel algorithms? A prominent example here is the maximum matching problem-one of the most classic graph problems. It is well known that in the PRAM model one can compute a 2-approximate maximum matching in O(logn) rounds. However, the exact complexity of this problem in the MPC framework is still far from understood. Lattanzi et al. (SPAA 2011) showed that if each machine has n(1+Omega(1)) memory, this problem can also be solved 2-approximately in a constant number of rounds. These techniques, as well as the approaches developed in the follow up work, seem though to get stuck in a fundamental way at roughly O(logn) rounds once we enter the (at most) near-linear memory regime. It is thus entirely possible that in this regime, which captures in particular the case of sparse graph computations, the best MPC round complexity matches what one can already get in the PRAM model, without the need to take advantage of the extra local computation power. In this paper, we finally refute that possibility. That is, we break the above O(logn) round complexity bound even in the case of slightly sublinear memory per machine. In fact, our improvement here is almost exponential: we are able to deliver a (2+epsilon)-approximate maximum matching, for any fixed constant epsilon > 0, in O (log logn)(2)) rounds. To establish our result we need to deviate from the previous work in two important ways that are crucial for exploiting the power of the MPC model, as compared to the PRAM model. Firstly, we use vertex-based graph partitioning, instead of the edge-based approaches that were utilized so far. Secondly, we develop a technique of round compression. This technique enables one to take a (distributed) algorithm that computes an O(1)-approximation of maximum matching in O(logn) independent PRAM phases and implement a super-constant number of these phases in only a constant number of MPC rounds.

ASSOC COMPUTING MACHINERY2018

Parallel subdomain solver strategies for the algebraic additive Schwarz preconditioner

Simone Deparis, Radu Popescu

Domain-decomposition (DD) methods are used in most, if not all, modern parallel implementations of finite element modeling software. In the solver stage, the algebraic additive Schwarz (AAS) domain-decomposition preconditioner represents a fundamental component and its performance and scalability are key to the overall performance of the solution process. The established approach to construct the preconditioner in a parallel MPI setting is with a 1-to-1 correspondence between the number of MPI processes and the number of AAS subdomains. In this paper, we describe our attempts to extend this paradigm with the possibility to assign more than one MPI process per AAS subdomain, with the goal of improving the overall performance of the AAS preconditioner on supercomputers with multicore nodes. We discuss the implementation of the new AAS preconditioner framework, based on two levels of MPI parallelism, and the performance of different subdomain solver strategies. Finally, we examine the behavior of our novel approach for a series of benchmark problems, performed with the LifeV parallel finite element library.

Elsevier Science Bv2016

Round Compression for Parallel Matching Algorithms

Aleksander Madry, Slobodan Mitrovic

ASSOC COMPUTING MACHINERY2018