Główna zawartość
Podstawy informatyki - program rozszerzony
Kurs: Podstawy informatyki - program rozszerzony > Rozdział 4
Lekcja 4: Obliczenia równoległe i rozproszoneObliczenia równoległe
Jednym ze sposobów przyspieszania algorytmów są obliczenia równoległe, które pozwalają jednocześnie wykonywać obliczenia należące do algorytmu na kilku procesorach.
Obliczenia sekwencyjne
Obliczenia sekwencyje są standardową metodą programowania: komputer wykonuje każdą operację obliczeniową osobno w podanej kolejności.
Przyjrzyjmy się poniższemu programowi, który przetwarza obrazy i oblicza na ilu obrazach występuje kot:
images ← [ "pet1.jpg", "pet2.jpg", "pet3.jpg", "pet4.jpg"]
numCats ← 0
FOR EACH image IN images
{
foundCat ← detectCat(image)
IF foundCat
{
numCats ← numCats + 1
}
}Program zaczyna się zdefiniowaniem listy plików i zmiennej reprezentującej liczbę obrazów z kotami. Początkową wartością tej zmiennej jest 0. Następnie, w pętli przechodzącej po elementach listy plików, dla każdego z plików wywoływana jest funkcja, która decyduje czy na podanym obrazie znajduje się kot. Jeśli tak, to zmienna odpowiadająca liczbie kotów zostaje zwiększona o 1.
Poniżej znajduje się wizualizacja działania tego programu wywołanego na 4 obrazach:
Teraz przyjrzyjmy się dokładniej temu programowi. Zobaczmy, ile czasu zajmuje każda operacja i ile razy jest wykonywana:
| Czas | Wywołania | Operacja |
|---|---|---|
| 3 | 1 | images ← [ "pet1.jpg", "pet2.jpg", "pet3.jpg", "pet4.jpg"] |
| 1 | 1 | numCats ← 0 |
| 1 | 4 | FOR EACH image IN images |
| 10 | 4 | foundCat ← detectCat(image) |
| 1 | 4 | IF foundCat |
| 2 | 4 | numCats ← numCats + 1 |
Uwaga: wartości w kolumnie z czasem nie są prawdziwe. Faktyczne wartości byłyby zależne od implementacji algorytmu oraz sprzętu na którym program byłby uruchomiony.
Możemy obliczyć całkowity czas wykonania programu. W tym celu mnożymy czas danej operacji przez to ile razy została ona wywołana, po czym dodajemy razem wartości obliczone dla każdej operacji.
Poniższa linia czasu obrazuje operacje komputera w czasie:
Obliczenia równoległe
Sekwencyjny model obliczeniowy zakłada, że w danym momencie tylko jedna operacja może być wykonywana i jest to prawda dla systemu składającego sie z jednego komputera z jednym procesorem. Większość nowoczesnych komputerów jednakże zawiera procesory wielordzeniowe i każdy rdzeń takiego procesora może wykonywać niezależne operacje obliczeniowe.
Procesory wielordzeniowe mogą wykorzystać obliczenia równoległe: model obliczeniowy, który dzieli program na mniejsze operacje sekwencyjne i wykonuje te mniejsze operacje w tym samym czasie (równolegle).
Zastanówmy się, czy możemy zmodifikować algorytm znajdujący koty na obrazkach w taki sposób, że może być on wykonany równolegle? Jest to możliwe tylko w przypadku, gdy operacje są niezależne od siebie.
🤔 Spójrz ponownie na program i sprawdź, czy możesz zidentyfikować operacje, które nie muszą być wykonywane sekwencyjnie.
W przypadku tego programu moglibyśmy równolegle wykonywać operacje znajdujące się w pętli, ponieważ wartość funkcji
detectCat nie zależy od wyników wywołania detectCat dla innych obrazów. Oznacza to, że te linie kodu mogą być wykonywane równolegle: foundCat ← detectCat(image)
IF foundCat
{
numCats ← numCats + 1
}Właściwy sposób zrównoleglenia programu jest zależny od języka programowania i środowiska obliczeniowego. Szczegóły na ten temat są pominięte w tym artykule.
U dołu umieszczona jest wizualizacja programu wykonującego te operacje równolegle:
Ile czasu tym razem zajmie wykonanie tego programu? Przypomnijmy, jak wyglądała poprzednia analiza:
| Czas | Wywołania | Operacja |
|---|---|---|
| 3 | 1 | images ← [ "pet1.jpg", "pet2.jpg", "pet3.jpg", "pet4.jpg"] |
| 1 | 1 | numCats ← 0 |
| 1 | 4 | FOR EACH image IN images |
| 10 | 4 | foundCat ← detectCat(image) |
| 1 | 4 | IF foundCat |
| 2 | 4 | numCats ← numCats + 1 |
Operacje, które nie zostały zrównoleglone, zajmą tyle samo czasu co poprzednio:
Czas spędzony na obliczenia równoległe zależy od liczby procesorów wykonujących obliczenia w tym samym czasie. Jeżeli program został uruchomiony na komputerze z czterordzeniowym procesorem, każdy rdzeń może przetwarzać jeden z czterech obrazów. Wobec tego, zrównoleglona część programu zajmie jedynie czas odpowiadający przetworzeniu pojedynczego obrazu:
Poniższa linia czasu obrazuje operacje komputera, który dzieli obliczenia programu na 4 niezależne procesy:
Porównanie modelu sekwencyjnego z modelem równoległym
Jednym ze sposobów oceny korzyści wynikających z zastosowania obliczeń równoległych jest pomiar przyspieszenia: stosunku czasu wykonania programu sekwencyjnego do czasu wykonania programu równoległego.
Nasz przykładowy program zajmuje 60 sekund w przypadku sekwencyjnym. W przypadku równoległym, przy użyciu czterech procesorów, gdzie przetworzenie każdego obrazu zajmuje 14 sekund, czas wykonania programu wynosi 18 sekund. Obliczamy przyspieszenie dzieląc 60 przez 18:
Nie osiągneliśmy przyspieszenia dokładnie 4, pomimo używania 4 procesorów. Początkowa sekwencyjna część programu zajmie taką samą ilość czasu, nawet jeśli użyjemy nieskończenie wiele procesorów. W związku z tym, sekwencyjny fragment naszego programu ogranicza maksymalne przyspieszenie jakie możemy osiągnąć poprzez zastosowanie obliczeń równoległych.
Równoległe programy są używane zazwyczaj dla problemów, gdzie wejście zawiera tysiące lub miliony przykładów do przetworzenia. Jeśli uruchomimy nasz program na tysiącach obrazów, początkowa część sekwencyjna zajmie niewielki ułamek czasu w porównaniu z częścią równoległą.
Zmienny czas wykonania
Operacje należące do równoległych części programu nie zawsze zajmują taką samą ilość czasu, szczególnie w przypadku przetwarzania danych wejściowych.
Na przykład, funkcja
detectCat w naszym przykładzie może używać algorytmu, którego czas różni się w zależności od rozmiaru lub trudności przetworzenia danego obrazu. Operacja może zająć tylko 10 sekund dla jednego obrazu, a 22 sekund w przypadku innego obrazu.U dołu znajduje się oś czasu odpowiadająca tej sytuacji:
Całkowity czas wykonania programu zwiększył się do 30 sekund, ponieważ równoległa część trwa tak długo jak najdłuższa z równoległych operacji.
Aby zrekompensować fakt, że często występują różnice w czasie wykonania równoległej części programu, możemy sprytniej przypisywać operacje do procesorów. Zamiast przydzielać zadania do procesorów z góry, możemy wysłać kolejne zadanie do dowolnego procesora, który nie jest aktualnie zajęty.
Na przykład, wyobraźmy sobie, że uruchomiliśmy program do wykrywania kotów na siedmiu zdjęciach, a operacja
detectCat() zajęła dużo czasu na trzecim zdjęciu. Program nie musi czekać na ukończenie analizy trzeciego zdjęcia aby przeanalizować siódmy obraz; może wysłać ten obraz do innego procesora, który jest wolny:🙋🏽🙋🏻♀️🙋🏿♂️Czy masz jakieś pytania na ten temat? Chętnie na nie odpowiemy — wystarczy, że zadasz pytanie w poniższym obszarze pytań!
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji