Simplex method on MPI
C Python C++
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
babazka_version
problem_generator
.gitignore
README.md
simplex.py
simplex_method.c
test.stud013.28847.trace.ttf.ttf
time_to_send.png
v23-128.pdf

README.md

Состояние проекта

  • simplex_method.c - алгоритм написанный на базе статьи из репозитория. На данный момент выдает некорректные результаты
  • simplex.py - модифицированная реализация на языке программирования Python. Является эталоном. Параллельна(можно переносить на С)
  • problem_generator - алгоритм генерации "правильных" случайных симплекс таблиц
  • папка babazka_version - содержит алгоритм, который не только работает, но еще и возвращает правильные результаты

Симплекс метод с ипользованием MPI

В данном репозитории находится версия симплекс метода, написанная с использованием MPI. Текущая реализация не является оптимальной и причина тому не очень правильно составленная перессылка данных. Изображение отображает временные затраты, на некоторые участки кода, из которых видно, что наибольшее количество времени тратиться на инициализацию данных и конечный сбор результатов.

Данный косяк можно обойте распаралелив и рассылку. К примеру, в случае с 12 процессами, мастер рассылает по трети данных: себе, четвертому и восьмому процессу. После получения, каждый из них, рассылает данные находящимся выше них(по нумерации) трем процессам. Аналогично и при получение, не все данные тут же шлются мастеру, а схлопываются по чуть-чуть.

Также для ускорения можно воспользоваться MPI структурами.

Алгоритм генерации исходных данных

Генерация исходных данных происходит по хитрому алгоритму, который обеспечивает большое количество итераций при решении симплекс метода. Алгоритм вроде бы построен для размещения точек в пространстве многогранника, расположенного в многомерном пространстве так, чтобы область не была близка к нулевым значениям.