thumb|300п|IBM-ов Блу Џин (енгл. Blue Gene) Паралелна обрада је облик рачунања у којем су многи прорачуни спроведени истовремено, а ради на принципу да се велики проблеми често могу поделити на мање, који се затим решавају истовремено („паралелно“). Постоји неколико различитих облика паралелног рачунарства: бит-ниво, ниво инструкција, података, и task паралелизам. Паралелизам се користи већ много година, углавном у рачунарству високих перформанси, али интересовање за њега је у последње време порасло због физичких ограничења које спречавају скалирање фреквенције. Како је потрошња енергије (а самим тим и роизводња топлоте) рачунара постала проблем у последњих неколико година, паралелно рачунарство је постало доминантна парадигма у рачунарској архитектури, углавном у облику вишејезграних процесора.

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

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

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

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

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

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

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

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

Амдалов закон и Густафсонов закон right|thumbnail|300п|Графички приказ Амдаловог закона

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

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

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

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

thumb|400px

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

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

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

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

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

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}- услови, заједничко искључење, синхронизација и паралелно успоравање Подзадаци у паралелном програму се често називају нитима. Неке паралелне рачунарске архитектуре користе мање, лагане верзије нити познатих као влакна (), док друге користе веће верзије познате као процеси. Међутим, „нити“ су опште прихваћене као општи израз за подзадатке. Нити често треба да ажурирају вредности променљивих које се деле између њих. Инструкције између два програма могу бити прошаране у било ком редоследу. На пример, размотрите следећи програм: Нит АНит Б1А: Читај промењиву П1Б: Читај промењиву П2А: Додај 1 на промењиву П2Б: Додај 1 на промењиву П3А: Пиши назад на промењиву П3Б: Пиши назад на промењиву П

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

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

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

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

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

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

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

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

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

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