Паралелна версия на алгоритъма, omp библиотека
omp.h библиотека
Разработчиците на OpenMP искаха да предоставят лесен начин за създаване на нишки в приложения, без да се изисква от програмиста да знае как да създава, синхронизира и унищожава нишки или да определя колко нишки да създаде. За да направят това, разработчиците на OpenMP са създали независим от платформата набор от прагми, директиви, извиквания на функции и променливи на средата, които изрично казват на компилатора как и къде да вмъкне нишки в приложение. Повечето цикли могат да бъдат паралелизирани чрез вмъкване само на една прагма директно преди цикъла. Освен това, като оставите изпълнението на рутинните функции на компилатора и OpenMP, можете да отделите повече време за определяне кои цикли да паралелизирате и как най-добре да преструктурирате алгоритмите за максимална производителност. Максималната OpenMP производителност се реализира, когато се използва този инструмент за паралелизиране на „горещи точки“, най-отнемащите време цикли в приложение.
Писането на паралелна версия се свежда до писане на прагми. Прагмите са директиви за препроцесор, игнорирани от компилатори, които не поддържат тази технология. Тоест програма, написана с помощта на тази технология, може да бъде компилирана като последователна, докато средата за разработка няма да даде никаква грешка. Списък на директивите, използвани в тази работа:
1) #pragma omp parallel - отваря нов регион за паралелизиране на вътрешни инструкции. Програмата е разделена на нишки, чийто брой може да се посочи с помощта на функцията omp_num_threads(int n), където n е броят на нишките.
2) #pragma omp for - използва се за паралелизиране на итеративни циклични операции. Тоест няколко итерацииработи паралелно на множество процесори.
Тъй като нишките изпълняват своите операции паралелно, те ще завършат работата си по различно време, така че тази опция за паралелизиране ще бъде безполезна, когато се използва за задачи от клас P = NP.
Кратко описание на паралелизиране на алгоритъма
Процесът на паралелизиране на алгоритъма на Ford-Fulkerson се свежда до паралелизиране на обхождането на ширината на графиката. Ако, когато прилагате алгоритъма, за търсене на пътища в графиката, например, използвате алгоритъма за търсене първо в дълбочина, тогава паралелизирането не е възможно.
При паралелизиране се използва библиотеката omp.h, която използва инструментите на технологията OpenMP. Алгоритъмът е разделен на няколко нишки и всяка нишка изпълнява своя собствена част от програмата. Паралелизмът се реализира чрез записване на прагми в съответните кодови фрагменти. Фигура 5 показва кодов фрагмент, използващ прагмите по-долу. Пълният списък е в Приложение B.
Основната цел на паралелизирането беше да се анализира ускоряването на алгоритъма. На практика ускоряването се забелязва само при много големи набори от данни, но много малко. Очакваното ускорение, изчислено по формулата на Amdahl, при 25% от операциите, изпълнявани паралелно на 2 процесора, е 300% от последователното изпълнение, но на практика такова ускорение не е постигнато, поради редица фактори, влияещи върху скоростта на операциите.
Фигура 5 - Фрагмент от паралелизирания програмен код