Implementation of Improved Parallel Stable Matching Algorithms

Undergraduate #245
Discipline: Computer Sciences and Information Management
Subcategory: Computer Science & Information Systems
Session: 1
Room: Exhibit Hall A

Michael Mandulak - Salisbury University
Co-Author(s): Enyue Lu, Salisbury University, MD

---

The stable marriage problem, as introduced by Gale and Shapley, poses the question pertaining to the generation of a stable matching between given sets of n men and n women based on 2n ranking lists where each man (woman) ranks each woman (man) based on marital preference. A stable matching is noted as a matching of each man (woman) to a single woman (man) such that no man or woman prefers another partner over their currently matched partner. Gale and Shapley, alongside this problem proposal, introduced an algorithm, the GS algorithm, that guarantees a stable matching with a time complexity of O(n^2). This solution, however, is considered too inefficient for modern applications in networking and the general matching of two sets, leading to explorations in parallel solutions through high-performance computation. Such work has led to algorithms such as the Parallel Iterative Improvement (PII) algorithm and the Convergent Parallel Iterative Improvement (CPII) algorithm, which efficiently provide stable matchings using n^2 processing elements (PEs). While the PII algorithm has results supporting its run time complexity improvement upon the GS algorithm with a logarithmic growth trend, the algorithm faces a cycling issue, reducing the accuracy to approximately 90%. The CPII algorithm, however, claims a run time complexity similar to that of the PII algorithm but with a guarantee of a stable matching in every case. While this claim is assumed from the basis of the PII algorithm, implementation-based results are needed to justify the efficiency and accuracy hypotheses of the CPII algorithm. As such, implementation of both the PII and CPII algorithms was conducted for result verification purposes utilizing C++ and OpenMPI parallelization across a twenty node high-performance computing cluster (approximately four-hundred threads total). Following tests of both algorithms from all n between four and twenty (ten-thousand and two-thousand tests per n, respectively), the resulting before and after time data was graphed and evaluated based on growth trends as n increases. Based on the data, the PII algorithm followed the logarithmic growth trend as expected, while the CPII algorithm also closely followed this logarithmic trend up until n of nineteen, where the time taken to find a stable matching spiked. Due to the nature of run time complexity analysis, it is fair to assume that, since relatively small values of n are being tested, this increase in run time is the starting point for the algorithm’s growth trend, otherwise the n_0 of the time complexity analysis. Despite this run time concern, the data collected supports the notion of the CPII algorithm’s improvement upon the PII algorithm through the guarantee of a stable matching in every case. Future work includes further data collection for the CPII algorithm’?s run time analysis with a more capable high-performance computing cluster in order to exceed the n of twenty maximum placed by the hardware constraints.

Funder Acknowledgement(s): This work is funded by the National Science Foundation under the Research Experience for Undergraduates Program CNS1757017 grant. We would like to thank Professor Matthias K. Gobbert at the University of Maryland, Baltimore County (UMBC) for allowing us to use the UMBC High Performance Computing Facility.

Faculty Advisor: Enyue Lu, ealu@salisbury.edu

Role: For this research project, I have programmed both the PII algorithm and the CPII algorithm in C++ for run time data collection based on the research papers that introduce these algorithms. Similarly, I have written scripts to arbitrarily generate preference lists for testing and to compile resulting time data for graphical representation and statistical analysis. All of this followed the initial steps of research on parallel computation and OpenMPI as well as the history of the stable marriage problem itself.