Масштабируемый алгоритм для решения нестационарных задач линейного программирования
Соколинская И.М., Соколинский Л.Б.

Статья посвящена исследованию алгоритма NSLP для решения нестационарных задач линейного программирования сверхбольшой размерности, ориентированного на кластерные вычислительные системы. В основе анализа лежит модель параллельных вычислений BSF, основанная на моделях BSP и SPMD. Даются краткие описания алгоритма NSLP и модели BSF. Рассматривается реализация алгоритма NSLP в виде BSF-программы. На базе стоимостной метрики модели BSF выводится верхняя граница масштабируемости алгоритма NSLP и оценивается эффективность его параллелизации. Описывается реализация алгоритма NSLP на основе программного каркаса BSF на языке Си и приводятся результаты экспериментов, исследующих масштабируемость указанной реализации на модельной задаче линейного программирования. Делается сравнение результатов, полученных аналитическим и экспериментальным путем.

Ключевые слова: нестационарная задача линейного программирования сверхбольшой размерности, алгоритм NSLP, модель параллельных вычислений BSF, оценка масштабируемости, кластерные вычислительные системы.

Название статьи, аннотация и ключевые слова на английском языке

  • Соколинская И.М. – Южно-Уральский государственный университет, факультет вычислительной математики и информатики, просп. Ленина, 76, 454080, Челябинск; доцент, e-mail: irina.sokolinskaya@susu.ru
  • Соколинский Л.Б. – Южно-Уральский государственный университет, просп. Ленина, 76, 454080, Челябинск; проректор по информатизации, e-mail: Leonid.Sokolinsky@susu.ru