MULTILEVEL ALGORITHMS OF DECOMPOSING A DATA GRAPH FOR PARALLEL SIMULATIONS ON A HETEROGENEOUS COMPUTER SYSTEM
N. V. Starostin, M. A. Pankratova VANT. Ser.: Mat. Mod. Fiz. Proc 2016. Вып.1. С. 6068.
The paper considers the urgent problem of architecturedependent decomposition that allows effectively planning a parallel job execution on a multiprocessor. “Planning” means decomposing the given parallel job for a required number of processors with regard to balance limitations and allocating the obtained portions of the job to the processors to minimize the cost of interprocessor communications. The procedure allows reducing the parallel code runtime. A mathematical formulation of the general problem of architecturedependent decomposition is given, its special cases are discussed, and two multilevel computational algorithms are presented. The first algorithm is based on recursively bisectioning the input problem data and the second one is based on sequentially relaxing the original data with further decomposing the data graph and solving the quadratic assignment problem. The algorithm execution results using test problems are compared with those obtained with the wellknown software products. Keywords: architecturedependent decomposition, mapping, parallel code, supercomputer, multilevel algorithm.
