Fizikai szimuláció és inverz problémák nagypárhuzamosságú rendszerekben
Angol cím
Physics Simulation and Inverse Problem Solution on Massively Parallel Systems
magyar kulcsszavak
Szimuláció, inverz problémák, GPGPU, Monte Carlo módszerek, Párhuzamos számítások
angol kulcsszavak
Simulation, Inverse problems, GPGPU, Monte Carlo methods, Parallel Computing
megadott besorolás
Informatika (Műszaki és Természettudományok Kollégiuma)
100 %
Ortelius tudományág: Orvosi informatika
zsűri
Műszaki és Természettudományi zsűrielnökök
Kutatóhely
Irányítástechnika és Informatika Tanszék (Budapesti Műszaki és Gazdaságtudományi Egyetem)
résztvevők
Áfra Attila Tamás Jakab Gábor Jákó Balázs Magdics Milán Szécsi László Tóth Balázs
projekt kezdete
2012-09-01
projekt vége
2017-08-31
aktuális összeg (MFt)
19.104
FTE (kutatóév egyenérték)
9.90
állapot
lezárult projekt
magyar összefoglaló
A kutatás összefoglalója, célkitűzései szakemberek számára Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára. A kutatás célja új algoritmusok kidolgozása komplex rendszerek masszívan párhuzamos hardveren (grafikus kártya, GPU) végrehajtott szimulációjához és inverz problémák megoldásához. Ennek során vizsgáljuk, hogy miként lehet a fizikai rendszerek szimulációját (differenciál, illetve integrál egyenletek megoldását) leképezni a GPU hardverre, figyelembe véve annak architekturális sajátosságait (gyűjtő algoritmusok - adjungált megközelítés, SIMD hardver - adatfüggetlen vezérlés, újrafelhasználás - faktorizáció). Az inverz problémák iteratív megoldásánál figyelembe vesszük a szimuláció lehetséges hibáit, hogy a módszer robusztusságát növelhessük. A Monte Carlo szimulációt és a az iteratív maximum likelihood becslési eljárást a sztochasztikus iteráció és a Metropolis mintavételezés elveinek felhasználásával kapcsoljuk össze. Javaslatot teszünk optimális és párhuzamos hardveren könnyen számítható regularizációs eljárásokra.
Mi a kutatás alapkérdése? Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek. A kutatás alapkérdése a sok százmillió paraméterrel leírható komplex rendszerek szimulációjának és paraméterbecslésének (inverz probléma) az elfogadható időn belüli megoldása. A szükséges számítási kapacitás a grafikus kártyák (GPU) és az azokból épített klaszterekben rendelkezésre áll, de ezek a megszokottól eltérő algoritmikus gondolkodást igényelnek. Olyan szimulációs és optimalizáló algoritmusok kell kidolgozni, amelyek: - jól skálázódnak a masszívan párhuzamos rendszerekben - képesek a párhuzamos rendszerekben is újrahasználni a más párhuzamos szálak részeredményeit - a szimulációt és az inverz feladat iteratív optimalizálását együtt kezelik, figyelembe véve azok költségigényét, numerikus hibáit és zajérzékenységét. - a párhuzamos hardverre jól illeszkedő és az a-priori ismereteket teljes mértékben felhasználó regularizációs sémákat alkalmaznak.
Mi a kutatás jelentősége? Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának! Komplex fizikai rendszerek (részecske és energia transzport, folyadékok dinamikája, merev és deformálható testek dinamikája) szimulációja fontos szerepet kap a számítógéppel segített tervezésben, meteorológiában, virtuális valóság és animációs rendszerekben. Ezek inverz problémája pedig a megvilágítás tervezésben, tomográfiában, számítógépes animációban lényeges.
A kutatás során olyan megoldásokat dolgozunk ki, amelyek orvosi képalkotó eszközökbe/tomográfokba, CAD rendszerekbe, animációs programokba beépíthetők, azok képességeit javítja. A leglényegesebb gyakorlati hasznosítási területnek az orvosi képalkotást (CT, MRI, PET, SPECT tomográfia) tekintjük, és a gyakorlati hasznosíthatóság érdekében az elméleti kutatás során is folyamatosan együttműködünk az orvosi képalkotással foglalkozó cégekkel (GE Hungary, Mediso) és egyetemekkel (Semmelweis Egyetem Radiológiai Klinika).
A kutatás összefoglalója, célkitűzései laikusok számára Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára. A kutatás egyik célja, hogy komplex fizikai rendszereket (foton, pozitron transzport, folyadékáramlás, dinamika) szimuláljunk valós időben az eredetileg a számítógépes játékokhoz fejlesztett grafikus kártyák segítségével. Tekintve, hogy a grafikus kártya speciális célú szuperszámítógép, a szimulációs algoritmusokat ezen specialitásoknak megfelelően kell felépíteni. A kutatás másik fő iránya az inverz problémák grafikus kártyán történő megoldása. Inverz probléma alatt a szimuláció fordítottját értjük, azaz míg a szimuláció során arra vagyunk kíváncsiak, hogy egy adott rendszer hogyan viselkedik, az inverz feladat arra ad választ, hogy milyen rendszer áll egy adott viselkedés mögött. A szimuláció és az inverz probléma megoldása különösen fontos a mérnöki tervezésben, tudományos kísérletek kiértékelésnél, orvosi képalkotó eszközök mérési adatainak feldolgozásában, és a számítógépes animációban.
A kutatómunkánk legfontosabb potenciális gyakorlati alkalmazásának a nagyobb felbontású és pontosabb számítógépes tomográfok (CT, MRT, PET, SPECT) létrehozását tartjuk.
angol összefoglaló
Summary of the research and its aims for experts Describe the major aims of the research for experts. The main objectives of this research project are to develop complex system simulation algorithms running on massively parallel hardware (GPU), and to address inverse problems emerging in such systems. We shall examine how the simulation of physical systems (differential or integral equations from the point of view of mathematics) can be mapped onto the GPU hardware, taking into account the architectural features and limitations (Gathering algorithms - adjoint operators; SIMD processing - data independent control; reuse - factoring). We shall address the error made by the simulation, i.e. the forward projection step during iterative inverse problem solution, and control the iterative optimization accordingly based on Metropolis sampling. Finally, we shall develop new regularization approaches with the objective of efficient parallel execution.
What is the major research question? Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments. The core research question is the solution of complex physical system simulation and of inverse problems in acceptable time. These systems can be described by hundred millions of parameters. We need to develop algorithms that - scale well on massively parallel systems and thus can exploit the supercomputer performance of GPUs, - are able to reuse results obtained by other parallel computational threads without prohibitive synchronization and communication times, - consider the simulation and iterative inverse problem solution not independently but as connected parts, taking into account their computational cost, numerical error, and sensitivity to noise, - involve regularization schemes based on all a-priori information and are appropriate for mapping on the parallel hardware.
What is the significance of the research? Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field. The simulation of complex physical systems (particle and energy transport, fluid dynamics, rigid and deformable body dynamics) is of great importance in Computer Aided Design, meteorology, virtual reality and animation. Their inverse problem emerges in lighting design, controlled animation, and most importantly in computer tomography.
We shall develop solutions that can be built into computer tomographs, CAD and animation systems, improving their capabilities. We consider medical imaging (CT, MRI, PET, SPECT tomography) the most important field of practical application. To guarantee the practical applicability of the results of theoretical research, we keep cooperating with companies involved in medical imaging (GE Hungary, Mediso) and universities (Semmelweis University, Institute of Radiology).
Summary and aims of the research for the public Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others. One objective of this reseach project is the real-time simulation of complex physical systems (photon, positron transport; fluid motion, dynamics) using the graphics cards originally develop for computer games. As the graphics card is a special purpose supercomputer, our mathematical approaches and algorithms should be tailored according to its special features. The other main direction is the solution of inverse problems on graphics cards. By inverse problem we mean the inverse of simulation, which, instead of producing a behavior from a system, finds the system that can present a prescribed behavior. Simulation and inverse problem solution are particularly important in Computer Aided Design, analysis of scientific experiments, medical imaging, and computer animation.
The most important practical application of our research could be the improvement of computer tomographs like CT, MRI, PET or SPECT.
Zárójelentés
kutatási eredmények (magyarul)
A projekt célja olyan GPU-n futó párhuzamos algoritmusok kidolgozása, amelyek alkalmasak komplex rendszerek szimulációjára és inverz problémák megoldására a részecske transzport és tomográfia alkalmazási területeken. A főbb eredmények:
- Vermet nem használó, térparticionáló adatstruktúrákat bejáró eljárás masszívan párhuzamos architektúrák számára.
- Közelítő eljárás másodfajú Fredholm féle integrálegyenletek megoldására, ahol elméletileg a megoldás egyre növekvő dimenziójú integrálok végtelen sorával fejezhető ki.
- Gyors pozitronvándorlás szimuláció, amely a pozíciófüggő, nagykernelű szűrést több FFT lépésre vezeti vissza.
- A többszörös fontosság szerinti mintavételezés elvének alkalmazása a gyűjtő és szóró típusú szimulációs stratégiák előnyeinek kombinálására.
- A Maximum-likelihood várható érték maximalizálás eljárás módosítása, figyelembe véve, hogy a projekciók csak közelítőleg számíthatók, és a közelítési hiba csökkentése a bevezetett átlagoló és Metropolis iterációk segítségével.
- Új adaptív, asszimetrikus mutációs stratégia kidolgozása Metropolis mintavételezéshez.
-A Bregman távolságot alkalmazó regularizációs séma tomográfiás rekonstrukcióhoz.
- 3D térfogati szűrés anizotrópikus diffúzióval, amelyet egy másik modalitás adatai vezérelnek.
- Hatékony részecsketranszport szimuláció erősen heterogén anyagokban.
kutatási eredmények (angolul)
This project aimed at GPU-based parallel algorithms that attack complex system simulation and inverse problem solution primarily in the fields of particle or energy transport and tomography. The main results are
- Stack-less space partitioning data structure traversal method for massively parallel architecture
- Approximation methods for the solution of Fredholm type integral equations of the second kind, where the solution can be theoretically expressed as an infinite series of growing dimensional integrals
- Fast positron range simulation algorithm that solves a spatial variant filtering using huge kernels with multiple Fourier transforms
- The application of multiple importance sampling to combine the advantages of gathering type simulations and scattering type simulations.
- Modification of the Maximum-Likelihood Expectation Maximization method to take into account that projections can only be approximately computed, and the development of averaging and Metropolis iterations.
- The proposition of a new adaptive, asymmetric mutation strategy for Metropolis sampling.
- The exploitation of Bregman distance in regularization of tomography reconstruction
- 3D volume filtering with anisotropic diffusion controlled by data obtained with other modalities.
- Efficient particle transfer simulation in strongly heterogeneous media.
László Szirmay-Kalos, Gábor Jakab: Analysis of Bregman Iteration in PET reconstruction, VII. Magyar Számítógépes Grafika és Geometria Konferencia, 2014
László Szirmay-Kalos, Bence Parajdi, Zsolt Csenki: Analysis of Image Descriptors for Zebrafish Toxicity Testing, VII. Magyar Számítógépes Grafika és Geometria Konferencia., 2014
László Szirmay-Kalos, Balázs Tóth, Gábor Jakab, Péter Gudics, Milán Magdics: Efficient Monte Carlo Method for Emission Tomography, VII. Magyar Számítógépes Grafika és Geometria Konferencia, 2014
László Szirmay-Kalos, Milán Magdics, Balázs Tóth: Multiple Importance Sampling for PET, IEEE TRANSACTIONS ON MEDICAL IMAGING 33:(4) pp. 970-978. Paper TMI2300932., 2014
Nagy Krisztián, Szirmay-Kalos László: Blind Logo and Identigram Exclusion for Image Matching, Képfeldolgozók és Alakfelismerők Társaságának 10. országos konferenciája. pp. 61-70., 2015
Parajdi Bence, Kovács Balázs, Szirmay-Kalos László: Dynamic PET Reconstruction with Binning in Time, Proceedings of the Workshop on the Advances of Information Technology (WAIT 2015), 2015
Szirmay-Kalos László, Magdics Milán, Tóth Balázs: PET rekonstrukció javítása kívülről vezérelt anizotróp diffúzióval, Képfeldolgozók és Alakfelismerők Társaságának 10. országos konferenciája. pp. 465-488., 2015
Szirmay-Kalos László: Filtering and gradient estimation for distance fields with quadratic regression, Proceedings of the Workshop on the Advances of Information Technology (WAIT 2015), 2015
Tóth Balázs, Papp László, Jakab Gábor, Patay Gergely, Szirmay-Kalos László: Adaptív bilaterális szűrés PET rekonstrukcióhoz, Képfeldolgozók és Alakfelismerők Társaságának 10. országos konferenciája. pp. 374-387., 2015
László Papp, Gábor Jakab, Balázs Tóth, László Szirmay-Kalos: Adaptive Bilateral Filtering for PET, IEEE Nucliear Science Symposium and Medical Imaging Conference. Seattle, 2014
László Szirmay-Kalos, Balázs Tóth, Gábor Jakab: Efficient Bregman Iteration in Fully 3D PET, IEEE Nuclear Science Symposium and Medical Imaging Conference. Seattle, 2014
László Szirmay-Kalos, Pirkko Oittinen, Balázs Teréki: Computational Aesthetics for Rendering Virtual Scenes on 3D Stereoscopic Displays, In: Kristóf Nyíri, András Benedek (szerk.) The Power of the Image: Emotion, Expression, Explanation. 2014. pp. 187-198. (Visual Learning; Volume 4.), 2014
Kacsó Ágota, Szirmay-Kalos László: Anatomy-based Regularization Methods for Dynamic PET Reconstruction, Szirmay-Kalos László, Renner Gábor (szerk.) VIII. Magyar Számítógépes Grafika és Geometria Konferencia. Konferencia helye, ideje: Budapest, Magyarország, 2016.03.30-2016., 2016
Szirmay-Kalos László, Tóth Balázs, Umenhoffer Tamás: Efficient Voxel Marking for Hierarchical Volumetric Fusion, Luis Gonzaga Magalhaes, Rafal Mantiuk (szerk.) EG 2016 - Posters. Konferencia helye, ideje: Lisszabon, Portugália, 2016.05.06-2016.05.13. [s. l.]: Eurographics - European, 2016
Szirmay-Kalos László, Kacsó Ágota: Direct Parametric Reconstruction for Dynamic PET on the GPU, Szirmay-Kalos László, Renner Gábor (szerk.) VIII. Magyar Számítógépes Grafika és Geometria Konferencia. Konferencia helye, ideje: Budapest, Magyarország, 2016.03.30-2016., 2016
L. Szirmay-Kalos, Á. Kacsó: Regularizing Direct Parametric Reconstruction for Dynamic PET with the Method of Sieves, 2016 Nuclear Science Symposium and Medical Imaging Conference, 2016
M. Sbert, V. Havran, L. Szirmay-Kalos:: Variance Analysis of Multi-sample and One-sample Multiple Importance Sampling,, Computer Graphics Forum, October, 2016., 2016
Ágota Kacsó, László Szirmay-Kalos: A sziták módszerének alkalmazása dinamikus PET rekonstrukció során, KÉPAF 2017: Képfeldolgozók és Alakfelismerők Társaságának 11. országos konferenciája. Konferencia helye, ideje: Szováta, Románia, 2017
Ágota Kacsó, László Szirmay-Kalos: Curve Fitting with Minimal Relative Error, Proceedings of the Workshop on the Advances of Information Technology: WAIT 2017. Budapest, 2017
Szirmay-Kalos László, Kacsó Ágota: Direct Parametric Reconstruction for Dynamic PET with Floating Frames, Proceedings of the Workshop on the Advances of Information Technology: WAIT 2017. Budapest, 2017
Szécsi László, Szirmay-Kalos László: Stratified Metropolis Method for Global Illumination Rendering, VIII. Magyar Számítógépes Grafika és Geometria Konferencia, GRAFGEO. Budapest, 2016
Milán Magdics, László Szirmay-Kalos, Balázs Tóth, Balázs Csébfalvi, Tamás Bükki: Higher Order Scattering Estimation for PET, IEEE Nuclear Science Symposium and Medical Imaging Conference, 2012. Anaheim, USA,, 2012
