Паралелно израчунавање

Из Википедије, слободне енциклопедије
Jump to navigation Jump to search

Паралелно израчунавање је облик рачунарства у коме се неколико прорачуна извршава током преклапања временског периодима-истовремено-уместо редом (један се заврши пре него што почне наредни). Ово је својство система, ово може бити индивидуални програм, рачунар или мрежа- постоји и посебна тачка извршење или "нит контроле" за свако израчунавање ("процеса"). Истовремено систем је онај где израчунавање може да напредује без чекања за све остале прорачуне да заврши-где више од једног прорачун може да напредује "у исто време".[1]

Као парадигма програмирања, истовремено рачунарство је облик модуларног програмирања, односно факторинг укупног рачунања у субцомпутатионс који се могу истовремено извршавати. Пионири у области рачунарства су Едсгер Дијкстра, Пер Бринцх Хансен, и C. А. Р Хоаре.

Увод[уреди]

Упоредно рачунарство је повезано, али се разликују од паралелног рачунарства, иако su ови концепти често збуњујући,[2][3]  и могу се описати као "више процеса извршавања у истом временском периоду". У паралелном рачунарству, извршење се буквално јавља у истом тренутку, на пример на одвојеним прерађивачима мулти-процесора машина, са циљем убрзавања израчунавања паралелног рачунарства јер је немогуће на једнојезграрном процесору, само као један рачун се може јавити у било ком тренутку (током било којег појединачног циклусу).[a]. Насупрот томе, истовремено рачунарство састоји се од процеса живота који се преклапају, али извршење се не мора десити у истом тренутку. Циљ је да се модел процеса у спољашњем свету које се дешава истовремено, као што више клијената приступа серверу у исто време. Структурирање софтверских система састоји се од више конкурентских, комуникациони делови могу бити корисни за борбу против комплексности, без обзира на то да ли ће се делови извршити паралелно.[4]

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

Паралелно израчунавање може се извршити паралелно,[2][5] Ben-Ari, Mordechai (2006).  на пример додељивање сваког процеса на посебан процесор или процесор језгра, или дистрибуира рачунање преко мреже, али генерално, језик, алати и технике за паралелно програмирање не може бити погодно за истовремено програмирање, и обрнуто.

Тачан тајминг када се извршавају задаци на систему истовремено зависи и од распореда и задаци не морају увек да буду истовремено извршени. На пример, с обзиром на два задатка, Т1 и Т2:

  • Т1 може се извршити и завршити пре Т2 или обрнуто (серијски и секвенцијални);
  • Т1 и Т2 могу бити наизменично извршени (серијски и конкурентно);
  • Т1 и Т2 могу се извршити истовремено у истом временском тренутку (паралелно и истовремено).

Реч "секвенцијално" се користи као супротна и за "истовремено" и "паралелно"; када се изричито разликује, истовремено / секвенцијално и паралелно / серијски се користе као супротни парови.[6] Распоред у којем се задаци извршавају један по један (серијски, не паралелизма), без преплитања (секуентуалли, нема конкуренцију: задатак не почиње док се претходни задатак не заврши) назива се серијски распоред. Скуп задатака који могу да се серијски закажу cу сериализабле, што поједностављује контролу конкуренције.

Координација приступа дељеним ресурсима[уреди]

Главни изазов у дизајнирању истовремених програма је контрола конкуренција: обезбеђује исправан редослед интеракција или комуникација између различитих рачунарских погубљења, и координира приступ ресурсима који се деле између погубљења.[5] Потенцијални проблеми су услови раса, застоја и ресурса глади. На пример, размотримо следеће алгоритме за прављење повлачења из текућег рачуна коју представљају заједнички биланс ресурса:

1 bool withdraw(int withdrawal)
2 {
3     if(balance >= withdrawal)
4     {
5         balance -= withdrawal;
6         return true;
7     } 
8     return false;
9 }

Претпоставимо да стање = 500, и два истовремена темена чине позивину поруку (300) и повлачење (350). Ако се линија 3 у обе операције извршава пре линије 5 обе операције ће да пронађу равнотежу >= повлачење вредност је тачна, а извршење ће наставити са одузимањем износа исплате. Међутим, пошто оба процеса извршавају своје повлачење, укупан износ повлачења ће завршити што је даље од првобитног биланса. Ове врсте проблема са дељеним ресурсима захтевају коришћење контроле конкуренција, или неблокирајући алгоритами.

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

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

Предности[уреди]

  • Повећана примена пропусно-паралелног извршење истовремених програма омогућава да се број задатака извршених у одређеном временском периоду повећа.
  • Високи одзив за улаз / излаз-улаз / излаз интензивне апликације углавном чекају улазне или излазне операције да се заврше. Истовремено програмирање омогућава времену које би се трошило да се користи за други задатак.
  • Више одговарајућих програмских структура-неких проблема и проблема домена су добро погодне за заступање и истовремених задатака или процеса.

Модели[уреди]

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

Имплементације[уреди]

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

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

У неким истовременим рачунарским системима, комуникација између истовремених компоненти је сакривена од програмера (на пример, помоћу будућности), док се у другима то мора експлицитно руковати. Експлицитне комуникација се могу поделити у две класе:

Заједничка меморија комуникације
Паралелне компоненте комуницирају мењањем садржаја заједничких меморијских локација (као на пример Јава и С #). Овај стил истовременог програмирања обично захтева примену неког облика закључавања (нпр мутекс, семафори, или монитора) да координира између нити. Програм који правилно спроводи било који од њих је безбедна нит.
Порука пролазности комуникација
Паралелне компоненте комуницирају разменом порука (као на пример Сцала, Ерлангова и Оkkам). Размена порука може се спровести асинхроно, или може користити синхрони "Рендезвоус" стил у коме се пошиљалац блокира док је порука примљена. Асинхрона порука пролазности може бити поуздана или непоуздана (понекад се назива "слање и молите"). Порука-пролази конкуренција тежи да много лакше размишља о односу схаред-меморије конкуренција, а обично се сматра више робустан облик истовременог програмирања. (Уреди) Разноврсност математичких теорија за поруке-пролазности система разумевања и анализирања су на располагању, укључујући глумца модела и разних процеса kалкулуса. Порука доношења се може ефикасно имплементирати на симетрични мултипроцесор, са или без заједничке кохерентне меморије.

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

Историја[уреди]

Упоредно рачунарство се развило из ранијег рада пруга и телеграфа, из 19. и почетком 20. века, а неки термини потичу из овог периода, као што је семафор. Настојао је да се позабави питањем како да рукује са више возова на истом железничком систему (избегавање судара и максималне ефикасности) и како да рукује на више преноса преко одређеног скупа жица (побољшање ефикасности), као што је време-Дивисион Мултиплекинг (1870с ).

Академске студије истовремених алгоритама су почеле 1960, Дијкстра (1965) је заслужан за први рад у овој области, идентификовање и решавање међусобног искључивања.[7]

Учесталост[уреди]

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

На нивоу програмског језика:

На нивоу оперативног система:

На нивоу мреже, умрежени системи су генерално истовремени по својој природи, јер се састоје од посебних уређаја.

Језици који га подржавају[уреди]

Паралелни програмски језици су програмски језици који користе језичке конструкције за конкуренцију. Ови конструкти могу да укључе мулти-тхреадинг, подршку са дистрибуираног рачунарства, порука пролази, заједничке ресурсе (укључујући дељене меморије) или будућности и обећања. Такви језици се понекад описују као паралелно оријентисани језици или паралелно оријентисано програмирање језика (ЦОПЛ).[8]

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

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

  • Ада - опште намене, уз подршку за поруке доношења и монитора на бази konkurencije
  • Алеф - конкурентно, са нитима и поруком у пролазу, за системско програмирање у раним верзијама План 9 из Белл Лабс
  • Алиса - проширење на Стандард МЛ, додаје подршку за конкуренцију преко будућности
  • Атеји ПX - проширење Јава са паралелним примитивцима инспирисаним од π-рачун
  • Акум - домен специфичан, истовремено, на основу Актер модела и . НЕТ Цоммон Лангуаге Рунтиме користећи C - као синтаксу
  • C++ - std::thread
  • Цω (Ц Омега) - за истраживања, простире C #, користи асинхрону комуникацију
  • C #, Подржава истовремено рачунарство од верзије 5.0 користећи браву, принос, асинхроне и чекају кључне речи
  • Цлојуре - модерна Лисп за ЈВМ
  • Истовремено чишћење - функционално програмирање, слично Хаскелу
  • Намед Колекције (ЦНЦ) - Ацхиевес имплицитно паралелизам независно од меморије модела експлицитно дефинише проток података и контроле
  • Истовремена Haskell - лењ, чист функционални језик ради истовремених процеса због дељења меморије
  • Истовремена МЛ - цонцуррент проширење Стандард МЛ
  • Истовремена Паскал - Пер Бринцх Хансен 
  • Кари 
  • D - више парадигма језичког система програмирања са експлицитном подршком за истовремено програмирање (глумац модел
  • Е - користи обећања да се не допусти застој 
  • ЕЦМАСцрипт - обећања која су доступна у различитим библиотекама, предложене за укључивање у стандарду у ЕЦМАСцрипт 6
  •  Ајфел - кроз СЦООП механизам на основу концепта пројекта по уговору 
  • Еликсир - динамична и функционална мета програмирања језика ради на Ерлангову ВМ. 
  • Ерланг-користи асинхрони поруку пролази без дељења 
  • ФАУСТ - у реалном времену функционалан, за обраду сигнала, преводилац омогућава аутоматску паралелизацију преко ОпенМП или одређеним радом - краде сцхедулер 
  • Фортран - цоарраис ће учинити сагласне део Фортран 2008 стандарда
  • Гоу - за системско програмирање, са конкурентским моделом програмирања на основу ЦСП
  • Хуме - функционални, истовремено, за ограничене за просторне и временске средине где аутомата процеси су описани од синхрони канала образаца и порука у пролазу 
  • Ио - глумац - основа конкуренције 
  • Јанус (програмски језик) - има различите аскерс и шалтере на логичким променљивима, баг канала; је чисто декларативан
  • ЈаваСкрипт - путем веб радника, у претраживачком окружењу, обећања, и цаллбацкс
  • ЈоЦамл - конкурентно и дистрибуирано канал на бази проширења ОЦамл, спроводи придружите рачуницу процеса Члан Јава конкурентно, на основу језика Јава 
  • Џул - датафлов - основа, комуницира поруком у пролазу 
  • Џојс - конкурентно, настава, изграђена на конкурентном Паскала са карактеристикама из СПР Пер Бринцх Хансен 
  • ЛабВИЕВ - графички, проток података, функције су чворови у графу, подаци жице између чворова; укључује објектно оријентисани језик 
  • Лимбо - рођак Алефа, за системско програмирање у Инферно (оперативни систем)
  • МултиЛисп - шема варијанти проширена тако да подржи паралелизам 
  • Модула - 2 - за програмирање система, Н. Вирт као наследник Пасцал уз подршку за цороутинес 
  • Модула - 3 - модераn члан Алгол породице са великим подршком за теме, мутекес, стање варијабле 
  • Невскуеак - за истраживање, са каналима као вредностиma прве класе; претходник Алеф 
  • Ноде.јс - сервер-страни рунтиме енвиронмент за ЈаваСцрипт 
  • Оццам утицајем тешко на комуницирање Секуентиал Процессес (ЦСП) 
    • Оццам - π - модерна варијанта Оццам, која укључује идеје из Милнер је π-рачуна
  • ОРЦ - веома конкурентно, недетерминистички, на основу Клинијева алгебра 
  • Оз - мултипарадигма, подржава заједничку државу и порукама у пролази конкуренцију и будућност 
  • ПараСаил - објектно оријентисано, паралелно, без показивача, трка услова 
  • Пицт - у суштини извршна примена Милнер је π-рачуна 
  • Перл са АниЕвент и Цоро 
  • Питон са Твистед, греенлет и гевент 
  • Реиа - користи асинхрону поруку пролази између дељивих - непостојећих објеката
  • Црвена / Систем - за систем програмирања, заснован на Ребол 
  • Руст - за програмирање система, фокусиран на масовној конкуренцији, користећи поруку у пролазу са променљиве семантике, заједничка непроменљива меморија, и подела променљиве меморије која је доказиво без расе услова.[9] 
  • САЛСА - глумац на основу знака додавања, придружи и првокласним наставцима за дистрибуирано рачунарство преко интернета 
  • Скала - опште намене, дизајнирани да изразе заједничке обрасце програмирања на концизан, елегантан, и тип - безбедан начин
  • СекуенцеЛ - опште намене функционални, главни циљеви дизајна су једноставност програмирања, код јасноћа - читљивост, и аутоматски паралелизација за наступ на мултицоре хардвер, а доказиво без трке услова 
  • СР - за истраживање 
  • Стацклесс Питхон 
  • СтратифиедЈС - комбинатор заснован на конкуренцији, на основу ЈаваСkрипт 
  • СуперПаскал - конкурентан, за наставу, изграђен на конкурентну Паскала и Јоице од  Пер Бринцх Хансена 
  • Уникон - за истраживање 
  • Термити Шема - аддс - Ерлангова као конкуренцију на шеми 
  • ТНСДЛ - за развој телекомуникационих размена, користи асинхрони Мессаге Пассинг 
  • ВХДЛ (ВХСИЦ Хардваре Опис Језик) - ИЕЕЕ СТД-1076 
  • - конкуренција - продужени подскуп језика, C развио XМОС, на основу Комуницирању Секуентиал процеса, уграђене конструкције за програмирање И / О

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

Види још[уреди]

Белешке[уреди]

  1. ^ This is discounting parallelism internal to a processor core, such as pipelining or vectorized instructions. A single-core, single-processor machine may be capable of some parallelism, such as with a coprocessor, but the processor itself is not.

Референце[уреди]

  1. ^ Operating System Concepts 9th edition, Abraham Silberschatz. "Chapter 4: Threads"
  2. 2,0 2,1 "Concurrency is not Parallelism", Waza conference Jan 11, 2012, Rob Pike (slides) (video)
  3. ^ „Parallelism vs. Concurrency”. Haskell Wiki. 
  4. ^ Schneider, Fred B. On Concurrent Programming. Springer. стр. 1. ISBN 9780387949420. 
  5. 5,0 5,1 Ben-Ari, Mordechai (2006). Principles of Concurrent and Distributed Programming (2nd изд.). Addison-Wesley. ISBN 978-0-321-31283-9. 
  6. ^ Patterson & Hennessy (2013). стр. 503.
  7. ^ „PODC Influential Paper Award: 2002”, ACM Symposium on Principles of Distributed Computing, Приступљено 24. 8. 2009 
  8. ^ Armstrong, Joe (2003). „Making reliable distributed systems in the presence of software errors”.  Недостаје или је празан параметар |url= (помоћ);
  9. ^ Blum, Ben (2012). „Typesafe Shared Mutable State”. Приступљено 14. 11. 2012. 

Литература[уреди]

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