Standard

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. p. 1830-1833.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Rakitskiy, AA & Trusov, KV 2023, Parallel Matching for Graph Partitioning on Shared Memory. in 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), pp. 1830-1833. https://doi.org/10.1109/edm58354.2023.10225180

APA

Rakitskiy, A. A., & Trusov, K. V. (2023). Parallel Matching for Graph Partitioning on Shared Memory. In 24th IEEE International Conference of Young Professionals in Electron Devices and Materials, EDM 2023; Novosibirsk; Russian Federation; 29 June 2023 до 3 July 2023 (pp. 1830-1833). Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/edm58354.2023.10225180

Vancouver

Rakitskiy AA, Trusov KV. Parallel Matching for Graph Partitioning on Shared Memory. In 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. p. 1830-1833 doi: 10.1109/edm58354.2023.10225180

Author

Rakitskiy, Anton A. ; Trusov, Kirill V. / Parallel Matching for Graph Partitioning on Shared Memory. 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. pp. 1830-1833

BibTeX

@inproceedings{8eb1712c37424233b4bbac0e89071df5,
title = "Parallel Matching for Graph Partitioning on Shared Memory",
abstract = "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.",
author = "Rakitskiy, {Anton A.} and Trusov, {Kirill V.}",
note = "The research was carried out within the state assignment of Ministry of Science and Higher Education of the Russian Federation (theme No. 123022200042-8). Публикация для корректировки.",
year = "2023",
doi = "10.1109/edm58354.2023.10225180",
language = "English",
isbn = "9798350336870",
pages = "1830--1833",
booktitle = "24th IEEE International Conference of Young Professionals in Electron Devices and Materials, EDM 2023; Novosibirsk; Russian Federation; 29 June 2023 до 3 July 2023",
publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

}

RIS

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