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