The algorithm implementation is shown in the following figure:
There are six functional blocks as shown in the figure:
- Get_Unselected_V is responsible to load the next set of vertices, which are labeled as unselected and pass it to the Get_degree.
- Get_degree: get all degrees for each vertex and pass them to the next module.
- V_edge_stream: extract all edges for input vertices, and assigned random-weights to each of them.
- Check_V module: check vertices and their connecting edges. If the random-weights of current is the smallest around its neighbors, label it as the MIS set members. If not,move to next candidate.
- Update_CS module: check the labeled status for vertexed. If it is labeled as an MIS set member, it along with the neighbors,are removed from the waiting group.
- Mem_sync: update all vertex status for processed vertex.
This processing repeat until there is a selected vertex for the current round.