Параллельная реализация поиска кратчайшего пути с помощью MPI

Здравствуйте. Собственно, нужно организовать параллельный расчет кратчайшего пути с помощью MPI, причем выполняться он будет на одной машине. Можно использовать алгоритм Флойда или Дейкстры. В связи с этим я уже три дня ломаю голову, как бы это сделать, так сказать, в духе MPI, но так ничего дельного и не придумал. Мне вообще кажется, что подобную задачу трудно разделить на независимые части, поэтому все время хочется как то использовать многопоточность и общую память. Поэтому возникли следующие вопросы:
- стоит ли пытаться организовать общую память между процессами, в которой хранилась бы матрица смежности или лучше все таки пользоваться обменом сообщениями между процессами?
- как вообще обычно организовывают общую память для вычислительных узлов в кластерах и трудно ли это?

P.S.: пока гуглил по этому вопросу встречал такие мысли, что "в хорошо распараллеленном приложении на собственно взаимодействие между ветвями (пересылки данных и синхронизацию) тратится небольшая доля времени" или "в хорошо распараллеленом алгоритме не требуются барьеры". Как по вашему, можно ли Флойда или Дейкстра "хорошо распараллелить"?

P.P.S.: естественно, ответ на все эти вопросы займет много времени и места, поэтому буду рад, если посоветуете хорошие книги по этой теме (желательно на русском).
Заранее спасибо
  • Вопрос задан
  • 4228 просмотров
Решения вопроса 2
IlyaEvseev
@IlyaEvseev
Opensource geek
Обязательно MPI? Не MPI2? В MPI2 есть операции, расчитанные на быструю работу поверх shared memory.
Ответ написан
IlyaEvseev
@IlyaEvseev
Opensource geek
буду рад, если посоветуете хорошие книги по этой теме (желательно на русском).

раньше основная подборка была здесь: parallel.ru/tech/tech_dev/mpi.html
и немного есть здесь: ilya-evseev.narod.ru/articles/#csa
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы