If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Obliczenia 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:
CzasWywołaniaOperacja
31images ← [ "pet1.jpg", "pet2.jpg", "pet3.jpg", "pet4.jpg"]
11numCats ← 0
14FOR EACH image IN images
104 foundCat ← detectCat(image)
14 IF foundCat
24 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.
left parenthesis, 3, dot, 1, right parenthesis, plus, left parenthesis, 1, dot, 1, right parenthesis, plus, left parenthesis, 1, dot, 4, right parenthesis, plus, left parenthesis, 10, dot, 4, right parenthesis, plus, left parenthesis, 1, dot, 4, right parenthesis, plus, left parenthesis, 2, dot, 4, right parenthesis, equals, 60
Poniższa linia czasu obrazuje operacje komputera w czasie:
Oś czasu programu zaczyna się od 0 sekund i kończy na 60 sekundach. Dla każdej iteracji pętli oznaczono jej czas początkowy - 4 sekundy, 18 sekund, 32 sekundy i 46 sekund.

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ż watrość funkcji detectCat niezależ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:
CzasWywołaniaOperacja
31images ← [ "pet1.jpg", "pet2.jpg", "pet3.jpg", "pet4.jpg"]
11numCats ← 0
14FOR EACH image IN images
104 foundCat ← detectCat(image)
14 IF foundCat
24 numCats ← numCats + 1
Operacje, które nie zostały zrównoleglone, zajmą tyle samo czasu co poprzednio:
left parenthesis, 3, dot, 1, right parenthesis, plus, left parenthesis, 1, dot, 1, right parenthesis, equals, 4
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:
1, plus, 10, plus, 1, plus, 2, equals, 14
Poniższa linia czasu obrazuje operacje komputera, który dzieli obliczenia programu na 4 niezależne procesy:
Oś czasu programu zaczyna się od 0 sekund i kończy na 30 sekundach. Po 4 sekundach 4 procesy równoległe zaczynają operację wykrywania kotów.

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:
60, slash, 18, equals, 3, point, start overline, 33, end overline
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łą.
Sprawdź swoją wiedzę
Program zajmuje 32 sekundy, gdy jest on uruchomiony równolegle na dwóch procesorach. Przetworzenie jednego obrazu zajmuje 14 sekund. Jakie jest przyspieszenie dla tego programu?
  • Prawidłowa odpowiedź to:
  • liczba całkowita, taka jak 6
  • właściwy uproszczony ułamek, taki jak 3, slash, 5
  • niewłaściwy uproszczony ułamek, taki jak 7, slash, 4
  • liczba mieszana, taka jak 1, space, 3, slash, 4
  • dokładny ułamek dziesiętny, taki jak 0, comma, 75
  • wielokrotność pi, taka jak 12, space, start text, p, i, end text lub 2, slash, 3, space, start text, p, i, end text

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:
Oś czasu programu zaczyna się od 0 sekund i kończy na 30 sekundach. Po 4 sekundach procesy równoległe zaczynają operację wykrywania kotów. Większość procesów kończy się po 18 sekundach od rozpoczęcia programu, ale trzeci proces kończy się dopiero po 30 sekundach.
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.
Sprawdź swoją wiedzę
Oryginalny sekwencyjny program zajmuje 60 sekund. Jeśli równoległy program zajmuje 30 sekund, jakie jest przyśpieszenie?
  • Prawidłowa odpowiedź to:
  • liczba całkowita, taka jak 6
  • właściwy uproszczony ułamek, taki jak 3, slash, 5
  • niewłaściwy uproszczony ułamek, taki jak 7, slash, 4
  • liczba mieszana, taka jak 1, space, 3, slash, 4
  • dokładny ułamek dziesiętny, taki jak 0, comma, 75
  • wielokrotność pi, taka jak 12, space, start text, p, i, end text lub 2, slash, 3, space, start text, p, i, end text

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:
Oś czasu programu zaczyna się od 0 sekund i kończy na 30 sekundach. Po 4 sekundach procesy równoległe zaczynają operację wykrywania kotów. Trzy procesy kończą się po 18 sekundach, po czym zaczynają przetwarzać kolejny obrazek. Procesy te kończą się po upływie 32 sekund od rozpoczęcia programu. Trzeci proces kończy się po 30 sekundach.
Sprawdź swoją wiedzę
Program sekwencyjny zajmuje 102 sekundy, gdy jest uruchomiony na siedmiu zdjęciach. Jeśli równoległy program zajmuje 32 sekundy, jakie jest przyspieszenie programu?
(Możesz podać przyśpieszenie jako ułamek)
  • Prawidłowa odpowiedź to:
  • liczba całkowita, taka jak 6
  • właściwy uproszczony ułamek, taki jak 3, slash, 5
  • niewłaściwy uproszczony ułamek, taki jak 7, slash, 4
  • liczba mieszana, taka jak 1, space, 3, slash, 4
  • dokładny ułamek dziesiętny, taki jak 0, comma, 75
  • wielokrotność pi, taka jak 12, space, start text, p, i, end text lub 2, slash, 3, space, start text, p, i, end text


🙋🏽🙋🏻‍♀️🙋🏿‍♂️Czy masz jakieś pytania na ten temat? Chętnie na nie odpowiemy — wystarczy, że zadasz pytanie w poniższym obszarze pytań!