Паралелна обрада

Из Википедије, слободне енциклопедије
IBM-ов Блу Џин (енгл. Blue Gene)

Паралелна обрада је облик рачунања у којем су многи прорачуни спроведени истовремено, а ради на принципу да се велики проблеми често могу поделити на мање, који се затим решавају истовремено ("паралелно"). Постоји неколико различитих облика паралелног рачунарства: бит-ниво, ниво инструкција, података, и task паралелизам. Паралелизам се користи већ много година, углавном у рачунарству високих перформанси, али интересовање за њега је у последње време порасло због физичких ограничења које спречавају скалирање фреквенције. Како је потрошња енергије (а самим тим и роизводња топлоте) рачунара постала проблем у последњих неколико година, паралелно рачунарство је постало доминантна парадигма у рачунарској архитектури, углавном у облику вишејезграних процесора.

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

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

Максимална могућа брзина неког програма као резултат паралелизације је познат као Амдалов закон.

Позадина[уреди]

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

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

Фреквенцијско скалирање је био доминантан разлог за побољшање перформанси рачунара од средине 1980-их до 2004. Извршавања програма је једнако броју инструкција помножен просечним временом по инструкцији. Одржавање свега осталог константним и повећавајући фреквенцију такта смањује се просечно време које је потребно да се изврши инструкција. Повећање такта на тај начин смањује време рада за све програме са рачунањем.

Међутим, потрошња енергије по чипу је дат једначином P = C × V2 × F, где је P снага, C је капацитивност када се укључи по циклусу (сразмерно броју транзистора чији улаза се мења), V је напон, и F је такт. Повећање такта повећава количину енергије која се троши. Повећање потрошње енергије је коначно довело до тога да Интел маја 2004 откаже њених Техас и Џејхак процесоре, што се обично наводи као крај фреквенцијског скалирања као доминантне парадигме архитектуре рачунара.

Муров закон је емпиријско запажање да се густина транзистора у микропроцесору удвостручује сваких 18 до 24 месеци. Упркос проблемима потрошње енергије, и поновљених предвиђања његовог краја, Муров закон и даље на снази. Са завршетком фреквенцијског скалирања, ови додатни транзистори (који се више не користе за фреквенцијско скалирање) може да се користи за додавање додатни хардвер за паралелно рачунарство.

Амдалов закон и Густафсонов закон[уреди]

A graphical representation of Amdahl's law

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

Потенцијално убрзање алгоритма на паралелној платформи је по Амдаловом закону, кога је првобитно формулисао Џин Амдал 1960. Он наводи да ће мали део програма који се не може паралелизирати ограничити укупно убрзање при паралелизацији. Програм који решава велики математички или инжењерски проблем се обично састоји од неколико делова које је могуће паралелизирати и неколико делова које није могуће паралелизирати (узастопни делови). Ако је \alpha део времена рада које програм троши на делове који се не могу паралелизирати, онда:

\lim_{P\to\infty}\frac{1}{\frac{1-\alpha}{P}+\alpha} = \frac{1}{\alpha}

је максимално убрзање паралелизацијом програма. Ако секвенцијални део програма чини 10% од радног времена (\alpha=0.1), не може се добити више од 10 × убрзања, без обзира на то колико је процесора додато. Ово ставља горњу границу на корисност додавања више упоредних извршних јединица. „Када задатак не може бити расподељен због узастопних ограничења, примена вишег напора нема утицаја на распоред. Ношење детета траје девет месеци, без обзира на то колико жена носи децу."

Густафсонов закон је још један закон у рачунарству, блиско повезан са Амдаловим законом. Он наводи да је убрзање са P процесора:

Optimizing-different-parts.svg
 S(P) = P - \alpha(P-1) \qquad = \alpha + P(1-\alpha). \,

И Амдалов и Густафсонов закон претпостављају да је радно време секвенцијалног дела програма независно од броја процесора. Амдахлов закон претпоставља да је цео проблем фиксне величине, тако да је укупан износ посла који треба да се уради паралелно такође независан од броја процесора, док Густафсон закон претпоставља да укупан износ посла који треба да се уради паралелно варира линеарно са бројем процесора.

Зависности[уреди]

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

Нека су Пи и Пј два сегмента програма. Бернстајнови услови описују када су оне независне и када се могу извршити паралелно. За Пи, нека Ии буду све улазне променљиве а Ои, а исто тако за Пј.

  •  I_j \cap O_i = \varnothing, \,
  •  I_i \cap O_j = \varnothing, \,
  •  O_i \cap O_j = \varnothing. \,

Повреда првог услова уводи зависност протока, што одговара првом сегменту који производи резултат коришћен од другог сегмента. Други услов представља анти-зависност, када други сегмент (Пј) производи променљиву која је потребна првом сегменту (Пи). Трећи и последњи услов представља излазну зависност: када два сегмента пишу на истој локацији, резултат долази из последњег логички извршеног сегмента.

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

1: function Dep(a, b)
2: c := a•b
3: d := 3•c
4: end function

Операција 3 у Dep(a, b) не може да се изврши пре (или чак паралелно са) операцијом 2, јер операција 3 користи резултат из операције 2. То крши услов 1, и на тај начин уводи зависност у алгоритам.

1: function NoDep(a, b)
2: c := a•b
3: d := 3•b
4: e := a+b
5: end function

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

Race услови, заједничко искључење, синхронизација и паралелно успоравање[уреди]

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

Нит A Нит B
1A: Читај промењиву V 1B: Читај промењиву V
2A: Додај 1 на промењиву V 2B: Додај 1 на промењиву V
3A: Пиши назад на промењиву V 3B: Пиши назад на промењиву V

Ако се инструкција 1B обрађује од 1А и 3А, или ако је инструкција 1А обрађивана између 1B и 3B, програм ће избацити погрешне податке. Ово је познато као race случај. Програмер мора да користи закључавање за пружање међусобне искључивости. Брава је програмски језик направљена за омогућавање једној нити да преузму контролу над променљивом и спречи друге нити да чита или пише по њему, док променљива није откључана. Нит која држи закључавање је слободана да изврши своју критичну секцију (одељак програма који захтева искључиви приступ некој променљивој), и за откључавање података када се заврши. Дакле, да гарантује исправно извршавање програма, горњи програм се може написато поново да користи закључавање:

Нит A Нит B
1A: Закључај промењиву V 1B: Закључај промењиву V
2A: Читај промењиву V 2B: Читај промењиву V
3A: Додај 1 на промењиву V 3B: Додај 1 на промењиву V
4A: Пиши назад на промењиву V 4B: Пиши назад на промењиву V
5A: Откључај промењиву V 5B: Откључај промењиву V

Једна нит ће успешно закључати променљиву V, док друга нит бити закључана без могућности да се настави све док се поново V не откључа. Ово гарантује исправно извршење програма. Иако је потребно да обезбеди исправно извршавање програма, закљулавање може у великој мери да успори програм.

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

Многи паралелни програми захтевају да њихови подзадаци раде синхронизовано. Ово захтева коришћење баријере. Баријере су углавном имплементиране корситећи софтверско закључавање. Једна класа алгоритама, позната као lock-free и wait-free алгоритми, потпуно заобилази потребу за баријерама и закључавањем. Ипак овај приступ је тежак за имплементацију.

Не убрзају сви паралелизми. Генерално, кад се задатак подели на више нити, те нити троше све већи проценат свог времена комуницирајући међусобно. Евентуално, време комуницирања ће претећи време коришћено за решавање проблема, и даља паралелизација увећава уместо да умањи обим посла. Ово је познато као паралелно успорење.

Фини, груби и срамни паралелизам[уреди]

Апликације су обично класификоване по томе колико често њихови подзадаци морају да се синхронизују или да комуницирају. У случају да много пута комуницирају у секунди, то је фини паралелизам, ако комуницирају мало то је груби паралелизам, а ако ретко или никад не комуницирају то је срамни паралелизам. Најлакше је паралелизовати срамно паралелне апликације.

Модели доследности[уреди]

Паралелни програмски језици и паралелни рачунари морају имати модел доследности. Овај модел дефинише правила како се операције на рачунарској меморији дешавају и какви ће резултати бити.

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

Трансакциона софтверска меморија је чест тип модела доследности. СТМ узима концепт о атомским трансакцијама из теорије база података и примењује их на приступе меморији.

Математички, ови модели се могу представити на неколико начина. Петри нетс, који је уведен у докторској тези Карла Адама Петрија је био рани покушај да се кодују ови модели. Датафлоу је направио Датафлоу архитектуре по овом принципу са циљем да физички имплементира идеје од Датафлоу теорији. Почев од раних 1970, процесни рачун као што је рачун комуникационих система и процеси са секвенцијалним комуницирањем су развијени да омогуће алгебарско резоновање о системима састављених од интерагујућих компоненти. Скорашњи додаци овој фамилији рачуна као што је Пи рачун, су додали могућност за резоновање динамичких топологија.

Флинова таксономија[уреди]

Мајкл Флин је направио једну од најранијих класификационих система за паралелне или секвенцијалне рачунаре и програме, који се данас зове Флинова таксономија. Флин је класификовао рачунаре и програме по томе да ли су оперисали користећи један скуп или више скупова инструкција, и да ли су ти скупови користили један или више скупова података. Једна-инструкција-једни-подаци (СИСД) класификације је еквивалентна потпуно секвенцијалном програму. Једна-инструкција-више-података (СИМД) класификација је аналогна понављању једне операције преко великог скупа података. Ово се често ради у апликацијама обраде сигнала. Више инструкција једни подаци (МИСД) се ретко користи. Постоје архитектуре које користе ово али мало апликација је направљено. Више инструкција више података (МИМД) програми су најчешћи паралелни програми.

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

Типови паралелизма[уреди]

Паралелизам на нивоу бита[уреди]

Од доласка ВЛСИ производне технологије '70, убрзање се постизало тако што су се увећавале ширине комјутерске речи. Повећање величине речи смањује број инструкција које процесор мора да обради да би одррадио операцију на промењивим чије су величине веће од ширине речи. На пример, када 8-битни процесор треба да сабере 16-битне целе бројеве, он мора прво да сабере доњих 8 битова, па онда горњих 8 битова, тако да овом процесору требају два циклуса за сабирање, а 16-битном један.

Историјски, 4-битне процесоре су заменили 8-битни, њих 16-битни, а њих 32-битни. 32-битни процесори су били стандард две деценије. Тек су скоро 64-битни процесори постали нормална ствар.


Паралелизам на нивоу инструкције[уреди]

Канонски петофазни цевовод, РИСЦ машина (IF = Узимање инструкције, ID = Декодирање инструкције, EX = Извршавање, MEM = приступ меморији, WB = писање на регистар)

Рачунарски програм је у основи поток инструкција које извршава процесор. Ове инструкције се могу реорганизовати и комбиновати у групе које се онда паралелно извршавају без мењања исхода програма. Ово се зове паралелизам на нивоу инструкције. Напредак у овом виду паралелизма су доминирали рачунарском архитектуром од 1980их до 1990их.

Модерни процесори имају вишефазне инструкцијске цевоводе. Свака фаза у цевоводу одговара разлилитој акцији коју процесор извршава на тој инструкцији у тој фази. Канонски пример је РИСЦ процесор, са 5 фаза: донеси, декодирај, изврши, приступи меморији и пиши назад. Пентијум 4 је имао 35 фаза.

петофазни цевоводни суперскаларни процесор, способан да изврши две инструкције по циклусу. Може да има две инструкције у свакој фази цевовода, за укупно 10 инструкција (показано зелено) које се симултано извршавају.

Паралелизам на нивоу задатка[уреди]

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

Хардвер[уреди]

Меморија и комуникација[уреди]

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

Логички поглед на Non-Uniform Memory Access (NUMA) архитектуру. Процесори у једном директоријуму могу да приступе меморији тог директоријума са мање латенције него што могу да приступе меморији другог директоријума.

Рачунарске архитектуре у којима се сваки елемент главне меморије може приступити са једнаком латенцијом и пропусним опсегом се зову Приступи Унифомној Меморији (УМА). Типично се ово може постићи само у систему са дељеном меморијом. Систем који нема ову особину се зове Неуниформни Приступ Меморији (НУМА). Дистрибуирани меморијски системи имају неуниформни приступ меморији.

Рачунарски системи користе кеш – мале, брзе меморије које су близу процесора и који садрже копије меморијских вредности. Паралелни системи имају тај проблем да ће можда у кеш меморији стајати погрешна копија неке вредности. Ови системи захтевају систем кохеренције кеша. Bus snooping је једна од честих метода којом се води рачуна о вредностима у кешу.

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

Класе паралелних рачунара[уреди]

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

Вишејезграно рачунање[уреди]

Вишејезграни процесор је процесор који садржи више јединица обраде (језгара) на истом чипу. Ови процесори се разликују од суперскаларних процесора који могу да одраде више инструкција по циклусу из једне нити.

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

Симетрично микропроцесирање[уреди]

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

Дистрибуирано рачунарство[уреди]

Дистрибуиран рачунар (такође познат као distributed memory multiprocessor) је рачунарски систем са дистрибуираном меморијом у коме су елементи обрада повезан са мрежом. Дистрибуирани рачунари су веома скалабилни.

Софтвер[уреди]

Паралелни програмски језици[уреди]

Истовремени програмски језици, библиотеке, АПИ и паралелне модели програмирања (као што су алгоритамски костури) створени су за програмирање паралелних рачунара. Они се генерално могу поделити у класе на основу претпоставки које доносе о основној меморијској архитектура дељене меморије, дистрибуирања меморије, или дељене дистрибуиране меморије. Програмски језици заједничке меморије комуницирају манипулацијом дељене меморије променљиве. Дистрибуирана меморија користи message passing. POSIX Threads и OpenMP су два најшире коришћема АПИја са дељеном меморијом, док је Message Passing Interface најкоришћенији систем за прослеђивање порука. Један концепт који се користи у програмирању паралелних програма је концепт будућности, где је један део програма обећава да испоручи потребне податке другом делу програма у неком будућем времену.

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

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

Мејнстрим језици паралелног рачунања остају експлицитно паралелни или парцијално имплицитни, где програмер даје директиве за паралелизацију. Неколико потпуно имплицитних паралелних програмских језика постоје: SISAL, Parallel Haskell, System C (за FPGАе), Mitrion-C, VHDL, и Verilog.

Application checkpointing[уреди]

Док рачунарски систем расте што се комплексности тиче, просечно време између грешака се смањује. Application checkpointing је техника где рачунарски систем узима снимак апликације, све тренутне алокације ресусра и стања промењивих. Ови подаци ће се искористити ако рачуанрски систем пропадне. Application checkpointing значи да програм може да се рестартује од последњег checkpoint-а, уместо од почетка.

Алгоритамске методе[уреди]

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

  • Густа линеарна алгебра
  • Ретка линеарна алгебра
  • Спектралне методе
  • Проблем н-тела
  • Стурктурни проблеми мреже
  • Неструктурни проблеми мреже
  • Монтекарло симулација
  • Комбинациона логика
  • Динамичко програмирање
  • Траверсал графа
  • Графички модели
  • Симулација машине са коначним стањем

Даље читање[уреди]

Спољашње везе[уреди]