Simulujte v Transimu program pro výpočet FWT (Fast Wavelet transform) se čtyřmi koeficienty. Hodnoceno bude i efektivita výsledného řešení, proto překrývejte komunikaci s výpočtem, Procesor může mít zahájenou komunikaci na každém kanálu a současně počítat. Sdružujte jednotlivé byty do jediné zprávy. Protože se fyzicky přenší jen jeden byte, použijte toto schema: simulujte komunikaci celé zprávy, ale vlastní zprávu si můžete vzít z (globální) paměti.
Počet procesorů, množství dat: dle uvážení 6 reprezentativních kombinací s jednou kombinací max. hodnot co umožňuje Transim, resp. Vaše řešení. Počet procesorů, nebo množství dat může být ve vech testech stejné.
Každý nezávislý řeitel si vybere dvě různé topologie (viz. schémata propojení ) z těchto:
Dle počtu koeficientů je potřeba pro výpočet výsledné hodnoty odpovídající počet hodnot, ve Vaem případě 4. Z těchto 4 hodnot jsou počítány dvě nové hodnoty: první dle vzorce z1=K1*x1+K2*x2+K3*x3+K4*x4, kde K1,K2,K3,K4 jsou konstanty pro danou WT a x1,x2,x3,x4 jsou původní hodnoty, druhá dle podobného vzorce s jinými konstantami, což je pro Vás nepodstatné. Pro dalí dvě nové hodnoty se použijí dalí 4 vstupní data, jakoby vstupní data posunutá o dvě.
x1 x2 x3 x4 x5 x6 x7 x8 y1=k1*x1+k2*x2+k3*x3+k4*x4 (SERV (7) z1=K1*x1+K2*x2+K3*x3+K4*x4 y2=k1*x3+k2*x4+k3*x5+k4*x6 z2=K1*x3+K2*x4+K3*x5+K4*x6 ... y4=k1*x7+k2*x8+k3*x1+k4*x2 z4=K1*x7+K2*x8+K3*x1+K4*x2
Nové hodnoty vstupují do dalího kola. Polovina z nich se nechá (řekneme z), s druhou polovinou se naloží úplně stejně, ale jich půl, poloviční náročnost výpočtu.
Počet kol závisí na množství dat, končí se až zůstane jediný koeficient y. (V předcházejícím kole se data použila dvakrát.) Pro jednoduchost proveďte 4 kola. Pro Vás tento postup znamená jen
Tento výpočet provádíte pro každý řádek dat nezávisle, po skončení výpočtu proveďte totéž pro každý sloupec nezávisle.
Způsob rozdělení dat mezi procesory zvolte podle uvážení (OpenMP), u Transimu je vhodné dle topologie propojení.
Dalí informace: část diplomky, myslím si, že nebudete potřebovat, spíe jen pro zpřesnění vysvětlení výpočtu.
Naprogramujte zasílání zpráv v migračním genetickém algoritmu s použitím knihovny MPI. Popis genetického algoritmu je uveden v zadání 2. projektu.
Není nutné implementovat genetické operátory (křížení, mutace) ani vyhodnocování funkce fitness. Můžete je nahradit čekáním po konstantní dobu (funkce usleeep, nanosleep). Těžitěm projektu je vhodné navržení a implementace komunikace pro předávání jedinců (chromozómů) mezi procesory. Procesory si mezi sebou předávají jednou za k generací (k >= 1) pouze několik nejlepích jedinců. Porovnejte dobu výpočtu pro tyto způsoby předávání chromozómů mezi procesory:
Zkuste použít funkce pro neblokující komunikaci, aby se dala překrývat s výpočtem. Použijte pro výpočet 8 procesorů, délku chromozómu zvolte několik set bytů, počet generací libovolný.
Odevzdávat se bude zdrojový kód programu, soubor Makefile pro překlad a změřená doba výpočtu pro variantu s rozesíláním chromozómů všem procesorům a variantu s posíláním skupině 3 procosorů.
Nezapomínejte ukončovat před skončením práce vechny své běžící procesy na počítačích, které jste použili k výpočtu - pokud se program v MPI úspěně nedokončí, obvykle zůstanou na počítačích běžet jeho procesy (viz ps -u login; kill xxxx).
Reference standardu MPI je dostupná na adrese http://www-unix.mcs.anl.gov/mpi/ .
Pro testování použijte 4-procesorový server Sun Enterprise 450 adela.fit.vutbr.cz. Studenti, kteří se přihlásí na variantu OpenMP, budou mít na tomto serveru povolen účet.
Dokumentace ke standardu OpenMP je dostupná na adrese http://www.openmp.org/ . Úvod do programování v OpenMP je v dokumentu openmpbook.ps.
Pro přihlášení polete e-mail na adresu staroba@fit.vutbr.cz s předmětem "PPP projekt 3". Aktuální obsazení zadání si můžete průběžně kontrolovat v následující tabulce.
FWT (max. 10 lidí) | GA (max. 10 lidí) | ||
---|---|---|---|
OpenMP | Transim | MPI | |
1. | Michal Berka (xberka02) - ring, mesh | Zbynek Krivka (xkrivk01) | |
2. | Kobliha Milos (xkobli03) - ring, full | Pavel Krivanek (xkriva11) | |
3. | Jaromir Capík (xcapik01) - full, ring | Spanel Michal (xspane01) | |
4. | Stransky Martin (xstran02) | Martin Vítek (xvitek10) | |
5. | Konecny Libor (xkonec25) | ||
6. | Holenka Jiri (xholen02) | ||
7. | Grulich Lukas (xgruli01) | ||
8. | Horak Jiri (xhorak22) | ||
9. | Jaroslav Škarvada (xskarv02) | ||
10. | Prochazka Zdenek (xproch38) |
Poslední změna: 28. 04. 2003