Implementation - 2023.2 English

Vitis Libraries

Release Date
2023.2 English

The algorithm implemention is shown in the figure below:

Figure 1 Maximal Independen Set (MIS) design

There are 6 functional blocks as shown in the figure:

  1. Get_Unselected_V is responsible to load the next set of vertexs which are labeled as unselected and pass it to the Get_degree.
  2. Get_degree get all degrees for each vertex and pass them to the next module.
  3. V_edge_stream extract all edges for input vertexs, and assigned random-weights to each of them.
  4. 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
  5. 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.
  6. Mem_sync update all vertex status for processed vertex.

This processing repeat utils there is no selected vertex for current round.