Анализ на комутативността; EWST Превод
Обобщение
Паралелните машини обещават значително увеличение на производителността, което позволява на множество процесори да изпълняват едновременно различни части от изчислението. Разработчиците традиционно разработват приложения за паралелни машини, използващи изрично паралелни езици. За разлика от серийните езици за програмиране, изрично паралелните езици имат сложен програмен модел, характеризиращ се с явления като блокиране, недетерминирано изпълнение и, в случай на машини за съобщения, необходимостта от пряко управление на потока от данни чрез изчисление. Поради това очевидните програмируеми предимства на последователната императивна парадигма на програмиране са вдъхновили развитието на техниките за анализ и компилатор, предназначени за автоматично паралелизиране на серийните програми.
Анализът на комутативността е рамка за статичен анализ за откриване на совалкови операции. Две операции се движат, когато генерират един и същ резултат, независимо от реда, в който изпълняват. Анализът на комутативността премахва много ограничения на съществуващите подходи, базирани на зависимостта от данните Вместо да запази относителния ред на отделните показания и да записва в отделни думи в паметта, анализът на комутативността обединява както данни, така и изчисления в големи зърнени единици. След това анализирайте статично изчислението при тази детайлност, за да разберете кога частите в изчислението на изхода генерират един и същ резултат, независимо от реда, в който се изпълняват. Ако всички операции, необходими за извършване на конкретна изчислителна совалка, компилаторът може автоматично да генерира паралелен код.
Този подход има някои интересни свойства. Тъй като анализът на превключването не се основава на информация за топологията на манипулираните структури от данни, компилаторът, който използва превключващ анализ, не трябва да анализира частите на кода, които изграждат структурата на данните. Следователно анализът на превключваемостта е подходящ за непълни изчисления, като приложения, които обработват постоянни данни (например обектно-ориентирани приложения на бази данни) или приложения, които манипулират географски разпръснати данни (например мобилни изчисления в глобалната мрежа). ). В тези случаи кодът, който първоначално е създал структурата на данните, може да е недостъпен или вече да не съществува. Анализът на комутативността също е особено подходящ за изчисления, които манипулират графики.
Тези експериментални резултати са много обнадеждаващи. Тези приложения имат много динамичен характер - или манипулират сложни базирани на указатели структури от данни, или представят силно достъпни модели за достъп до данни. Използването на паралелизъм с груби зърна в приложения с тези характеристики е признато за много труден проблем. Не ни е известна друга техника за компилиране или компилация, която може да извлече значителни количества съвпадение за тези изчисления. Освен това положителните експериментални резултати предоставят конкретни доказателства за практическото значение на анализа на комутативността като техника за автоматично компилиране на успоредяване.