Maximum weighted matching using the partitioned global address space model
Alicia Thorsen, Phillip Merkey, Fredrik Manne · 2009
Efficient parallel algorithms for problems such as maximum weighted matching are central to many areas of combinatorial scientific computing. Manne and Bisseling [13] presented a parallel approximation algorithm which is well suited to distributed memory computers. This algorithm is based on a distributed protocol due to Hoepman [9]. In the current paper, a partitioned global address space (PGAS) implementation is presented. PGAS programmers have the conveniences of using a shared memory model, which provides implicit communication between processes using normal loads and stores. Since the shared memory is partitioned according to the affinity of a process, one is also able to exploit data locality. This paper addresses the main differences between the PGAS and MPI implementations of the Manne-Bisseling algorithm. It highlights some advantages of using the PGAS model such as shorter, simpler code, similarity to the sequential algorithm, and options for fine-grained and coarsegrained communication. 1.