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. С. 60-68.
The paper considers the urgent problem of architecture-dependent 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 architecture-dependent 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 well-known software products. Keywords: architecture-dependent decomposition, mapping, parallel code, supercomputer, multilevel algorithm.
|
English
