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

Question

[Perzh]

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

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

P.P.S.: естественно, ответ на все эти вопросы займет много времени и места, поэтому буду рад, если посоветуете хорошие книги по этой теме (желательно на русском).
Заранее спасибо

Answer 1

[Ilya Evseev]

Обязательно MPI? Не MPI2? В MPI2 есть операции, расчитанные на быструю работу поверх shared memory.

Comments

[Perzh]

Думаю можно использовать и MPI 2. Вы имеете в виду MPI_get() и MPI_Put()?

[Ilya Evseev]

Да, их. MPI2 one-sided RMA operations. Но использует ли общую память та или иная реализация mpi2, надо проверять. Особенно если это MPICH.

Answer 2

[Ilya Evseev]

буду рад, если посоветуете хорошие книги по этой теме (желательно на русском).

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