Wprowadzenie do programowania równoległego

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Jaką maksymalną prędkość operacji zmiennoprzecinkowych osiągał komputer UNIVAC I?

500 operacji na sekundę

100 operacji na sekundę

1000 operacji na sekundę (correct)

2000 operacji na sekundę

W którym roku powstał komputer UNIVAC I?

1951 (correct)

1948

1960

1955

Na czym polega różnica między przetwarzaniem sekwencyjnym a równoległym?

Równoległe wymaga więcej pamięci niż sekwencyjne

Sekwencyjne jest szybsze od równoległego

Sekwencyjne wykonuje zadania w jednym czasie, równoległe w wielu (correct)

Równoległe jest używane tylko w komputerach osobistych

Które z poniższych stwierdzeń najlepiej opisuje komputer z lat 60. XX wieku?

Funkcjonował w dedykowanym pokoju z terminalami Signup and view all the answers

Jakie były główne miejsca pracy z komputerem w latach 80. XX wieku?

Własne biurko Signup and view all the answers

Jakie zalety wpływają na popularność przetwarzania równoległego?

Zwiększona moc obliczeniowa i efektywność Signup and view all the answers

Jakie zagrożenia mogą wynikać z wykorzystania przetwarzania równoległego?

Niska wydajność w przypadku braku synchronizacji Signup and view all the answers

Jakie zmiany zaszły w miejscach pracy z komputerem do lat 90-tych XX wieku?

Ruchome stanowiska pracy Signup and view all the answers

Jakie są główne zalety przetwarzania równoległego w odniesieniu do przetwarzania sekwencyjnego?

Zwiększa szybkość obliczeń przez rozdzielenie zadań na wiele procesorów. Signup and view all the answers

Jaką wydajność obliczeniową ma CPU, który wykonuje obliczenia w 15 minut w przedstawionym przykładzie?

1 TFlop/s Signup and view all the answers

Jaka jest całkowita liczba operacji zmiennoprzecinkowych do wykonania w danym przykładzie?

84 700 000 000 000 Signup and view all the answers

Co przedstawia klasyczny program sekwencyjny?

Wykonywanie operacji w kolejności jedna po drugiej. Signup and view all the answers

Jakie ograniczenie związane jest z przesyłaniem danych z RAM do CPU?

Odległość między RAM a CPU nie może przekraczać 0.3 mm. Signup and view all the answers

Jakie zadanie wykorzystuje obliczenia równoległe w przykładzie podanym w treści?

Analiza zmienności temperatury, ciśnienia i wilgotności. Signup and view all the answers

Jakie ograniczenie dotyczące pamięci wpływa na wykonanie obliczeń przedstawionych w przykładzie?

Wymagana pamięć wynosi 350 GB. Signup and view all the answers

Jakie GPU zajmuje 55 miejsce na liście TOP 500 w 2024 roku?

Helios GPU Signup and view all the answers

Jakie pamięci są charakterystyczne dla maszyn z pamięcią współdzieloną (SM)?

Wspólna przestrzeń adresowa dla wszystkich procesorów. Signup and view all the answers

Które z poniższych stwierdzeń dotyczących maszyn typu MIMD jest poprawne?

Każdy procesor ma niezależną przestrzeń adresową. Signup and view all the answers

Co jest typowe dla komputerów z wielordzeniowymi procesorami?

Są maszynami typu MIMD. Signup and view all the answers

Jaka jest główna różnica między pamięcią wspólną (SM) a pamięcią rozproszoną (DM)?

W SM każdy procesor ma dostęp do tej samej pamięci. Signup and view all the answers

Które z poniższych stwierdzeń jest prawdziwe o pamięci lokalnej (DM)?

Każdy programista musi znać adresy pamięci. Signup and view all the answers

Jaki był główny impuls do rozwoju pamięci lokalnej i rozproszonych systemów komputerowych?

Rozwój sieci komputerowych w latach 90-tych XX wieku. Signup and view all the answers

Jakie operacje są przedstawione w fragmentach kodu?

Dodawanie i dzielenie elementów tablic. Signup and view all the answers

Jakie są różnice w dostępie do pamięci między SM a DM?

W DM, każdy procesor ma swój własny adres pamięci. Signup and view all the answers

Jakie są kluczowe cechy architektur MIMD?

Każdy procesor może wykonywać różne instrukcje niezależnie. Signup and view all the answers

Co oznacza pojęcie 'równoległość procesowa'?

Wykonywanie wielu niezależnych zadań przez wiele procesorów. Signup and view all the answers

Jakie są potencjalne problemy związane z przetwarzaniem równoległym?

Zwiększone opóźnienia w przekazywaniu informacji. Signup and view all the answers

Które z poniższych opisuje 'przetwarzanie rozproszone'?

Systemy składające się z wielu elementów przetwarzających lub przechowujących. Signup and view all the answers

Jaką rolę odgrywa czas dostępu do pamięci w Hierarchicznej Pamięci Współdzielonej?

Czas dostępu zależy od lokalizacji pamięci w hierarchii. Signup and view all the answers

Dlaczego zmiany w algorytmie są często konieczne przy wzroście udziału kodu równoległego?

Zwiększenie równoległości wymaga lepszego podziału zadań. Signup and view all the answers

Czym różni się system równoległy od systemu rozproszonego?

System równoległy działa na jednym problemie, a rozproszony na wielu. Signup and view all the answers

Jakie podejście reprezentuje 'równoległość tablicowa'?

Wykonywanie wielu operacji na tych samych danych równocześnie. Signup and view all the answers

Jaką rolę pełni warunek 'brak_danych' w monitorze 'wyświetlaj_dane'?

Służy do czekania na ustawienie liczby. Signup and view all the answers

Jakie są wartości domyślne dla 'liczba_dostępna' w monitorze?

false Signup and view all the answers

Co się stanie, gdy procedura 'ustaw' zostanie wywołana?

Ustawia wartość liczby i sygnalizuje dostępność danych. Signup and view all the answers

Jakie równanie przedstawia prawo Amdahla dotyczące przyspieszenia?

S(n, P) = β(n) + 1 - β(n) / P Signup and view all the answers

Czym jest efektywność programu równoległego?

Proporcją czasu obliczeń do czasu dodatkowego. Signup and view all the answers

Jakie jest znaczenie zmiennych β(n) i (1 - β(n)) w równaniu przyspieszenia?

Określają proporcje pomiędzy częścią sekwencyjną a równoległą. Signup and view all the answers

Co oznacza oznaczenie 'S(n, P) > P' w kontekście przyspieszenia?

Przyspieszenie może być większe niż liczba procesorów. Signup and view all the answers

Jak można zmierzyć niebalansowanie obciążenia systemu?

Obliczając czas maksymalny zrealizowanych procesów. Signup and view all the answers

Study Notes

Wprowadzenie do programowania rozproszonego i równoległego

Wykład oparty na książce „Wprowadzenie do obliczeń równoległych" Z.J.Czech, PWN, 2013.
Autor wykładu: Piotr Marek Oramus.
Wykład obejmuje tematykę historii, definicji przetwarzania sekwencyjnego, współbieżnego i równoległego, architektury systemów, parametrów i praw rządzących programowaniem rozproszonym i równoległym.

Historia

Pierwszy komputer ogólnego przeznaczenia - UNIVAC I (1951) - 1 kflop/s.
Ewolucja pracy z komputerami:
- Lata 60. - praca w pokoju z komputerem.
- Lata 70. - praca w pokoju terminalowym.
- Lata 80. - praca przy własnym biurku.
- Lata 90. - komputery mobilne.
Superkomputer Prometheus (czerw. 2024) - 2,65 Pflop/s, składa się z 55 Helios GPU, 177 Athena, 305 Helios CPU i 442 Ares.
Popularność wielordzeniowych procesorów w komputerach osobistych (PC).
Przykładowe komputery:
- Raspberry Pi Pico W - dwurdzeniowy ARM Cortex M0+ @133MHz.
- Six-core "Istanbul" Opteron.

Po co przetwarzać równolegle?

Przykładem jest symulacja pogody:
- Siatka nad Polską - 7 350 000 000 komórek elementarnych.
- 100 operacji zmiennoprzecinkowych na komórkę.
- Symulacja 4 dni z krokiem czasowym 5 minut.
- Potrzeba 84 700 000 000 000 operacji zmiennoprzecinkowych.
- Jedyny CPU o wydajności 1GFlop/s wykonuje rachunki w 10 dni.
CPU o wydajności 1TFlop/s może teoretycznie zakończyć rachunki w 15 minut, ale:
- Potrzeba 350GB pamięci.
- Dane z RAM do CPU muszą być przesyłane 1 000 000 000 000 razy/sek.

Program sekwencyjny

Składa się z jednego ciągu instrukcji.
Przekształca dane wejściowe w wyjściowe.
Wykonywany przez jeden wirtualny procesor.
Operacje wykonywane są kolejno po sobie.
Przykład:

for ( i = 0; i < size; i++ )
    C[ i ] = A[ i ] + B[ i ];

for (j = 0; j < size; j++ )
    D[j] = E[ j ] / F[j];

Maszyny typu MIMD (Multiple Instractions Multiple Data)

Dzielą się na:
- Shared Memory (SM):
  - Pamięć wspólna, współdzielona, globalna.
  - Wszystkie procesory mają dostęp do wspólnej przestrzeni adresowej.
  - Typowy przykład: komputer z wielordzeniowym procesorem.
- Distributed Memory (DM):
  - Pamięć lokalna, rozproszona.
  - Programista musi podzielić dane.
  - Odczyt danych wymaga znajomości adresu i lokalizacji pamięci.
  - Typowy przykład: klaster obliczeniowy.
Architektury z pamięcią wspólną:
- Rozwiązania sprzętowe (np. SGI Origin 2000).
- Rozwiązania programowe (np. vSMP).
Hierarchiczna pamięć współdzielona - czas dostępu do pamięci zależy od jej lokalizacji.

Wnioski

Przetwarzanie równoległe często jest konieczne.
Wymiana informacji między procesorami generuje narzuty.
Zwiększenie udziału kodu równoległego może wymagać zmiany algorytmu.

Definicje

Równoległość procesowa: wykonywanie niezależnych zadań przez wiele procesorów (np. supermarket/bank).
Równoległość tablicowa: przetwarzanie multimediów (np. musztra wojskowa).
Równoległość potokowa: wykonywanie działań w łańcuchu (np. taśma produkcyjna).
Przetwarzanie rozproszone: system z wieloma elementami przetwarzającymi, przechowującymi, współbieżnymi lub działającymi programami, które są ze sobą powiązane (luźno lub ściśle).
System równoległy: ściśle powiązany system rozproszony, gdzie zasoby są podporządkowane rozwiązaniu jednego problemu.
System rozproszony: może pracować nad wieloma problemami równocześnie.
Monitor: mechanizm synchronizacji, który zarządza dostępem do zasobów współdzielonych.
- Przykład: monitor z warunkiem, który czeka na ustawienie wartości zmiennej.

Parametry

Lokalność: zakres danych, do których procesor ma bezpośredni dostęp.
Granulacja: rozmiar pojedynczej jednostki pracy (program grubo/drobno-ziarnisty).
Niezbalansowanie obciążenia systemu: mierzy się w procentach.
Determinizm: powtarzalność wyników przy tych samych danych.
Przyspieszenie: stosunek czasu wykonania programu sekwencyjnego do równoległego.
Efektywność: stosunek przyspieszenia do liczby procesorów.
Prawo Amdahla: określa maksymalne osiągalne przyspieszenie dla programu, które zawiera część sekwencyjną i równoległą.

Prawa rządzące programowaniem rozproszonym i równoległym

Prawo Amdahla:
- Określa maksymalne przyspieszenie programu.
- Zależne od udziału kodu sekwencyjnego.
- Im większy udział kodu sekwencyjnego, tym mniejsze maksymalne przyspieszenie.
Prawo Gustafsona:
- Skalowanie problemu wraz ze wzrostem liczby procesorów.
- Zamiast minimalizować czas wykonywania, celem jest rozwiązanie większego problemu w tym samym czasie.
Prawo skalowania:
- Określa, jak wydajność systemu zmienia się wraz ze wzrostem liczby procesorów.
- Zależne od architektury i algorytmu.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Ten quiz oparty jest na książce „Wprowadzenie do obliczeń równoległych”, autorstwa Z.J.Czech. Skupia się na historii rozwoju programowania sekwencyjnego, współbieżnego oraz równoległego. Zawiera także istotne informacje o architekturze systemów i parametrach programowania rozproszonego.