Open AccessA scalable algorithm for solving non-stationary linear programming problems
Author(s) -
Irina M. Sokolinskaya,
Leonid B. Sokolinsky
Publication year - 2018
Publication title -
vyčislitelʹnye metody i programmirovanie
Language(s) - English
Resource type - Journals
eISSN - 1726-3522
pISSN - 0507-5386
DOI - 10.26089/nummet.v19r448
Subject(s) - spmd , scalability , computation , computer science , metric (unit) , parallel computing , linear programming , algorithm , mathematical optimization , mathematics , engineering , operations management , database
Статья посвящена исследованию алгоритма NSLP для решения нестационарных задач линейного программирования сверхбольшой размерности, ориентированного на кластерные вычислительные системы. В основе анализа лежит модель параллельных вычислений BSF, основанная на моделях BSP и SPMD. Даются краткие описания алгоритма NSLP и модели BSF. Рассматривается реализация алгоритма NSLP в виде BSF-программы. На базе стоимостной метрики модели BSF выводится верхняя граница масштабируемости алгоритма NSLP и оценивается эффективность его параллелизации. Описывается реализация алгоритма NSLP на основе программного каркаса BSF на языке Си и приводятся результаты экспериментов, исследующих масштабируемостьуказанной реализации на модельной задаче линейного программирования. Делается сравнение результатов, полученных аналитическим и экспериментальным путем. This paper is devoted to the scalability study of an NSLP algorithm for solving non-stationary high-dimension linear programming problems on cluster computing systems. The analysis is based on the BSF model of parallel computations. TheBSF model is a new parallel computation model designed on the basis of BSP and SPMD models. The brief descriptions of the NSLP algorithm and the BSF model are given. The NSLP algorithm implementation in the form of a BSF program isconsidered. On the basis of the BSF cost metric, the upper bound of the NSLP algorithm scalability is derived and its parallel efficiency is estimated. The NSLP algorithm implementation using BSF skeleton is described. The scalability estimates obtained analytically and experimentally are compared.