Zadání projektů do předmětu Paralelní a Distribuované algoritmy

 

!!! Pro získání zápočtu a úspěšné ukončení předmětu je nutné za každý projekt získat minimálně jeden bod (tedy oba projekty odevzdat v řádném termínu), za celý semestr (projekty a půlsemestrální zkoušku) pak celkem alespoň 13 bodů !!!

 

Jedná se o následující projekty:

  1. Seznámení se s prostředím PRAM. V rámci tohoto projektu se nic neodevzdává a tento projekt není hodnocen.

 

  1. Implementace algoritmu Odd-even transportion sort v jazyce PM2. (10b)

Datum odevzdání: 13. dubna

Doporučený formát vstupu (můžete použít i jiný, pokud to zdůvodníte v dokumentaci):

1. hodnota – počet řazených hodnot (a současně počet procesorů) N

2. hodnota a všechny následující – jednotlivá řazená čísla, oddělená mezerami

                        Příklad: „6 2 3 3 1 4 7“ (6 prvků)

Doporučený formát výstupu (můžete použít i jiný, pokud to zdůvodníte v dokumentaci) - stejný, jako formát vstupu

                        Příklad: „6 1 2 3 3 4 7“

 

  1. Implementace algoritmu Minimum extraction sort v jazyce PM2. (10b)

Počet řazených prvků přitom může být libovolný (nemusí jít o mocninu 2).

Datum odevzdání: 4. května

Doporučený formát vstupu (můžete použít i jiný, pokud to zdůvodníte v dokumentaci):

1. hodnota – počet řazených hodnot N

2. hodnota a všechny následující – jednotlivá řazená čísla, oddělená mezerami

                        Příklad: „7 5 3 3 1 4 9 8“ (7 prvků)

Doporučený formát výstupu (můžete použít i jiný, pokud to zdůvodníte v dokumentaci) - stejný, jako formát vstupu

                        Příklad: „7 1 3 3 4 5 8 9“

 

U obou projektů platí, že hodnoty ve vstupních souborech mohou být odděleny nejen mezerami, ale i tabelátory, nebo znaky konce řádku (případně posloupností těchto znaků).

Hodnoty ve výstupních souborech však budou mezi sebou odděleny pouze jednou mezerou!

 

Projekty budou odevzdány prostřednictvím fakultního informačního systému. Obě implementace budou uloženy v archivu společně s dokumentací k projektu. Obsahem dokumentace bude komentovaný výpis algoritmu v jazyce PM2, stručný rozbor algoritmu, analýza tohoto algoritmu s ohledem na postup řešení, rozbor provedených experimentů a závěr. Rozborem experimentů je myšleno porovnání časové složitosti dosažených výsledků s předpokládanou (teoreticky vypočtenou) a komentář k souladu, případně nesouladu. Součástí tohoto rozboru tedy bude také tabulka, případně graf výsledných hodnot.

 

Archiv bude pojmenován:              xlogin00.zip (zip/tgz/tar.gz)

Zdrojový kód:                               xlogin00.pm2

Dokumentace:                               xlogin00.pdf nebo xlogin00.ps

 

V případě potřeby je možno záležitosti týkající se projektů konzultovat s cvičícím. Při použití e-mailu Vás prosím, abyste v kolonce "Předmět" uváděli na začátku zkratku PRL (tedy např. "PRL dotaz", "PRL dotaz k projektu č.2")

 

ad. 0

Nejprve je třeba nainstalovat aplikace nezbytné pro zdárné vyřešení projektů. Jedná se o dva překladače a jeden interpretr. Ten je schopen provádět jistý binární kód a jeho běh odpovídá běhu programu na architektuře PRAM. Tento kód lze získat překladem a to překladem jazyka PEL. Jedná se o jazyk na nízké úrovni abstrakce a tedy může v tomto jazyce být nepohodlné vytvářet programy. Jazykem vyšší úrovně, který lze přeložit do jazyka PEL, je jazyk PM2. Tedy z hlediska programátora je nejprve napsán kód v jazyce PM2, ten je přeložen do jazyka PEL a dále, po zpracování pre-procesorem cpp, je překladem získán binární kód, který lze interpretovat. Celý popsaný proces je demonstrován na obrázku 1.

Obrázek 1. Proces tvorby, překladu a spuštění aplikace v jazyce PM2

 

K dispozici jsou následující archivy

http://www.fit.vutbr.cz/~skrivan/vyuka/prl/pm2.tar.gz (pm2)
http://www.fit.vutbr.cz/~skrivan/vyuka/prl/emulator.tar.z (pram)

 

Doporučené prostření pro překlad:

djgpp v 2.04, OS WIN-XP (je potřebná knihovna curses.h, použijte cygWin (Q:/cygWin) a v souboru makefile nahraďte parametr linkeru "LIBRARIES=-lcurses -ltermlib" parametrem "LIBRARIES=-lncurses". Dále je v dávce potřeba změnit cestu k preprocesoru cpp (z "/usr/lib/cpp" na "/bin/cpp") )

Pokud preferujete Linux, anebo máte se systémem Windows XP problémy, jednoduše rozbalte archivy do adresáře a spusťte make, který provede vše potřebné.

 

Jako alternativní můžete využít řešení pana Petra Machaty, který upravil program pm2 a odstranil z něj některé chyby:

http://www.stud.fit.vutbr.cz/~xmacha31/pm2/pm2.html

 

Poslední úpravy 25. 2. 2008, Ing. Roman Skřivánek