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

 

Ú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 úplné riešenie (samozrejme aj s postupom) možno získať v tejto sérii dva body. Zlomky bodov možno získať aj za čiastočné riešenia. Riešenia tejto série je nutné doručiť do 28. 3. 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 môjho priečinka). Neskôr dodané a opisované riešenia nebudú opravované ani hodnotené. Problémy môžete konzultovať po prednáške, elektronickou poštou alebo prostredníctvom diskusnej skupiny {pds2019@googlegroups.com}.

 

1. Majme n procesov s myid od 0 po n-1. Procesy komunikujú v kruhu obojsmerne so svojimi susedmi (bidirectional ring), sú zoradené v kruhu podľa myid (proces s myid = i komunikuje na rozhraní left s procesom s myid = (i-1) mod n, na rozhraní right s procesom (i+1) mod n) a poznajú aktuálnu hodnotu n. Každý proces má v lokálnej premennej x svoju hodnotu. Chceme dosiahnuť, aby vzájomnými výmenami hodnôt x (ako v CompareExchange z prednášky) vznikla situácia, že proces i bude mať v premennej x i-tu najnižšiu hodnotu zo všetkých pôvodných hodnôt – teda pôvodné hodnoty budú premiestnené tak, aby v procesoch v poradí 1, ... , n tvorili usporiadanú neklesajúcu postupnosť. Navrhnite algoritmus (ľubovoľný) a zapíšte ho v distribuovanom modeli výpočtu. Ukážte jeho korektnosť (správnosť výsledku, ukončenie všetkých procesov a vyprázdnenie kanálov) a spočítajte jeho časovú a komunikačnú zložitosť.

2. Realizujeme voľbu koordinátora v synchrónnej kruhovej obojsmernej sieti s deviatimi procesmi s myid v poradí 3, 2, 7, 9, 1, 5, 6, 4, 8. Popíšte stavy výpočtu pomocou HS algoritmu z prednášky postupne po každom distribuovanom kroku. Spočítajte presný počet (synchrónnych) krokov a počet všetkých prenesených správ pri realizácii s uvedenými konkrétnymi vstupmi. Aký by bol najvyšší počet krokov a správ pri tomto počte procesov? Stanovte tiež také počiatočné priradenie myid, pri ktorom by sa dosiahla táto najvyššia časová a komunikačná  zložitosť.