2011
informatika
GPU-ra adaptált celluláris particle filter
Témavezető:
Tornai Gábor János, Dr. Horváth András, Dr. Cserey György
Tornai Gábor János, Dr. Horváth András, Dr. Cserey György
Összefoglaló
A particle filter (részecskeszűrő) több szakterületen is ismert és alkalmazott módszer, többek között robotikai, pénzügyi és képfeldolgozási feladatok megoldásában hasznos. Nemlineáris rejtett állapotsorról adott nemlineáris, nem feltétlenül Gaussi eloszlású zajjal terhelt megfigyelés esetében analitikusan nem számolható ki a rejtett állapotsor optimális becslése, viszont particle filterrel megadható. A részecskeszűrő alapja, hogy minden állapotban részecskék segítségével számítunk közelítést. A részecskék követik a rendszer dinamikáját, és állapotról állapotra frissülnek. Általában a részecskeszám növelésével csökkenthető a közelítés négyzetes hibája. Bár robotikai alkalmazások esetén pár száz részecske is elegendő lehet, léteznek olyan pénzügyi feladatok melyek során egy-egy állapotban több ezer, tízezer vagy millió részecske alkalmazása szükséges. A hagyományos algoritmus tehát roppant nagy számítási igényű is lehet, így a futása napokon át is tarthat adott esetben, ezért nem alkalmazható gyors döntéshozatalra. Ezzel szemben a celluláris particle filter (CPF) hatékonyan és gyorsan tud futni alkalmas architektúrán. Ez a módosított algoritmus csupán az újramintavételezés lépésében tér el a hagyományos algoritmustól. A négyzetes hiba a valódi és a becsült állapotsor között lényegében azonos a két módszer esetén, sőt bizonyos részecskeszám fölött a celluláris particle filter jobb közelítést ad. Az implementálásához olyan párhuzamos architektúrára van szükség, amely lokális összeköttetésekkel rendelkezik. A GPU (Grafics Processing Unit) megfelelő hardver, ráadásul a játékipar miatt viszonylag olcsó. A számítási kapacitása már most is rendkívül magas, azonban a technológiai fejlődés ütemét tekintve várhatóan tovább emelkedik majd. Számos API (Application Programming Interface) áll rendelkezésre, amelyek lehetővé teszik a GPU-k jól programozhatóságát, így általános számítási feladatok (mint a CPF) elvégzésére is rendkívül alkalmasak. A MatLab 2008b szoftver felhasználásával elkészített szimulációk alapján párhuzamos architektúrára (NVIDIA GF 9600GT videokártyára CUDA nyelven) adaptált, új celluláris particle filter implementációt készítettem, kihasználva az architektúra sajátosságait. Meggyőződtem az algoritmus hatékonyságáról, melyet mérésekkel validáltam.
Tornai Gábor János
tornai.gabor@itk.ppke.hu
Dr. Horváth András
horvath.andras@itk.ppke.hu
Dr. Cserey György