Аутоматска паралелизација

Аутоматска паралелизација, такође аутопаралелизација, или паралелизација, користи се у контексту претварања секвенцијалног кода у вишенитни или векторски код (или чак оба), како би се симултано искористило више процесора у заједничкој меморији мултипроцесорске (СМП) машине. Циљ аутоматске паралелизације је да ослободи програмере од напорних и грешакама склоних процеса ручне паралелизације.^[1] Иако је квалитет аутоматске паралелизације побољшан последњих неколико деценија, потпуна аутоматска паралелизација секвенцијалних програма компајлерима остаје велики изазов због потребе за комплексним анализама програма и непознатих фактора (као што је опсег улазних података ) током компилације.^[2]

Програмске контролне структуре на којима аутопаралелизација највише ставља акценат су петље, јер, генерално, највише времена извршења програма се одвија унутар неког облика петље. Постоје два основна приступа паралелизацији петље: угнежђена вишенитна обрада и циклична вишенитна обрада.^[3]

На пример, размотримо петљу која у свакој итерацији врши стотине операција, и траје хиљаду итерација. Ово се може посматрати као мрежа 100 колона од 1000 редова, укупно 100.000 операција. Циклична вишенитна обрада додељује сваки ред засебној нити. Линијска вишенитна обрада додељује сваку колону засебној нити.

Циклична вишенитна обрада

Циклична вишенитна обрада паралелног компајлера покушава да раздвоји петљу тако да се свако понављање може извршити на засебном процесору истовремено.

Компајлер паралелне анализе

Компајлер обично спроводи две пролазне анализе пре стварне паралелизације како би се утврдило следеће:

Да ли је безбедно да се паралелизује петља? Одговар на ово питање захтева прецизно анализирање зависности и алијаса.
Да ли је вредно да се паралелизује? Овај одговор захтева поуздану процену (моделирање) програмског оптерећења и капацитета паралелног система.

Први пролаз компајлера обавља анализу зависности података петље да би се утврдило да ли се свака итерација петље може извршити независно од других. Зависности података се понекад могу разрешити, али то може да унесе додатно оптерећење у виду размене порука, синхронизације заједничке меморије, или неког другог начина процесорске комуникације.

Други пролаз покушава да оправда напоре паралелизације упоређивањем теоријског времена извршавања кода након паралелизације са секвенцијалним временом извршења. Понекад се, у нескладу са интуицијом, код не побољшава паралелизацијом. Додатни рад узрокован коришећењем вишеструких процесора може да поништи потенцијална убрзања паралелизованог кода.

Пример

Петља се зове DOALL ако се све њене итерације, у сваком призивању, могу упоредо извршити. Фортран код испод је DOALL, и компајлер га може аутоматски паралелизовати јер је свака итерација независна од других, а крајњи резултат низа z ће бити исправан без обзира на редослед извршавања других итерација.

   do i = 1, n
     z(i) = x(i) + y(i)
   enddo

Постоји много пријатних паралелних проблема које имају такве DOALL петље. На пример, када рендеринг прати филм, сваки фрејм филма може независно да се искаже, а сваки пиксел појединачног оквира може бити независно исказан.

Са друге стране, следећи код не може бити аутопаралелизован, јер вредност z(i) зависи од резултата претходне итерације, z(i - 1) .

   do i = 2, n
     z(i) = z(i - 1)*2
   enddo

То не значи да се код не може паралелизовати. Еквивалентно је

   do i = 2, n
     z(i) = z(1)*2**(i - 1)
   enddo

Међутим, садашњи компајлери паралелизације обично нису у стању да произведу аутоматску паралелизацију, а и питање је да ли ће тај код имати користи од паралелизације на првом месту.

Угнежђено коришћење кода

Угнежђено коришћење кода паралелног компајлера покушава да расчлани редослед операција унутар петље у низ кодних блокова, тако да се сваки блок кода извршава на одвојеним процесорима истовремено.

Постоје многи пријатно паралелни проблеми које имају такве релативно независне кодне блокове, посебно системи који користе цеви и филтере. На пример, при преносу телевизијког програма уживо, следећи задаци се морају обављати више пута у секунди:

Прочитајте оквир сировог пиксела података са сензора слике,
Извршите MPEG компензацију кретања на сировим подацима,
Ентропски компримујте векторе кретања и друге податке,
Разложите компримоване податке у пакете,
Додајте одговарајућу корекцију грешке и извршите ФФТ да бисте конвертовали пакете података у COFDM сигнале, и
Пошаљите COFDM сигнале из ТВ антене.

Угнежђена вишенитна обрада паралелизирајућег компајлера може да додели сваку од ових 6 операција различитом процесору, можда уређехих у систолном низу, умећући одговарајући код да проследи излаз једног процесора на следећи процесор.

Недавна истраживања су фокусирана на коришћење моћи ГПУ процесора^[4] и вишејезгарних система^[5] за израчунавање таквих независних кодних блокова (или једноставно независних итерација петље) у рунтиме. Меморија приступа (директно или индиректно) може бити једноставно обележена за различите итерације петље и може се поредити ради детекције зависности. Користећи ову информацију, итерације се групишу у нивое тако да су итерације истог нивоа независне једна од друге, те да се могу паралелно извршавати.

Тешкоће

Аутоматска паралелизација компајлерима или алатима је веома тешка из следећих разлога:^[6]

анализа зависности је тешка за код који користи индиректно адресирање, показиваче, рекурзију, или посредне функцијске позиве, јер је тешко открити такве зависности при компајлирању;
Петље имају непознат број итерација
приступ глобалним ресурсима се тешко може координирати у смислу алокације меморије, I/O, и заједничких променљивих;
нерегуларни алгоритми, који користе преусмерења која су зависна од уноса, ометају анализу при компајлирању и оптимизацији. ^[7]

Заобилазак

Због својствених потешкоћа остваривања потпуно аутоматске паралелизације, постоји неколико лакших приступа да би се добио паралелни програм вишег квалитета. Они су:

Дозволити програмерима да додају "савете" свијим програмима за вођење компајлерске паралелизације, као што су HPF за дистрибуирану меморију система и OpenMP или OpenHMPP за заједничку меморију система.
Градити интерактивни систем између програмера и паралелизационог алата/компајлера. Значајни примери су Pareon предузећа Vector Fabrics, SUIF Explorer (конмпајлер интермедијарног формата Станфордског универзитета), Поларис компајлер, и ПараВајс (формално КАПалати).
Хардверски подржана спекулативна вишенитна обрада.

Историјска паралелизација компајлера

Већина истраживања компајлера за аутоматску паралелизацију разматра Фортран програме, јер Фортран чини јаче гаранције о алијасу него језици као што су C. Типични примери су:

Парадигма компајлер
Поларис компајлер
Рајс Фортран компајлер D
СУИФ компајлер
Беш Фортран компајлер

Види још

Референце

^ "Yehezkael, Rafael (2000). „Experiments in Separating Computational Algorithm from Program Distribution and Communication”. Lecture Notes in Computer Science of Springer Verlag. 1947: 268—278. "
^ Fox, Geoffrey; Williams, Roy; Messina, Paul (1994). Parallel Computing Works!. Morgan Kaufmann. стр. 575,593. ISBN 978-1-55860-253-3.
^ Simone Campanoni, Timothy Jones, Glenn Holloway, Gu-Yeon Wei, David Brooks.
^ J Anantpur, R Govindarajan, Runtime dependence computation and execution of loops on heterogeneous systems[1] Архивирано на сајту Wayback Machine (6. октобар 2015)
^ X. Zhuang, A. E. Eichenberger, Y. Luo, Kevin O’Brien, Kathryn, Exploiting Parallelism with Dependence-Aware Scheduling
^ „Automatic parallelism and data dependency”. Архивирано из оригинала 14. 07. 2014. г. Приступљено 08. 01. 2016.
^ Rünger, Gudula (2006). „Parallel Programming Models for Irregular Algorithms”. Parallel Algorithms and Cluster Computing. 52: 3—23. doi:10.1007/3-540-33541-2_1.

[1] "Yehezkael, Rafael (2000). „Experiments in Separating Computational Algorithm from Program Distribution and Communication”. Lecture Notes in Computer Science of Springer Verlag. 1947: 268—278. "

[pcworks-2] Fox, Geoffrey; Williams, Roy; Messina, Paul (1994). Parallel Computing Works!. Morgan Kaufmann. стр. 575,593. ISBN 978-1-55860-253-3.

[3] Simone Campanoni, Timothy Jones, Glenn Holloway, Gu-Yeon Wei, David Brooks.

[4] J Anantpur, R Govindarajan, Runtime dependence computation and execution of loops on heterogeneous systems[1] Архивирано на сајту Wayback Machine (6. октобар 2015)

[5] X. Zhuang, A. E. Eichenberger, Y. Luo, Kevin O’Brien, Kathryn, Exploiting Parallelism with Dependence-Aware Scheduling

[6] „Automatic parallelism and data dependency”. Архивирано из оригинала 14. 07. 2014. г. Приступљено 08. 01. 2016.

[7] Rünger, Gudula (2006). „Parallel Programming Models for Irregular Algorithms”. Parallel Algorithms and Cluster Computing. 52: 3—23. doi:10.1007/3-540-33541-2_1.

[1]

[2]

[3]

[4]

[5]

[6]

[7]