Úlohy z vláknového programování PV Lukáš Hejtmánek, Petr Holub Obsah Úlohy nezávislé na programovacím jazyce Úkol : Paralelní ood ll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Úkol : Přetahovaná ve vláknech . . . . . . . . . . . . . . . . . . . . . . . . Úkol : Re ektor UDP paketů . . . . . . . . . . . . . . . . . . . . . . . . . C/C++ Úkol : Producent konzument . . . . . . . . . . . . . . . . . . . . . . . . . Úkol : Kancelační body . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Úkol : Procházení seznamu . . . . . . . . . . . . . . . . . . . . . . . . . . Úkol : Paralelní quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . Úkol : Lock-free datové struktury . . . . . . . . . . . . . . . . . . . . . . . Java Úkol : Měření výkonu zámků . . . . . . . . . . . . . . . . . . . . . . . . . Úkol : Měření výkonu sychronizace pomocí atomických proměnných . Úkol : Měření výkonu kolekcí . . . . . . . . . . . . . . . . . . . . . . . . . Úkol : Implementace webového crawleru . . . . . . . . . . . . . . . . . . Úkol : Signalizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Úkol : Paralelizace rozvrhování . . . . . . . . . . . . . . . . . . . . . . . . Ada Úkol : Implementace semaforu, závlačky a bariéry v Adě . . . . . . . . . Úkol : Neblokující zásobník a fronta . . . . . . . . . . . . . . . . . . . . . *Úkol : Implementace thread pools v Adě . . . . . . . . . . . . . . . . . . Z uvedených příkladů si každý student vybere jeden, který samostatně zpracuje. Pokud si dva studenti vyberou stejné zadání, bude v rámci zkoušky posuzována i originalita řešení. Úkoly, které považujeme za obtížnější, jsou označeny hvězdičkou ­ při diskusi jejich řešení bude brán zřetel na vyšší obtížnost úkolu. V případě, že budete mít vlastní nápad na vhodné zadání, ozvěte se nám ­ pokud bude rozumné, tak Vám po předchozí dohodě jeho implementaci umožníme. S případnými dotazy se obracejte na adresy: * Lukáš Hejtmánek (xhejtman@ics.muni.cz) ohledně úkolů v jazyce C/C++, * Petr Holub (hopet@ics.muni.cz) ohledně úkolů v jazycích Java a Ada. eventuálně na kteroukoli z výše zmíněných adres pokud jde o úkoly nezávislé na jazyku (a také v případě nedostupnosti jednoho z nás). Úlohy nezávislé na programovacím jazyce Úkol : Paralelní ood ll S pomocí knihovny libSDL (případně jiné vhodné knihovny pro práci s gra kou) implementujte algoritmus ood ll . Aplikace bude schopna paralelně (parametricky až n vláken) vyplnit obrazec (alespoň pětiúhelník). Každé vlákno bude kreslit svou barvou, již vyplněná plocha se nesmí vyplňovat znova. Úkol : Přetahovaná ve vláknech S pomocí knihovny libSDL (případně jiné vhodné knihovny pro práci s gra kou) implementuje přetahování o provaz. Vytvořte vlákna, která představují hráče přetahované. Hráči stojí v rozích čtverce, od každého vede lano doprostřed čtverce, kde jsou svázaná dohromady. Vlákna tahají náhodná čísla, která odpovídají přitáhnutí provazu směrem k hráči. Střed lan se bude pohybovat uvnitř čtverce podle výsledků náhodných čísel. Hra končí, jakmile nějaký hráč bude mít střed lan u sebe. Jako prémiové obtížnější zadání je možno tuto úlohu implementovat pro parametrizovatelný počet n za provaz tahajících vláken. Úkol : Re ektor UDP paketů Implementujte paralelní re ektor UDP paketů s následující funkcionalitou: . Každý přijatý paket je analyzován na zdrojovou IP adresu a port: pokud tato kombinace ještě není mezi účastníky, je tam automaticky přidána. . Každý přijatý paket je rozeslán všem účastníkům. . Každý účastník, který déle jak s neposlal na re ektor ani jeden paket je vyloučen ze seznamu účastníků . Účastníky je možno přidat na začátku explicitně a tito účastníci nepodléhají s expiraci. Přijímání, odesílání a housekeeping budou řešeny jako samostatná vlákna. Navrhněte a implementujte vhodné datové struktury, proveďte měření a diskutujte výkonnost implementovaného řešení. Případně můžete srovnat s jednovláknovým řešením. C/C++ Úkol : Producent konzument Naimplementujte varianty klasické úlohy producent/konzument. Producent bude nějakou rychlostí produkovat objekty, konzument je bude nějakou rychlostí spotře- http://en.wikipedia.org/wiki/Flood_fill bovávat. Maximální množství vyprodukovaných ale nezkonzumovaných objektů bude omezeno ­ tj. nejen konzument bude čekat na producenta, ale i producent bude čekat na konzumenta, produkuje-li příliš rychle. Jako objekty použijte např. MB kusy paměti vyplněné nějakou hodnotou. . Objekty řaďte do fronty, kterou není nutné zamykat. Zkonzumované objekty neuvolňujte a předávejte zpět producentovi k opětovnému použití. . Objekty řaďte do obyčejné fronty, kterou při přidání prvku či odebrání prvku zamknete. Objekty alokujte nové a staré uvolňujte. Srovnejte rychlost obou řešení. Úkol : Kancelační body Implementujte pomocí vláken vyhledávání v textu. Vygenerujte si nějaký řádově stomegabytový soubor s textem a pomocí několika vláken v něm vyhledávejte nějaký vzor. Jakmile některé vlákno vzor najde, pošle ostatním cancel a oznámí úspěch (každé ukončené vlákno po sobě musí ,,uklidit``, tj. zavřít soubor a podobně. Vlákna musí prohledávat vždy jinou část souboru. V další části programu vytvořte nová vlákna a spočítejte četnost nalezeného vzoru. Výsledek opět oznamte na terminál. Úkol : Procházení seznamu Implementujte následující aplikaci. Master vlákno prochází seznam objektů. Každý objekt má tři atributy: int x, int y, char data[9000]. Master vlákno odebere ze seznamu objekt a dá ho na zpracování workerům. Workeři sdílí jeden velký bu er velikosti int w * int h. Worker převezme objekt, podívá se, jestli x * y není již za hranicí bu eru (x y + 9000 < w h), pokud není, zavolá memcpy(buffer + x*y, data, 9000). Pokud je, uvolní bu er a alokuje nový tak, aby se do něj objekt vešel a následně do něj data nakopíruje. Pozor na to, že nelze uvolnit bu er, do kterého jiný worker právě kopíruje data. Aplikace by měla škálovat na více procesorů. Úkol : Paralelní quicksort Implementujte paralelně algoritmus třízení quicksort . Porovnejte rychlost paralelní implementace se sekvenční verzí. Paralelní verze by měla škálovat na více procesorech. Třiďte objekty typu double. Úkol : Lock-free datové struktury Implementujte korektně lock-free RCU strukturu. Tedy strukturu, která je převážně čtena a občas aktualizována. Aktualizace se provádí pomocí kopie prvku nebo celé http://cs.wikipedia.org/wiki/Quicksort struktury a aktualizace je provedena v nové kopii. Původní prvek nebo strukturu je potřeba uvolnit až ve chvíli, kdy se nepoužívá. Navrhněte vhodný způsob dodatečného uvolňování těchto objektů či struktur. Pro test použijte mapu nebo seznam o řádově miliónech položkách, po cca přečtených položkách jednu změnte. Porovnejte se sekvenčním řešením a ukažte, jak aplikace škáluje pro - CPU jádra. Java Úkol : Měření výkonu zámků Navrhněte (najděte) a implementujte vhodný algoritmus pro porovnání výkonu * synchronized * ReentrantLock * ReadWriteLock Proveďte a zpracujte měření v rozsahu až vláken, a to v režimech nízkého až středního versus vysokého soutěžení o zámek. Úkol : Měření výkonu sychronizace pomocí atomických proměnných Navrhněte (najděte) a implementujte vhodný algoritmus pro porovnání výkonu * synchronized/ReentrantLock * AtomicXXX * ThreadLocal Proveďte a zpracujte měření v rozsahu až vláken, a to jak v režimu nízkého a vysokého ,,soutěžení o zámek`` (i tam, kde se ve skutečnosti nezamyká ;-) ). Úkol : Měření výkonu kolekcí Zpracujte studii porovnávající výkon synchronizovaných a paralelních kolekcí, zejména * CopyOnWriteXXX v porovnání se synchronizovanými seznamy a množinami, * ConcurrentHashMap v porovnání se synchronizedMap a Hashtable, * srovnání s WaitFreeReadQueue a WaitFreeWriteQueue, podaří-li se získat přistup k funkční implementaci. V rámci studie je třeba vybrat a implementovat několik vhodných algoritmů, na kterých bude srovnání provedeno. Úkol : Implementace webového crawleru Pomocí vzoru kradení práce s vlastní frontou úloh pro každé vlákno implementujte webový crawler, který bude procházet web počínaje zadanou stránkou do parametricky zadané hloubky a bude počítat statistiku výskytu HTML elementů na stránkách. Pro počítání statistik zvolte vhodnou strukturu (tak, abyste byli své rozhodnutí schopni zdůvodnit!). Crawler si bude vnitřně měřit statistiky, jak často se použil prostý model práce producent-konzument a jak často bylo využito mechanismu kradení práce. Úkol : Signalizace Pomocí signalizačních mechanismů (wait(), notify(), notifyAll()) implementujte ekvivalenty následujících synchronizačních mechanismů: * BlockingQueue * BlockingDequeue * semafor * CountDownLatch * bariéru * Exchanger Úkol : Paralelizace rozvrhování Úkolem studenta je zparalelizovat sekvenční optimalizační cyklus. Tento cyklus se používá na optimalizaci rozvrhu či plánu ­ například školního rozvrhu nebo plánu pořadí výpočtu úloh na (super)počítačích. Jeden cyklus se skládá že tři kroku: . výběr úlohy(předmětů) z rozvrhu . přesunutí úlohy na jiné místo v rozvrhu . vyhodnocení této změny a její přijetí/zamítnutí v závislosti na zlepšení/zhoršení rozvrhu Takovýto algoritmus lze velice dobře paralelizovat. Nejdůležitějším úkolem studenta tak bude efektivně vyřešit problém reprezentace rozvrhu, který musí pro jednotlivá vlákna zůstat konzistentní, tj. nesmí být ovlivněn kroky ostatních vláken. Triviální řešení představuje duplikace této datové struktury pro každé nové vlákno, což ale nemusí být paměťové efektivní. Dalším zajímavým problémem je otázka duplikovaných kroku, kdy bez vzájemné komunikace vláken hrozí, že jednotlivá vlákna budou duplikovat již jednou provedené optimalizační kroky jiných vláken. Ve nále je potom potřeba provést sadu experimentálních vyhodnocení, kdy student změří výslednou kvalitu řešení a časově nároky paralelní i původní sekvenční verze programu. Dále pak podle potřeby vyhodnotí jednotlivé možnosti paralelizace a na základě experimentálních výsledků (např. časová vs. paměťová náročnost) zvolí nejvhodnější variantu řešení. Sekvenční algoritmus pro zájemce poskytne dr. Klusáček. Ada Úkol : Implementace semaforu, závlačky a bariéry v Adě Implementujte semafor, závlačku (ekvivalent CountDownLatch z Javy) a bariéru dvěma způsoby: ( ) pomocí tasků, ( ) pomocí protected typů. Pro každý z uvedených typů implementujte jednoduchou aplikaci, která jej bude používat. Úkol : Neblokující zásobník a fronta Implementujte v Adě následující dvě struktury: * neblokující zásobník Treiberovým algoritmem ­ implementace pro Javu je dostupná na adrese http://www.javaconcurrencyinpractice.com/ listings/ConcurrentStack.java, * neblokující frontu algoritmem Michael-Scott ­ probráno na přednášce. Pro implementaci využijte generika. Vytvořte jednoduchý příklad, který struktury bude využívat. *Úkol : Implementace thread pools v Adě Navrhněte a implementujte mechanismus ekvivalentní thread pools v jazyce Ada. Využijte předávání práce pomocí access typů na procedury. read pools budou mít jako parametry minimální počet vláken, maximální počet vláken a hodnotu keep-alive, po jejímž uplynutí bez vykonání práce budou vlákna ukončena. R. K. Treiber. "Systems Programming: Coping with Parallelism.", Technical Report RJ , IBM Almaden Research Center, April . M. M. Michael and M. L. Scott. "Simple, Fast, and Practical Non-Blocking ad Blocking Concurrent Queue Algorithms." In Symposium on Principles of Distributed Computing, pages - . . http: //citeseer.ist.psu.edu/michael96simple.html