The algorithm implemention is shown in the figure below:
There are 6 functional blocks as shown in the figure:
- Get_Unselected_V is responsible to load the next set of vertexs 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 vertexs, and assigned random-weights to each of them.
- Check_V module check vertexs and their connecting edges, if the random-weights of current is the smallest around its’ neighbours, then label it as MIS set members; if not, do nothing and move to next candidate
- Update_CS module check the labeled status for vertexed, if it is labeled as MIS set member, it would be removed from waiting group and also its’ neighbours.
- Mem_sync update all vertex status for processed vertex.
This processing repeat utils there is no selected vertex for current round.