Open AccessMultilevel procedure for decomposition and mapping graphs
Author(s) -
Н. В. Старостин,
M A Bykova,
S V Nebaikin
Publication year - 2020
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1679/3/032017
Subject(s) - computer science , decomposition , multiprocessing , task (project management) , parallel computing , decomposition method (queueing theory) , metis , software , execution time , programming language , mathematics , ecology , management , discrete mathematics , world wide web , economics , biology
The paper analyzes the actual problem of architecture-dependent decomposition, allowing efficient planning of running a parallel task in a multiprocessor computer network. The procedure of planning means decomposition of a parallel task in a required number of processors accounting for balance restrictions and mapping of obtained portions to processors in order to minimize interprocessor communication costs. This procedure allows to reduce parallel program execution time and consequently expensive hardware usage time. The paper provides general mathematical formulation of this problem, and special cases are considered. Multilevel algorithms are suggested for a special and a general case of the problem. Results of experiments in well-known benchmarks as compared to renowned software METIS and SCOTCH.