Algoritmy a datové struktury pro velmi velké řídké matice

Přehled

Název: Algorimty a datové struktury pro velmi velké řídké matice
Autor: Ing. Daniel Langr, Ph.D.
Školitel: prof. Ing. Pavel Tvrdík, CSc.
Datum obhajoby: 22. května 2015
Organizace: Fakulta informačních technologií, České vysoké učení technické v Praze

Ke stažení

Abstrakt

Násobení řídké matice vektorem (sparse matrix-vector multiplicatoin; SpMV) představuje jednu z nejdůležitějších numerických operací pro vědecké a inženýrské výpočty. Na dnešních a budoucích nejvýkonnějších výpočetních systémech (výkonnová úroveň petascale a exascale) jsou třemi hlavními problémy souvisejícími s operací SpMV: minimalizace komunikace mezi procesory v prostředí s distribuovanou pamětí, maximalizace efektivity lokální operace SpMV vykonávané jedním procesorem a implemetace efektivní odolnosti na systémové chyby s pomocí nebo bez pomoci metody chceckpointing-restart. Obecné řešení těchto problémů je zcela za hranicí rozsahu jedné vědecké práce. Tato práce řeší několik výzkumných úkolů souvisejících s výpočty založenými na operaci SpMV, konkrétně návrh paměťově úsporného úložného formátu pro řídké matice a vývoj souvisejících algoritmů, experimentální ohodnocení vhodnosti tohoto formátu pro ukládání matic na paralelní souborový systém, definici obecných kritérii pro hodnocení řídkých úložných formátů, návrh paralelního škálovatelného generátoru testovacích řídkých matic a implementaci rychlého paralelního generátoru velkých náhodných permutací.

Ocenění

Tato práce byla oceněna 2. místem v Ceně Josepha Fouriera za počítačové vědy v roce 2014. [diplom]

Vybrané relevantní publikace

  • D. Langr, P. Tvrdík. Evaluation Criteria for Sparse Matrix Storage Formats. IEEE Transactions on Parallel and Distributed Systems, 27(2):428–440, 2016. [DOI]

  • D. Langr, P. Tvrdík, I. Šimeček, T. Dytrych. Downsampling Algorithms for Large Sparse Matrices. International Journal of Parallel Programming, 43(5):679–702, 2015. [DOI]

  • D. Langr, P. Tvrdík, T. Dytrych, J.P. Draayer. Algorithm 947: Paraperm: Parallel Generation of Random Permutations with MPI. ACM Transactions on Mathematical Software, 41(3):5:1–5:24, 2014. [DOI]

  • D. Langr, I. Šimeček, P. Tvrdík, T. Dytrych. Large-Scale Visualization of Sparse Matrices. Scalable Computing: Practice and Experience, 15(1):21–31, 2014. [DOI]

  • D. Langr, I. Šimeček, P. Tvrdík, T. Dytrych. Scalable Parallel Generation of Very Large Sparse Benchmark Matrices. Ve sborníku konference 10th International Conference on Parallel Processing and Applied Mathematics (PPAM 2013). Lecture Notes in Computer Science, 8384:178–187, 2014. [DOI]

  • D. Langr, I. Šimeček, P. Tvrdík, T. Dytrych, J.P. Draayer. Adaptive-Blocking Hierarchical Storage Format for Sparse Matrices. Ve Sborníku konference Federated Conference on Computer Science and Information Systems (FedCSIS 2012), 545–551, 2012. [HTTP]

Obrázky

Příspěvky práce (červeně) v kontextu dnešních a budouchích problémů souvisejících s operací násobení řídké matice vektorem na velkých škálách (modře):

Contributions of the Thesis

Vizualizace hustoty nenulových prvků velké řídké matice:

Matrix visualization

Kontakt

Daniel Langr

e-mail: daniel.langr(at)fit.cvut.cz

Katedra počítačových systémů

Fakulta informačních technologií

České vysoké učení technické v Praze

Menu