Zadania (MPI)

1. Proszę wykonać algorytm z pierwszego przykładu, tzn. algorytm do obliczenia X^(T) według

   xi(t+1) = ( xi-1(t) + 2*xi(t) + xi+1(t) ) / 4
   

   dla N = 4.
   
   
2. Proszę zmodyfikować algorytm z zadania 1 tak, by pracował dla problemu dwuwymiarowego według

   xi,j(t+1) = 4xi,j(t) + xi-1,j(t) + xi,j-1(t) - xi+1,j(t) + 5xi,j+1(t).
   

3. Niech będzie w drugim przykładzie z wykładu I(x_i,x_j) = I(x_j,x_i) dla wszystkich i i j. Proszę zmodyfikować algorytm tak, żeby konieczne były
   tylko N/2 iteracje do obliczenia wszystkich I(x_i,x_j).
   
   
4. Proszę opisać równoległą wersję algorytmu quicksort.
   
   
5. Proszę napisać MPI-program, w którym każdy task pisze swój numer (rank) oraz liczbę tasków w progamie.
   
   
6. Proszę napisać MPI-program, który sumuje kwadraty liczb od 1 do N. Wartość N ma być podana przez ilość tasków.
   
   
7. Proszę napisać MPI-program obliczający wektor X^T przy użyciu
   
   a)    X_i^(t+1) = ( X_i-1^(t) + 2 * X_i^(t) + X_i+1^(t) ) / 4 .
   
   b)    równania z zadania 2.
   
   
8. Component Labeling
   Niech będzie dana dwuwymiarowa tablica zawierająca elementy 0 i 1. Komponentą tabeli jest grupa 1, które są swoimi sąsiadami.
   Przykład: Następująca tablica ma dwie komponenty.

   0 0 1 0 0
   0 0 1 0 1
   0 0 1 0 1
   0 1 1 0 1
   

   Celem jest nadanie etykiety do 1 w tabeli tak, że dwie 1 mają tą samą etykietę wtw. leżą w tej samej komponencie.
   Metoda:
   Na początku każde 1 dostaje jednoznaczną etykietę (n.p. numer). Potem iterujemy następucący krok: Każde 1 dostaje minimum z etykiet swojego
   i jego sąsiadów.
   
   a)    Proszę opracować algorytm równoległyna podstawie tej metody.
   
   b)    Proszę wykonać implementację algorytmu z punktu a) w MPI.
   
   
9. Odd-Even-Transposition-Sort
   Sortowanie listy {a₁, ... a_n} metodą bubblesort można wykonywać równolegle w następujący sposób:
   Task i otzrymuje jako dane element a_i i wykonujemy naprzemian
   
   
   1. odd/even-change
      każdy task i (dla nieparzystego i) porównuje swój element a_i z elementem a_i+1 swojego prawego sąsiada. Jeżeli a_i > a_i+1, elementy zostają zamienione.
      
   2. even/odd-change
      każdy task i (dla parzystego i) porównuje swój element a_i z elementem a_i+1 swojego prawego sąsiada. Jeżeli a_i > a_i+1, elementy zostają zamienione.
      
      
   a)   Ile iteracji potrzebuje ten algorytm?
   
   b)   Proszę wykonać implementację algorytmu.
   
   
10. Proszę wykonać MPI-implementację broadcast'u w pierścieniu (startując taskiem 0).
    
    
11. a) Proszę skontruować hypercube dla N = 16.
    
    b) Proszę wykonać MPI-implementację broadcast'u w hypercube.
        Wskazówka: Pomocna jest następująca metoda. Numery tasków zostają przedstawione jako liczby binarne. Ilość pierwszych 0 (od lewej) decyduje o tym,
        czy task jest aktywny w i-tym kroku. Jeżeli w i-tym kroku i+1 bit tasku jest 0, task wysyła, jeżeli jest 1, task otrzymuje wiadomość.
        Tzn. (dla N = 8) w pierwszym kroku task 000 wysyła do tasku 001. W drugim kroku task 000 wysyła do tasku 010, a task 001 do 011, i tak dalej.
    
    
12. Proszę napisać MPI-program wykonujący natstepujące czynności:
    Task 0 wysyła wartość początkową k do wszystkich innych tasków. Każdy task i oblicza iloczyn k*i, który wysyła z powrotem do tasku 0. Task 0 sumuje
    wszystkie iloczyny.
    
    
13. Proszę napisać MPI-program, który szacuje wartość π na podstawie równania π = ₀∫¹ 4/(1+x²)dx używając przybliżenia całki jako powierzchni n prostokątów:
    Task 0 czyta z klawiatury wartość n i wysyła n do wszystkich innycn tasków, które obliczają powierzchnię prostokątów. Nastęnie task 0 sumuje przesłane
    przez inne taski wartości.
    Uwaga: Liczba tasków moż być mniejsza niż liczba prostokątów n!
    
    
14. Proszę zmodyfikować program sortujący z zadania 9 tak, by każdy task prowadził nie jeden element, lecz listę elementów. Task 0 otrzymuje przy tym na początku
    całą listę elementów do sortowania, rozdziela ją między innymi taskami i zbiera ich wyniki.
    
    
15. Proszę napisać algorytmy obliczające iloczyny macierz-wektor i macierz-macierz. W jaki sposób można przy tym podzielić dane miedzy taskami?
    
    
16. Proszę zmierzyć koszty obliczeniowe algorytmów równoległych z zadań 7, 9, 13, 14 i 15. (Można przy tym wykorzystać funkcję MPI_Wtime().) Jakie są koszty
    odpowiednich algorytmów sekwencyjnych?
    
    
17. Proszę implementować w MPI relację producent-konsument.