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

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

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

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

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

Позадина

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

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

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

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

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

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

Графички приказ Амдаловог закона

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

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

$\lim _{P\to \infty }{\frac {1}{{\frac {1-\alpha }{P}}+\alpha }}={\frac {1}{\alpha }}$

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

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

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 услови, заједничко искључење, синхронизација и паралелно успоравање

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

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

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

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

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

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

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

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

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

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

Модели доследности

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

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

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

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

Флинова таксономија

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

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

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

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

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

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

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

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

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

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

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

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

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

Хардвер

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

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

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

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

Рачунарски системи користе кеш – мале, брзе меморије које су близу процесора и који садрже копије меморијских вредности. Паралелни системи имају тај проблем да ће можда у кеш меморији стајати погрешна копија неке вредности. Ови системи захтевају систем кохеренције кеша. 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-а, уместо од почетка.

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

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

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

Референце

^ Patterson and Hennessy, p. 748.
^ Culler et al. p. 15.
^ Пат, Јејл (април 2004). "The Microprocessor Ten Years From Now: What Are The Challenges, How Do We Meet Them? Архивирано 2008-04-14 на сајту Wayback Machine (wmv). Distinguished Lecturer talk at Carnegie Mellon University. Добављено 7. новембра 2007.

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

Rodriguez, C.; Villagra, M.; Baran, B. (29. 8. 2008). „Asynchronous team algorithms for Boolean Satisfiability”. Bio-Inspired Models of Network, Information and Computing Systems, 2007. Bionetics 2007. 2nd: 66—69. doi:10.1109/BIMNICS.2007.4610083.

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

Kredel, Heinz (2010). „Parallel and distributed Gröbner bases computation in JAS”. arXiv:1008.0011  .

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

[1] Patterson and Hennessy, p. 748.

[2] Culler et al. p. 15.

[3] Пат, Јејл (април 2004). "The Microprocessor Ten Years From Now: What Are The Challenges, How Do We Meet Them? Архивирано 2008-04-14 на сајту Wayback Machine (wmv). Distinguished Lecturer talk at Carnegie Mellon University. Добављено 7. новембра 2007.

[1]

[2]

[3]