Knowledge base: Warsaw University of Technology

Settings and your account

Back

Pattern recognition algorithms using GPGPU computations

Paweł Grzegorz Pasznik

Abstract

The thesis presents the advantages of applying pattern recognition algorithms in parallel environments. The classifiers chosen for analysis are k-NN and SVM. The parallel implementations are compared with sequential algorithms for CPU. The nearest neighbor classifier has been implemented from scratch. A CPU version of the support vector machine is LIBSVM library. CUDA was chosen as a parallel environment, allowing for general purpose computing on graphic cards and special dedicated Tesla devices (GPGPU). The thesis introduces the tested algorithms along with their mathematical derivation, describes the test environment and explains problems encountered during the implementation. At the end, time and correctness results are presented. A chapter about CUDA describes its history and programming restrictions. A GPU version of the support vector machine is developed as a modification to multisvm library. The main change is addition of interoperability with LIBSVM library, resulting in a common model file format and datasets file format. The other important change is a different implementation of reduction, done with Thrust library. Various reduction implementations have been tested. The thesis also contains a comparison of results obtained for single and double precision floating-point numbers. Results of testing two-class and multiclass datasets are presented separately.
Record ID
WUT307760
Diploma type
Master of Science
Author
Paweł Grzegorz Pasznik (FEIT/ICS) Paweł Grzegorz Pasznik,, The Institute of Computer Science (FEIT/ICS)Faculty of Electronics and Information Technology (FEIT)
Title in Polish
Algorytmy rozpoznawania obrazów wykorzystujące przetwarzanie GPGPU
Supervisor
Rajmund Kożuszek (FEIT/ICS) Rajmund Kożuszek,, The Institute of Computer Science (FEIT/ICS)Faculty of Electronics and Information Technology (FEIT)
Certifying unit
Faculty of Electronics and Information Technology (FEIT)
Affiliation unit
The Institute of Computer Science (FEIT/ICS)
Language
(pl) Polish
Status
Finished
Issue date (year)
2012
Internal identifier
ENII-PM.001641
Keywords in Polish
rozpoznawanie obrazów, klasyfikatory, k-NN, SVM, LIBSVM, GPGPU, CUDA
Keywords in English
pattern recognition, classifiers, k-NN, SVM, LIBSVM, GPGPU, CUDA
Abstract in Polish
W pracy określono korzyści wynikające z implementacji algorytmów rozpoznawania obrazów w środowisku równoległym. Dokładnej analizie poddano algorytm k-NN i klasyfikator SVM. Za punkt odniesienia przyjęto implementację na procesor jednordzeniowy CPU — realizację autorską w przypadku algorytmu najbliższego sąsiada i bibliotekę LIBSVM w przypadku maszyny wektorów nośnych. Do badania wybrano dynamicznie rozwijaną technologię CUDA, umożliwiającą uruchamianie równoległego kodu ogólnego przeznaczenia na procesorach karty graficznej oraz na dedykowanych urządzeniach Tesla — przetwarzanie GPGPU. W pracy przedstawiono testowane algorytmy rozpoznawania obrazów, ich aparat matematyczny, środowisko testowe, problemy pojawiające się podczas implementacji oraz wyniki testów. Zawarto też opis technologii CUDA, opis zauważonych ograniczeń wynikających z zastosowania architektury CUDA oraz przedstawiono charakterystykę jej rozwoju. W ramach realizacji klasyfikatora SVM wykorzystującego jednostki obliczeniowe karty graficznej wykonano modyfikację biblioteki multisvm. Wprowadzono kompatybilność z biblioteką LIBSVM na poziomie pliku modelu oraz plików ze zbiorami uczącym i testowym. Dokonano zmiany użytych wewnątrz algorytmu uczenia i klasyfikowania operacji redukcji na zrealizowane przy pomocy biblioteki Thrust. Wykonano analizę różnych sposobów implementacji redukcji i porównano czas ich wykonywania. Przy badaniu wydajności implementacji klasyfikatora SVM uwzględniono wersje z liczbami zmiennoprzecinkowymi pojedynczej oraz podwójnej precyzji. Osobno przedstawiono przypadek zbiorów wieloklasowych i dwuklasowych.
File
Request a WCAG compliant version

Uniform Resource Identifier
https://repo.pw.edu.pl/info/master/WUT307760/
URN
urn:pw-repo:WUT307760

Confirmation
Are you sure?
Report incorrect data on this page