Geodesic
Scalability evaluation of Cimmino algorithm for solving systems of linear inequalities on cluster computing systems
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 8 (2019) no. 1, pp. 20-35

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper is devoted to a scalability study of Cimmino algorithm for linear inequality systems. This algorithm belongs to the class of iterative projection algorithms. For the analytical analysis of the scalability, the BSF (Bulk Synchronous Farm) parallel computation model is used. An implementation of the Cimmino algorithm in the form of operations on lists using higher-order functions Map and Reduce is presented. An analytical estimation of the upper scalability bound of the algorithm for cluster computing systems is derived. Information about the implementation of Cimmino algorithm on lists in C++ language using the BSF program skeleton and MPI parallel programming library is given. The results of large-scale computational experiments performed on a cluster computing system are demonstrated. A conclusion about the adequacy of the analytical estimations by comparing them with the results of computational experiments is made.
Keywords: Cimmino algorithm, system of linear inequalities, iterative algorithm, projection algorithm, parallel computation model, BSF, scalability estimation, speedup, parallel efficiency, cluster computing systems. 
@article{VYURV_2019_8_1_a1,
     author = {I. M. Sokolinskaya and L. B. Sokolinsky},
     title = {Scalability evaluation of {Cimmino} algorithm for solving systems of linear inequalities on cluster computing systems},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {20--35},
     publisher = {mathdoc},
     volume = {8},
     number = {1},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2019_8_1_a1/}
}
TY  - JOUR
AU  - I. M. Sokolinskaya
AU  - L. B. Sokolinsky
TI  - Scalability evaluation of Cimmino algorithm for solving systems of linear inequalities on cluster computing systems
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2019
SP  - 20
EP  - 35
VL  - 8
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VYURV_2019_8_1_a1/
LA  - ru
ID  - VYURV_2019_8_1_a1
ER  - 
%0 Journal Article
%A I. M. Sokolinskaya
%A L. B. Sokolinsky
%T Scalability evaluation of Cimmino algorithm for solving systems of linear inequalities on cluster computing systems
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2019
%P 20-35
%V 8
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VYURV_2019_8_1_a1/
%G ru
%F VYURV_2019_8_1_a1
I. M. Sokolinskaya; L. B. Sokolinsky. Scalability evaluation of Cimmino algorithm for solving systems of linear inequalities on cluster computing systems. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 8 (2019) no. 1, pp. 20-35. http://geodesic.mathdoc.fr/item/VYURV_2019_8_1_a1/