Motiváció Eredmények Összefoglalás
Nemlineáris optimalizálási problémák párhuzamos megoldása grafikus processzorok felhasználásával Sipos Ágoston1 1 Eötvös
Loránd Tudományegyetem, Informatikai Kar
Kari TDK, 2016. 05. 10.
Sipos Ágoston
Motiváció Eredmények Összefoglalás
Tartalom
1
Motiváció Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
2
Eredmények Megvalósítás Elemzés Homográfiaillesztés
Sipos Ágoston
Motiváció Eredmények Összefoglalás
Tartalom
1
Motiváció Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
2
Eredmények Megvalósítás Elemzés Homográfiaillesztés
Sipos Ágoston
Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
Motiváció Eredmények Összefoglalás
Numerikus optimalizálás Optimalizálási feladatok
arg minf (x) x
Illesztések
Sipos Ágoston
Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
Motiváció Eredmények Összefoglalás
Numerikus optimalizálás Optimalizálási feladatok
arg minf (x) x
Illesztések
Sipos Ágoston
Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
Motiváció Eredmények Összefoglalás
Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
Numerikus optimalizálás Automatikus differenciálás
Automatikus differenciálás Duális számokat használ Pontos Csak explicit módon megadható, elemi függvényekre használható
Sipos Ágoston
Numerikus differenciálás Véges differenciákat használ Gyors, de numerikusan pontatlan Bármilyen kiértékelhető függvényre alkalmazható
Motiváció Eredmények Összefoglalás
Tartalom
1
Motiváció Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
2
Eredmények Megvalósítás Elemzés Homográfiaillesztés
Sipos Ágoston
Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
Motiváció Eredmények Összefoglalás
Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
GPU programozás Eredetileg grafikai számítások elvégzésére Párhuzamosítottságot támogat Nagy számítási kapacitás kiaknázható
Számítógépes látásban sok ezer adatpont −→ jó a párhuzamosítás Sipos Ágoston
Motiváció Eredmények Összefoglalás
Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
GPU programozás Eredetileg grafikai számítások elvégzésére Párhuzamosítottságot támogat Nagy számítási kapacitás kiaknázható
Számítógépes látásban sok ezer adatpont −→ jó a párhuzamosítás Sipos Ágoston
Motiváció Eredmények Összefoglalás
Tartalom
1
Motiváció Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
2
Eredmények Megvalósítás Elemzés Homográfiaillesztés
Sipos Ágoston
Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
Motiváció Eredmények Összefoglalás
Alkalmazások Számítógépes látás
Síkhomográfia Kamerakalibráció
Sipos Ágoston
Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
Motiváció Eredmények Összefoglalás
Alkalmazások Számítógépes látás
Síkhomográfia Kamerakalibráció
Sipos Ágoston
Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
Motiváció Eredmények Összefoglalás
Tartalom
1
Motiváció Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
2
Eredmények Megvalósítás Elemzés Homográfiaillesztés
Sipos Ágoston
Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
Motiváció Eredmények Összefoglalás
Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
Google Ceres
Jelenleg a legkorszerűbb numerikus optimalizációs rendszer Nyílt forrású, C++ template könyvtár Automatikus differenciálást is használ
Sipos Ágoston
Motiváció Eredmények Összefoglalás
Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
Google Ceres
Jelenleg a legkorszerűbb numerikus optimalizációs rendszer Nyílt forrású, C++ template könyvtár Automatikus differenciálást is használ
Sipos Ágoston
Motiváció Eredmények Összefoglalás
Tartalom
1
Motiváció Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
2
Eredmények Megvalósítás Elemzés Homográfiaillesztés
Sipos Ágoston
Megvalósítás Elemzés Homográfiaillesztés
Motiváció Eredmények Összefoglalás
Megvalósítás Elemzés Homográfiaillesztés
Duális számok
Komplex számokhoz hasonló algebrai struktúra (a, b) · (c, d) = (a · c, b · c + a · d)
C++ template osztállyal jól kezelhető Pontos deriváltkiértékelésre alkalmas (automatikus deriválás)
Sipos Ágoston
Motiváció Eredmények Összefoglalás
Megvalósítás Elemzés Homográfiaillesztés
Duális számok
Komplex számokhoz hasonló algebrai struktúra (a, b) · (c, d) = (a · c, b · c + a · d)
C++ template osztállyal jól kezelhető Pontos deriváltkiértékelésre alkalmas (automatikus deriválás)
Sipos Ágoston
Motiváció Eredmények Összefoglalás
Megvalósítás Elemzés Homográfiaillesztés
Duális számok
Komplex számokhoz hasonló algebrai struktúra (a, b) · (c, d) = (a · c, b · c + a · d)
C++ template osztállyal jól kezelhető Pontos deriváltkiértékelésre alkalmas (automatikus deriválás)
Sipos Ágoston
Motiváció Eredmények Összefoglalás
Megvalósítás Elemzés Homográfiaillesztés
Kódgenerálás
Matematikai függvények (Rn → R) kódjainak generálására Duális számok segítségével deriváltak kódját is elkészíti
Sipos Ágoston
Motiváció Eredmények Összefoglalás
Megvalósítás Elemzés Homográfiaillesztés
Kódgenerálás
Matematikai függvények (Rn → R) kódjainak generálására Duális számok segítségével deriváltak kódját is elkészíti
Sipos Ágoston
Motiváció Eredmények Összefoglalás
Deriváltkiértékelés SIMD paradigma használatával
n
∑ fi (p, xi )
i=0
Sipos Ágoston
Megvalósítás Elemzés Homográfiaillesztés
Motiváció Eredmények Összefoglalás
Algoritmusok Numerikus optimalizálás
Gradiens módszer Gauss-Newton módszer Levenberg-Marquardt módszer
Sipos Ágoston
Megvalósítás Elemzés Homográfiaillesztés
Motiváció Eredmények Összefoglalás
Algoritmusok Numerikus optimalizálás
Gradiens módszer Gauss-Newton módszer Levenberg-Marquardt módszer
Sipos Ágoston
Megvalósítás Elemzés Homográfiaillesztés
Motiváció Eredmények Összefoglalás
Algoritmusok Numerikus optimalizálás
Gradiens módszer Gauss-Newton módszer Levenberg-Marquardt módszer
Sipos Ágoston
Megvalósítás Elemzés Homográfiaillesztés
Motiváció Eredmények Összefoglalás
Tartalom
1
Motiváció Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
2
Eredmények Megvalósítás Elemzés Homográfiaillesztés
Sipos Ágoston
Megvalósítás Elemzés Homográfiaillesztés
Motiváció Eredmények Összefoglalás
Megvalósítás Elemzés Homográfiaillesztés
Konvergencia Körillesztés
A körillesztés - generált kezdőkörökre - mindig konvergált.
Sipos Ágoston
Motiváció Eredmények Összefoglalás
Megvalósítás Elemzés Homográfiaillesztés
Konvergencia Ellipszisillesztés
Az ellipszisillesztés - kevés kivételtől eltekintve - konvergált.
Sipos Ágoston
Motiváció Eredmények Összefoglalás
Megvalósítás Elemzés Homográfiaillesztés
Hatékonyság
Az OpenCL lehetővé teszi a hardverválasztást. ) CPU-n futtatott tesztek −→összehasonlíthatók GPU-n futtatott tesztek
Sipos Ágoston
Motiváció Eredmények Összefoglalás
Hatékonyság Körillesztés
Sipos Ágoston
Megvalósítás Elemzés Homográfiaillesztés
Motiváció Eredmények Összefoglalás
Hatékonyság Ellipszisillesztés
Sipos Ágoston
Megvalósítás Elemzés Homográfiaillesztés
Motiváció Eredmények Összefoglalás
Tartalom
1
Motiváció Numerikus optimalizálás GPU programozás Alkalmazások Google Ceres
2
Eredmények Megvalósítás Elemzés Homográfiaillesztés
Sipos Ágoston
Megvalósítás Elemzés Homográfiaillesztés
Motiváció Eredmények Összefoglalás
Homográfiaillesztés
Sipos Ágoston
Megvalósítás Elemzés Homográfiaillesztés
Motiváció Eredmények Összefoglalás
Összefoglalás
Egy OpenCL alapú numerikus optimalizálási rendszer. Többféle (illesztési és számítógépes látási) problémán validálva. Kitekintés További feladatok megoldása. Hatékonyság további javítása.
Sipos Ágoston
Appendix
Irodalom (kivonat) Jeffrey A. Fike, Juan J. Alonso. The Development of Hyper-Dual Numbers for Exact Second Derivative Calculations. 2011. John E. Stone, David Gohara, Guochun Shi. OpenCL: A Parallel Programming Standard for Heterogeneous Computing Systems. 2010. Sameer Agarwal, Keir Mierle and Others. Ceres Solver. http://ceres-solver.org
Sipos Ágoston
Appendix
Vége
Köszönöm a figyelmet!
Sipos Ágoston
