Zestaw 1
Załóżmy, że sieć poniżej jest modelem pewnego przedsięwzięcia. Który wierzchołek może opisywać zdarzenie początkowe?
1 – bo nie dochodzą do tego wierzchołka żadne łuki; jest to jedyny taki wierzchołek
2
5
7
Sieć poniżej jest modelem pewnego przedsięwzięcia. Czasy realizacji wszystkich czynności wynoszą 1. Jaki jest luz czasowy zdarzenia 5?
0
1
2
3
Jeżeli algorytm o złożoności O(n4) w ciągu 1h jest w stanie rozwiązać problem o rozmiarze N to jeżeli prędkość procesora wzrośnie 1000-krotnie wówczas w tym samym czasie rozwiążemy problem o rozmiarze:
10 n
5,62 n * (wykład 1, strona 7 - sposób) => 1000^(1/4)
250 n
3,98n
Jeżeli algorytm sekwencyjny w ciągu 1h jest w stanie rozwiązać problem o rozmiarze N, to jeżeli dysponować będziemy p = 10 procesorami (przy założeniu braku opóźnień komunikacyjnych i połączeniach między procesorami typy każdy z każdym) to w czasie 1h rozwiążemy problem o rozmiarze:
>=10N
= 10N
<=10N
chuj wie
Jeżeli czas działania algorytmu sekwencyjnego wynosi 3 oraz czas działania algorytmu równoległego przy założeniu, że dostatecznie duża liczba procesorów jest dostępna, wynosi 2, to górne ograniczenie na czas działania alg. równoległego reprezentowanego przez pewien AGS i wykorzystującego p = 3 procesory będzie:
<=2
<=5
<=4
<=3
Jeżeli czas działania algorytmu sekwencyjnego wynosi 7 oraz czas działania algorytmu równoległego przy założeniu, że dostatecznie duża liczba procesorów jest dostępna wynosi 3, to dolne ograniczenie na czas działania alg równoległego reprezentowanego przez pewien AGS i wykorzystującego p = 2 procesory będzie:
>=3
>=7
>=2
>=1
Załóżmy, że graf z zadania 2 reprezentuje AGS pewnego problemu obliczeniowego w którym pominięto wierzchołki wejściowe. Ile wynosi optymalna liczba procesorów p* dla tego AGS:
3
2
1
6
Najkrótsza droga dla sieci z zadania 1 z wierzchołka nr 1 do wierzchołka nr 5 ma długość:
9
12
14
23
Załóżmy, że graf z zad 2 reprezentuje AGS pewnego problemu obliczeniowego w którym pominięto wierzchołki wejściowe. Ile wynosi długość harmonogramu przy założeniu, że liczba procesorów p = 3:
3
6
5
7
Jeżeli czas działania algorytmu sekwencyjnego wynosi 5 oraz czas działania algorytmu równoległego (reprezentowanego przez pewien AGS) przy p=3 procesorach wynosi 3 to dolne ograniczenie na czas działania alg równoległego przy dostatecznie dużej liczbie procesorów będzie:
>=2
>=1
>=3
>=5
W praktyce efektywność algorytmu równoległego wykorzystującego p procesorów jest:
Zawsze <=1
Zawsze należy do przedziału [0, 1]
Zawsze jest >1
Może być >1
Który z wymienionych elementów stanowi podstawową zaletę obliczeń asynchronicznych:
znaczna redukcja czasu obliczeń (wykład 3 str. 15)
mniejsza częstotliwość przesyłania danych między procesorami
łatwość w określeniu zbieżności algorytmu
szybsza komunikacja między procesorami
Długość harmonogramu wyznaczanego dla grafu AGS jest w szeregowaniu zadań nazywana:
całkowitym czasem zakończenia zadania
max opóźnieniem
max spóźnieniem
długością uszeregowania
Mamy listę 5-ciu zadań o czasach wykonywania odpowiednio: 5, 4, 7, 3, 2. Długość uszeregowania tych zadań na p = 2 procesorach według zasady LPT wynosi:
11
13
12
10
Algorytm Hu służy do szeregowania:
zadań niepodzielnych, niezależnych na procesorach identycznych
zadań niepodzielnych, niezależnych na procesorach dowolnych
zadań niepodzielnych, zależnych na procesorach identycznych
zadań niepodzielnych, zależnych na procesorach dowolnych
ZESTAW 3
Załóżmy, że sieć poniżej jest modelem pewnego przedsięwzięcia. Który wierzchołek może opisywać zdarzenie początkowe?
1 – bo nie dochodzą do tego wierzchołka żadne łuki; jest to jedyny taki wierzchołek
2
5
7
Sieć poniżej jest modelem pewnego przedsięwzięcia. Czasy realizacji wszystkich czynności wynoszą? Jaki jest luz czasowy zdarzenia?
2
3
4
1
Jeżeli algorytm o złożoności O(n2) w ciągu 1h jest w stanie rozwiązać problem o rozmiarze N to jeżeli prędkość procesora wzrośnie 1000-krotnie wówczas w tym samym czasie rozwiążemy problem o rozmiarze:
500 n
31,62 n
10.0 n
1000 n
Jeżeli algorytm sekwencyjny w ciągu 1h jest w stanie rozwiązać problem o rozmiarze N, to jeżeli dysponować będziemy p = 5 procesorami (przy założeniu braku opóźnień komunikacyjnych i połączeniach między procesorami typy każdy z każdym) to w czasie 1h rozwiążemy problem o rozmiarze:
>=5N
= 5N
<=5N
chuj wie
Jeżeli czas działania algorytmu sekwencyjnego wynosi 7 oraz czas działania algorytmu równoległego przy założeniu, że dostatecznie duża liczba procesorów jest dostępna, wynosi 2, to górne ograniczenie na czas działania alg. równoległego reprezentowanego przez pewien AGS i wykorzystującego p = 3 procesory będzie:
<=4
<5
<4
<=5
Jeżeli czas działania algorytmu sekwencyjnego wynosi 11 oraz czas działania algorytmu równoległego przy założeniu, że dostatecznie duża liczba procesorów jest dostępna wynosi 5, to dolne ograniczenie na czas działania alg równoległego reprezentowanego przez pewien AGS i wykorzystującego p = 3 procesory będzie:
>=3
>=11
>=5
>=2
Załóżmy, że graf z zadania 2 reprezentuje AGS pewnego problemu obliczeniowego w którym pominięto wierzchołki wejściowe. Ile wynosi optymalna liczba procesorów p* dla tego AGS:
3
2
1
4
Najkrótsza droga dla sieci z zadania 1 z wierzchołka nr 1 do wierzchołka nr 4 ma długość:
13
12
14
23
Załóżmy, że graf z zad 2 reprezentuje AGS pewnego problemu obliczeniowego w którym pominięto wierzchołki wejściowe. Ile wynosi długość harmonogramu przy założeniu, że liczba procesorów p = 1:
8 (podobno ok)
6
5
7
Jeżeli czas działania algorytmu sekwencyjnego wynosi 8 oraz czas działania algorytmu równoległego (reprezentowanego przez pewien AGS) przy p = 3 procesorach wynosi 4 to dolne ograniczenie na czas działania alg równoległego przy dostatecznie dużej liczbie procesorów będzie
>2
>1
>=2
>=3
W praktyce efektywność algorytmu równoległego wykorzystującego p procesorów jest:
Zawsze <=1
Zawsze należy do przedziału [0,1]
Zawsze jest >1
Może być >1
Który z wymienionych elementów stanowi podstawową zaletę obliczeń synchronicznych:
Mała częstotliwość przesyłania danych między procesorami
Znaczna redukcja czasu obliczeń
Małe opóźnienia w realizacji operacji
Szybsza komunikacja między procesorami
Długość harmonogramu wyznaczanego dla grafu AGS jest w szeregowaniu zadań nazywana:
całkowitym czasem zakończenia zadania
max opóźnieniem
max spóźnieniem
długością uszeregowania
Mamy listę 5-ciu zadań o czasach wykonywania odpowiednio: 5, 4, 7, 3, 2. Długość uszeregowania tych zadań na p = 2 procesorach według zasady LPT wynosi:
12
11
13
21
Algorytm Hu służy do szeregowania:
zadań podzielnych, zależnych na procesorach identycznych
zadań podzielnych, zależnych na procesorach dowolnych
zadań niepodzielnych, zależnych na procesorach identycznych
zadań niepodzielnych, zależnych na procesorach dowolnych
ZESTAW 4
Załóżmy, że sieć poniżej jest modelem pewnego przedsięwzięcia. Jaki jest najwcześniejszy termin realizacji przedsięwzięcia (zdarzeniem końcowym jest zdarzenie nr 5):
23
17
14
18
Sieć poniżej jest modelem pewnego przedsięwzięcia. Czasy realizacji wszystkich czynności wynoszą 1. Jaki jest najpóźniejszy dopuszczalny termin rozpoczęcia czynności J:
2
3
4
1
W praktyce przyspieszenie algorytmu równoległego wykorzystującego p procesorów jest:
zawsze należy do przedziału [1, p]
zawsze jest <= 1
może być <=1
może być >=p
Załóżmy, że graf z zad 2 reprezentuje AGS pewnego problemu obliczeniowego w którym pominięto wierzchołki wejściowe. Ile wynosi długość harmonogramu przy założeniu że liczba procesorów p = 2?
4
6
5
7
Załóżmy, że graf z zad 2 reprezentuje AGS pewnego problemu obliczeniowego w którym pominięto wierzchołki wejściowe. Ile wynosi optymalna długość harmonogramu dla tego AGS?
5
4
6
1
Jeżeli czas działania algorytmu sekwencyjnego wynosi 10 oraz czas działania algorytmu równoległego przy założeniu, że dostatecznie duża liczba procesorów jest dostępna wynosi 4, to dolne ograniczenie na czas działania alg równoległego reprezentowanego przez pewien AGS i wykorzystującego p = 5 procesory będzie:
>=3
<=10
>=5
>=4
Jeżeli czas działania algorytmu sekwencyjnego wynosi 5 oraz czas działania algorytmu równoległego przy założeniu, że dostatecznie duża liczba procesorów jest dostępna wynosi 3, to przyspieszenie algorytmu równoległego z dowolna liczbą procesorów:
<=0.6
<=1.67
>=0.6
>=2
Najkrótsza droga dla sieci z zadania 1 z wierzchołka nr 1 do wierzchołka nr 5 ma długość:
14 (1->7->8->3->5)
17
23
13
Jeżeli algorytm sekwencyjny w ciągu 1h jest w stanie rozwiązać problem o rozmiarze N, to jeżeli dysponować będziemy p = 11 procesorami (przy założeniu braku opóźnień komunikacyjnych i połączeniach między procesorami typu każdy z każdym) to w czasie 1h rozwiążemy problem o rozmiarze:
>=11N
= 11N
<=11N
chuj wie
Jeżeli algorytm o złożoności O(n^(1/8)) w ciągu 1h jest w stanie rozwiązać problem o rozmiarze N, to jeżeli prędkość procesorów wzrośnie 10-krotnie wówczas w tym samym czasie rozwiążemy problem o rozmiarze:
10 N
N
100N
1000N
10^8 N
Efektywność algorytmu równoległego reprezentowanego przez AGS z zadania 2 (w którym pominięto wierzchołki wejściowe) dla p = 4 procesorów jest:
0.5
0.8
0.4
0.2
Mamy listę 5-ciu zadań o czasach wykonywania odpowiednio: 8, 4, 7, 3, 2. Długość uszeregowania tych zadań na p = 2 procesorach według zasady LPT wynosi:
13
11
12
10
Algorytm wyznaczania ścieżki krytycznej służy do szeregowania:
zadań niezależnych, niepodzielnych w systemach jednoprocesorowych
zadań niezależnych, podzielnych w systemach jednoprocesorowych
zadań zależnych, niepodzielnych w systemach bezprocesorowych
zadań zależnych, podzielnych w systemach bezprocesorowych.
Który z wymienionych elementów stanowi podstawową wadę obliczeń synchronicznych:
duża częstotliwość przesyłania danych między procesorami
znaczne wydłużenie czasu obliczeń
trudność w określeniu zbieżności algorytmu
wolniejsza komunikacja między procesorami (?)
Przyspieszenie algorytmu równoległego reprezentowanego przez AGS z zadania 2, w którym pominięto wierzchołki wejściowe, dla p = 2 procesorów jest równe:
2.0
0.8
1.2
1.6
Przykładowe pytania testowe
Wartość efektywności algorytmu równoległego:
zawsze jest >=1;
zawsze jest <=1;
nie musi być >=1;
nie musi być <=1;
Harmonogramowanie według reguły SPT oraz LPT:
gwarantuje otrzymanie tej samej postaci harmonogramu, ale inną długość harmonogramu;
gwarantuje otrzymanie tej samej postaci harmonogramu oraz tą samą długość harmonogramu;
nie gwarantuje otrzymanie tej samej postaci harmonogramu, ale tą samą długość harmonogramu;
nie gwarantuje otrzymanie tej samej postaci harmonogramu, ani tej samej długości harmonogramu;
Podstawową wadą obliczeń asynchronicznych jest:
wydłużenie czasu obliczeń w stosunku do obliczeń synchronicznych;
duża intensywność przesyłania danych między procesorami;
zwiększenie rozmiaru danych do obliczeń;
zmniejszenie dokładności otrzymanych rozwiązań;
Część Nowaka
Grupa 1
Różnice między modelem „stacja robocza = serwer” a modelem „pula procesorów”.
Wytłumacz działanie ssi w klastrze obliczeniowym.
Opisać sposób rozpraszania obliczeń w pvm.
Grupa 2
Różnica między now i pulą procesorów.
Realizowanie obliczeń równoległych w mpi.
Pytanie z ssi. (konkretnie jakie nie wiem, pewnie opisać)
Wyszukiwarka
Podobne podstrony:
ORR Testy
MND Testy Wersja Mini (v0 1)
Prezentacja kwalifikacja testy
Wyklad 6 Testy zgodnosci dopasowania PL
Testy immunologiczne
Metodologia SPSS Zastosowanie komputerów Brzezicka Rotkiewicz Testy zależne
06 Testy korelacjiid 6413 ppt
wyklad 6 Testy zgodnosci dopasowania PL
W 4 biomonitoring testy rodzaje
BM 4 3 Testy projekcyjne
testy nieparametryczne
Testy Krak w
2008 04 testy odpowiedzi
więcej podobnych podstron