|
|
Meeting the challenges of k-nearest neighbor search implementation for GPU accelerators
Hanák, Drahomír ; Kruliš, Martin (vedoucí práce) ; Yaghob, Jakub (oponent)
Podobnostní vyhledávání je často používaná technika v databázích pro hledání objektů podobných danému dotazu. Používá se ve vyhledávání podle vzoru komplexních objektů, jako jsou například obrázky, získávání informací a statistickém učení. Naše práce se za- měřuje na implementaci a optimalizaci algoritmu k nejbližších sousedů (kNN) na GPU, který se často používá pro podobnostní vyhledávnání. Analyzovali a vyhodnotlili jsme existující implementace kNN na GPU pro různé konfigurace problému. Pro každou kon- figuraci jsme navrhli nejrychlejší řešení. Také jsme navrhli několik optimalizací výběru k nejbližších sousedů. Implementovali jsme přístup, který dosanuje až 80% maximání teo- retické propustnosti na typické konfiguraci problému a je rychlejší než ostatní přístupy v literatuře. Také jsme implementovali algoritmus, který najde k nejbližších sousedů bez toho, aniž by musel uložit matici vzdáleností do paměti, a algoritmus pro velké hodnoty parametru k, který je podstatně rychlejší než optimalizované paralelní třídění. 1
|
host ::
RSS.