Dekompozice kvádru na bloky s optimálními rozměry
Motivace: simulace proudění pomocí metody LBM, viz prezentace z konference HPCSE 2022.
Výpočetní oblast (=ekvidistantní mřížku) je třeba rozdělit „optimálním“ způsobem na daný počet podoblastí.
Formální zadání
Kvádr o přirozenočíselných rozměrech Nx, Ny, Nz chceme rozdělit na P částí tak, aby každá část byl kvádr o přirozenočíselných rozměrech, objem každé části byl co nejblíž V/P, a plocha mezi kvádry byla co nejmenší.
- požadavek na objem = load balancing pro paralelní výpočty
- požadavek na plochu mezi bloky = minimalizace komunikace mezi workery
Zadání budeme postupně rozšiřovat o další požadavky, např. aby rozměry v jednom směru (např. osa y) byly násobky 32 (na vstupu i na výstupu - při dělení).
Proč se tomu zde věnujeme
- využití v praxi – můj výzkum :-)
- zajímavý otevřený problém (celočíselné programování je NP-úplná úloha)
- já sám dopředu nevím, co vznikne – takže vám můžu ukázat možnosti řešení problému v praxi
- praktická úloha bude nejlepší způsob, jak ukázat aplikaci některých návrhových vzorů (design patterns)
Možnosti práce
- implementace optimalizačních algoritmů
- vizualizace výsledku v GUI
- unit testy
- propojení s externími knihovnami
- další nápady?
Soubory ke stažení
Zatím neumíme pracovat s gitem, tak začneme bez něj: project_v1.zip, project_v2.zip
Další verze jsou na GitLabu:
git clone https://gitlab.com/prop2022/block-decomposition.git