Title: Przetwarzanie równoległe i strumieniowe

PRS

Przetwarzanie równoległe i strumieniowe

Wykład 6

Algorytmy równoległe

Zaliczenie

Algorytmy równoległe

Algorytm równoległy to algorytm, który wykonuje obliczenia równocześnie na wielu procesorach lub rdzeniach

Algorytmy równoległe pozwalają na równoległe wykonywanie wielu operacji jednocześnie, co pozwala na znaczne przyspieszenie procesów obliczeniowych.

https://ifunny.co/picture/the-prof-me-my-parallel-algorithm-that-should-not-work-CjPopSk19

Algorytmy równoległe

Algorytmy równoległe są szczególnie użyteczne w przypadku dużych problemów obliczeniowych, których rozwiązanie wymaga przetwarzania dużej ilości danych lub złożonych operacji, które mogą zostać podzielone na mniejsze, równoległe kroki.

https://ifunny.co/picture/the-prof-me-my-parallel-algorithm-that-should-not-work-CjPopSk19

Algorytmy równoległe

Równoległe wersje znanych algorytmów wykorzystują dwie metody działania:

- podział dziedziny problemu na N równych części i przydział każdemu procesorowi mniejszej części a następnie synchronizacja wyników (nie zawsze możliwe),
- podział wykonywanych operacji na N procesorów i synchronizacja w przypadku możliwych błędów dostępu do wspólnych danych

Algorytmy równoległe

Ian Foster w książce "Designing and Building Parallel Programs" opisuje cztery kroki projektowania algorytmów równoległych:

1. Partitioning - find possible ways to split the data among the workers as fine-grain as possible.
2. Communication - identify the communication patterns.
3. Agglomeration - reduce the initial partitions to coarse-grain tasks according to the resources available.
4. Mapping - map the tasks onto the processing units.

Algorytmy równoległe - partitioning

Etap podziału projektu ma na celu ujawnienie możliwości równoległego wykonania. Dlatego nacisk kładziony jest na zdefiniowanie dużej liczby małych zadań w celu uzyskania tego, co nazywa się drobnoziarnistą dekompozycją problemu.

Dobry podział dzieli na małe części zarówno obliczenia związane z problemem, jak i dane, na których działają te obliczenia.

Algorytmy równoległe - Communication

Zadania generowane przez partycję mają być wykonywane współbieżnie, ale generalnie nie mogą być wykonywane niezależnie.

Obliczenia do wykonania w jednym zadaniu zazwyczaj wymagają danych powiązanych z innym zadaniem.

Dane muszą być następnie przesyłane między zadaniami, aby umożliwić kontynuację obliczeń. Ten przepływ informacji jest określony w fazie komunikacji projektu.

Algorytmy równoległe - Agglomeration

W pierwszych dwóch etapach procesu projektowania podzieliliśmy obliczenia do wykonania na zestaw zadań i wprowadziliśmy komunikację między nimi.

W rzeczywistości nasz algorytm może być bardzo nieefektywny, jeśli na przykład tworzy znacznie więcej zadań niż procesorów na komputerze docelowym.

W trzecim etapie, aglomeracji, ponownie analizujemy decyzje podjęte w poprzednich fazach w celu uzyskania algorytmu, który będzie działał wydajnie. W szczególności rozważamy, czy warto łączyć lub aglomerować zadania, aby zapewnić mniejszą liczbę zadań.

Algorytmy równoległe - Mapping

W czwartym i ostatnim etapie procesu projektowania algorytmu równoległego określamy, gdzie każde zadanie ma zostać wykonane.

Ten problem z mapowaniem nie występuje na komputerach jednoprocesorowych ani na komputerach z systemami operacyjnymi, które zapewniają automatyczne planowanie zadań.

- Umieszczamy zadania, które mogą być wykonywane współbieżnie na różnych procesorach, aby zwiększyć współbieżność.
- Zadania, które często się komunikują, umieszczamy na tym samym procesorze, aby zwiększyć lokalność.

Algorytmy równoległe - Przykład

Weźmy jako przykład algorytm wyliczający liczbę Fibonacciego:

def computeFib(int n):
        if(n==0):
            return 0
        if( n==1 || n ==2):
            return 1
        return computeFib(n-1)+computeFib(n-2)


Można obliczać równolegle:

def computeFibParallel(int n):
        if(n==0):
            return 0
        if( n==1 || n ==2):
            return 1
        return threading.Thread(computeFib(n-1))+ threading.Thread(computeFib(n-2))

Algorytmy sortujące

https://medium.com/@ruth_obe/sorting-array-of-objects-in-javascript-with-sort-c71faeb174ef

Algorytmy sortujące

Algorytmy sortujące to zestawy procedur i reguł, które umożliwiają uporządkowanie elementów zbioru według ustalonego klucza sortowania.

Elementy te mogą być liczbami, literami, obiektami lub innymi wartościami, które można porównać między sobą.

W zależności od sytuacji i wymagań, w której jest stosowany, można wybrać różne algorytmy sortujące, które różnią się między sobą szybkością sortowania, ilością pamięci wymaganej do sortowania, czy stabilnością sortowania (czyli zachowaniem kolejności elementów o tej samej wartości).

Algorytmy sortujące - sortowanie bąbelkowe

Sortowanie bąbelkowe (Bubble Sort) to prosty algorytm sortowania, który porównuje kolejne pary elementów w tablicy i zamienia je, jeśli kolejność jest nieprawidłowa. Algorytm ten powtarza tę procedurę aż do momentu, gdy cała tablica jest posortowana.

Algorytm sortowania bąbelkowego ma złożoność czasową O(n^2).

https://pl.wikipedia.org/wiki/Sortowanie_b%C4%85belkowe#/media/Plik:Bubble-sort-example-300px.gif

Algorytmy sortujące - sortowanie bąbelkowe

Równoległe sortowanie bąbelkowe (Parallel Bubble Sort) może polegać na rozdzieleniu tablicy na mniejsze fragmenty, a następnie sortowaniu każdego z tych fragmentów równolegle na oddzielnych procesorach lub rdzeniach.

Algorytm sortowania bąbelkowego ma złożoność czasową Max(O(n),O(n^2 / p)).

https://pl.wikipedia.org/wiki/Sortowanie_b%C4%85belkowe#/media/Plik:Bubble-sort-example-300px.gif

Algorytmy sortujące - sortowanie bąbelkowe

Możliwym pomysłem jest także uruchomienie wielu iteracji w sposób potokowy, tj.
rozpocznij kolejny wątek zamieniąjący obiekty po tym jak poprzedni przesunął się o kolejny indeks w prawo, tak by żaden wątek nie wyprzedził poprzedniego.

Podejście to wymaga synchronizacji między procesami, ale może być wykonywany "falowo".

Algorytmy sortujące - Bubble Odd-Even

Sortowanie z zamianą parzystych i nieparzystych elementów jest wariantem sortowania bąbelkowego, w którym działania wykonywane są w dwóch naprzemiennych fazach:

- Faza parzysta: parzyste procesy wymieniają wartości z właściwymi sąsiadami
  - (P0 ↔ P1, P2 ↔ P3, ...)
- Faza nieparzysta: procesy nieparzyste wymieniają wartości z prawymi sąsiadami
  - (P1 ↔ P2, P3 ↔ P4, ...)

W przypadku programowania sekwencyjnego sortowanie z zamianą nieparzystych-parzystych nie ma przewagi nad normalnym sortowaniem bąbelkowym. Jednak jego równoległa realizacja odpowiada złożoności czasowej O(n).

Algorytmy sortujące - merge sort

Merge sort (sortowanie przez scalanie) to algorytm sortowania, który dzieli listę na pół, sortuje każdą z tych połówek rekurencyjnie, a następnie scalając je w posortowaną listę.

https://en.wikipedia.org/wiki/Merge_sort#/media/File:Merge_sort_algorithm_diagram.svg

Algorytmy sortujące - merge sort

Zakłądając, że mamy nieograniczoną liczbę procesorów. Patrząc na drzewo algorytmu sortowania przez scalanie w algorytmie sekwencyjnym, możemy spróbować przypisać jednoczesne operacje do oddzielnych procesorów, które będą pracować współbieżnie, aby wykonać dzielenie i łączenie na każdym poziomie.

https://stackoverflow.com/questions/61910607/parallel-merge-sort-using-mpi

Algorytmy sortujące - merge sort

Drugie podejście do zrównolelenia to podział tablicy na N części i sortowanie każdej części na osobnym procesorze a następnie scalenie posortowanych tablic.

https://devblogs.microsoft.com/pfxteam/parallel-merge-sort-using-barrier/

Algorytmy sortujące - odd-even merge

Scalanie parzyste i nieparzyste (posortowanych list A i B) :

1. Podziel A na podlisty A_p i A_n zawierające elmenty na parzystych i nieparzystych indeksach. Podobnie podziel B na B_p i B_n.

2. Scal A_p i B_n, aby utworzyć C i scal A_n i B_p, aby utworzyć D.

3. Scal C i D.

Algorytmy sortujące - odd-even merge

Na pierwszy rzut oka wydaje się że nic nie zyskujemy.

Okazuje się jednak, że scalanie C i D ma specyficzne własności. Pierwsze dwa elementy ogólnej posortowanej listy to górne elementy w C i D w pewnej kolejności, trzeci i czwarty element w posortowana lista to drugie elementy C i D w jakiejś kolejności i tak dalej. W ten sposób połączenie C i D można wykonać równolegle, po jednym procesorze na każdą pozycję.

Rozważ połączenie A=1467 i B=2389. Wtedy C jest połączeniem 47 i 28, D jest połączeniem 16 i 39; więc C to 2478, a D to 1369.

Algorytmy przeszukiwania - Binary Search

Binary Search to algorytm wyszukiwania elementu w posortowanej tablicy.

Polega on na podziale posortowanej tablicy na pół i porównaniu szukanego elementu z elementem środkowym. Jeśli szukany element jest większy niż element środkowy, to algorytm powtarza operację na prawej połowie tablicy, w przeciwnym razie na lewej.

Proces ten jest powtarzany, aż do znalezienia elementu lub stwierdzenia, że elementu nie ma w tablicy.

Algorytmy przeszukiwania - Binary Search

Algorytm równoległy Binary Search polega na podziale posortowanej tablicy na mniejsze podtablice, które są przeszukiwane równolegle przez każdy procesor.

W każdym kroku algorytmu, każdy procesor porównuje klucz poszukiwanego elementu z elementem środkowym swojej podtablicy, a następnie wybiera jedną z połówek tablicy, w której element może być zawarty.

https://en.wikipedia.org/wiki/Binary_search_algorithm#/media/File:Binary_search_complexity.svg

Algorytmy przeszukiwania - Binary Search

Proces ten jest powtarzany, aż do znalezienia elementu lub stwierdzenia, że elementu w tablicy nie ma.

W celu efektywnego działania, algorytm ten wymaga równomiernego podziału tablicy między procesory i komunikacji między procesorami w celu synchronizacji wyników wyszukiwania.

Algorytmy przeszukiwania - BFS

BFS (Breadth-First Search) to algorytm przeszukiwania grafu, który rozpoczyna się od zdefiniowanego wierzchołka (lub wierzchołków) i przeszukuje graf warstwami, od najbliższych wierzchołków, aż do odwiedzenia wszystkich wierzchołków.

Algorytm BFS wykorzystuje kolejkę FIFO (First-In-First-Out), aby przechowywać wierzchołki, które zostały już odwiedzone i czekają na przetworzenie.

https://pl.wikipedia.org/wiki/Przeszukiwanie_wszerz#/media/Plik:Animated_BFS.gif

Algorytmy przeszukiwania - BFS

Algorytm BFS zaczyna od wierzchołka startowego i odwiedza najbliższych sąsiadów tego wierzchołka. Następnie przechodzi do sąsiadów odwiedzonych w pierwszej kolejności, aż do odwiedzenia wszystkich wierzchołków grafu.

Algorytm BFS pozwala na znalezienie najkrótszej ścieżki między dwoma wierzchołkami w grafie nieważonym (czyli takim, w którym krawędzie nie mają przypisanych wag), gdyż przeszukuje graf warstwami, zaczynając od najbliższych sąsiadów.

https://www.programming-books.io/essential/algorithms/finding-the-shortest-path-from-source-to-other-nodes-fc0bcc1c2ee847d39daa48c8751d9d90

Algorytmy przeszukiwania - BFS

Idea równoległego wykonywania BFS polega na tym, że zasadniczo można przetwarzać wszystkie wierzchołki na jednym poziomie w tym samym czasie.

Oznacza to, że po znalezieniu wszystkich wierzchołków poziomu 1 można wykonać pętlę równoległą, która bada każdy z nich w celu znalezienia wierzchołków poziomu 2.

Zatem kod równoległy będzie sekwencyjnie przetwarzał warstwy ale każda warstwa może być przetworzona równolegle.

https://www.programming-books.io/essential/algorithms/finding-the-shortest-path-from-source-to-other-nodes-fc0bcc1c2ee847d39daa48c8751d9d90

Algorytmy przeszukiwania - BFS

W kodzie równoległym możliwe jest, że podczas przetwarzania poziomu i dwa wierzchołki v i w znajdą ten sam wierzchołek poziomu i+1, o nazwie x jako sąsiad. Spowoduje to race condition, gdy obaj spróbują ustawić poziom[x]=i+1, a także gdy każdy spróbuje ustawić rodzica[x] na siebie.

Jest to jednak „łagodny race condition” - gdyż w rzeczywistości nie powoduje on żadnego problemu, ponieważ niezależnie od tego, który wątek będzie szybszy ustawimy ten sam poziom [x] i dla poprawności algorytmu nie ma też znaczenia, czy rodzic[x] będzie v lub w.

Algorytmy przeszukiwania - BFS

Trudniejszym problemem jest to, że wszystkie wątki eksplorujące wierzchołki poziomu i będą próbowały jednocześnie dodać nowe wierzchołki poziomu i+1 do kolejki typu FIFO.

Znów kolejność przetwarzania na jednym poziomie nie jest istotna więc race condition do kolejki nie jest dla nas problemem.

Rozwiązaniem problemu ograniczenia przetwarzania do jednej warstwy jest utrzymywanie dwóch kolejek, lub zbiorów, zapamiętujących aktualnie przetwarzany poziom oraz kolejny poziom w przetwarzaniu i umiejętne przełączanie wątków pomiędzy tymi strukturami.

Algorytmy przeszukiwania - DFS

DFS (Depth-First Search) to algorytm przeszukiwania grafu, który działa na zasadzie przeszukiwania w głąb. Algorytm DFS rozpoczyna przeszukiwanie od zdefiniowanego wierzchołka startowego i przeszukuje graf, przemieszczając się do wierzchołków nieodwiedzonych, aż do odwiedzenia wszystkich wierzchołków.

Algorytm DFS używa stosu do przechowywania kolejnych wierzchołków do odwiedzenia i zdejmowania z niego wierzchołków już odwiedzonych.

https://en.wikipedia.org/wiki/File:Depth-First-Search.gif

Algorytmy przeszukiwania - DFS

Algorytm DFS jest stosowany w wielu dziedzinach, takich jak sztuczna inteligencja, grafika komputerowa czy sieci komputerowe. Wadą algorytmu DFS jest to, że może prowadzić do utworzenia nieskończonej pętli w grafie, jeśli graf zawiera cykle.

Algorytm DFS, bez dodatkowych mechanizmów, nie gwarantuje znalezienia najkrótszej ścieżki między wierzchołkiem startowym a innymi wierzchołkami w grafie.

https://en.wikipedia.org/wiki/File:Depth-First-Search.gif

Algorytmy przeszukiwania - DFS

DFS można zaimplementować równolegle, dzieląc przestrzeń wyszukiwania na poddrzewa, które są przeszukiwane równolegle.

Każdy procesor przeszukuje rozłączne poddrzewo w pierwszej kolejności w głąb, co można zrobić asynchronicznie bez żadnej komunikacji.

Kiedy procesor zakończy swoją pracę, próbuje uzyskać nieprzeszukane poddrzewo z innego procesora.

Algorytmy mnożenia macierzy

Mnożenie macierzy to operacja polegająca na pomnożeniu dwóch macierzy, które muszą spełniać warunki odpowiedniej liczby kolumn i wierszy.

Wynikowa macierz będzie miała tyle samo wierszy, co pierwsza macierz, i tyle samo kolumn, co druga macierz.

Operacja ta jest wykorzystywana w wielu dziedzinach matematyki, informatyki i nauk technicznych.

Algorytmy mnożenia macierzy

Mając dwie macierze:

A = | 2 3 |

       | 1 4 |

B = | 5 6 |

       | 7 8 |

Możemy pomnożyć je, stosując algorytm mnożenia macierzy:

| 2 3 |  | 5 6 | = | 25+37 26+38 |

                 X

| 1 4 |  | 7 8 | = | 15+47 16+48 |

Otrzymujemy macierz wynikową:

| 19 24 |

| 33 46 |

Algorytmy mnożenia macierzy

Problem mnożenia macierzy można sprowadzić do wykonania n·k niezależnych operacji (korzystają z niezmienianych danych a wyniki nie wpływają na siebie) na wierszach macierzy A i kolumnach macierzy B.

Ponadto iteracje mogą być wykonywane w dowolnej kolejności.

W najprostszym podejściu każde pole wynikowej macierzy obliczamy równolegle na osobnym procesorze.

Algorytmy kolorowania grafów

Kolorowanie grafów to proces przypisywania kolorów wierzchołkom lub krawędziom grafu w taki sposób, że dwa sąsiednie wierzchołki lub krawędzie nie mają tego samego koloru.

Niech G = (V, E) będzie grafem, gdzie V to zbiór wierzchołków, a E to zbiór krawędzi. Kolorowanie wierzchołkowe grafu G to funkcja f: V -> C, która przypisuje każdemu wierzchołkowi v z G kolor f(v) z pewnego zbioru kolorów C w taki sposób, że dwa sąsiednie wierzchołki w G mają różne kolory, tj. f(v) != f(u) dla każdej pary sąsiednich wierzchołków v, u w G.

https://en.wikipedia.org/wiki/Graph_coloring#/media/File:Petersen_graph_3-coloring.svg

Algorytmy kolorowania grafów

Algorytmy sekwencyjne kolorowania grafów: największy-stopień-pierwszy, najmniejszy-stopień-ostatni można łatwo zrównoleglić.

Opierając się to na prostej obserwacji, że każdy niezależny zbiór wierzchołków (wierzchołków niepołączonych krawędzią) można pokolorować równolegle, gdyż nie zaistnieje konflikt przy kolorowaniu.

Przypisywać będziemy wierzchołkom najniższy dostępny kolor: najmniejszy kolor (kolory traktujemy tu jako liczby), który nie został jeszcze przypisany do sąsiedniego wierzchołka.

Algorytmy kolorowania grafów

Algorytm kolorowania grafów Jones-Plassmann :

- Przypisz wierzchołkom losowo różne liczby.
- Dla każdego wierzchołka sprawdź czy jego liczba jest wyższa niż u wszystkich sąsiadów.
- Jeżeli tak pokoloruj go za pomocą najniższego wolnego koloru.

Algorytmy kolorowania grafów

Algorytm kolorowania grafów Jones-Plassmann :

https://ireneli.eu/2015/10/26/parallel-graph-coloring-algorithms/