Systemy czasu rzeczywistego (QNX)
III rok informatyki studia MUZ

 rok akademicki 2006/2007 semestr zimowy

Zadanie 2.

1. Treść

W różnych systemach informatycznych ważny jest problem sortowania tablic. Znanych jest wiele metod i algorytmów sortowania o różnej złożoności obliczeniowej. Jest również wiele modyfikacji, które umożliwiają równoległą realizację tych algorytmów: do obliczeń wykorzystujemy nie jeden, lecz kilka pracujących jednocześnie procesorów.

Zadanie dla Państwa polega na przebadaniu kilku wariantów równoległych realizacji algorytmów sortowania. Przy czym, nie będziecie Państwo modyfikować samego algorytmu sortowania, ale różne sposoby łączenia podciągów posortowanych przez współpracujące procesy tak, by uzyskać jeden posortowany ciąg.

Zakładamy, że liczba wykorzystywanych do obliczeń procesów wynosi P, zaś liczba elementów ciągu, który będziemy sortować wynosi n.

Działanie algorytmu przebiega w trzech etapach:
1. Dany n-elementowy ciąg należy podzielić na P podciągów przy, czym w zadaniu nalezy rozważyć wszystkie warianty rozdziału zadań:
- zarówno przypadek, kiedy n jest podzielne przez P - i wszystkie procesory realizują wtedy obliczenia dla jednakowo licznych podciągów,
- jak i przypadek, gdy n nie jest podzielne przez P - i wtedy część procesorów będzie sortować podciąg o jeden element dłuższy niż pozostałe.
2. Każdy z procesorów (niezależnie od pozostałych) realizuje sortowanie przydzielonego mu podciągu. W ćwiczeniu należy wykorzystać kilka typowych algorytmów sortowania, różniących się wyraźnie złożonością obliczeniową (np. algorytm sortowania bąbelkowego, algorytm sortowania przez proste wybieranie oraz metoda quicksort).
3. Stosując odpowiedni (jeden z podanych poniżej, lub też inny) algorytm agregacji, należy złożyć z P posortowanych lokalnie pociągów (czyli zawierających n/P elementów) jeden posortowany ciąg n-elementowy. Algorytm agregacji należy zrealizować w wersji sekwencyjnej (czyli realizuje go jeden procesor, który posiada wszystkie te posortowane podciągi) oraz - na ile to możliwe - równoległej.

Algorytmy agregacji, które możecie Państwo wykorzystywać go łączenia posortowanych podciągów w jeden posortowany ciąg:
1. Algorytm drzewiasty Polega na kolejnym łączeniu binarnym posortowanych podciągów. Liczba agregacji będzie w tej metodzie wynosiła log2P, przy czym łączniu będą podlegały kolejno podciągi n/P, 2n/P, 4n/P, 8n/P- elementowe.
2. Algorytm sekwencyjny Pierwotnie polegał na połączeniu dwóch posortowanych podciągów n/P elementowych, a następnie dołączeniu do tak otrzymanego ciągu 2n/P elementowego kolejnych podciągów n/P elementowych. Liczba agregacji koniecznych do połączenia wszystkich podciągów wynosiła (P-1).
3. Algorytm równoległy Polega na jednoczesnym agregowaniu wszystkich posortowanych n/P elementowych podciągów. Do modyfikacji ciągu roboczego (takiego składającego się z P elementów - bierzemy po jednym z każdego posortowanego podciagu) można wykorzystać algorytm sortowania przez proste wybieranie.

W ćwiczeniu należy przebadać i porównać wszystkie przedstawione algorytmy agregacji dla jednej z metod sortowania (wybranej przez prowadzącego zajęcia). Obliczenia należy wykonać dla czterech procesorów, oraz dla różnych (rozumianych w bardzo szerokim zakresie) wielkości sortowanych ciągów n.

Decydującym kryterium oceny badanych rozwiązań jest zmierzony czas realizacji, dlatego bardzo istotne są:
- odpowiedni sposób pomiaru,
- odpowiednia synchronizacja czasu realizacji.

2. Zasady

Zadania wykonujecie Państwo w grupach 4-o osobowych.

3. Materiały pomocnicze (przykładowe programy)
Materiały z programowania w QNX-ie dostępne są na poprzednich stronach.

Materiały dot. sortowania:

(wyk. A.Zatwarnicka)

prof. J. Sadecki