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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Типови паралелизма

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

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

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

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

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

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

Хардвер

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

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

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

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

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

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

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

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

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

Софтвер

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

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

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

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

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

Референце

Додатна литература

Додатна литература

Спољашње везе 

 Go Parallel: Translating Multicore Power into Application Performance
 
 Lawrence Livermore National Laboratory: Introduction to Parallel Computing
 Comparing programmability of Open MP and pthreads
 What makes parallel programming hard?
 Designing and Building Parallel Programs, by Ian Foster
 Internet Parallel Computing Archive
 Parallel processing topic area at IEEE Distributed Computing Online
 Parallel Computing Works Free On-line Book 
 Frontiers of Supercomputing Free On-line Book Covering topics like algorithms and industrial applications
 Universal Parallel Computing Research Center
 Course in Parallel Programming at Columbia University (in collaboration with IBM T.J Watson X10 project)
 Course in Parallel Computing at University of Wisconsin-Madison
 OpenHMPP, A New Standard for Manycore

Паралелна обрада
Програмске парадигме
Паралелна обрада је облик рачунања у којем су многи прорачуни спроведени истовремено , а ради на принципу да се велики проблеми често могу поделити на мање , који се затим решавају истовремено ( „ паралелно “ ) . Постоји неколико различитих облика паралелног рачунарства : бит-ниво , ниво инструкција , података , и task паралелизам . Паралелизам се користи већ много година , углавном у рачунарству високих перформанси , али интересовање за њега је у последње време порасло због физичких ограничења које спречавају скалирање фреквенције . Како је потрошња енергије ( а самим тим и роизводња топлоте ) рачунара постала проблем у последњих неколико година , паралелно рачунарство је постало доминантна парадигма у рачунарској архитектури , углавном у облику вишејезграних процесора . Паралелни рачунари се могу грубо класификовати према нивоу на којем хардвер подржава паралелизам : где вишејезграни и вишепроцесорски рачунари имају више елемената обраде унутар једне машине , а кластери , МППС и решетке користите више рачунара да раде на истом задатку . Специјализоване паралелне рачунарске архитектуре се понекад користе заједно са традиционалним процесорима , за убрзавање специфичних задатака . Теже је писати паралелне рачунарске програме него секвенцијалне , јер конкурентност уводи неколико нових класа потенцијалних софтверских грешака . Комуникација и синхронизација између различитих подзадатака су обично неке од највећих препрека за добијање добрих перформанси паралелног програма . Максимална могућа брзина неког програма као резултат паралелизације је познат као Амдалов закон . Позадина Традиционално , рачунарски софтвер је написан за серијско израчунавања . За решавање проблема , алгоритам је конструисан и реализован као серијски ток инструкција . Ове инструкције се извршавају на процесору на једном рачунару . Само једна инструкција може извршити у време након што се заврши претходна инструкција . Паралелно рачунарство , с друге стране , користи више елемената за обраду истовремено да реши проблем . Ово се постиже поделом проблема на независне делове , тако да сваки елемент обраде може да изврши свој део алгоритма истовремено са осталима . Елементи обрада могу бити разноврсни и обухватају ресурсе као што су рачунар са више процесора , неколико умрежених рачунара , специјализовани хардвер , или било коју њихову комбинацију . Фреквенцијско скалирање је био доминантан разлог за побољшање перформанси рачунара од срединеих до Извршавања програма је једнако броју инструкција помножен просечним временом по инструкцији . Одржавање свега осталог константним и повећавајући фреквенцију такта смањује се просечно време које је потребно да се изврши инструкција . Повећање такта на тај начин смањује време рада за све програме са рачунањем . Међутим , потрошња енергије по чипу је дата једначином -{ P = C × V2 × F }- , где је -{ P }- снага , -{ C }- је капацитивност када се укључи по циклусу ( сразмерно броју транзистора чији улаз се мења ) , -{ V }- је напон , и -{ F }- је такт . Повећање такта повећава количину енергије која се троши . Повећање потрошње енергије је коначно довело до тога да Интел мајаоткаже своје Тексас и Џејхак процесоре , што се обично наводи као крај фреквенцијског скалирања као доминантне парадигме архитектуре рачунара . Муров закон је емпиријско запажање да се густина транзистора у микропроцесору удвостручује свакихдомесеци . Упркос проблемима потрошње енергије , и поновљених предвиђања његовог краја , Муров закон и даље на снази . Са завршетком фреквенцијског скалирања , ови додатни транзистори ( који се више не користе за фреквенцијско скалирање ) могу да се користе за додавање додатног хардвера за паралелно рачунарство . Амдалов закон и Густафсонов закон Оптимално , убрзање услед паралелизације би било линеарно . Удвостручавање броја процесних елемената би требало да преполови време путовања , и то удвостручење други пут би требало да поново преполови време рада . Међутим , веома мали број паралелних алгоритама постигне оптимално убрзање . Већина њих има скоро линеарно убрзање за мали број процесних елемената , који се поравнава у константној вредности за велики број процесних елемената . Потенцијално убрзање алгоритма на паралелној платформи је по Амдаловом закону , који је првобитно формулисао Џин Амдал Он наводи да ће мали део програма који се не може паралелизирати ограничити укупно убрзање при паралелизацији . Програм који решава велики математички или инжењерски проблем се обично састоји од неколико делова које је могуће паралелизирати и неколико делова које није могуће паралелизирати ( узастопни делови ) . Ако је део времена рада које програм троши на делове који се не могу паралелизирати , онда : је максимално убрзање паралелизацијом програма . Ако секвенцијални део програма чини од радног времена ( ) , не може се добити више од× убрзања , без обзира на то колико је процесора додато . Ово ставља горњу границу на корисност додавања више упоредних извршних јединица . „ Када задатак не може бити расподељен због узастопних ограничења , примена вишег напора нема утицаја на распоред . Ношење детета траје девет месеци , без обзира на то колико жена носи децу . " Густафсонов закон је још један закон у рачунарству , блиско повезан са Амдаловим законом . Он наводи да је убрзање са процесора : И Амдалов и Густафсонов закон претпостављају да је радно време секвенцијалног дела програма независно од броја процесора . Амдалов закон претпоставља да је цео проблем фиксне величине , тако да је укупан износ посла који треба да се уради паралелно такође независан од броја процесора , док Густафсон закон претпоставља да укупан износ посла који треба да се уради паралелно варира линеарно са бројем процесора . Зависности Разумевање зависности података је кључно у спровођењу паралелних алгоритама . Ниједан програм не може да ради брже од најдужег ланца зависних прорачуна ( познат као критичан пут ) , јер се калкулације које зависе од претходних калкулација у ланцу морају извршити по реду . Међутим , већина алгоритама се не састоји само од дугог ланца зависних прорачуна , већ обично постоје могућности да се изврши независно рачунање паралелно . Нека су Пи и Пј два сегмента програма . Бернстајнови услови описују када су оне независне и када се могу извршити паралелно . За Пи , нека Ии буду све улазне променљиве а Ои , а исто тако за Пј . Повреда првог услова уводи зависност протока , што одговара првом сегменту који производи резултат коришћен од другог сегмента . Други услов представља анти-зависност , када други сегмент ( Пј ) производи променљиву која је потребна првом сегменту ( Пи ) . Трећи и последњи услов представља излазну зависност : када два сегмента пишу на истој локацији , резултат долази из последњег логички извршеног сегмента . Размотрите следеће функције које показују неколико врста зависности : function Dep( a , b ) c \ := a •b d\:=c end function Операцијау Dep( a , b ) не може да се изврши пре ( или чак паралелно са ) операцијом јер операцијакористи резултат из операције То крши услов и на тај начин уводи зависност у алгоритам. function NoDep( a , b ) c \ := a •b d\:=b e \ := a+b end function У овом примеру , не постоје зависности између инструкција , тако да сви они могу бити извршени паралелно . Бернстајнови услови не дозвољавају да се меморија дели између различитих процеса . Због тога је неопходно неко средство за синхронизацију између адреса , као што су семафоре , баријере или нека друга метода синхронизације. -{ Race }- услови , заједничко искључење , синхронизација и паралелно успоравање Подзадаци у паралелном програму се често називају нитима . Неке паралелне рачунарске архитектуре користе мање , лагане верзије нити познатих као влакна ( ) , док друге користе веће верзије познате као процеси . Међутим , „ нити “ су опште прихваћене као општи израз за подзадатке . Нити често треба да ажурирају вредности променљивих које се деле између њих . Инструкције између два програма могу бити прошаране у било ком редоследу . На пример , размотрите следећи програм : Ако се инструкција обрађује између и , или ако је инструкција обрађивана између и , програм ће израчунати погрешне резултате . Ово је познато као -{ race }- случај . Програмер мора да користи закључавање за пружање међусобне искључивости . Брава је конструкт програмског језика , направљен за омогућавање једној нити да преузму контролу над променљивом и спречи друге нити да читају или пишу по њој , док променљива не буде откључана . Нит која држи закључавање је слободана да изврши своју критичну секцију ( одељак програма који захтева искључиви приступ некој променљивој ) , и за откључавање података када се заврши . Дакле , да гарантује исправно извршавање програма , горњи програм се може написати поново тако да користи закључавање : Једна нит ће успешно закључати променљиву П , док друга нит бити блокирана без могућности да се настави све док се поново П не откључа . Ово гарантује исправно извршење програма . Иако је неопходно да би обезбедило исправно извршавање програма , закључавање може у великој мери да успори програм . Закључавање више променљивих користећи не-атомично закључавање уводи могућност застоја програма . Атомично закључавање закључава више променљивих одједном . Ако их не може закључати , не закључава ниједну . Ако од две нити свака треба да се закључа исте две промењиве користећи неатомично закључивање , могуће је да ће једна нит блокирати једну а друга другу промењиву . У том случају , ниједна нит не може да се заврши . Многи паралелни програми захтевају да њихови подзадаци раде синхронизовано . Ово захтева коришћење баријере . Баријере су углавном имплементиране користећи софтверско закључавање . Једна класа алгоритама , позната као -{ lock-free }- и -{ wait-free }- алгоритми , потпуно заобилази потребу за баријерама и закључавањем . Ипак овај приступ је тежак за имплементацију . Не убрзају сви паралелизми . Генерално , кад се задатак подели на више нити , те нити троше све већи проценат свог времена комуницирајући међусобно . У случају довољно великог броја нити , време комуницирања ће постати веће од времена коришћеног за решавање проблема , и даља паралелизација увећава уместо да умањи обим посла . Ово је познато као паралелно успорење . Фини , груби и срамни паралелизам Апликације су обично класификоване по томе колико често њихови подзадаци морају да се синхронизују или да комуницирају . У случају да много пута комуницирају у секунди , то је фини паралелизам , ако комуницирају мало то је груби паралелизам , а ако ретко или никад не комуницирају то је срамни паралелизам . Најлакше је паралелизовати срамно паралелне апликације . Модели доследности Паралелни програмски језици и паралелни рачунари морају имати модел доследности . Овај модел дефинише правила како се операције на рачунарској меморији дешавају и какви ће резултати бити . Један од првих модела је био Лели Лемортов секвенцијални модел . Секвенцијална доследност је особина паралелног програма да паралелно извршавање има исти резултат као и секвенцијални програм . Програм је секвенцијално доследан ако су резултати једног извршења исти као да су операције свих процесора извршене у неком редоследу , и операције сваког појединачног процесора појављују у овом редоследу по редоследу одређен својим програмом . Трансакциона софтверска меморија је чест тип модела доследности . СТМ узима концепт атомичних трансакција из теорије база података и примењује их на приступе меморији . Математички , ови модели се могу представити на неколико начина . Петријеве мреже , уведене у докторској тези Карла Адама Петрија су биле рани покушај да се кодификују ови модели . Датафлоу је направио Датафлоу архитектуру по овом принципу са циљем да физички имплементира идеје од Датафлоу теорији . Почев одд почетка процесни рачун као што је рачун комуникационих система и процеси са секвенцијалним комуницирањем су развијени да омогуће алгебарско резоновање о системима састављеним од интерреагујућих компоненти . Скорашњи додаци овој фамилији рачуна као што је Пи рачун , су додали могућност за резоновање динамичких топологија . Флинова таксономија Мајкл Флин је направио један од најранијих класификационих система за паралелне или секвенцијалне рачунаре и програме , који се данас зове Флинова таксономија . Флин је класификовао рачунаре и програме по томе да ли су оперисали користећи један скуп или више скупова инструкција , и да ли су ти скупови користили један или више скупова података . Једна-инструкција-једни-подаци ( СИСД ) класификација је еквивалентна потпуно секвенцијалном програму . Једна-инструкција-више-података ( СИМД ) класификација је аналогна понављању једне операције над великим скупом података . Ово се често ради у апликацијама обраде сигнала . Више инструкција једни подаци ( МИСД ) се ретко користи . Постоје архитектуре које користе ово али мало апликација је направљено . Више инструкција више података ( МИМД ) програми су најчешћи паралелни програми . Према Дејвиду Патерсону и Џону Хенесију , „ неке машине су хибриди ових категорија , али овај класични модел је преживео зато што је једноставан , лак за разумевање , и даје добре апроксимације . Такође је најчешће коришћена шема можда због лаког разумевања . “ Типови паралелизма Паралелизам на нивоу бита Од појаве ВЛСИ производне технологијеих , убрзање се постизало тако што су се увећавале ширине рачунарске речи . Повећање величине речи смањује број инструкција које процесор мора да обради да би одррадио операцију над промењивим чије су величине веће од ширине речи . На пример , кадабитни процесор треба да саберебитне целе бројеве , он мора прво да сабере доњихбитова , па онда горњихбитова , тако да овом процесору требају два циклуса за сабирање , абитном један . Историјски,битне процесоре су заменилибитни , њихбитни , а њихбитни.битни процесори су били стандард две деценије . Тек су скоробитни процесори постали уобичајени . Паралелизам на нивоу инструкције Рачунарски програм је у основи ток инструкција које извршава процесор . Ове инструкције се могу реорганизовати и комбиновати у групе које се онда паралелно извршавају без мењања исхода програма . Ово се зове паралелизам на нивоу инструкције . Напредак у овом виду паралелизма су доминирали рачунарском архитектуром одих доих . Модерни процесори имају вишефазне инструкцијске цевоводе . Свака фаза у цевоводу одговара различитој акцији коју процесор извршава на тој инструкцији у тој фази . Канонски пример је РИСЦ процесор , сафаза : донеси , декодирај , изврши , приступи меморији и пиши назад . Пентијумје имаофаза . Паралелизам на нивоу задатка Паралелизам на нивоу задатка је карактеристика паралелних програма где се потпуно другачије калкулације могу извршити на или истим или различитим скуповима података . Паралелизам на нивоу задатка се обично не скалира са величином проблема . Хардвер Меморија и комуникација Главна меморија у паралелном рачунару је или дељена меморија или дистрибуирана меморија . Дистрибуирана меморија подразумева да је меморија логички дистрибуирана , али често имлицира да је и физички дистрибуирана . Дистрибуирана дељена меморија и меморија виртуелизације комбинују ова два приступа где процесни елемент има своју локалну меморију и приступ меморији на нелокалним процесорима . Приступ локалној меморији је обично бржи од приступа нелокалној меморији . Рачунарске архитектуре у којима се сваки елемент главне меморије може приступити са једнаком латенцијом и пропусним опсегом се зову униформни приступ меморији ( УМА ) . Типично се ово може постићи само у систему са дељеном меморијом . Систем који нема ову особину се зове неуниформни приступ меморији ( НУМА ) . Дистрибуирани меморијски системи имају неуниформни приступ меморији . Рачунарски системи користе кеш – мале , брзе меморије које су близу процесора и који садрже копије меморијских вредности . Паралелни системи имају тај проблем да ће можда у кеш меморији стајати погрешна копија неке вредности . Ови системи захтевају систем кохеренције кеша. -{ Bus snooping }- је једна од честих метода којом се води рачуна о вредностима у кешу . Комуникација процесор – процесор и процесор – меморија се може имплементирати хардверски на неколико начина укључујући преко дељене меморије , дељеног буса , или -{ crossbar }- прекидача . Класе паралелних рачунара Паралелни рачунари на бази повезаних мрежа морају да имају неку врсту рутирања да би омогућили пролазак порука кроз чворове који нису директно повезани . Они нису међусобно ексклузивни . На пример групе симетричних процесора су релативно честе . Вишејезграно рачунање Вишејезграни процесор је процесор који садржи више јединица обраде ( језгара ) на истом чипу . Ови процесори се разликују од суперскаларних процесора који могу да одраде више инструкција по циклусу из једне нити . Свако језгро може потенцијално бити и суперскалар . Сваког циклуса , свако језгро може пустити више инструкција из једног тока инструкција . Симултано вишенитно обрађивање је прва форма идеје вишејазграних процесора . Симетрично микропроцесирање Симетрични микропроцесор је рачунарски систем са више идентичних процесора који деле меморију и повезани су бусом . Засићење буса спречава скалирање архитектуре буса . Као резултат СМПи генерално не садрже више одпроцесора . Дистрибуирано рачунарство Дистрибуиран рачунар ( такође познат као мултипроцесор са дистрибуираном меморијом ) је рачунарски систем са дистрибуираном меморијом у коме су елементи обрада повезан са мрежом . Дистрибуирани рачунари су веома скалабилни . Софтвер Паралелни програмски језици Истовремени програмски језици , библиотеке , АПИ и паралелни модели програмирања ( као што су алгоритамски костури ) створени су за програмирање паралелних рачунара . Они се генерално могу поделити у класе на основу претпоставки које доносе о основној меморијској архитектура дељене меморије , дистрибуирања меморије , или дељене дистрибуиране меморије . Програмски језици заједничке меморије комуницирају манипулацијом дељене меморије променљиве . Дистрибуирана меморија користи прослеђивање порука. -{ POSIX Threads }- и -{ OpenMP }- су два најшире коришћема АПИја са дељеном меморијом , док је -{ Message Passing Interface }- најкоришћенији систем за прослеђивање порука . Један концепт који се користи у програмирању паралелних програма је концепт „ фјучера “ , где је један део програма „ обећава “ да ће испоручити потребне податке другом делу програма у неком будућем времену . Аутоматска паралелизација Аутоматска паралелизација секвенцијалног програма од стране компајлера је свети грал у паралелном рачунарству . Упркос деценијама рада на овоме , није било много успеха . Мејнстрим језици паралелног рачунања остају експлицитно паралелни или парцијално имплицитни , где програмер даје директиве за паралелизацију . Неколико потпуно имплицитних паралелних програмских језика постоје : -{ SISAL }- , -{ Parallel Haskell }- , -{ System C }- ( за -{ FPGA } -е ) , -{ Mitrion-C }- , -{ VHDL }- , и -{ Verilog }- . Application checkpointing Док рачунарски систем расте што се комплексности тиче , просечно време између грешака се смањује . Application checkpointing је техника где рачунарски систем узима снимак апликације , све тренутне алокације ресусра и стања промењивих . Ови подаци ће се искористити ако рачуанрски систем пропадне . Application checkpointing значи да програм може да се рестартује од последњег checkpoint-а , уместо од почетка . Алгоритамске методе Како паралелни рачунари постају већи и бржи , постаје могуће да реше проблеме који су се раније предуго решавали . Паралелно рачунарство се користи у широком спектру области , од биоинформатике ( савијање протеина и анализе секвенци ) до економије ( математичке финансије ) . Уобичајене врсте проблема које се налазе у паралелним рачунарским апликацијама су : Густа линеарна алгебра Ретка линеарна алгебра Спектралне методе Проблем н-тела Стурктурни проблеми мреже Неструктурни проблеми мреже Монтекарло симулација Комбинаторна логика Динамичко програмирање Пролазак графа Графички модели Симулација машине са коначним стањем Референце Додатна литература Додатна литература Спољашње везе Go Parallel : Translating Multicore Power into Application Performance Lawrence Livermore National Laboratory : Introduction to Parallel Computing Comparing programmability of Open MP and pthreads What makes parallel programming hard ? Designing and Building Parallel Programs , by Ian Foster Internet Parallel Computing Archive Parallel processing topic area at IEEE Distributed Computing Online Parallel Computing Works Free On-line Book Frontiers of Supercomputing Free On-line Book Covering topics like algorithms and industrial applications Universal Parallel Computing Research Center Course in Parallel Programming at Columbia University ( in collaboration with IBM T.J Watson X10 project ) Course in Parallel Computing at University of Wisconsin-Madison OpenHMPP , A New Standard for Manycore Паралелна обрада Програмске парадигме