Documentation<\/strong><\/p>\n\n\n\n https:\/\/github.com\/DIPS-QUB\/LaganLighter\/tree\/main\/docs<\/strong><\/a><\/p>\n\n\n\n LaganLighter supports the following graph formats:<\/p>\n\n\n\n In addition to execution time, we use the PAPI<\/a> library to measure hardware counters such as L3 cache misses, hardware instructions, DTLB misses, and load and store memory instructions. ( As an example, the following execution of Thrifty<\/a>, shows that the “Zero Planting” step has been performed in 8.98 milliseconds and with a 8.22% load imbalance, while processors have been idle for 72.22% of the execution time, on average, in the “Initial Push” step.<\/p>\n\n\n\n <\/p>\n\n\n\n In order to assign consecutive partitions (vertices and\/or their edges) to each parallel processor, we initially divide partitions and assign a number of consecutive partitions to each thread. Then, we specify the order of victim threads in the work-stealing process. During the initialization of LaganLighter parallel processing environment (in A thread, first, steals jobs (i.e., partitions) from consequent threads in the same NUMA node and then from the threads in consequent NUMA nodes. As an example, the following image shows the stealing order of a 24-core machine with 2 NUMA nodes. This shows that thread 1 steals from threads 2, 3, …,11, and ,0 running on the same NUMA socket and then from threads 13, 14, …, 23, and 12 running on the next NUMA socket. <\/p>\n\n\n\n We use <\/p>\n\n\n\n As “we write bugs that in particular cases have been tested to work correctly”, we try to evaluate and validate the algorithms and their implementations. If you receive wrong results or you are suspicious about parts of the code, please contact us<\/a> or submit an issue<\/a>.<\/p>\n\n\n\n Licensed under the GNU v3 General Public License<\/a>, as published by the Free Software Foundation. You must not use this Software except in compliance with the terms of the License. Unless required by applicable law or agreed upon in writing, this Software is distributed on an “as is” basis, without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose, neither express nor implied. For details see terms of the License<\/a>. LaganLighter<\/a><\/strong><\/p>\n\n\n\nAlgorithms in This Repo<\/strong><\/h2>\n\n\n\n
\n
alg1_sapco_sort<\/code><\/li>\n\n\n\nalg2_thrifty<\/code><\/li>\n\n\n\nalg3_mastiff<\/code><\/li>\n\n\n\n
<\/li>\n<\/ul>\n\n\n\nCloning<\/strong><\/h2>\n\n\n\n
git clone https:\/\/github.com\/MohsenKoohi\/LaganLighter.git --recursive<\/code><\/p>\n\n\n\nGraph Types<\/h2>\n\n\n\n
\n
external git repository<\/li>\n<\/ul>\n\n\n\nMeasurements<\/strong><\/h2>\n\n\n\n
papi_(init\/start\/reset\/stop)<\/code> and (print\/reset)_hw_events<\/code> functions defined in omp.c<\/a><\/code>).
To measure load balance, we measure the total time of executing a loop and the time each thread spends in this loop (mt<\/code> and ttimes<\/code> in the following sample code). Using these values, PTIP macro (defined in omp.c<\/a><\/code>) calculates the percentage of average idle time (as an indicator of load imbalance) and prints it with the total time (mt<\/code>). <\/p>\n\n\n\nmt<\/strong> = - get_nano_time()\n#pragma omp parallel <\/strong>\n{\n unsigned tid = omp_get_thread_num();\n ttimes<\/strong>[tid] = - get_nano_time();\n\t\n #pragma omp for nowait<\/strong>\n for(unsigned int v = 0; v < g->vertices_count; v++)\n {\n \/\/ .....\n }\n ttimes<\/strong>[tid] += get_nano_time();\n}\nmt<\/strong> += get_nano_time();\nPTIP<\/strong>(\"Step ... \");\n<\/code><\/pre>\n\n\n\n![\"\"](\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/load-imbalance.jpg\")
<\/figure>\n\n\n\nNUMA-Aware and Locality-Preserving Partitioning and Scheduling<\/strong><\/h2>\n\n\n\n
initialize_omp_par_env<\/strong>()<\/code> function defined in file omp.c), for each thread, we create a list of threads as consequent victims of stealing. <\/p>\n\n\n\n![\"\"](\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Stealing-order.png\")
<\/figure>\n\n\n\ndynamic_partitioning_...()<\/strong><\/code> functions (in file partitioning.c) to process partitions by threads in the specified order. A sample code is in the following:<\/p>\n\n\n\nstruct dynamic_partitioning* dp = dynamic_partitioning_initialize<\/strong>(pe, partitions_count);\n\n#pragma omp parallel <\/strong>\n{\n unsigned int tid<\/strong> = omp_get_thread_num();\n unsigned int partition<\/strong> = -1U;\t\t\n\n while(1)<\/strong>\n {\n partition<\/strong> = dynamic_partitioning_get_next_partition<\/strong>(dp, tid, partition);\n if(partition == -1U)\n\t break<\/strong>; \n\n for(v = start_vertex[partition<\/strong>]; v < start_vertex[partition<\/strong> + 1]; v++)\n {\n\t\/\/ ....\n }\n }\n}\n\ndynamic_partitioning_reset<\/strong>(dp);\n<\/code><\/pre>\n\n\n\nBugs & Support<\/h2>\n\n\n\n
License<\/h2>\n\n\n\n
Copyright 2022 The Queen’s University of Belfast, Northern Ireland, UK<\/strong><\/p>\n\n\n\nRelated Posts<\/strong>
<\/h2>\n\n\n
![\"\"](\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2025\/01\/potra-150x150.jpg\")
<\/div>