Optimalizace programů především s ohledem na efektivní
využívání skryté paměti
Další skupina výsledků se týká optimalizace algoritmů pro lineární algebru z hlediska využití paměťové hierarchie procesorů Intel a nových architektonických rysů těchto procesorů a optimalizace paralelních řešičů metodou Schurových doplňků na klastrech.
Byla provedena optimalizace algoritmu Choleského faktorizace (CHF) založená na myšlence souběžného výpočtu dvou dynamicky následných skalárních součinů vektorů. Dále byla navržena, implementována a ověřena bloková verze CHF úzkých pásových matic, založená na myšlence rozdělení matice na dvě stejně velké podmatice [D14]. Byl vyvinut pravděpodobnostní model chování skrytých pamětí během CHF, založený na vzdálenosti použití jednotlivých paměťových adres (reuse distances) a byla ověřena jeho přesnost [D3]. Přínos modelu je v tom, že postihuje i vazby mezi voláními podprogramů.
Byla provedena optimalizace násobení řídké matice vektorem (spMxV) a následně i metody sdružených gradientů (CG) pro matice reprezentované pomocí komprimovaných řádků založená na tzv. prokládání řádků. Tato optimalizace poskytuje spolehlivé urychlení výpočtu o 9% [D2,10,11]. Byla navržena a ověřena bloková verze spMxV, založená na nové heuristice pro vyhledávání pravidelných shluků nenulových prvků v řídké matice s jejich následným uložením v hustém formátu [D4]. K tématice patří také vyvinutí a ověření přesnosti pravděpodobnostního modelu chování skrytých pamětí při spMxV a jeho následné využití pro metodu sdružených gradientů [D7,11]. Byly navrženy nové formáty uložení husté matice pro spMxV adaptivní podle parametrů skrytých pamětí [D4].
Byl vyvinut emulátor skrytých pamětí, umožňující kvantitativní analýzu chování těchto pamětí pro různé algoritmy tak, že výsledky nejsou zkresleny ostatními souběžně běžícími procesy. V roce 2005 byl emulátor rozšířen o možnost simulace víceprocesorových systémů se sdílenou pamětí [D12].
Byla vyvinuta nová heuristika (nazvaná QB) pro statické vyvažování zátěže paralelního řešiče rozsáhlých řídkých soustav lineárních rovnic založeného na počítání Schurových doplňků obálkovou metodou. Heuristika QB byla ověřena na klastru na praktických úlohách počítaných metodou konečných prvků [D5]. QB heuristika byla též modifikována pro částečnou faktorizaci přímou řídkou metodou, bylo do ní zapracované urychlení pomocí rychlé predikce (odhadu) paměťových a výpočetních nároků částečné faktorizace a byla vyzkoušena ve vyvažování výpočtu časově závislých mechanických problémů [D6].
Byla vyvinuta speciální verze Sloanova algoritmu pro výpočet Schurových doplňků obálkovou metodou a ověřena na praktických úlohách. Oproti klasickému Sloanovu algoritmu přináší v průměru cca 15% paměťovou a cca 25% výpočetní úsporu [D1]. Řešení podúloh v metodě Schurových doplňků zlepšuje i modifikace heuristiky násobného minimálního stupně pro přečíslování neznámých před částečnou faktorizací přímou řídkou metodou [D5].
Publikace
- [D 1] O. Medek, P. Tvrdík: Variable Reordering for a Parallel Envelope Metod. In: Proceedings of the 2004 International Conference on Parallel Processing Workshops. IEEE Computer Society Press, ISBN 0-7695-2198-3. Los Alamitos, 2004, pp.254-261.
- [D 2] O. Medek, P. Tvrdík, J. Kruis: Load and Memory Balanced Mesh Partitioning for a Parallel Envelope Metod. In: Euro-Par 2004 Parallel Processing, ISBN 3-540-22924-8. Springer, LNCS 3149, 2004, pp.734-741.
- [D 3] I. Šimeček, P. Tvrdík: Analytical Model for Analysis of Cache Behavior during Cholesky Factorization and Its Variants. In: Proceedings of the 2004 International Conference on Parallel Processing Workshops, ISBN 0-7695-2198-3. IEEE Computer Society Press, Los Alamitos, 2004, pp.190-197.
- [D 4] I. Šimeček, P. Tvrdík: A new diagonal blocking format and model of cache behavior for sparse matrices. To appear in Proceedings of Parallel Processing and Applied Mathematics, Poznaň.
- [D 5] O. Medek, J. Kruis, Z. Bittnar, P. Tvrdík: Static load balancing applied to Schur complement method. To appear in Advances in Engineering Sofware, Elsevier, 2005.
- [D 6] O. Medek, P. Tvrdík: Quality balancing heuristics with three variants of Sloan algorithm. In: T. Fahringer, M. Hamza (eds.): Proc. of the IASTED Int. Conf. on Parallel and Distributed Computing and Networks, ISBN 0-88986-468-3. IASTED, ACTA Press, 2005, pp.644-650.
- [D 7] I. Šimeček, P. Tvrdík: Performance optimization and evaluation for linear codes. In: Z. Li et al. (eds.): Numerical Analysis and Applications, ISBN 3-540-24937-0. LNCS 3401, Springer Verlag, 2004, pp.566-573.
- [D 8] O. Medek, J. Kruis, Z. Bittnar, P. Tvrdík: Static Load Balancing Applied to Time Dependent Mechanical Problems. Seminar on Numerical Analysis. Seminar on Numerical Analysis 2005, ISBN 80-86407-04-7. Institute of Geonics AV ČR, Ostrava, 2005, pp.61-64.
- [D 9] P. Tvrdík, I. Šimeček: Optimalizace a hodnocení efektivity lineárních kódů. Seminář numerické analýzy 2005, Ústav geoniky Av ČR, Ostrava, 2005, pp.120-125.
- [D10] I. Šimeček: Improving of the performance of spase matrix-vector multiplication on the modern architectures. CTU FEE POSTER, Prague, 2004.
- [D11] P. Tvrdík, I. Šimeček: Architecture Dependent Linear Code Optimizations. Proceedings of CTU Workshop 9, ISBN 80-01-03201-99. Prague, 2005, pp.178-179, 2005.
- [D12] P. Tvrdík, I. Šimeček: Software Cache Analyzer. Proceedings of CTU Workshop 9, ISBN 80-01-03201-9. Prague, 2005, pp.180-181.
- [D13] I. Šimeček: Possibilities of GPU Computing. Proceedings of CTU Workshop 9, ISBN 80-01-03201-9. Prague, 2005, pp.182-183.
- [D14] I. Šimeček: Semi-sparse Cholesky Factorization. Proceedings of CTU Workshop, ISBN 80-01-03201-9. Prague, pp.184-185.