2.2 Анализ сложности алгоритма

На каждом шаге алгоритм добавляет поток увеличивающего пути к уже имеющемуся потоку. Если пропускные способности всех рёбер — целые числа, легко доказать по индукции, что и потоки через все рёбра всегда будут целыми. Следовательно, на каждом шаге алгоритм увеличивает поток по крайней мере на единицу, следовательно, он сойдётся не более чем за O(f) шагов, где f — максимальный поток в графе. Можно выполнить каждый шаг за время O(E), где E — число рёбер в графе, тогда общее время работы алгоритма ограничено O(Ef).

Если величина пропускной способности хотя бы одного из рёбер — иррациональное число, то алгоритм может работать бесконечно, даже не обязательно сходясь к правильному решению. На рисунке 4 представлен псевдокод алгоритма Форда-Фалкерсона.

2.3 Псевдокод

Ford_Fulkerson(G, s, t)

1 for каждого ребра (u, v) є E[G]

2 do f[u,v] «-0

3 f[v,u] «- 0

4 while существует путь p из s в t в остаточной сети G_f

5 do сf(р) «— min {c_f(u, v) : (u, v) принадлежит р}

6 for каждого ребра (u, v) in p

7 do f[u,v] «- f[u] + c_f(p)

8 f[v,u] «- -f[u,v]

Рисунок 4 – Псевдокод алгоритма Форда-Фалкерсона

3 Распараллеленный вариант алгоритма

3.1 Библиотека omp.H

Разработчики OpenMP хотели предоставить простой способ создания потоков в приложениях, не требуя от программиста знаний о создании, синхронизации и уничтожении потоков, а также необходимости определения, сколько потоков следует создать. Для этого разработчики OpenMP создали независимый от платформы набор прагм, директив, вызовов функций и переменных среды, которые явным образом указывают компилятору, как и где именно следует вставить потоки в приложение. Большинство циклов можно распараллелить, вставив всего одну прагму непосредственно перед циклом. Более того, оставив исполнение рутинных функций компилятору и OpenMP, вы можете больше времени уделить определению того, какие циклы следует распараллелить, и как наилучшим образом изменить структуру алгоритмов для достижения максимальной производительности. Максимальная производительность OpenMP реализуется при использовании этого инструмента для распараллеливания "горячих точек", - наиболее трудоемких циклов в приложении.

Написание параллельного варианта сводится к написанию прагм. Прагмы – это директивы препроцессора, игнорируемые компиляторами, которые не поддерживают данную технологию. То есть программа, написанная с применением данной технологии, могут быть скомпилированы как последовательные, при том среда разработки не выдаст никакой ошибки. Список директив, использованных в данной работе:

1. #pragma omp parallel – открывает новый регион для распараллеливания внутренних инструкций. Программа делится на потоки, число которых можно указать с помощью функции omp_num_threads(int n), где n – число потоков.

2. #pragma omp for – применяется для распараллеливания итерационных циклических операций. То есть, несколько итераций выполняется параллельно на нескольких процессорах.

Так как потоки выполняют свои операции параллельно, то заканчивать свою работу будут в разное время, поэтому данный вариант распараллеливания будет бесполезен при использовании на задачах класса P = NP.