Масштабируемый алгоритм для решения нестационарных задач линейного программирования

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