THIS IS NOT A GROUP PROJECT! You may talk about the project and possible solutions in general terms, but must not share code. In this project, you will be asked to implement two parallel graph matching algorithms. Your program should take a legal matrix-market matrix file as input and output the matching results.
This document is not a complete specification of the project. You will encounter important design and implementation issues that need to be addressed in your project solution. Identifying these issues is part of the project. As a result, you need to start early, allowing time for possible revisions of your solution.
Given a graph G = (V, E), while V is the set of vertices (also called nodes) and E ⊂ |V | 2 . A matching M in G is a set of pairwise non-adjacent edges which means that no two edges share a common vertex. A vertex is matched if it is an endpoint of one of the edges in the matching. Otherwise the vertex is unmatched [3]. In Figure 1, we show three different matchings for the same graph.
A maximum matching can be defined as a matching where the total weight of the edges in the matching is maximized. In Figure 1, (c) is a maximum matching because the total weight of the edges in the matching is 7, and there could be no other matching that has total weight greater than 7 for this graph.
The graph matching problem is not easy to parallelize. Most existing matching algorithms such as blossom algorithm are embarrassingly sequential. Here we describe two handshaking-based algorithms [2] that are amenable to parallelization.
1.2.1 One-Way Handshaking Matching
Given a graph G, two vertices shake hands only when there is an edge between these two and they are the strongest neighbor of each other. We will define “strongest neighbor”. The edge that connects the two handshaking vertices is added to the matching M. We show an example of one-way handshaking matching in Figure 2.
To identify handshaking vertices, each vertex v in G extends a hand to its strongest neighbor. Here the strongest neighbor of a vertex v is the neighbor vertex that sits on the maximum-weight edge incident to v. This is a greedy algorithm that aims to maximize the total weight in the matching. If there are multiple incident edges of v that have maximum weight, the neighbor vertex that has the smallest vertex index will be chosen as the strongest neighbor. For example, in Figure 2(b), the strongest neighbor of vertex E is vertex B because it has an edge weight of 4 and a smaller index (alphabetical order) than vertex F.
For each vertex, we check if its strongest neighbor extends a hand back. If so, these two vertices are matched. Then the corresponding edge will be added to the matching. For example, in Figure 2(c), vertex B extends a hand to vertex E and vertex E also extends a hand to vertex B, so edge BE will be added to the matching.
At every pass of the process, we check all the vertices that are not matched from previous passes (each vertex is checked once in each pass), and identify if there is any new edge that can be added to the matching. We repeat this until no more edges can be added to the matching. We show the passes in Figure 2(b), (c), (d),(e) and (f). The handshaking method is highly data parallel, since each vertex can be processed independently and there is no data race.
1.2.2 N-Way Handshaking Matching
In one-way handshaking matching, it is possible that one vertex will have extended hands from multiple neighbors, but at most one of these neighbors can be matched. This may affect the matching efficiency. For example, in Figure 2 (b), both vertex D and vertex H extend hands to vertex E. However, since vertex E’s strongest neighbor is vertex B, so neither vertex D nor H will be matched at this pass of handshaking in Figure 2 (b).
Instead of extending one hand, N-way handshaking matching allows each vertex to extend N hands (N > 1). We show an example of 2-way handshaking matching in Figure 3. In Figure 3(b), each vertex extends (up to) 2 hands at once, which extends to its strongest and second strongest neighbors. For example, vertex H extends one hand to vertex E which is its strongest neighbor and another hand to vertex I which is the second strongest neighbor.
In the next step, we take the edges whose two end points do not shake hands out of consideration (as if we “discard” edges). In Figure 3(b), there is no handshaking between vertex H and vertex E, so the edge HE is “as if” discarded (before next step in the same pass). After this, we will obtain an updated graph with a max degree N (N=2 in Figure 3(c)), we will refer to this graph as N-way graph in the remaining of the project description.
We now do one-way handshaking matching on the updated N-way graph. The matching on the N-way graph may yield more matched vertices. For example, in Figure 3(e), both vertex H and vertex D can be matched in the first pass, while compared with one-way matching in Figure 2, both vertex H and vertex D have to be matched in the second pass.
A thread is defined as an independent stream of instructions that can be scheduled to run in its own context. Multiple threads run in multiple active contexts.
Historically, hardware vendors have implemented their own proprietary versions of threads. For UNIX systems, a standardized C language threads programming interface has been specified by the IEEE POSIX 1003.1c standard. Implementations that adhere to this standard are referred to as POSIX threads, or pthreads[1].
For more details on how to use pthreads API to write a parallel program and how to compile a pthreads program, please refer to the pthread tutorial [1] and the recitations.
In this project, you will be asked to do the following:
1) implement the parallel one-way handshaking matching algorithm
2) Extra Credit: implement the parallel N-way handshaking matching algorithm
Un-directed weighted graph In this project, we use adjacency lists to represent an undirected weighted graph. There are four arrays: index[], offset[], degree[], and weight[]. The array index[] keeps the neighbor lists of all vertices, for instance, node v 0 ’s neighbor list is followed by neighbor v 1 ’s neighbor list, and so on. The array offset[] stores where a node’s neighbor list starts in the index[] array. The corresponding weight[] array stores the weight of each edge. The array degree[] stores the degree of each vertex, which is the number of neighbors for each vertex.
An example of adjacency array representation is shown in Figure 4. For vertex v 2 , its degree is 2 (degree[2] = 2). The offset[2] value is 5 which means its neighbor list starts at index[5], thus index[5] = 5 (corresponding to vertex v 5 ), index[6] = 1 (corresponding to vertex v 1 ), and vertex v 5 and vertex v 1 are two neighbors of vertex v 2 .
Pleas be aware that within a neighbor list (of a specific vertex), the neighbors are sorted in descending order such that the strongest neighbor is always placed as the first item and the second strongest neighbor is placed as the second item and so on. We already sorted the neighbors of each vertex for you. You do not have to sort them to find the strongest neighbor, however, you do need to filter out the nodes that are already matched from previous passes.