Geodesic
Parallel algorithm for computing points on a computation front hyperplane
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 1, pp. 145-152 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A parallel algorithm for computing points on a computation front hyperplane is described. This task arises in the computation of a quantity defined on a multidimensional rectangular domain. Three-dimensional domains are usually discussed, but the material is given in the general form when the number of measurements is at least two. When the values of a quantity at different points are internally independent (which is frequently the case), the corresponding computations are independent as well and can be performed in parallel. However, if there are internal dependences (as, for example, in the Gauss–Seidel method for systems of linear equations), then the order of scanning points of the domain is an important issue. A conventional approach in this case is to form a computation front hyperplane (a usual plane in the three-dimensional case and a line in the two-dimensional case) that moves linearly across the domain at a certain angle. At every step in the course of motion of this hyperplane, its intersection points with the domain can be treated independently and, hence, in parallel, but the steps themselves are executed sequentially. At different steps, the intersection of the hyperplane with the entire domain can have a rather complex geometry and the search for all points of the domain lying on the hyperplane at a given step is a nontrivial problem. This problem (i.e., the computation of the coordinates of points lying in the intersection of the domain with the hyperplane at a given step in the course of hyperplane motion) is addressed below. The computations over the points of the hyperplane can be executed in parallel. 
@article{ZVMMF_2015_55_1_a12,
     author = {M. M. Krasnov},
     title = {Parallel algorithm for computing points on a computation front hyperplane},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {145--152},
     year = {2015},
     volume = {55},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_1_a12/}
}
TY  - JOUR
AU  - M. M. Krasnov
TI  - Parallel algorithm for computing points on a computation front hyperplane
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2015
SP  - 145
EP  - 152
VL  - 55
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_1_a12/
LA  - ru
ID  - ZVMMF_2015_55_1_a12
ER  - 
%0 Journal Article
%A M. M. Krasnov
%T Parallel algorithm for computing points on a computation front hyperplane
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2015
%P 145-152
%V 55
%N 1
%U http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_1_a12/
%G ru
%F ZVMMF_2015_55_1_a12
M. M. Krasnov. Parallel algorithm for computing points on a computation front hyperplane. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 1, pp. 145-152. http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_1_a12/

[1] Nvidia CUDA, http://www.nvidia.com/object/cuda_home_new.html

[2] Intel Xeon Phi, http://www.intel.com/content/www/us/en/processors/xeon/xeon-phi-detail.html

[3] Andrianov A. N., Efimkin K. N., Zadykhailo I. B., Podderyugina N. V., “Yazyk Norma”, Preprinty IPM im. M. V. Keldysha, 1985, 165

[4] Zadykhailo I. B., Pimenov S. P., “Semantika yazyka Norma”, Preprinty IPM im. M. V. Keldysha, 1986, 139

[5] Andrianov A. N., “Organizatsiya tsiklicheskikh vychislenii v yazyke Norma”, Preprinty IPM im. M. V. Keldysha, 1986, 171

[6] Andrianov A. N., Sintez parallelnykh i vektornykh programm po neprotsedurnoi zapisi na yazyke Norma, Diss. ... kand. fiz.-matem. nauk, M., 1990

[7] Andrianov A. N., Sistema Norma. Razrabotka, realizatsiya i ispolzovanie dlya resheniya zadach matematicheskoi fiziki na parallelnykh EVM, Diss. ... dokt. fiz.-matem. nauk, M., 2001

[8] DVM sistema, http://www.keldysh.ru/dvm

[9] Krasnov M. M., Feodoritova O. B., “Operatornaya biblioteka dlya resheniya trekhmernykh setochnykh zadach matematicheskoi fiziki s ispolzovaniem graficheskikh plat s arkhitekturoi CUDA”, Preprinty IPM im. M. V. Keldysha, 2013, 009 http://library.keldysh.ru/preprint.asp?id=2013-9

[10] Metod Gaussa–Zeidelya, http://ru.wikipedia.org/wiki/Metod_Gaussa_-_Zeidelya

[11] Lamport L., “The parallel execution of DO loops”, Communications of the ACM, 17:2, February (1974), 83–93 | DOI

[12] Reingolt E., Nivergelt Yu., Deo N., Kombinatornye algoritmy. Teoriya i praktika, Mir, M., 1980

[13] Khu T., Tselochislennoe programmirovanie i potoki v setyakh, Mir, M., 1974

[14] Latsis A. O., Parallelnaya obrabotka dannykh, “Akademiya”, M., 2010