Physics Simulation and Inverse Problem Solution on Massively Parallel Systems  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
104476
Type K
Principal investigator Szirmay Kalos, László
Title in Hungarian Fizikai szimuláció és inverz problémák nagypárhuzamosságú rendszerekben
Title in English Physics Simulation and Inverse Problem Solution on Massively Parallel Systems
Keywords in Hungarian Szimuláció, inverz problémák, GPGPU, Monte Carlo módszerek, Párhuzamos számítások
Keywords in English Simulation, Inverse problems, GPGPU, Monte Carlo methods, Parallel Computing
Discipline
Information Technology (Council of Physical Sciences)100 %
Ortelius classification: Medical informatics
Panel Natural Sciences Committee Chairs
Department or equivalent Department of Control Engineering and Information Technology (Budapest University of Technology and Economics)
Participants Áfra, Attila Tamás
Jakab, Gábor
Jákó, Balázs
Magdics, Milán
Szécsi, László
Tóth, Balázs
Starting date 2012-09-01
Closing date 2017-08-31
Funding (in million HUF) 19.104
FTE (full time equivalent) 9.90
state closed project
Summary in Hungarian
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.
Summary
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.




 

Final report

  
Results in Hungarian
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.
Results in English
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.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=104476
Decision
Yes





 

List of publications

  
László Szirmay-Kalos, Milán Magdics, Balázs Tóth: Volume Enhancement with Externally Controlled Anisotropic Diffusion, VISUAL COMPUTER, 2017
László Szirmay-Kalos, Iliyan Georgiev, Milán Magdics, Balázs Molnár and Dávid Légrády: Unbiased Light Transport Estimators for Inhomogeneous Participating Media, COMPUTER GRAPHICS FORUM, Vol 36, No 2,, 2017
Attila T Áfra, László Szirmay-Kalos: Stackless Multi-BVH Traversal for CPU, MIC and GPU Ray Tracing, COMPUTER GRAPHICS FORUM 33:(1) pp. 129-140., 2014
Gábor Jakab, László Szirmay-Kalos: Hybrid Monte Carlo CT Simulation on GPU, LECTURE NOTES IN COMPUTER SCIENCE 8353: pp. 139-146., 2014
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
Milán Magdics, László Szirmay-Kalos, Balázs Tóth, Anton Penzov: Analysis and Control of the Accuracy and Convergence of the ML-EM Iteration, LECTURE NOTES IN COMPUTER SCIENCE 8353: pp. 147-154., 2014
Áfra Attila: High-Performance Ray Tracing on Modern Parallel Processors, BABES-BOLYAI UNIVERSITY, FACULTY OF MATHEMATICS AND COMPUTER SCIENCE DEPARTMENT OF COMPUTER SCIENCE, 2013
Magdics Milán: GPU-BASED PARTICLE TRANSPORT FOR PET RECONSTRUCTION, Department of Control Engineering and Information Technology, Budapest University of Technology and Economics, 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
László Szirmay-Kalos, Milán Magdics, Balázs Tóth: Volume Enhancement with Externally Controlled Anisotropic Diffusion, VISUAL COMPUTER, 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ászló Szirmay-Kalos: Filtering and Gradient Estimation for Distance Fields by Quadratic Regression, PERIODICA POLYTECHNICA-ELECTRICAL ENGINEERING AND COMPUTER SCIENCE 59:(4) pp. 175-180. (2015), 2015
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
László Szirmay-Kalos, Milán Magdics, Balázs Tóth, Tamás Umenhoffer, Judit Lantos, Gergely Patay: Fast Positron Range Calculation in Heterogeneous Media for 3D PET Reconstruction, IEEE Nuclear Science Symposium and Medical Imaging Conference, 2012. Anaheim, Amerikai Egyesült Államok, 2012
Balázs Teréki, Pirkko Oittinen, László Szirmay-Kalos: Informational Aesthetic Measure for 3D Stereoscopic Imaging, KÉPAF 2013. Bakonybél, Magyarország, 2013.01.29-2013.02.01. pp. 57-66., 2013
Károly Zsolnai, László Szirmay-Kalos: Automatic Parameter Control for Metropolis Light Transport, KÉPAF 2013. Bakonybél, Magyarország, 2013.01.29-2013.02.01. pp. 67-81, 2013
Károly Zsolnai, László Szirmay-Kalos: Real-time control of Newtonian fluids using the Navier-Stokes equations, KÉPAF 2013. Bakonybél, Magyarország, 2013.01.29-2013.02.01. pp. 15-25, 2013
L Szécsi, L Szirmay-Kalos, Gy Egri, G Patay: Binned Time-of-Flight Positron Emission Tomography, KÉPAF 2013. Bakonybél, Magyarország, 2013.01.29-2013.02.01. pp. 340-350., 2013
Zsolt Márta, László Szirmay-Kalos: Partial Volume Effect Correction using Anisotropic Backward Diffusion, KÉPAF 2013. Bakonybél, Magyarország, 2013.01.29-2013.02.01. pp. 144-157., 2013
László Szirmay-Kalos, Milán Magdics, Balázs Tóth, Tamás Bükki: Averaging and Metropolis Iterations for Positron Emission Tomography, IEEE TRANSACTIONS ON MEDICAL IMAGING 32:(3) pp. 589-600., 2013
Károly Zsolnai, László Szirmay-Kalos: Automatic Parameter Control for Metropolis Light Transport, EG 2013 - Short Papers. Girona, Spanyolország, 2013. pp. 53-56, 2013



Back »