Паралелни алгоритам

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

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

Паралелност

Алгоритми се разликују по томе колико се могу паралелизовати, од алгоритама који се лако паралелизују до алгоритама који се не могу паралелизовати. Штавише, задати проблем се може прилагодити различитим алгоритмима , који могу бити лакше или теже паралелизовани.

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

Неки проблеми се не могу поделити у парелелне делове, јер захтевају резултате из претходног корака да би ефективно наставили са извршавањем следећег корака алгоритма - они се називају наследно серијски проблеми. Примери укључују итеративне нумеричке методе, као што је Њутнов метод, итеративна решења за проблем три тела, а већина од доступних алгоритама израчунавање броја Пи (π).

Мотивација

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

Проблеми

Комуникација

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

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

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

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

Балансирање оптерећењем

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

Расподењени алгоритми

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

Види још

• Паралелна обрада
• Систем са више агената
• Расподељено израчунавање
• Паралелизам података

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

• Designing and Building Parallel Programs page at the US Argonne National Laboratories
• Designing and Building Parallel Programs, by Ian Foster
• What makes parallel programming hard?