IV112 Projekt z programování paralelních aplikací
Projekt číslo 6: Tranzitivní uzávěr grafu zadaného maticí (OpenMP)
Termín odevzdání: 7. 11. 2019 20:00
Odevzdávarna: Zadání: V tomto projektu je vaším úkolem implementovat paralelní výpočet tranzitivního uzávěru orientovaného grafu, zadaného jako matici sousednosti. Je nutné pro tuto paralelní implementaci použít systém OpenMP.
Vaším úkolem je dodat soubory parallel.cpp a sequential.cpp (viz Makefile), které demonstrují rozdíl ve výpočtu sekvenčním a výpočtu paralelním, implementovaném pomocí primitiv OpenMP. Stačí implementovat metodu "Matrix::closure()" která z dané matice napočítá její tranzitivní uzávěr. Pro násobení dvojice matic použijte naivní O(n^3) algoritmus, pro výpočet tranzitivního uzávěru aplikujte algoritmus, který použije O(log n) násobení.
Soubor common.h deklaruje a částečně implementuje datovou strukturu Matrix, soubor main.cpp obsahuje "ovladač" který spustí výpočet. Jako parametr lze použít název souboru, v takovém případě bude tento soubor načten, nebo dvojici čísel, které spustí program pro náhodnou matici velikosti dané prvním číslem a random seed daným druhým číslem (nepovinné).
Krom implementace sequential.cpp a parallel.cpp je vašim úkolem doplnit Makefile o target "check" který zkontroluje, že binárky sequential a parallel dávají očekávané výsledky pro testovací data dostupné v input/ a expected/. (Tzn. že výstup ./sequential input/c by se měl shodovat s obsahem souboru expected/c.) Navíc cíl check bude kontrolovat, že implementace je idempotentní: ./sequential expected/c nesmí změnit vstupní matici.
Poslední částí úkolu je textově popsat přínosy paralelizace tohoto problému, stručný návrh na další možné přístupy mimo vámi zvoleného (existují-li) a úvaha o efektivitě reprezentace matic použité v souboru common.h (včetně odhadu její paměťové náročnosti v závislosti na n, v bajtech; pomůcka: konzultujte dokumentaci, případně hlavičkové soubory STL). Součástí textové zprávy bude také výpis časů srovnávajících sekvenční a paralelní výpočet pro matice velikosti 500, 1000 a 1200.
Výstupem tedy bude tarball, který obsahuje:
Výstupní tarball *nebude* obsahovat další soubory (zejména ne binárky, zálohy textového editoru a pod.).
Projekt:
Odevzdávarna: Zadání: V tomto projektu je vaším úkolem implementovat paralelní výpočet tranzitivního uzávěru orientovaného grafu, zadaného jako matici sousednosti. Je nutné pro tuto paralelní implementaci použít systém OpenMP.
Vaším úkolem je dodat soubory parallel.cpp a sequential.cpp (viz Makefile), které demonstrují rozdíl ve výpočtu sekvenčním a výpočtu paralelním, implementovaném pomocí primitiv OpenMP. Stačí implementovat metodu "Matrix::closure()" která z dané matice napočítá její tranzitivní uzávěr. Pro násobení dvojice matic použijte naivní O(n^3) algoritmus, pro výpočet tranzitivního uzávěru aplikujte algoritmus, který použije O(log n) násobení.
Soubor common.h deklaruje a částečně implementuje datovou strukturu Matrix, soubor main.cpp obsahuje "ovladač" který spustí výpočet. Jako parametr lze použít název souboru, v takovém případě bude tento soubor načten, nebo dvojici čísel, které spustí program pro náhodnou matici velikosti dané prvním číslem a random seed daným druhým číslem (nepovinné).
Krom implementace sequential.cpp a parallel.cpp je vašim úkolem doplnit Makefile o target "check" který zkontroluje, že binárky sequential a parallel dávají očekávané výsledky pro testovací data dostupné v input/ a expected/. (Tzn. že výstup ./sequential input/c by se měl shodovat s obsahem souboru expected/c.) Navíc cíl check bude kontrolovat, že implementace je idempotentní: ./sequential expected/c nesmí změnit vstupní matici.
Poslední částí úkolu je textově popsat přínosy paralelizace tohoto problému, stručný návrh na další možné přístupy mimo vámi zvoleného (existují-li) a úvaha o efektivitě reprezentace matic použité v souboru common.h (včetně odhadu její paměťové náročnosti v závislosti na n, v bajtech; pomůcka: konzultujte dokumentaci, případně hlavičkové soubory STL). Součástí textové zprávy bude také výpis časů srovnávajících sekvenční a paralelní výpočet pro matice velikosti 500, 1000 a 1200.
Výstupem tedy bude tarball, který obsahuje:
- main.cpp a common.h (součást zadání)
- adresáře input/ a expected/ (součást zadání)
- Makefile (s přidaným cílem check)
- sequential.cpp (sekvenční implementace)
- parallel.cpp (paralelní implementace postavená na OpenMP)
- případné pomocné soubory pro implementaci make check
- textovou zprávu v souboru zprava.txt
Výstupní tarball *nebude* obsahovat další soubory (zejména ne binárky, zálohy textového editoru a pod.).
Projekt: