Úlohy na precvičenie – PDS 2019 – séria B

Úlohy riešte samostatne a podrobne. Celý postup zaznamenajte a komentujte. Odpovede zdôvodňujte celými vetami (väčšinou je otázok v úlohe viac!). Cieľom cvičenia nie je vyhľadanie riešenia, ale získanie skúseností so samostatným riešením úloh. Vo výnimočných situáciách použité citácie uveďte v riešení. Je slušné tiež uviesť mená osôb, s ktorými ste riešenie konzultovali (čo samozrejme je povolené, pokiaľ riešenie spíšete potom samostatne). Uprednostnite ručný zápis – umožní vám jednoducho pridávať ilustračné obrázky a nákresy.

Za každé správne a vyčerpávajúce riešenie (samozrejme aj s postupom) možno získať bod (ak nie je uvedené inak). Zlomky bodov možno získať aj za čiastočné riešenia. Riešenia tejto série je nutné doručiť do 28. 2. 2019, 14:25 (do začiatku prednášky). Pred týmto termínom je možné odovzdať riešenia na sekretariáte Ústavu informatiky (do priečinka Jirásek). Neskôr dodané riešenia a plagiáty nebudú opravované ani hodnotené. Problémy môžete konzultovať po prednáške resp. elektronickou poštou.

Úplné riešenie úlohy zahŕňa väčšinou (pokiaľ to nie je uvedené inak) aj zápis algoritmu (bez odvolávania sa na literatúru a knižnice)! Správne slovné úvahy bez zápisu algoritmu budú hodnotené len zlomkami bodov.

1. Pre model EREW PRAM s p procesormi navrhnite čo najefektívnejší algoritmus, ktorý zistí, či n-prvkové pole M[1..n] obsahuje aspoň jedno párne číslo. Zapíšte algoritmus pre i-ty procesor, spočítajte jeho časovú zložitosť, zrýchlenie a efektivitu. Tú istú úlohu vyriešte aj na CRCW-common PRAM modeli.

2 V CRCW-common PRAM modeli s n procesormi navrhnite a zapíšte algoritmus, ktorý v konštantnom čase vyhľadá v zadanom poli M[1..n] prvok s hodnotou v M[n+1], ale do výsledku M[n+2] zapíše jeho index len vtedy, keď sa bude prvok v poli vyskytovať práve raz (ak tam bude viackrát, do výsledku zapíše -1). Ako by ste riešili úlohu pre neobmedzený počet procesorov ?

3. Vstupné pole M[1..n], obsahuje v každom prvku kód pre ľavú alebo pravú zátvorku alebo niečo iné. Zapíšte EREW PRAM algoritmus, ktorý v čase O(log n) s najviac n procesormi zistí, či postupnosť prvkov poľa tvorí dobre uzátvorkovaný výraz (skúste využiť prefixové súčty).

4. Program, vykonávaný sekvenčne na výkonnom procesore, pracuje na 90% v častiach, ktoré sa dajú ľahko paralelizovať. Máme možnosť zakúpiť viacprocesorový systém, ktorý ale obsahuje procesory s tretinovým výkonom oproti nášmu procesoru.
(i) Koľko procesorov musí minimálne obsahovať, aby sme mohli dosiahnuť nejaké zrýchlenie výpočtu ?
(ii) Zakúpili sme 64-procesorový systém. Spočítajte, aké zrýchlenie výpočtu dosiahneme na tomto systéme oproti výpočtu na pôvodnom jednoprocesorovom výkonnom systéme, keď budeme paralelizovať 90% sekvenčného výpočtu.
(iii) Aké maximálne zrýchlenie je možné podľa Amdahlovho zákona dosiahnuť ?
(iv) Aby sme presvedčili investorov, potrebujeme ukázať na zakúpenom 64-procesorovom systéme aspoň 20 násobné zrýchlenie. Skúsime teda paralelizovať aj zvyšné časti programu. Akú najväčšiu časť z času vykonávania paralelizovaného algoritmu je možné vykonať sekvenčne tak, aby bola podmienka zrýchlenia splnená ?