Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Parallel Matching for Graph Partitioning on Shared Memory. / Rakitskiy, Anton A.; Trusov, Kirill V.
24th IEEE International Conference of Young Professionals in Electron Devices and Materials, EDM 2023; Novosibirsk; Russian Federation; 29 June 2023 до 3 July 2023. Institute of Electrical and Electronics Engineers (IEEE), 2023. стр. 1830-1833.Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Parallel Matching for Graph Partitioning on Shared Memory
AU - Rakitskiy, Anton A.
AU - Trusov, Kirill V.
N1 - The research was carried out within the state assignment of Ministry of Science and Higher Education of the Russian Federation (theme No. 123022200042-8). Публикация для корректировки.
PY - 2023
Y1 - 2023
N2 - Graph partitioning may require a considerable amount of time for large-scale problems and one of the most time-consuming phases is finding maximal matching for graph coarsening. Approaches to find approximately maximal matching uses heuristic strategies to obtain balance between quality and performance, for example, there are used random matching and heavy edge matching approaches for unweighted and weighted undirected graphs respectively. In this paper we present the parallel algorithms for these techniques to increase the performance and maintain matching quality for multi-core systems. The main idea of this approach is to distribute vertices into subsets, perform matching in parallel and launch the serial matching algorithm for unmatched vertices to obtain better quality. Serial phase requires much less time, because after parallel phase number of vertices that are checked for possible matching considerably decreases. Setting minimum size of the subsets helps to reduce number of vertices for processing in serial phase. The potential acceleration is up to number of used processes.
AB - Graph partitioning may require a considerable amount of time for large-scale problems and one of the most time-consuming phases is finding maximal matching for graph coarsening. Approaches to find approximately maximal matching uses heuristic strategies to obtain balance between quality and performance, for example, there are used random matching and heavy edge matching approaches for unweighted and weighted undirected graphs respectively. In this paper we present the parallel algorithms for these techniques to increase the performance and maintain matching quality for multi-core systems. The main idea of this approach is to distribute vertices into subsets, perform matching in parallel and launch the serial matching algorithm for unmatched vertices to obtain better quality. Serial phase requires much less time, because after parallel phase number of vertices that are checked for possible matching considerably decreases. Setting minimum size of the subsets helps to reduce number of vertices for processing in serial phase. The potential acceleration is up to number of used processes.
UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85172016560&origin=inward&txGid=b12b7053a106dc3947bd91f66c4bc9ac
UR - https://www.mendeley.com/catalogue/2a1df23e-6d3b-3046-9736-e7ba08daa98c/
U2 - 10.1109/edm58354.2023.10225180
DO - 10.1109/edm58354.2023.10225180
M3 - Conference contribution
SN - 9798350336870
SP - 1830
EP - 1833
BT - 24th IEEE International Conference of Young Professionals in Electron Devices and Materials, EDM 2023; Novosibirsk; Russian Federation; 29 June 2023 до 3 July 2023
PB - Institute of Electrical and Electronics Engineers (IEEE)
ER -
ID: 59175570