Реализация параллельного алгоритма Флойда-Уоршелла

Доброго времени суток! Буквально пару дней назад я опубликовал реализацию линейного алгоритма Флойда-Уоршелла поиска кротчайших путей между всеми вершинами взвешенного графа. В той статье я обещал разобраться и реализовать параллельный алгоритм Флойда-Уоршелла, прошло несколько дней и родилась эта статья.

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

В качестве инструмента будет использована уже знакомая библиотека MPICH(установка библиотеки).

Схема параллельного алгоритма Флойда-Уоршелла

В оригинальном линейном алгоритме единственная операция это нахождение минимума, как справедливо замечено в крохах источников, что я находил, ее нет смысла распараллеливать. Вся сложность алгоритма(О^3) заключается в полном переборе «матрицы смежности». Напомню, что я так называю матрицу размера NxN, в которой на пересечении i-й строки и j-го столбца стоит вес ребра из i-ой вершины в j-ую.

читать далее «Реализация параллельного алгоритма Флойда-Уоршелла»

Реализация алгоритма Флойда-Уоршелла на C/C++

Доброго времени суток, друзья! Сегодня моя копилка реализованных алгоритмов на графах пополнится алгоритмом поиска кратчайших путей между всеми вершинами в графе. Для начала перечислю алгоритмы, которые уже опубликованы на сайте.

Реализация поиска в ширину на графе;
Реализация поиска в глубину на графе;
Реализация топологической сортировки и поиска компонент сильной связности;

Реализация обычного алгоритма Флойда-Уоршелла нужна мне для того, чтобы запрограммировать параллельное вычисление этой задачи с помощью библиотеки MPI. Отчет о результатах распараллеливания я напишу уже совсем скоро(я очень на это надеюсь). А сейчас поговорим о стандартном алгоритме Флойда-Уоршелла.

Суть алгоритма Флойда-Уоршелла

Как я упомянул, алгоритм предназначен для нахождения кратчайших путей между всеми вершинами в графе. По сути он представляет собой простой перебор всех путей и выбор из них наименьшего. Перебор осуществляется по так называемой «матрице смежности» размера NxN, где N — количество вершин графа.

читать далее «Реализация алгоритма Флойда-Уоршелла на C/C++»

Реализация преобразования string to int на C/C++

Доброго времени суток! Такие функции, как stoi, atoi, atol, soul, stof, to_string и некоторые другие появились в стандарте C++11 и уже стали привычными. Особенно для пользователей Visual Studio версии 13 года и старше. Но бывают исключительные случаи, когда под рукой нет такого крутого инструмента, а только блокнот и старенький gcc. Либо инструмент есть, но он упорно отказывается работать с C++11.

Именно с такой проблемой я недавно столкнулся. Мне позарез нужно было конвертировать строку в целое число, а мой Eclipse даже через 2 часа шаманствования с бубном так и не стал дружить с функцией stoi. Было принято волевое решение написать свою реализацию преобразования string to int. Я остановился на реализации преобразования целых десятичных положительных и отрицательных чисел, этого вполне хватило.

Функция преобразования string  to int на C/C++

читать далее «Реализация преобразования string to int на C/C++»

Общение процессов в MPI

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

Набор статей про библиотеку MPI разрастается, поэтому я решил привести список предыдущих «серий». Итак, мы уже умеем:
устанавливать MPI в Linux Ubuntu
настраивать Eclipse для работы с MPI
писать простейшую программу с помощью базовых функций MPI

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

Функции отправки сообщения MPI_Send и MPI_Isend

В чем отличие блокирующих функций от неблокирующих? Первые сразу после отправки полностью останавливают выполнение программы до тех пор, пока отправленное сообщение не будет получено. Соответственно, вторые не останавливают исполнение программы. Наличие такого инструмента дает очень большой простор для творчества.

читать далее «Общение процессов в MPI»

Основные функции MPI и пример простейшей программы

Приветствую всех в третьей статье посвященной параллельному программированию с помощью библиотеки MPICH. В прошлых сериях мы научились устанавливать MPI в Linux Ubuntu и заставили Eclipse понимать код библиотеки. Наконец пришло время взяться за программирование. А какую программу должен написать каждый уважающий себя программист? Правильно, сегодня мы напишем «Hello World» на MPI, и заодно глянем на самые базовые функции библиотеки. Поехали!

Основные функции MPI

Я сейчас говорю о тех, которые помогут нам грамотно идентифицировать каждый процесс, чтобы управлять общей логикой приложения. Реализовано это следующим образом: все процессы делятся на группы, называемые коммуникаторами, при этом один процесс может находиться сразу в нескольких коммуникаторах. По умолчанию все процессы попадают в коммуникатор MPI_COMM_WORLD. Каждый процесс имеет порядковый номер в коммуникаторе, называемый рангом. Как правило, процесс с рангом 0 назначается главным, он рулит бизнес логикой приложения и раздает команды другим процессам, еще он может отвечать за вывод в консоль, если вывод предусмотрен.

читать далее «Основные функции MPI и пример простейшей программы»