{"id":3276,"date":"2024-08-21T12:37:52","date_gmt":"2024-08-21T11:37:52","guid":{"rendered":"https:\/\/blogs.qub.ac.uk\/dipsa\/?p=3276"},"modified":"2025-05-09T18:01:53","modified_gmt":"2025-05-09T17:01:53","slug":"random-vertex-relabelling-in-laganlighter","status":"publish","type":"post","link":"https:\/\/blogs.qub.ac.uk\/dipsa\/random-vertex-relabelling-in-laganlighter\/","title":{"rendered":"Random Vertex Relabelling in LaganLighter"},"content":{"rendered":"\n

To evaluate the impacts of locality-optimizing reordering algorithms, a baseline is required. To create the baseline a random assignment of IDs to vertices may be used to produce a representation of the graph with reduced locality [ DOI:10.1109\/ISPASS57527.2023.00029<\/a>, DOI:10.1109\/IISWC53511.2021.00020<\/a> ].<\/p>\n\n\n\n

To that end, we create the random_ordering()<\/code> function in relabel.c<\/a> file. It consists a number of iterations. In each iteration, concurrent threads traverse the list of vertices and assign them new IDs. The function uses xoshiro<\/a> to produce random numbers.<\/p>\n\n\n\n

The alg4_randomize<\/a> tests this function for a number of graphs. For each dataset, an initial plot of degree distribution of Neighbor to Neighbor Average ID Distance (N2N AID<\/strong>) [DOI:10.1109\/IISWC53511.2021.00020<\/a>] is created. Also, after each iteration of random_ordering()<\/code> the N2N AID distribution is plotted. This shows the impacts of randomization.<\/p>\n\n\n\n

The complete results for all graphs can be seen in this PDF file<\/a>. The results for some graphs are in the following.<\/p>\n\n\n\n