Pw egzamin - sama teoria
Parallel Programming Quiz
Test your knowledge of parallel programming concepts with our comprehensive quiz!
Whether you are a beginner or an experienced developer, this quiz covers various topics related to parallel computing, including:
- SPMD and MPMD models
- Amdahl's Law and Gustafson's analysis
- OpenMP and pthreads
- Thread management and synchronization
Model programowania SPMD (single program multiple data):
Może być realizowany tylko na maszynach SIMD
może być realizowany I w MPI, I w OpenMP
Zawsze polega na wzbogaceniu kodu sekwencyjnego dyrektywami kompilatora
W standardowych środowiskach programowania jest ogólniejszy niż MPMD (każdy program MPMD można sprowadzić do SPMD)
Wymaga, aby każda linijka kodu była wykonywana przez wszystkie procesy (wątki), tyle że pracujące na różnych danych
Standardowe programy w stosunku do programu rozważanego w analizie Amdahla mają najczęściej:
Mniejszy udział części nie dającej się zrównoleglić
Większy udział części nie dającej się zrównoleglić
Mniejszy czas komunikacji
Większy czas komunikacji
Gorsze przyspieszenie obliczeń równoległych (dla dużych p)
Lepsze przyspieszenie obliczeń równoległych (dla dużych p)
Sposób podziału iteracji równoległej pętli for pomiędzy wątki przy zastosowaniu klauzuli schedule (dynamic) oznacza, że:
Przydział będzie dokonywany w trakcie działania programu
. Jeden wątek może dostać wszystkie iteracje
Liczba iteracji przydzielanych poszczególnym wątkom może być różna
narzut związany z wykonaniem równoległym będzie duży
rozmiar porcji będzie zmienny (określany dynamicznie)
rozmiar porcji będzie równy 1
Sposób podziału w ostateczności zależeć będzie od wartości odpowiedniej zmiennej środowiskowej
Klauzula firstprivate oznacza, że objęta nią zmienna:
Będzie prywatna dla pierwszego wątku
Będzie pierwszą zmienną prywatną wątków
Będzie zmienną prywatną wątków inicjalizowaną jako pierwsza
będzie zmienną prywatną wątków, inicjalizowaną wartością sprzed rozpoczęcia wykonywania dyrektywy
będzie zmienną prywatną wątków, której wartość z pierwszego wątku zostanie skopiowana do wątku głównego po zakończeniu wykonywania dyrektywy
W analizie Gustafsona rozważa się zadania, których czas rozwiązania programem równoległym przy rosnącej liczbie procesorów jest stały, albowiem:
Rozmiar zadania rośnie wraz z liczbą procesorów (rośnie więc czas rozwiązania na jednym procesorze)
Czas komunikacji rośnie wolniej niż czas obliczeń
udział procentowy części sekwencyjnej w czasie rozwiązania na jednym procesorze maleje wraz ze wzrostem rozmiaru zadania
. część równoległa osiąga przyspieszenie ponadliniowe
Monitor w programowaniu współbieżnym:
Jest strukturą danych zawierającą informacje o sekcjach krytycznych
Służy do monitorowania ewentualnych konfliktów wątków w dostępie do pamięci wspólnej
Jest strukturą danych gwarantującą wzajemne wykluczanie przy realizacji jego procedur
. Jest jednym z mechanizmów wbudowanych w model obiektów Javy
jest jednym z mechanizmów wbudowanych w model muteksów pthreads
W wyniku wykonania procedury systemowej fork powstają dwa procesy realizujące ten sam kod, które:
Posiadają wspólne zmienne globalne
Posiadają wspólne zmienne lokalne
Otrzymują jako wartość zwracaną funkcji fork nazwajem swoje identyfikatory
Są w pełnie niezależne I nie mogą być synchronizowane
Pełnią różne role: jeden jest procesem nadrzędnym, drugi potomnym
Proces nadrzędny może synchronizować swoje działanie z działaniem procesu potomnego
Przetwarzanie w przeplocie oznacza sytuację kiedy:
System operacyjny przydziela wątki tego samego zadania różnym rdzeniom (procesom)
System operacyjny realizuje przetwarzanie współbieżne na jednym procesorze (rdzeniu)
Procesor(rdzeń) stosuje tzw. Simultaneous multithreading
pojedynczy procesor (rdzeń) na przemian wykonuje fragmenty wielu wątków
pojedynczy proces korzysta na przemian z wielu rdzeni
Argumentami procedury tworzenia nowego wątku pthread_create są m.in.:
Nazwa funkcji, którą zacznie wykonywać wątek – funkcji startowej wątku (będąca w rzeczywistości wskaźnikiem do funkcji)
Rozmiar stosu przydzielonego wątkowi
Zadany przez użytkownika identyfikator wątku
Obiekt określający atrybuty (m. in. sposób funkcjonowania) wątku
Argument dla funkcji startowej wątku będący wskaźnikiem
Cechami charakterystycznymi funkcjonowania wątków Pthreads są m.in.
Istnienie odrębnych funkcji tworzenia I uruchamiania wątków
Brak możliwości zmiany domyślnego sposobu funkcjonowania wątków w trakcie ich tworzenia
Konieczność używania jako funkcji startowej wątków, funkcji o tylko jednym argumencie
Posługiwanie się identyfikatorami wątków tożsamymi z identyfikatorami z systemu operacyjnego
Każdy wątek Pthreads posiada własne, niezależne od innych wątków:
Przestrzeń adresową
Przestrzeń pamięciową jądra systemu
Ciągi algorytmiczne
Zestaw rejestrów
Własny stos
Ciąg rozkazów
Przyspieszenie równoległe programu rozwiązującego pewien problem jako funkcję liczby procesorów p można zdefiniować jako stosunek:
Czasu rozwiązania problemu najlepszym programem sekwencyjnym do czasu rozwiązania problemu p-razy większego rozważanym programem na p procesorach
czasu pracy jednego procesora przy rozwiązaniu problemu rozważanym programem na p procesorach do czasu pracy na wszystkich procesorach
Czasu rozwiązania problemu najlepszym programem sekwencyjnym do czasu rozwiązania problemu rozważanym programem na p procesorach
Liniowe (idealne) przyspieszenie obliczeń równoległych można scharakteryzować jako:
Nie dającego się nigdy przewyższyć
Przyspieszenie w sytuacji gdy czas obliczeń równoległych na p procesorach jest p razy krótszy niż czas obliczeń sekwencyjnych
Przewidywane przez analizę Amdhala
Przyspieszenie programu rozważanego w analize Amdhala ulega nasyceniu (przestaje rosnąć) mimo zwiększajacej się liczby procesów ponieważ program:
Posiada część sekwencyjną, którą zawsze musi wykonać tylko jeden proces (wątek)
Ma rozmiar rosnący wraz z liczbą procesorów
Wykazuje duży narzut na komunikację
Błedne założenie (w stosunku do praktyki stosowania rzeczywistych programów równoległych) w ramach analizy Amdhala polega na rozważaniu:
Zbyt dużej liczbie procesorów
Zadań zbyt trudnych do zrównoleglenia
Zadań o stałym rozmiarze przy rosnącej liczbie procesorów
Procesory wielordzeniowe:
Są nazywane inaczej układami scalonymi wieloprocesorowymi
Pracują w modelu SIMD (single instruction multiple data)
Nigdy nie przekroczą liczby rdzeni ok. kilkunastu
Nie posiadają pamięci podręcznej L2 I L3
żadna odpowiedź nie jest prawidłowa
Klastry:
Są specjalistycznymi superkomputerami
Powstają przez połączenie wielu komputerów siecią I wyposażenie ich w specjalne oprogramowanie pozwalające traktować je jak pojedynczy system do uruchamiania programów
Zakładają najczęściej model programowania bez pamięci wspólnej
są najdroższymi komputerami równoległymi
Skalują się (dają się praktycznie wykorzystywać) dla liczb procesorów (rdzeni) do rzędu kilku dziesięciu
Skalują się (dają się praktycznie wykorzystywać) dla liczb procesorów (rdzeni) do rzędu kilku tysięcy
Skalują się (dają się praktycznie wykorzystywać) dla liczb procesorów (rdzeni) do rzędu kilkuset tysięcy
Potokowe przetwarzanie rozkazów oznacza przetwarzanie:
Potoku rozkazów – kolejny rozkaz po zakończeniu poprzedniego
Zbliżone do pracy na taśmie produkcyjnej – pojedyncza jednostka funkcjonalna procesora realizuje tylko część przetwarzania rozkazu
dzięki któremu procesor może współbieżnie przetwarzać wiele rozkazów
Wymagające istnienia złożonych procesorów o wielu jednostkach funkcjonalnych
takie jak w kartach graficznych (inaczej przetwarzanie strumieniowe)
Wskaż prawidłową kolejność etapów przetwarzania potokowego (ID – dekodowanie rozkazu, IE – wykonanie rozkazu, IF – pobranie rozkazu, OF – pobranie argumentów, WB – zapis wyniku):
IE ID OF IF WB
ID IF WB IE OF
IE IF WB ID OF
WB IE IF ID OF
IF ID OF IE WB
Na stosie w trakcie realizacji programu przechowywane są:
dane programu
Dane wspólne procedur
Dane wejściowe (argumenty) procedur
Dane prywatne (lokalne) procedur
Dane do komunikacji procedur z systemem operacyjnym
Dane do komunikacji międzyprocesowej
Współbieżność wykonania programów P1 I P2 oznacza:
Wykonanie równoległe (wymaga systemu wieloprocesorowego)
Nakładanie się czasów wykonania (możliwe wykonanie w przeplocie na jednym procesorze)
Posiadanie wspólnej przestrzeni adresowej przez P1 I P2
Konieczność zarządzania przez system operacyjny dostępem do urządzeń wejścia/wyjścia przez P1 I P2
żadne z powyższych stwierdzeń nie jest prawdziwe
Współbieżność wykonania programów wprowadzona została w celu:
Umożliwienia działania procesorów wielordzeniowych
Usprawnienia pracy komputera przy realizacji operacji wejścia/wyjścia
Szybszej obsługi połączeń sieciowych
Umożliwienia funkcjonowania procesów wielowątkowych
żadne z powyższych stwierdzeń nie jest prawdziwe
Proces od wątku różni się m.in.:
Posiadaniem własnego zestawu rejestrów w trakcie wykonania (wątek współdzieli rejestry z innymi wątkami tego samego procesu)
Posiadaniem własnej przestrzeni adresowej (wątek współdzieli przestrzeń adresową z innymi wątkami tego samego procesu)
Posiadaniem bardziej rozbudowanej struktury umożliwiającej zarządzanie przez system operacyjny
Posiadaniem wyższego priorytetu wykonania
żadne z powyższych stwierdzeń nie jest prawdziwe
W skład narzędzi programowania OpenMP wchodzą:
Dyrektywy kompilatora
Funkcje biblioteczne
Predefiniowane obiekty (struktury)
Typy danych
Zmienne środowiskowe
żadna odpowiedź nie jest prawidłowa
W trakcie wykonania programu OpenMP obszar równoległy:
Zaczyna się po dyrektywie parallel
Zaczyna się po dowolnej dyrektywie podziału pracy
Oznacza, że program może być wykonywany wielowątkowo (w przeciwieństwie do obszaru sekwencyjnego)
Oznacza, że zmienne prywatne funkcjonują w wielu kopiach (po jednej dla każdego wątku)
żadna odpowiedź nie jest prawidłowa
Liczba wątków tworzonych przy wchodzeniu do obszaru równoległego może (jeśli system pozwala) zostać jawnie określona za pomocą:
Klauzuli num_threads dyrektywy parallel
Klauzuli num_threads dowolnej dyrektywy podziału pracy
Procedury omp_set_num_threads wewnątrz obszaru równoległego
Procedury omp_set_num_threads przed wejściem do obszaru równoległego
Zmiennej środowiskowej OMP_NUM_THREADS ustawianej przed uruchomieniem programu
Zmiennej środowiskowej OMP_NUM_THREADS ustawianej przed wejściem przez program do obszaru równoległego
żadna odpowiedź nie jest prawidłowa
Zmiana wartości zmiennej wspólnej w OpenMP:
Musi odbywać się w sekcji krytycznej
Może, a czasami powinna odbywać się w sekcji krytycznej
Może być dokonana przez dowolny wątek w obszarze równoległym
może zostać zrealizowana niepodzielnie (dyrektywa atomic)
Dokonana przez jeden wątek jest widoczna dla wszystkich wątków
żadna odpowiedź nie jest prawidłowa
Zmiana wartości zmiennej prywatnej w OpenMP:
Musi odbywać się w sekcji krytycznej
Powinna odbywać się w sekcji krytycznej
Może być dokonana przez dowolny wątek w obszarze równoległym
dokonana przez jeden wątek jest widoczna dla wszystkich wątków
Może zostać zrealizowana niepodzielnie (dyrektywa atomic)
żadna odpowiedź nie jest prawidłowa
Zmienna lokalna funkcji staje się zmienną prywatną wątków w obszarze równoległym jeśli w kodzie:
Jest objęta dyrektywą threadprivate w dowolnej funkcji
Jest objęta dyrektywą threadprivate w tej samej funkcji, w której znajduje się dyrektywa parallel
jest objęta jedną z klauzul private, firstprivate itp. W dyrektywie parallel danego obszaru równoległego
Jest objęta jedną z klauzul private, firstprivate itp. W dyrektywie parallel danego obszaru równoległego w danej funkcji
Jest zmienną sterującą pętli for
Jest zmienną sterującą równoległej pętli for
żadna odpowiedź nie jest prawidłowa
Zakończenie operacji wysyłania danych procedurą MPI_Send (powrót z procedury) lub MPI_Isend (np. powrót z procedury MPI_Wait) oznacza zawsze, że:
Dane dotarły do adresata
System odnalazł adresata gotowego do odebrania komunikatu (adresata, który wywołał procedurę MPI_Recv z pasującymi argumentami)
System skopiował dane do wewnętrznego bufora przesyłania danych
Obszary danych objęte poleceniem wysyłania mogą być zmieniane, co nie spowoduje zmiany zawartości komunikatu
System potwierdził rozpoczęcie operacji przesyłania danych
żadna z powyższych odpowiedzi nie jest prawidłowa
Po powrocie z procedury odbierania nieblokującego MPI_Irecv( &a, ……… &req), gdzie a oznacza pewną zmienną, mamy pewność, że wartość a jest wartością otrzymaną w komunikacie P:
Od razu
Dopiero po sprawdzeniu zawartości obiektu req (type MPI_Request)
Dopiero po powrocie z procedury MPI_Wait (& req, & stat)
Dopiero po powrocie z procedury MPI_Wait (& req, & stat) I sprawdzeniu odpowiedniej zmiany wartości obiektu stat
Dopiero po powrocie z procedury MPI_Test (& req, & flag, & stat)
Dopiero po powrocie z procedury MPI_Test (& req, & flag, & stat) I sprawdzeniu odpowiedniej zmiany wartości obiektu stat
Dopiero po powrocie z procedury MPI_Test (& req, & flag, & stat) I sprawdzeniu odpowiedniej zmiany wartości zmiennej flag
żadna z powyższych odpowiedzi nie jest prawidłowa
Komunikator w MPI:
Jest konieczny tylko do przeprowadzenia komunikacji grupowej
Jest konieczny do realizacji dowolnego przesyłania komunikatów
Oznacza grupę procesów I związane z nią informacje umożliwiające wymianę komunikatów
Oznacza proces pośredniczący w wymianie komunikatów
Jest reprezentowany zawsze przez obiekt MPI_COMM_WORLD
Jest zawsze tylko jeden w programie
Jest co najmniej jeden w programie; jeśli jeden, to jest to MPI_COMM_WORLD
Jest co najmniej jeden w programie, zawsze typu MPI_Comm
żadne z powyższych twierdzeń nie jest prawdziwe
Przyspieszenie programu rozważanego w analizie Amdahla ulega nasyceniu (przestaje rosnąć) mimo zwiększającej się liczby procesorów ponieważ program:
Posiada część sekwencyjną, którą zawsze musi wykonywać tylko jeden proces (wątek)
Ma rozmiar rosnący wraz z liczbą procesorów
Wykazuje duży narzut na komunikację
Błędne założenie (w stosunku do praktyki stosowania rzeczywistych programów równoległych) w ramach analizy Amdahla polega na rozważaniu:
Zbyt dużej liczby procesorów
Zadań zbyt trudnych do zrównoleglenia
Zadań o stałym rozmiarze przy rosnącej liczbie procesorów
W analizie Gustaffsona rozważa się zadania w których rozmiar rośnie wraz z liczbą procesorów ale czas rozwiązania programem równoległym na p procesorach jest stały albowiem zakłada się że:
Czas komunikacji rośnie wolniej niż czas obliczeń
Udział procentowy części sekwencyjnej w czasie rozwiązania na jednym procesorze maleje wraz z wzrostem rozmiaru zadania
Część równoległa osiąga przyspieszenie ponadliniowe
W analizie Amdahla rozważa się zrównoleglenie programu:
którego sekwencyjny czas rozwiązania problemu jest najkrótszy z możliwych
Którego czas wykonania sekwencyjnego jest równy sumie czasu wykonania części sekwencyjnej I części dającej się zrównoleglić
Który posiada część, którą zawsze musi wykonywać jeden proces (wątek)
Który posiada część dającą się zrównoleglić z idealną komunikacją
Który posiada część dającą się zrównoleglić idealnie
Który daje się wydajniej (efektywniej) zrównoleglić niż zdecydowana większość programów rzeczywistych
W analizie Amdahla graniczną wartość przyspieszenia obliczeń , której nie może przekroczy program o czasie wykonywania T(p) = s+r/p jest (w poniższych wzorach f oznacza t.zw. udział części sekwencyjnej f = s/(s+r))
F
1+f
1+ 1/f
1/f
1/(1+f)
1/( 1+ 1/f)
żadna odpowiedź nie jest prawidłowa
Złożoność obliczeniowa algorytmu to:
Stopień skomplikowania algorytmu
Wymagany stopień skomplikowania komputera konieczny do realizacji algorytmu
Ilość zasobów komputera wymaganych do realizacji algorytmu
Ilość zasobów komputera wymaganych do realizacji algorytmu dla najbardziej wymagających (skomplikowanych) danych
Ilość zasobów komputera wymaganych do realizacji algorytmu jako funkcja rozmiaru danych wejściowych
Złożoność pesymistyczna algorytmu oznacza:
Złożoność dla największych dopuszczalnych danych
Złożoność dla najmniej korzystnych warunków realizacji zadania
złożoność dla najmniej korzystnych przypadków danych wejściowych
Złożoność dla najmniej korzystnych architektur procesorów
Algorytmy sortowania posiadają złożoność czasową:
Liniową (problem „łatwy”)
Wielomianową (problem „łatwy”)
Wykładniczą (problem „trudny”)
Silnia (problem „trudny”)
Nie można określić nie podając o jaką złożoność chodzi (optymistyczną, pesymistyczną czy oczekiwaną)
Problem nie posiada rozwiązania, prowadzi do sprzeczności
Złożoność czasowa algorytmu obliczania średniej ciągu liczb jest funkcją liczby liczb w ciągu:
Liniową (problem „łatwy”)
Wielomianową (problem „łatwy”)
Wykładniczą (problem „trudny”)
Silnia (problem „trudny”)
Nie można określić nie podając o jaką złożoność chodzi (optymistyczną, pesymistyczną czy oczekiwaną)
problem nie posiada rozwiązania, prowadzi do sprzeczności
{"name":"Pw egzamin - sama teoria", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"Test your knowledge of parallel programming concepts with our comprehensive quiz!Whether you are a beginner or an experienced developer, this quiz covers various topics related to parallel computing, including:SPMD and MPMD modelsAmdahl's Law and Gustafson's analysisOpenMP and pthreadsThread management and synchronization","img":"https:/images/course4.png"}