Sprawozdanie.doc

WOJSKOWA AKADEMIA TECHNICZNA

Laboratorium z przedmiotu

Obliczenia równoległe i rozproszone

SPRAWOZDANIE

Sprawozdanie wykonał:

Tomasz Florczak

I7B1S1

Prowadzący:

mgr Adam Misztak

Warszawa 5.06.2010

Numer zadania: 8

Wyszukiwanie wzorca długości k w tekście o długości n, n>k

Graf AGS:

Graf narysowany jest dla wzorca długości 3 (x5,x6,x7) w tekście o długości 5 (x0,x1,x2,x3,x4). Operacja „=” odzwierciedla porównywanie liter (zwracane jest 1- true albo 0 - false), natomiast operacja AND to iloczyn logiczny.

Harmonogram dla tego samego wzorca i tekstu uwzględniający równoległość:

Klasa pesymistycznej złożoności obliczeniowej algorytmu sekwencyjnego jest równa O(n × k), gdzie n oznacza liczbę znaków tekstu, a k liczbę znaków wzorca. Jednakże w typowych warunkach algorytm pracuje w czasie O(n), ponieważ zwykle wystarczy porównanie kilku początkowych znaków okna z wzorcem, aby stwierdzić, iż są one niezgodne.

a)    Opóźnienia przesyłu danych między procesorami są zerowe

Dla 1 procesora:

T1 = Θ(n*k)

n oznacza liczbę znaków tekstu, a k liczbę znaków wzorca

Dla nieskończonej liczby procesorów:

T ∞ = Θ(n)

b)   Opóźnienia przesyłu danych między procesorami są równe 2 oraz opóźnienia przesyłu danych wewnątrz każdego procesora są równe 1

Dla 1 procesora:

T1 = 2n*k + 2k + n

n oznacza liczbę znaków tekstu, a k liczbę znaków wzorca

Dla nieskończonej liczby procesorów:

T ∞ = n+2n

c)    Symulacja obliczeń równoległych

I.      Jednorodne procesory, jednorodne zadania

Ilość procesorów: 3

Ilość procesorów: 5

Ilość procesorów: 9

II.  Niejednorodne procesory, Niejednorodne zadania

Ilość procesorów:

1.      3

2.      5

3.      9

Wybrane algorytmy harmonogramowania:

1.      Hu

2.      Heurystyczny

3.      SPT

4.      LPT

Wybrane algorytmy wyboru procesora:

1.      Pierwszy wolny

2.      Najdawniej nieużywany

Zostaną wykonane 24 symulacje (4*2*3) dla różnych rodzaji algorytmów i różnej ilości procesorów. Zgodnie z treścią zadania, każdy kolejny procesor jest dwa razy szybszy od poprzedniego.

Przypadek 1: 3, Hu, Pierwszy wolny

Przypadek 2: 3, Hu, Najdawniej nieużywany

Przypadek 3: 3, Heurystyczny, Pierwszy wolny

Przypadek 4: 3, Heurystyczny, Najdawniej nieużywany

Przypadek 5: 3, SPT, Pierwszy wolny

Przypadek 6: 3, SPT, Najdawniej nieużywany

Przypadek 7: 3, LPT, Pierwszy wolny

Przypadek 8: 3, LPT, Najdawniej nieużywany

Przypadek 9: 5, Hu, Pierwszy wolny

Przypadek 10: 5, Hu, Najdawniej nieużywany

Przypadek 11: 5, Heurystyczny, Pierwszy wolny

Przypadek 12: 5, Heurystyczny, Najdawniej nieużywany

Przypadek 13: 5, SPT, Pierwszy wolny

Przypadek 14: 5, SPT, Najdawniej nieużywany

Przypadek 15: 5, LPT, Pierwszy wolny

Przypadek 16: 5, LPT, Najdawniej nieużywany

Przypadek 17: 9, Hu, Pierwszy wolny

Przypadek 18: 9, Hu, Najdawniej nieużywany

Przypadek 19: 9, Heurystyczny, Pierwszy wolny

Przypadek 20: 9, Heurystyczny, Najdawniej nieużywany

Przypadek 21: 9, SPT, Pierwszy wolny

Przypadek 22: 9, SPT, Najdawniej nieużywany

Przypadek 23: 9, LPT, Pierwszy wolny

Przypadek 24: 9, LPT, Najdawniej nieużywany

...