Решаване на проблема с пътуващия търговец с паралелни изчисления

ВИСОКО ПРОИЗВОДИТЕЛНИ ТЕХНИЧЕСКИ ИЗЧИСЛЕНИЯ С MPI

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

• Литературен преглед
• Методика
• Резултати
• Заключение

Проучването представя ефективността на MPI при решаването на сложни проблеми с оптимизацията и подчертава потенциала на HPC клъстера за предоставяне на ефективни решения на такива проблеми. Резултатите демонстрират осъществимостта на използването на HPC клъстери за решаване на сложни проблеми по навременен и рентабилен начин, което го прави обещаващ подход.

Литературен преглед

HPC

Високопроизводителните изчисления (HPC) са област на компютърните науки, която е специализирана в изграждането и използването на мощни компютърни системи, включително клъстери и суперкомпютри. Тези системи са проектирани да се справят със сложни изчислителни предизвикателства и могат да извършват милиарди изчисления в секунда, което ги прави полезни в различни приложения като научни изследвания, инженерство и анализ на данни.

За да постигне паралелна изчислителна мощност, HPC използва специализиран хардуер и софтуер. Тези системи обикновено се изграждат с помощта на клъстери от високопроизводителни компютри, свързани в едно цяло. Хардуерните компоненти на тези системи са проектирани да увеличат максимално производителността, с многобройни взаимосвързани процесори, бързи връзки, достатъчно памет и съхранение. Освен това, специално разработен софтуер като интерфейса за предаване на съобщения (MPI) се използва за координиране на процесорите и им позволява да си сътрудничат и да се справят заедно със сложни изчислителни проблеми.

Проблем с скитащия търговец и NP HARD

WSP или проблемът с скитащия търговец е добре известно предизвикателство за оптимизация в компютърните науки. Това изисква намиране на възможно най-краткия път, който посещава набор от градове само веднъж. Този проблем се счита за NP-труден, което означава, че намирането на точно решение за по-големи случаи става изчислително непрактично.

NP-трудните проблеми, като категория, не могат да бъдат решени за полиномиално време с нито един известен алгоритъм. Следователно тяхното време за работа нараства бързо с размера на проблема, което прави намирането на точни решения трудно. Вместо това често се използват евристики или приблизителни решения за решаване на тези проблеми.

WSP има значително значение в различни области, като изследване на операциите, логистика и компютърни науки, и има множество приложения в реалния свят, като маршрутизиране на превозни средства, планиране и проектиране на вериги. Предизвикателството за решаване на WSP доведе до създаването на различни алгоритми, като точни алгоритми, алгоритми за приближение и евристики.

Клон и граница

Подходът Branch and Bound, наричан B&B, е стратегия, използвана за ефективно решаване на проблема с скитащия търговец. B&B използва систематичен подход за навигация в пространството на потенциални решения и намаляване на броя на клоновете за проучване.

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

Цели

Задача 1: Създайте сериен алгоритъм за решаване на алгоритъма за разклоняване и свързване

Задача 2: Проектирайте паралелен алгоритъм за решаване на проблема с скитащия търговец с помощта на MPI.

Задача 3:Тествайте паралелната програма в 17 града с различни методи на комуникация и оптимизация.

Задача 4: Измерете ефективността на вашите серийни и паралелни кодове и обсъдете.

Методика

Полумесец HPC клъстер

HPC инфраструктурата, използвана за този проект, е Crescent, изследователско съоръжение в университета Cranfield, което предлага 1488 налични ядра, разпределени в комбинация от типове възли, включително 2U шасита, отделни 1U и 2U възли. Тези възли са оборудвани с процесори Intel Sandy Bridge и Haswell, осигуряващи общо 16 до 32 ядра на възел и обхват на споделена памет от 64 GB до 256 GB. Съоръжението е подходящо за стартиране на MPI-базирани приложения, осигурявайки достатъчно изчислителни ресурси за проекта. [3]

MPI

В този проект ще използваме интерфейса за предаване на съобщения (MPI), за да паралелизираме нашия код и да използваме пълноценно наличните изчислителни ресурси в HPC инфраструктурата. MPI е библиотека, която позволява паралелно програмиране на разпределени системи, като позволява комуникация между множество процесори за координиране на изпълнението на задачата.

Друг модел на паралелно програмиране е OpenMP, използван главно за системи със споделена памет, където много нишки имат достъп до една и съща памет. MPI е по-подходящ за разпределени системи, където всеки процесор има собствена памет и комуникацията между процесорите е необходима за координиране на изчисленията.

Паралелизирането без споделена памет, както в случая с MPI, може да доведе до повече разходи от междупроцесна комуникация. Независимо от това, той е идеален избор за големи системи, където броят на процесорите надхвърля наличната споделена памет, което го прави оптимално решение за този проект.

Слабо и силно разпределение

По време на този проект ние внимателно ще управляваме и оптимизираме разпределението на задачите, за да избегнем слабо разпределение. Слабо разпределение възниква, когато разпределението на работата не води до намаляване на времето за изчисление, често поради времето, изразходвано за комуникация между екземпляри, надвишаващо времето, изразходвано за изчисление на действителната задача. За да смекчим това, ние ще се стремим да сведем до минимум времето за комуникация, доколкото е възможно, като същевременно гарантираме ефективното и ефективно разпределение на задачите. [6]

Алгоритми

В този проект ще оценяваме два алгоритъма — алгоритъмът Brute Force и алгоритъмът Branch and Bound. Алгоритъмът Brute Force ще работи, като изследва всеки път на дървото, докато алгоритъмът Branch and Bound ще бъде по-ефективен, като прави селективен избор кой път да изследва и подрязва дървото възможно най-скоро в процеса.

DFS

В този проект и двата алгоритъма ще използват алгоритъм за първо търсене в дълбочина (DFS) за изследване на дървото на потенциалните пътища. Алгоритъмът на DFS ще работи рекурсивно и ще търси дълбоко в дървото, като изследва отгоре надолу, отляво надясно.

Разклонение и граници

Алгоритъмът за клонове и граници се извиква рекурсивно и ще се опита да посети всички непосетени градове, започвайки от даден предварителен път. Алгоритъмът ще проверява всеки път дали цената на пътя чрез добавяне на непосетения град е под най-добрата цена, намерена досега. Ако случаят е такъв, алгоритъмът продължава DFS, ако не, той ще подкастри дървото, започвайки от този град, намалявайки възможността за по-нататъшно изследване. Както е представено от псевдокода на фигура 1.

Функцията за разклоняване и граници може да започне от всеки даден предварителен път, стига първоначалната му текуща цена и непосетеният град да се актуализират за дадения предварителен път. Този метод ще се използва широко за паралелизиране на алгоритъма за разклонения и граници сред всички наши процеси.

Забележка: за изследване с груба сила ще следваме същия принцип, използвайки DFS алгоритъм, разликата е, че никога няма да наблюдаваме дали текущата_цена е под най-добрата_цена, намерена досега, и все пак ще изследваме всички възможности на дървото.

Фигура 1: Алгоритъм за разклонения и граници на псевдокод:

function branch_and_bound(current_path, current_cost, best_cost):
    if length of current_path = num_cities:
        # Base case: if current cost < best cost update it
        best_cost = min(best_cost, current_cost)
    else:
        for each unvisited city in cities:
            # Calculate cost of adding the city to current path
            cost = calculate_cost(last_city, city)
            if current_cost + cost < best_cost:
                # Add the city to the current path
                new_path = current_path + [city]
                # Recursively call branch_and_bound with updated path and cost
                new_cost = branch_and_bound(new_path, current_cost + cost, best_cost)
                
# Initial call to branch_and_bound with an starting from city 0
branch_and_bound([0], 0, INT_MAX)

Паралелно изпълнение

За да се позволи ефективно паралелизиране на серийния код, предварителни пътеки на дървото ще бъдат генерирани и присвоени на всеки процес. Предварителният път ще ръководи процесите да работят в посока на дървото, така че да могат да извършват различни изчисления и да паралелизират работата по ефективен начин. Предварителната пътека ще бъде генерирана за X град в дълбочина на дървото, както е представено на Фигура 2, няколко реализации ще бъдат извършени и сравнени в секцията с резултати, за да се види най-ефективната.

След генерирането на предварителния път те ще бъдат разбъркани един в друг. Разместването на предварителния път е важно, защото ще помогне за балансиране на натоварването между всички процеси. Ще се възползваме от произволното преразпределение, така че един процес да не работи на конкретно място на дървото. Този метод ще гарантира, че работното натоварване е балансирано и че един процес няма да следва няколко трудни пътя подред, което ще създаде пречка в нашия софтуер.

След това предварителните пътища се присвояват между всички процеси. След това процесите ще преминат през списъка с пътища, присвоени на техния ранг, и ще изпълнят същия метод на разклоняване и обвързване, както при серийната реализация. Единствената разлика е, че те ще започнат от зададения им предварителен път.

При завършване на търсенето през предварителните пътеки, процесите ще се включат в комуникация между процесите, за да обменят своите изчислени минимални стойности на разходите (min_cost). Чрез използването на функцията MPI „ReduceAll“, процесите колективно ще определят глобалната минимална цена (min_global cost), която ще бъде използвана за по-ефективно подрязване на дървото в следващите итерации. Честотата на комуникация ще бъде анализирана в секцията с резултати, за да се оптимизира балансът между твърде много и твърде малко комуникация. Псевдокодът на паралелната реализация е представен на фигура 3.

Фигура 3: Псевдокод на паралелния алгоритъм

ALGORITHM parallel_wsp_branch_and_bounds:

1. Initialize variables and data structures

2. Read the input file and create the distance matrix 

3. Create all possible pre-paths:
   a. Generate all possible pre-paths for X cities deep
   b. Shuffle the pre-paths
   c. Distribute the pre-path shuffled amoung all processes

4. Loop through all pre-paths assigned:
   a. Initialize the curr-distance depending of the current pre-path
   b. Initialized the visited city for each city in the current pre-path
   c. Call the function `dfs` starting from the current pre-path
   d. Reduce the min_cost from all the processes

5. Print the final results

Комуникация

За комуникация между процесите по време на този проект ще бъдат използвани няколко метода. Повечето от комуникациите използват метода ReduceAll на MPI, за да поддържат само минималното разстояние между всеки процес. Неблокиращият IreduceAll също ще бъде внедрен и тестван, за да видим дали можем да се възползваме от буфера в нашия HPC клъстер за подобряване на ефективността.

В допълнение, софтуерът ще следи времето на празен ход на всеки процес с цел подобряване, така че да можем да сравним ефекта на различни параметри върху нашата реализация. Времето на неактивност ще се наблюдава за всяка комуникация на синхронизирани контролни точки и нараствания в променлива. След това времето на неактивност за процес ще бъде отпечатано в края на изчислението.

Без излъчване

При паралелния подход изборът беше направен така, че всички процеси да прочетат входния файл и да създадат своя собствена матрица на разстоянието. Другото решение можеше да бъде, че ранг 0 чете и създава матрицата на разстоянието и след това я излъчва към всички процеси. Освен това матрицата на разстоянието ще се съхранява в 1D масив, където индексирането за достъп до правилната променлива ще се извършва ръчно. 1D масивът беше избран вместо съхраняване на разстоянието в 2D масив след провеждане на някои тестове, които показват по-голяма ефективност за 1D.

Резултати

За следващата част от доклада ще фокусираме всички наши тестове и резултати върху случая със 17 града. Освен това, за да сме в съответствие с нашето сравнение и резултат, ние ще проведем теста, като започнем търсенето си от град 1 - резултатите, започващи от всеки град, могат да бъдат намерени в Приложението - въпреки това, в окончателния софтуер, изборът на първия град ще бъдете произволни. Можем да визуализираме градовете на карта, както е представено на фигура 4, и ще използваме това представяне по-късно, за да начертаем най-добрия намерен път и да имаме визуално валидиране на нашия резултат. Всеки град е свързан с друг град чрез матрицата на разстоянието, както е представено на фигура 5.

Най-добрият намерен път за 17 града е 1, 10, 4, 14, 15, 9, 6, 11, 13, 5, 8, 3, 16, 2, 17, 7 и 12 с цена 278. Пътят е представен на фигура 6. Това представяне ни помага да имаме първо глобално валидиране на нашия резултат, тъй като представеният път има смисъл и визуално изглежда възможно най-краткият, като се започне от град 1.

Ефект от разместването на предварителни пътеки

Едно ранно подобрение в нашия софтуер беше прилагането на механизъм за разбъркване за предварителните пътища, генерирани преди присвояването им на отделни процеси. Това беше направено, за да се гарантира, че работното натоварване е равномерно разпределено между всички процеси, избягвайки всяка ситуация, при която на един процес е назначена по-предизвикателна част от дървото за изследване. Балансирането на натоварването е от решаващо значение при всеки метод за паралелизиране, тъй като може значително да подобри ефективността на изчисленията чрез минимизиране на времето на престой на процесорите. За да оценим въздействието на разбъркването на предварителните пътища, сравнихме средното време на неактивност за процес и общото време за изчисление между версия на кода, където пътищата са били разбъркани, и версия, където не са били разбъркани. Резултатите са показани на фигури 7 и 8 и демонстрират значението на балансирането на натоварването при оптимизирането на паралелните изчисления.

Нашият резултат показва, че произволното преразпределение на пътя между процесите ни позволява да разделим на 5 средното време на неактивност на процесор и да разделим на 2 общото време за изчисление. Това показва, че балансирането на натоварването е от решаващо значение при всяко паралелизиране

Блокираща/неблокираща комуникация

Друго подобрение на програмата беше прилагането на неблокираща комуникация, за да се опитаме да имаме по-малко време на празен ход на нашите различни процеси и да се възползваме от буфера на нашата HPC инфраструктура. Начинът, по който е реализирано неблокирането, е следният: процесите извикват функцията IreduceAll и след това продължават да изследват други предварителни пътища, след проучване на други предварителни пътища те се опитват да получат IreduceAll на другия процес, преди да продължат да изследват други възможности .

Сравнението на общото време за изчисление е представено на Фигура 9. Виждаме, че неблокиращата комуникация не е намалила общото време за изчисление на нашата реализация. Една от причините може да е, че не внедрих неблокиращата комуникация по правилния начин, за да се възползвам от нея по правилния начин. Другата причина е, че дори ако изпращането не е блокиращо за IreduceAll, процесът пак ще трябва да изчака резултата от комуникацията. Ако един процес е заседнал в дълъг цикъл на изследване на различни възможности, дори ако другият процес междувременно е извършил други изчисления, той пак ще трябва да изчака IreduceAll на другия процес да приключи, преди да продължи. Така че в приложението това само ще забави забавянето и в крайна сметка няма да повлияе на скоростта на изчислението

Ефект от комуникацията

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

Както е представено на Фигура 10, с включена комуникация общото време за изчисление е почти разделено на 2, което означава, че ефектът от споделянето на най-добрите разходи между процесите си струва времето, загубено от синхронизирането и комуникацията на процесите.

Но както беше казано по-рано, има добра междинна граница между недостатъчната и твърде много комуникация, която може да доведе до неефективни режийни разходи, които не си заслужават. За по-нататъшно изследване на ефекта от комуникацията, общото време на изчисление беше наблюдавано с различен брой комуникации. Софтуерът е програмиран да комуникира всяко X проучване преди пътя, като X варира от 5 до 400.

Както е показано на фигура 11 и както се очаква, недостатъчната и твърде много комуникация ще доведе до увеличаване на времето за комуникация. Важно е да тествате паралелното внедряване, за да намерите оптималния брой комуникации, които да се изпълняват в оптимално състояние. В нашия случай с предварителни пътеки, генерирани за 5 дълбоки града, което води до 43 680 предварителни пътеки за изследване, оптималната стратегия е да се съобщава на всеки 60 проучени предварителни пътеки. Това съотношение е идеално за компенсиране на разходите за комуникация между процесите и времето, спечелено от по-ранното подрязване на дървото.

Ефект от генерирането на предварителен път

Една важна оптимизация е броят на генерираните предварителни пътища и колко дълбоко проучвате дървото на пътищата, преди да го разпространите. Броят на генерираните предварителни пътища влияе върху разпределението на натоварването между процеса и възникването на комуникация между процесите. За да се тестват различни конфигурации на 5, 6 и 7 града бяха проведени дълбоки предварителни пътеки и сравнени заедно. За да бъдем последователни в сравнението и че само броят на предварителните пътища влияе върху резултата, броят на комуникациите остава същият за всяка конфигурация.

Както е показано на фигури 12 и 13, времето за изчисление и времето на неактивност варират за всяка конфигурация. От направения тест установих, че оптималната конфигурация е с генерирането на 6 дълбоки предварителни пътеки в града. Дори ако средното време на неактивност е по-ниско с конфигурацията от 7 града, броят на генерираните предварителни пътища — 5 765 760 — е твърде голям и прави програмата по-бавна в общото време за изпълнение. Перфектната междина се намира с конфигурацията на дълбоки предварителни пътеки на 6 града. С по-задълбочено генериране на предварителен път, възможността за изследване на даден предварителен път е по-малка и всеки процес ще изследва по-тясна част от дървото, избягвайки един процес да остане в трудни пътища и да създаде пречка в софтуера.

Финална програма за разклонения и граници

Накрая, с всички оптимизации, открити по-рано, крайният софтуер беше тестван и сравнен със серийното внедряване, за да се получи окончателното ускоряване и да се сравни с теорията. Резултатът от крайното изпълнение е представен на фигура 14.

Можем да наблюдаваме, че ускоренията следват теоретичната линия почти до 16 процесора, след което ускорението намалява. Това може да се обясни с архитектурата на нашия HPC клъстер. Всъщност процесорите са 16 в един възел и ако искаме да имаме повече от 16 процесора, тогава ще използваме няколко възела вътре в HPC. Както се вижда в документацията и лекциите, комуникацията между възлите е по-бавна, отколкото вътре в един и същи възел. Тъй като внедряването на нашата програма комуникира много, това може да обясни падащото меню на ускоряването, започвайки от 16 процесора. [3]

Като цяло виждаме, че софтуерът се мащабира прилично, дори ако броят на комуникациите е голям, за да се постигне, че по време на този проект са проведени няколко теста, за да се проучи кой параметър трябва да бъде избран при внедряването, за да се възползва от наличния хардуер .

Последна програма Brute Force

Можем да сравним нашия софтуер Branch and Bounds с внедряването на Brute Force. Първото нещо, което трябва да забележите, е, че нашата програма Brute Force е по-ефективна при Speedups и почти следва теоретичната линия, както е представено на фигура 15. Изпълнението на Brute Force не включва комуникация между процесите, така че не се добавят допълнителни разходи за изчислението. Това означава, че мащабирането на софтуера е ефективно и си заслужава.

Дискусия

Едно първо сравнение, което трябва да се направи, е ефикасността на различните алгоритми, грубата сила не реши проблема с 16-те града дори като работи на 64 процесора паралелно за един ден. Това показва важността на алгоритъма, избран за решаване на проблем. Не трябва да приемаме, че паралелизирането е единственият начин за намаляване на времето за изчисление, но първо е важно да се разработи най-ефективният алгоритъм, използвайки най-добрите структури от данни, за да имаме функционален и ефективен алгоритъм. Тогава е възможно времето за изчисление да се намали още повече чрез паралелизиране.

Прилагането на паралелни изчисления често изисква цялостна преоценка на основния алгоритъм, за да се използват ефективно възможностите за паралелна обработка. От решаващо значение е да се разграничат задачите, които изискват комуникация, и тези, които не изискват, за да се използват ефективно неблокиращи комуникационни методи.

Както се вижда по време на цялата част с резултатите, провеждането на тест за намиране на перфектната конфигурация за конкретната употреба на хардуер е изключително важно, един малък параметър може да подобри драстично общото време за изчисление на софтуера - разликата между генерирането на 5 и 6 града дълбоко преди пътят е от 29s до 14s.

Забелязвам, че и на кривата на ускорението за грубата сила и клона и връзките не наблюдавахме намаляване на ускорението, видяхме само нарастваща фаза. Обикновено паралелният софтуер има фаза на нарастване, горна фаза и след това фаза на намаляване на ускорението. Което може да означава, че нашият софтуер може да има повече ускорения, когато го тестваме — защото бяхме ограничени до 64 процесора на Crescent HPC Cluster. Би било интересно да видим къде може да бъде върха и дали нашето внедряване също ще има намаляваща фаза в бъдеще.

Възможни подобрения

Забелязвам няколко подобрения, които могат да бъдат направени в изпълнението. Една от основните според мен е да се използват по-ефективни структури от данни и да се спре преразпределянето на памет за всяка итерация. В DFS търсенето посетеният масив и масивът с пътеки се управляват по динамичен начин, където текущият добавен град се използва push_back() и след това pop_back() в края на масива. Което може да означава, че всеки път, когато масивът трябва да се копира на друго място в паметта, което, ако случаят е такъв, ще доведе до много режийни разходи.

Един от начините може да бъде да разпределите масив с фиксиран размер от самото начало и след това да наблюдавате индекса на текущия град, за да работите директно върху конкретния индекс в масива и да не преразпределяте памет за всяка итерация. В C, C++ ефективното управление на паметта е един от най-добрите методи за подобряване на ефективността и коректността на част от кода.

Заключение

В заключение, този проект ни позволи да имаме по-задълбочено и по-добро разбиране на паралелното програмиране и как да използваме HPC клъстер като Crescent. По време на този проект успяхме да разберем и да се поучим от предизвикателствата на разработването на ефективна паралелна програма. Намиране на добър метод за паралелизиране чрез трансформиране на първоначалния сериен алгоритъм и извършване на няколко теста, за да се намери перфектният баланс между комуникация и режийни разходи.

Откриваме, че основното пречка в паралелната програма често е контролната точка за синхронизиране и комуникацията. Това означава, че е важно да ги наблюдаваме, както направихме ние, като създадем допълнителни показатели — като времето на неактивност на процесор — и намалим комуникацията само до необходимата.

Както се вижда в дискусионната част, намирането на ефективен алгоритъм, който ще опрости първоначалния проблем и ще намали необходимото количество изчисления, е още по-важно, преди да започнем да паралелизираме нашата работа. Можехме да паралелизираме с възможно най-доброто ускоряване на алгоритъма Brute Force, но бих могъл да свърша за една седмица на 64 процесора работата, извършена от алгоритъма за разклоняване и граници на един процесор за 5 минути.

Намерете повече от кода тук.

Препратки

[1] Peter Pacheco (1997), Паралелно програмиране с MPI, Morgan Kaufm ann.

[2] Peter Pacheco (2011), Въведение в паралелното програмиране, Elsevier.

[3] Д-р Ирен Мулицас (2022 г.), Високопроизводителни технически изчисления, Университет Кранфийлд.

[4] Amey Gohil, Manan Tayal, Tezan Sahu и Vyankatesh Sawalpurkar (2021), Traveling Salesman Problem: Parallel Implementations & Analysis

[5] Джонсън, DB, & McGeoch, LA (1997). Проблемът с пътуващия търговец: Казус от локалната оптимизация.

Научете повече

AWS Cloud Computing с Python

Множествена линейна регресия, градиентно спускане /w Python

© Всички права запазени, март 2023 г., Симеон ФЕРЕЗ