Przetwarzanie superrównoległe

Prowadzący

Michał Cieślak

Opis

Warsztaty zakładają wprowadzenie uczestników do programowania gpu przy użyciu technologii CUDA. CUDA to opracowana przez Nvidię architektura wielordzeniowa pozwalająca wykorzystać jednostki GPU do ogólnych celów. Pozwala ona w pełni wykorzystać moc karty graficznej dla problemów podatnych na zrównoleglanie. Dzięki temu możemy otrzymać znaczny (lub wręcz ogromny  - nawet 100x) wzrost wydajności w porównaniu do zwykłego CPU.

Program zajęć

Zakresu materiału poruszanego na zajęciach (wstępnie):

- omówienie architektury sprzętowej, rodzajów pamięci, jednostek przetwarzających
- wprowadzenie do środowiska programistycznego (w zasadzie jest to język c do którego dodano kilka nowych elementów składniowych)
- tworzenie wątków i zarządzanie nimi
- porównanie kosztów operacji na pamięciach
- techniki efektywnego zarządzania pamięcią
- kwestie synchronizacji i ograniczenia z tym związane
- analiza konkretnych algorytmów i ich implementacja (np. alg. genetyczne)

Wszystkim zagadnieniom (może z wyjątkiem pierwszego) będzie towarzyszyć część praktyczna polegająca na pisaniu kodu i stosowaniu wiedzy w praktyce. Istotnym elementem będą również doświadczenia dotyczące wydajności.

Wymagania

- dobra znajomość języka C
- mile widziana znajomość podstawowych zagadnień i technik programowania współbieżnego (niekoniecznie) [można ją będzie zdobyć na warsztatach "Programowanie współbieżne" Zyxa]

Na warsztatach planuję omawiać wszystkie nieznane uczestnikom zagadnienia i nie realizować kolejnych zagadnień, dopóki wcześniejsze nie zostaną opanowane przez uczestników (nawet kosztem niezrealizowania całości materiału), tak więc poza powyższymi dwoma wskazaniami i chęciami do pracy nie potrzeba nic więcej :)

Zadania kwalifikacyjne

Zadanie 1

Algorytmy genetyczne są świetnym przykładem zastosowania zjawisk naturalnych w informatyce.
Sposób przetwarzania danych przypomina ewolucję - występują tu terminy analogiczne do tych, jakich używa się w biologi - populacja, osobnik, gen, selekcja, krzyżowanie, mutacja.
W koncepcji AG, rozwiązanie badanego problemu jest naszym osobnikiem. Zazwyczaj przestrzeń poszukiwań rozwiązania jest bardzo duża (na tyle duża, że nie ma sensu sprawdzać wszystkich przypadków po kolei). Dlatego też operujemy jedynie na skończonej puli rozwiązań (osobników) zwanej populacją. Populacja z czasem ewoluuje, najlepiej przystosowane osobniki się krzyżują dając początek nowym pokoleniom, giną osobniki najsłabsze, najmniej przystosowane. AG to ciekawe zagadnienie i można by na ten temat pisać dużo, lecz nie w tym rzecz ;). Twoim zadaniem jest zaimplementowanie podstawowej metody krzyżowania osobników - krzyżowania binarnego jednopunktowego.

Krzyżowanie to polega na rozcięciu ciągu bitów dwóch osobników (oba w tym samym, losowym miejscu i sklejenia ich na krzyż)

dla podanych rodziców i punktu podziału po szóstym bicie:
rodzic 1: 011110|10101010101
rodzic 2: 101001|000101010001

otrzymujemy:
potomek 1: 011110 000101010001
potomek 2: 101001 10101010101

Napisz funkcję realizującą to zadanie o sygnaturze:

unsigned int* krzyzowanie(unsigned int* osobniki, int rand)

zakładamy, że wskaźnik osobniki wskazuje na tablicę 4-elementową. Dwa pierwsze elementy to bity pierwszego osobnika, dwa następne to osobnik drugi.
Argument rand to liczba z zakresu 0-RAND_MAX, użyj jej do wyznaczenia punktu podziału. Osobniki potomne zwróć w tablicy analogicznej do tej będącej argumentem.

Zadanie 2.

Liczby zmiennoprzecinkowe, np. float są kodowane z użyciem standardu IEEE754. Składają się one z trzech części - znaku, wykładnika i mantysy. Napisz funkcję, która będzie pobierała zmienną typu float, natomiast efektem jej działania będzie wypisanie znaku (+/-), wykładnika (jako liczba całkowita) oraz mantysy (liczba zmiennoprzecinkowa).


Rozwiązania proszę przysyłać na adres moc.liamg|clahcim.nimda#moc.liamg|clahcim.nimda.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License