Analytical Estimation of the Scalability of Iterative Numerical Algorithms on Distributed Memory Multiprocessors

Abstract

This article presents a new high-level parallel computational model named BSF - Bulk Synchronous Farm. The BSF model extends the BSP model to deal with the compute-intensive iterative numerical methods executed on distributed-memory multiprocessor systems. The BSF model is based on the master-worker paradigm and the SPMD programming model. The BSF model makes it possible to predict the upper scalability bound of a BSF-program with great accuracy. The BSF model also provides equations for estimating the speedup and parallel efficiency of a BSF-program.

Submitted to a special issue of Lobachevskii Journal of Mathematics on "Parallel Structure of Algorithms"

Cited by in corpus (5)

• BSF: a parallel computation model for scalability estimation of iterative numerical algorithms on cluster computing systems
• Scalable parallel algorithm for solving non-stationary systems of linear inequalities
• Visualizing Multidimensional Linear Programming Problems
• VaLiPro: Linear Programming Validator for Cluster Computing Systems
• FRaGenLP: A Generator of Random Linear Programming Problems for Cluster Computing Systems