Tomáš Čelko ve své diplomové práci vyvinul inovativní metodu paralelního zpracování obrovského množství dat z pixelových detektorů elementárních částic, jako je Timepix3. Řešení výrazně urychluje kritický proces klasteringu, tedy spojování jednotlivých „zásahů“ částic do trajektorií. Díky využití grafických karet (GPU) a optimalizace s datovou strukturou union-find dosáhl zrychlení až o dva řády oproti původním metodám.
Mohl byste nám stručně představit svou diplomovou práci „Clustering hits and predictions in data from TimePix3 detectors“?
Projekt je zameraný na spracovanie dát z pixelových detektorov elementárnych častíc. Aby sme mohli problém lepšie pochopiť, pozrime sa zjednodušene na to, ako takýto detektor funguje. Detektor Timepix3 má senzor o veľkosti 1,4 x 1,4 cm, na ktorom je matica 256 x 256 pixelov. Keď častica preletí cez kremíkový senzor detektora, môže z atómov uvoľniť elektrón, ktorý následne smeruje k elektróde, kde indukuje napätie. To vieme zmerať – konkrétne aj s časovým razítkom, ktoré určuje, kedy a kde k udalosti došlo, a to s presnosťou v nanosekundách. Takúto udalosť nazývame hit. V animácii možno vidieť prelet jednotlivých častíc a ich deponovanú energiu zobrazenú v aplikácii TrackLab. Osi x a y označujú jednotlivé pixely a farba reprezentuje množstvo energie v keV.
Takýchto hitov dokáže napríklad jeden detektor Timepix3 generovať frekvenciou až 40 miliónov za sekundu, takže je jasné, že spracovanie týchto dát v reálnom čase si vyžaduje efektívne algoritmy.
Aby fyzici mohli tieto dáta analyzovať, typicky potrebujú spájať jednotlivé hity do trajektórií podľa ich priestorovej a časovej blízkosti – tento proces sa nazýva klastering. V podstate ide o analýzu súvislých komponentov grafu. Tento krok predstavuje prvé úzke hrdlo spracovania, a preto sme navrhli spôsob, ako ho pre dáta tohto typu počítať distribuovane.
Okrem toho sme prácu rozšírili a algoritmus redizajnovali s využitím dátovej štruktúry union-find. Tú sme upravili pre aplikáciu na grafických kartách s vysokým stupňom paralelizácie (tisíce vlákien), čím sme dosiahli zrýchlenie až o dva rády oproti jednovláknovej variante. Na nasledujúcich obrázkoch ukazujeme, ako rýchlosť spracovania („throughput“) škáluje s rastúcim stupňom paralelizácie pre CPU a GPU, v danom poradí. Rôzne farby v grafe znázorňujú rôzne typy častíc s postupne rastúcou veľkosťou trajektórii. Od najmenších 1-pixelových trajektóríí fotónov až po trajektórie olova s desaťtisícmi pixelov.
Tieto výsledky sme tiež odprezentovali na konferencii International Workshop for Radiation Imaging detectors v Lisabone.
Co vás inspirovalo k tomu, abyste se zaměřil právě na toto téma?
Asi prvou motiváciou bolo, že už počas mojej bakalárskej práce som mal možnosť sa s pixelovými detektormi zoznámiť a identifikovať problémy v spracovaní týchto dát. Počas tohto obdobia som okrem podpory od môjho vedúceho práce RNDr. Františka Mráza, CSc., na MFF UK, spoznal aj kolegov z Ústavu technickej a experimentálnej fyziky (ÚTEF) na ČVUT, s ktorými som konzultoval ich pohľad na problém.
Okrem nápomocného kolektívu, bola mojou motiváciou aj to, že klastering je nutný ako jeden z prvých krokov pre väčšinu aplikácii a jedná sa o úzke hrdlo spracovania dát. Tak mi bolo jasné, že ak sa nám podarí ho zrýchliť, bude to široko aplikovateľné v praxi.
S jakými technologiemi jste pracoval a jaké metody jste využíval?
Kvôli optimalizácii na výkon, ktorý je pre spracovanie v reálnom čase nevyhnutný, sme sa rozhodli pre implementáciu v jazyku C++. Vo variante klastrovania pre CPU využívame paralelizáciu cez vlákna procesora (typicky niekoľko desiatok), zatiaľ čo v implementácii pre GPU využívame platformu CUDA, s ktorou cielime na tisícky až desaťtisícky paralelných vlákien. Výhodou spracovania na GPU je, že odbremeňuje CPU a to sa môže venovať iným úlohám, ako napríklad komunikácii s detektorom (či už cez Ethernet, USB alebo PCI Express) alebo jednoduchej vizualizácii dát v reálnom čase.
Co bylo během psaní vaší práce nejtěžší? Ocitl jste se někdy ve slepé uličce? Je něco, co byste zpětně udělal jinak?
Áno, takýchto (zrejme) slepých uličiek bolo niekoľko. Myslím si, že som prišiel s fungujúcimi nápadmi až po vyčerpaní ostatných zlých riešení... Nápadov bolo určite viac, napríklad sme sa snažili relaxovať podmienku 8-susednosti hitov v priestore a namiesto toho nakresliť okolo nejakého jadra klastra obdĺžnik a len kontrolovať reláciu náležania pixelov do vnútra obdĺžnika. Nielen, že tento postup v praxi viedol občasne na nie úplne klastre, dokonca ani nebol merateľne efektívnejší.
Ďalej sme navrhli napríklad dvojfázový prístup ku klastrovaniu – najprv zhromažďovať hity podľa času a potom – paralelne – tieto skupiny rozdeliť podľa priestorovej susednosti. Ani tento prístup však nepriniesol merateľné zlepšenie rýchlosti spracovania.
Aj napriek tomu si myslím, že skúmanie týchto slepých uličiek nám prinieslo cenné poznatky, ktoré sa inak získať nedajú a posunulo nás tým „správnym“ smerom.
Jakým způsobem jste ověřoval výsledky své práce?
Po implementácii algoritmu bolo samozrejme treba odmerať, ako rýchlo funguje a tiež overiť jeho korektnosť. Korektnosť sa podarilo overiť pomerne rýchlo, ale problém bol s meraním rýchlosti. V súčasnosti totiž jeden Timepix3 detektor nedokáže produkovať dáta takou rýchlosťou na akú sme cielili, takže v prvej fázi sme si museli vystačiť s simulovaným generovaním dát. O pár mesiacov neskôr sa nám ale podarilo dostať sa priamo do SPS (Super Proton Sychrotron) v CERN (naša zostava je na obrázku nižšie), kde sme poprvýkrát mohli odmerať rýchlosť klastrovania na dátach v reálnom čase.
Tam sa nám podarilo dostať blízko limitu detektora, s tým že samotné klastrovanie fungovalo podľa očakávaní. Pri meraniach sme boli limitovaný radiačnou bezpečnosťou v SPS, ktorá nám síce paprsok väčšej intenzity nepovolila, no aj tak meranie považujeme za úspech. Nič z toho by sa samozrejme nepodarilo bez podpory môjho vedúceho RNDr. Františka Mráza, CSc., z MFF UK a kolegov z ÚTEF pod vedením MSc. Benedikta Bergmanna, Ph.D.
Máte pocit, že vaše práce může být inspirací pro další studenty nebo odborníky v dané oblasti?
To úplne neviem posúdiť, ale pokiaľ by to niekoho motivovalo dať si záležať na svojej diplomke, bol by som rád. Myslím, že je to jeden z príkladov, že aj v rámci diplomovej práce sa dá vytvoriť niečo zaujímavé, čo nemusí skončiť „v šuflíku“. Obecne si myslím, že fyzika je zdrojom viacerých interdisciplinárnych úloh zaujímavých aj pre informatikov.
Jaké jsou vaše plány do budoucna?
V rámci doktorandského štúdia na MFF UK by som sa chcel téme paralelného klastrovania ešte ďalej venovať, hlavne by som ho veľmi rád aplikoval v rámci nejakého väčšieho projektu. Aktuálne pracujeme na variante algoritmu ktorá by umožnila ešte väčší stupeň paralelizácie a spotrebovala menej pamäte. Ďalej je nutné vyriešiť problém s I/O operáciami na sériových linkách obsluhovanými procesorom (Ethernet, USB...), ktoré sú teraz novým úzkym hrdlom. Teda tým, že sme navrhli nový klastrovací algoritmus, sme síce vyriešili pre fyzikov dôležitý problém, ale je to len jeden kúsok celej skladačky.
Okrem software sa pracuje aj na tom aby sme mali k dispozícii readout (zariadenie ktoré stojí medzi detektorom a počítačom), ktorý dokáže veľké dátové toky ustáť. Navyše ani samotný detektor často pri vyšších intenzitách radiácie nemusí byť stabilný. Vývoj detektorov a hardware však postupuje rýchlo dopredu (napr. detektory Timepix4 alebo PicoPix s ešte rádovo vyššími dátovými tokmi) a našou úlohou je zaručiť, aby za nimi software nezaostával.
Odkazy:
Repozitář
UK
Informace k softwarové knihovně (primárně pro fyziky)
Parallel
CPU- and GPU-based connected component algorithms for event building for hybrid
pixel detectors
