kNN: OpenCL - zadanie zaliczeniowe

Algorytm k-najbliższych sąsiadów (k-Nearest Neighbors) jest jednym z najprostszych algorytmów maszynowego uczenia się. Załóżmy, że mamy dany zbiór treningowy \(n\) przykładów (punktów) o znanych etykietach (klasach) \(0..l-1\) i współrzędnych w \(d\)-wymiarowej przestrzeni liczb rzeczywistych \(R^d\). Zadaniem algorytmu jest klasyfikacja \(q\) przykładów których etykiet nie znamy. Algorytm oblicza odległość (euklidesową) między klasyfikowanym przykładem a punktami ze zbioru treningowego; wybiera \(k\) najbliższych punktów zbioru treningowego; a następnie przypisuje etykietę która jest najczęstsza wśród tych punktów (w przypadku gdy wiele etykiet jest tak samo częstych algorytm wybiera leksykograficznie najmniejszą z nich).

Prosimy o implementację algorytmu kNN w OpenCL.

Programy będą testowane automatycznie. Prosimy o ścisłe przestrzeganie podanej poniżej formy wejścia i wyjścia.

10 2 2 2 3
1 0.0 0.0
1 0.1 0.0
1 0.0 0.1
1 0.0 0.2
1 0.2 0.0
0 0.5 0.5
0 0.6 0.6
1 1.0 1.0
1 0.9 0.9
1 0.95 0.95
0.3 0.3
0.55 0.55

1
0

Prosimy o oddanie pojedynczego pliku .zip zawierającego pojedynczy katalog odpowiadający loginowi (ab123456), a w nim następujące pliki:

• kod źródłowy programu hosta;
• kod lub kody źrółowe kerneli;
• Makefile: make bez parametrów powinien skompilować program do pliku knn; knn powinien uruchamiać najszybszą wersję kernela;
• krótki raport opisujący zastosowany algorytm oraz zastosowane techniki optymalizacji czasu działania; dla każdej z technik prosimy o podanie speed-up'u względem rozwiązania bazowego.

• zastosowany algorytm: 0-2;
• zastosowane techniki optymalizacji czasu działania: 0-2;
• szybkość działania: 0-4;
• raport: 0-2;

Jeśli program będzie działał niepoprawnie na naszych testach, będziemy odejmować do 5 punktów (a w przypadkach skrajnych: do 10).

Za każde rozpoczęte 12 godzin spóźnienia odejmujemy 1 punkt.

Prosimy o niekorzystanie z kodów źródłowych - gotowych implementacji kNN.

• V Garcia, E Debreuve, M Barlaud, "Fast k nearest neighbor search using GPU", http://arxiv.org/pdf/0804.1448
• N Sismanis, N Pitsianis, X Sun, "Efficient k-NN Search Algorithms on GPUs", http://developer.download.nvidia.com/GTC/PDF/GTC2012/PresentationPDF/S0314-GTC2012-Efficient-k-Nearet.pdf

• Dokładność obliczeń

Proszę używać liczb zmiennoprzecinkowych o pojedynczej precyzji.

• Sprawdzanie poprawności a błędy zaokrągleń.

Nasze testy będą brały pod uwagę możliwe błędy zaokrągleń z powodu stosowania pojedynczej precyzji.

• Jakie są limity pamięciowe dla CPU i GPU? Czy może wystarczy, że program działa na maszynie nvidia1?

Wystarczy że program działa na nvidia1/2.

• Jakie jest oczekiwane zachowanie algorytmu w przypadku gdy jest więcej niż k punktów w równej, najbliższej odległości od punktu, o który pytamy?

Można wybrać dowolne k z równoodległych punktów.

• Czy wystarczy dostarczyć najszybszą wersję kernela czy trzeba dołączyć poprzednie, wymienione w raporcie?

Proszę dołączyć kod wszystkich wersji kernela (i programów hosta, jeśli kolejne kernele wymagają również zmiany w hoscie).

• Czy można przyjąć, że n >= k ?

Tak.

• Czy można przyjąć minimalne ograniczenia na n i q?

Można przyjąć że n >= k. Dane weryfikacyjne będą miały małe wartości n i q (np. takie jak podane w przykładzie). Wydajność będziemy testować dla dużych wartości n i q (co najmniej tysiące).

• Czy w rozwiązaniu zadania zaliczeniowego można wielokrotnie wykonywać

kernel, przeplatając te wykonania z transferem pamięci? Czy w takim rozwiązaniu również wystarczy podać sumaryczny czas wykonania kernela oraz sumaryczny czas wykonania kernela i transferów pamięci?

Tak, proszę podawać sumaryczne czasy: wykonania wszystkich kerneli i wszystkich transferów pamięci.

• "dla każdej z technik prosimy o podanie speed-up'u względem rozwiązania bazowego" - przez rozwiązanie bazowe rozumiemy rozwiązanie na CPU czy niezoptymalizowane rozwiązanie na GPU?

Niezoptymalizowane rozwiązanie na GPU.

• Czy czasy działania kerneli i przesyłania pamięci są jedynymi miarami wydajności programu? Chodzi o to, że niektóre (w szczególności wszystkie) obliczenia można wykonać poza kernelami. Taki zabieg skróci czasy działania kerneli i przesyłania pamięci lecz nie koniecznie czas wykonania całego programu.

My będziemy również (a nawet przede wszystkim) mierzyć czas wykonania całego programu (używając time). Jeśli przeprowadzenie części obliczeń na CPU przyspiesza wykonanie całego zadania (w stosunku do obliczeń na GPU), to oczywiście można to zrobić. W takim przypadku proszę o jasne opisanie tej motywacji w raporcie.

• W przypadku remisu decyzji etykiet rozumiem, że wybieramy je według porządku leksykograficznego tak, jak na zwykłych napisach (czyli w szczególności 9 > 10)?

NIE. (treść zadania została zaktualizowana). W przypadku remisu (k=4 najbliższych sąsiadów ma etykiety 9, 9, 10, 10) wybieramy najmniejszą etykietę (9).

• Czy można założyć, że testy wydajnościowe będą przeprowadzane dla dużych wartości d i k (ok 20, 30).

NIE. Testy wydajnościowe będą dla dużych n i q oraz dla różnych d i k (od 3 do podanych maksimów).

• Co to znaczy niezoptymalizowane rozwiązanie na GPU? Czy to jest np rozwiązanie, które oblicza wszystko jednym wątkiem?, czy może rozwiązanie, które sortuje punkty w czasie kwadratowym? Wierzę, że nie, że optymalizacje mają dotyczyć specyfiki kart graficznych, a nie optymalizacji algorytmu, gdyż takie porównania nie miałoby by sensu.

Chodzi o "naiwną" implementację wybranego algorytmu. Kolejne optymalizacje powinny być oparte o specyficzne techniki używane w programowaniu kart graficznych (np. użycie pamięci local). Można również w pewnym momencie zmienić algorytm: np. może być tak, że algorytm asymptotycznie logarytmiczny używany jest w zadaniu dla małych liczności zbiorów i do tego słabo się optymalizuje na karcie - i można wtedy sprawdzić czy zamiana na algorytm liniowy nie poprawi wydajności.

My będziemy oceniać zarówno pomysłowość autora w optymalizacjach, jak i osiągnięty rezultat.

• OpenCL na khaki

Można uruchomić programy OpenCL na niektórych maszynach khaki (na niektórych nie działa) przez:

LD_LIBRARY_PATH=/usr/lib64/nvidia
export LD_LIBRARY_PATH
./knn wejscie wyjscie