Domů › Paralelní vrcholové obarvení grafu

Paralelní algoritmus

Ne, 03/07/2010 - 21:06 — oberhuber

Sekvenční algoritmus lze zpracovat buď rekurzivně, nebo s použítím zásobníku. Pro paralelní algoritmus je použit zásobník, do kterého jsou ukládány neprohledané podstromy – tedy stavy obarvení, kde ještě nebyly obarveny všechny vrcholy.

Inicializace
Na rootu je vytvořen graf, který se má obarvit. Tento graf se následně přepošle všem ostatním vrcholům. Poté je na nultém procesu spuštěn algoritmus prohledávání do hloubky a neprojité podstromy se ukládají do zásobníku. Dojde-li algoritmus do listu stromu, který není řešením, vezme si jako aktuální podstrom poslední vložený podstrom a pokračuje s ním.

Komunikace
Po určitém předem definovaném intervalu nastává vzájemná komunikace mezi procesy. Jejím účelem je vyvážení počtu neprohledaných podstromů mezi procesy a také ukončení výpočtu v případě, že bylo nalezeno řešení nebo byly prohledány všechnz podstromy.

Komunikace probíhá takto:

  1. Root shromáždí zprávy (Gather) od všech procesů. Tyto zprávy obsahují:
    a. ID procesu
    b. Aktuální počet podstromů v zásobníku
    c. Informaci, zda proces nalezl řešení úlohy
    d. V případě nalezení řešení i obarvení a použitý počet barev
  2. Root ze shromážděných dat zjistí, zda má úlohu zakončit. To nastává tehdy, pokud nějaký proces úspěšně nalezl řešení, nebo pokud mají všechny procesy nulový počet podstromů v zásobníku. V tom případě byly prohledány všechny podstromy.
  3. Root rozešele (Broadcast) všem procesům informaci, zda mají či nemají skončit výpočet.
  4. Obdrží-li proces informaci o ukončeném výpočtu, běh úlohy na daném procesu končí. Root vypíše výsledek a končí také. Dále již žádná komunikace neprobíhá.
  5. Není-li splněna ukončovací podmínka, root spočítá, jaké procesy musí předat určitý počet podstromů jiným procesům, aby byly počty podstromů v zásobnících stejné. Každý proces buď odesílá nebo přijímá podstromy (oboje může i od více procesů).
  6. Root rozešle (Scatter) zprávu všem procesům. Tato zpráva obsahuje buď
    a. Počty podstromů, které má proces odeslat
    b. ID procesů, které je mají přijmout
    nebo
    a. Počty podstromů, které má proces přijmout
    b. ID procesů, které je mají odeslat
  7. Procesy buď odešlou (Send) nebo přijmou (Receive) výše určený počet podstromů.
  8. Každý proces má nyní téměř stejně podstromů v zásobníku. Každý proces prochází podstromy ze zásobníku až dokud nenastane čas ke komunikaci.