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

Садржај обрисан Садржај додат

Инлајн

Верзија на датум 9. јануар 2016. у 00:00

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

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

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

.

Циклично многоструко-намотавање

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

Пипелинед мулти-тхреадинг

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

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

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

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

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

Тешкоће

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

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

Заобилазак

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

Дозволити програмерима да додају "савете " свијим програмима за вођење компајлера паралелизације, као што су ХПФ за дистрибуирану меморију система и ОтворенМП или ОтворенХМПП заједничку меморију система.
Градити интерактивни систем између програмера и паралелизације алата/компајлера. Значајни примери су Вектор тканине Пареон, СУИФ истраживач (Станфорд Универзитет Средњег Формата компајлера) Поларис компајлер, и ПараВајс (формално КАПалати) .
Хардвер подржан спекулативно Спмт .

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

Већина истраживања компајлера за аутоматску паралелизацију разматра Фортран програме ^{[citation needed]}] јер Фортран чини јаче гаранције о алијасу него језици као што су Ц. Типични примери су:

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

Белешке

^ Fox, Geoffrey; Roy Williams; Paul Messina (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.
^ „Automatic parallelism and data dependency”.
^ 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.

Види такође

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

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

[3] „Automatic parallelism and data dependency”.

[4] 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]