velikost textu

Employing Parallel Architectures in Similarity Search

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Employing Parallel Architectures in Similarity Search
Název v češtině:
Nasazení paralelních architektur v podrobnostním vyhledávání
Typ:
Disertační práce
Autor:
RNDr. Martin Kruliš, Ph.D.
Školitel:
RNDr. Jakub Yaghob, Ph.D.
Oponenti:
Ing. Jan Platoš, Ph.D.
Dr. Sabri Pllana
Id práce:
70643
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra softwarového inženýrství (32-KSI)
Program studia:
Informatika (P1801)
Obor studia:
Softwarové systémy (4I2)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
10. 6. 2013
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Klíčová slova:
paralelní, databáze, plánování, GPGPU, podobnostní vyhledávání
Klíčová slova v angličtině:
parallel, databases, scheduling, GPGPU, similarity search
Abstrakt:
Tato práce se zabývá možnostmi nasazení masivně paralelních architektur v data- bázových systémech využívajících podobnostní vyhledávání. Hlavním předmětem našeho zájmu je využití výpočetní síly současné generace grafických karet pro vyhledávání v databázích obrázků. I přes významný pokrok v posledních letech zůstává oblast podobnostního vyhledávání velmi výpočetně náročná, takže je možné tyto metody aplikovat pouze u databází menšího rozsahu. Grafické čipy disponují obrovskou výpočetní silou, avšak jejich použitelnost pro konkrétní problémy bývá komplikovaná z důvodu specifických vlastností této architektury, které si vyžadují individuální úpravu existujících algoritmů a datových struktur. Zabývali jsme se všemi aspekty této problematiky, od efektivního využití grafických čipů pro obecné výpočty přes akceleraci vyhledávacího procesu až po efektivní indexaci obrázků. Ve většině případů přineslo nasazení grafických karet zrychlení přibližně o dva řády ve srovnání s jednojádrovými procesory a několikanásobné zrychlení ve srovnání s běžnými víceprocesorovými NUMA servery. Tato práce shrnuje naše poznatky z několikaletého výzkumu, algoritmy upravené pro specifické podmínky masivně paralelních čipů, ale také výsledky provedených experimentů, které potvrzují naše závěry.
Abstract v angličtině:
This work examines the possibilities of employing highly parallel architectures in database systems, which are based on the similarity search paradigm. The main objective of our research is utilizing the computational power of current GPU devices for similarity search in the databases of images. Despite leaping progress made in the past few years, the similarity search problems remain very expensive from a compu- tational point of view, which limits the scope of their applicability. GPU devices have a tremendous computational power at their disposal; however, the usability of this power for particular problems is often complicated due to the specific properties of this architecture. Therefore, the existing algorithms and data structures require extensive modifications if they are to be adapted for the GPUs. We have addressed all the aspects of this domain, such as efficient utilization of the GPU hardware for generic computations, parallelization of similarity search process, and acceleration of image indexing techniques. In most cases, employing the GPU devices brought a speedup of two orders of magnitude with respect to single-core CPUs and approximately one order of magnitude with respect to multiprocessor NUMA servers. This thesis summarizes our experience and discoveries from several years of research, related algorithms adopted for the specific conditions of GPU architectures, and the results of empirical experiments performed in order to verify our claims.
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce RNDr. Martin Kruliš, Ph.D. 5.09 MB
Stáhnout Příloha k práci RNDr. Martin Kruliš, Ph.D. 35.97 MB
Stáhnout Abstrakt v českém jazyce RNDr. Martin Kruliš, Ph.D. 36 kB
Stáhnout Abstrakt anglicky RNDr. Martin Kruliš, Ph.D. 33 kB
Stáhnout Posudek vedoucího RNDr. Jakub Yaghob, Ph.D. 91 kB
Stáhnout Posudek oponenta Ing. Jan Platoš, Ph.D. 117 kB
Stáhnout Posudek oponenta Dr. Sabri Pllana 558 kB
Stáhnout Záznam o průběhu obhajoby 134 kB