Komutatívna analýza; EWSTranslate
Zhrnutie
Paralelné stroje sľubujú výrazné zvýšenie výkonu, čo umožňuje viacerým procesorom spúšťať rôzne časti výpočtu súčasne. Vývojári tradične vyvíjajú aplikácie pre paralelné stroje, ktoré používajú výslovne paralelné jazyky. Na rozdiel od sériových programovacích jazykov majú výslovne paralelné jazyky komplexný programovací model charakterizovaný javmi, ako je blokovanie, nedeterministické vykonávanie a v prípade automatov na správu potreba priameho riadenia toku údajov výpočtom. Zjavné programovateľné výhody paradigmy sekvenčného imperatívneho programovania preto inšpirovali vývoj analytických a kompilátorových techník určených na automatickú paralelizáciu sériových programov.
Komutatívna analýza je rámec statickej analýzy na detekciu kyvadlových operácií. Dve operácie sa presunú, keď vygenerujú rovnaký výsledok, bez ohľadu na to, v akom poradí vykonajú. Komutatívna analýza odstraňuje mnoho obmedzení existujúcich prístupov založených na dátovej závislosti. Namiesto udržania relatívneho poradia jednotlivých čítaní a zápisov v jednotlivých pamäťových slovách komutatívna analýza agreguje dáta aj výpočty do veľkých zŕn. Potom staticky analyzujte výpočet s touto členitosťou, aby ste zistili, kedy časti vo výstupnom výpočte generujú rovnaký výsledok bez ohľadu na to, v akom poradí. Ak sú potrebné všetky operácie potrebné na vykonanie konkrétneho výpočtového modulu, môže kompilátor automaticky generovať paralelný kód.
Tento prístup má niekoľko zaujímavých vlastností. Pretože prepínacia analýza nie je založená na informáciách o topológii manipulovaných dátových štruktúr, kompilátor, ktorý používa prepínaciu analýzu, nemusí analyzovať časti kódu, ktoré vytvárajú dátovú štruktúru. Analýza prepínateľnosti je preto vhodná pre neúplné výpočty, ako sú aplikácie, ktoré spracúvajú perzistentné údaje (napr. Objektovo orientované databázové aplikácie) alebo aplikácie, ktoré manipulujú s geograficky rozptýlenými údajmi (napr. Mobilné výpočty na sieti WWW). ). V týchto prípadoch môže byť kód, ktorý pôvodne vytvoril dátovú štruktúru, nedostupný alebo už neexistuje. Komutatívna analýza je obzvlášť vhodná pre výpočty, ktoré manipulujú s grafmi.
Tieto experimentálne výsledky sú veľmi povzbudivé. Tieto aplikácie majú veľmi dynamický charakter - buď manipulujú so sofistikovanými údajovými štruktúrami založenými na ukazovateľoch, alebo predstavujú vysoko prístupné modely prístupu k údajom. Využitie paralelizmu s hrubými zrnami v aplikáciách s týmito charakteristikami bolo uznané ako veľmi ťažký problém. Nie sme si vedomí žiadnej inej kompilácie alebo techniky kompilácie, ktorá by pri týchto výpočtoch mohla vyťažiť značné množstvo súbežnosti. Pozitívne experimentálne výsledky navyše poskytujú konkrétny dôkaz o praktickom význame komutatívnej analýzy ako techniky automatickej kompilácie paralelizácie.