Scalability evaluation of Cimmino algorithm for solving systems of linear inequalities on cluster computing systems

I. M. Sokolinskaya, L. B. Sokolinsky

South Ural State University (pr. Lenina 76, Chelyabinsk, 454080 Russia)

Abstract: 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.

UDC: 519.688, 004.272.2

Received: 05.05.2018

DOI: 10.14529/cmse190102

Bibliographic databases:

•