Paralelno izračunavanje

Paralelno izračunavanje je oblik računarstva u kome se nekoliko proračuna izvršava tokom preklapanja vremenskog periodima-istovremeno-umesto redom (jedan se završi pre nego što počne naredni). Ovo je svojstvo sistema, ovo može biti individualni program, računar ili mreža- postoji i posebna tačka izvršenje ili "nit kontrole" za svako izračunavanje ("procesa"). Istovremeno sistem je onaj gde izračunavanje može da napreduje bez čekanja za sve ostale proračune da završi-gde više od jednog proračun može da napreduje "u isto vreme".

Kao paradigma programiranja, istovremeno računarstvo je oblik modularnog programiranja, odnosno faktoring ukupnog računanja u subcomputations koji se mogu istovremeno izvršavati. Pioniri u oblasti računarstva su Edsger Dajkstra, Per Brinch Hansen, i C. A. R Hoare.

Uvod

Uporedno računarstvo je povezano, ali se razlikuju od paralelnog računarstva, iako su ovi koncepti često zbunjujući,  i mogu se opisati kao "više procesa izvršavanja u istom vremenskom periodu". U paralelnom računarstvu, izvršenje se bukvalno javlja u istom trenutku, na primer na odvojenim prerađivačima multi-procesora mašina, sa ciljem ubrzavanja izračunavanja paralelnog računarstva jer je nemoguće na jednojezgrarnom procesoru, samo kao jedan račun se može javiti u bilo kom trenutku (tokom bilo kojeg pojedinačnog ciklusu).. Nasuprot tome, istovremeno računarstvo sastoji se od procesa života koji se preklapaju, ali izvršenje se ne mora desiti u istom trenutku. Cilj je da se model procesa u spoljašnjem svetu koje se dešava istovremeno, kao što više klijenata pristupa serveru u isto vreme. Strukturiranje softverskih sistema sastoji se od više konkurentskih, komunikacioni delovi mogu biti korisni za borbu protiv kompleksnosti, bez obzira na to da li će se delovi izvršiti paralelno.

Na primer, istovremeni procesi mogu biti pogubljeni na jednom jezgru interleaving prilikom izvršavanja koraka svakog procesa preko vremenskih krugova:, samo jedan proces radi na vreme, a ako se to ne završi tokom vremena kruga, zastao je, drugi proces počinje ili se nastavlja, a kasnije originalni proces se nastavlja. Na taj način više procesa se izvršava u jednom trenutku, ali samo jedan proces se izvršava u tom trenutku.

Paralelno izračunavanje može se izvršiti paralelno, Ben-Ari, Mordechai (2006).  na primer dodeljivanje svakog procesa na poseban procesor ili procesor jezgra, ili distribuira računanje preko mreže, ali generalno, jezik, alati i tehnike za paralelno programiranje ne može biti pogodno za istovremeno programiranje, i obrnuto.

Tačan tajming kada se izvršavaju zadaci na sistemu istovremeno zavisi i od rasporeda i zadaci ne moraju uvek da budu istovremeno izvršeni. Na primer, s obzirom na dva zadatka, T1 i T2:

• T1 može se izvršiti i završiti pre T2 ili obrnuto (serijski i sekvencijalni);
• T1 i T2 mogu biti naizmenično izvršeni (serijski i konkurentno);
• T1 i T2 mogu se izvršiti istovremeno u istom vremenskom trenutku (paralelno i istovremeno).

Reč "sekvencijalno" se koristi kao suprotna i za "istovremeno" i "paralelno"; kada se izričito razlikuje, istovremeno / sekvencijalno i paralelno / serijski se koriste kao suprotni parovi. Raspored u kojem se zadaci izvršavaju jedan po jedan (serijski, ne paralelizma), bez preplitanja (sekuentualli, nema konkurenciju: zadatak ne počinje dok se prethodni zadatak ne završi) naziva se serijski raspored. Skup zadataka koji mogu da se serijski zakažu cu serializable, što pojednostavljuje kontrolu konkurencije.

Koordinacija pristupa deljenim resursima

Glavni izazov u dizajniranju istovremenih programa je kontrola konkurencija: obezbeđuje ispravan redosled interakcija ili komunikacija između različitih računarskih pogubljenja, i koordinira pristup resursima koji se dele između pogubljenja. Potencijalni problemi su uslovi rasa, zastoja i resursa gladi. Na primer, razmotrimo sledeće algoritme za pravljenje povlačenja iz tekućeg računa koju predstavljaju zajednički биланс resursa:

bool withdraw(int withdrawal)
{
    if(balance >= withdrawal)
    {
        balance -= withdrawal;
        return true;
    } 
    return false;
}

Pretpostavimo da стање = 500, i dva istovremena temena čine pozivinu поруку (300) i повлачење (350). Ako se linija 3 u obe operacije izvršava pre linije 5 obe operacije će da pronađu равнотежу >= повлачење vrednost je tačna, a izvršenje će nastaviti sa oduzimanjem iznosa isplate. Međutim, pošto oba procesa izvršavaju svoje povlačenje, ukupan iznos povlačenja će završiti što je dalje od prvobitnog bilansa. Ove vrste problema sa deljenim resursima zahtevaju korišćenje kontrole konkurencija, ili neblokirajući algoritami.

Zbog istovremenih sistema se oslanjaju na korišćenje zajedničkih resursa (uključujući komunikacione medije), istovremeno računarstvo uopšteno zahteva upotrebu nekog oblika arbitra koji negde u implementaciji posreduje pristup tim resursima.

Nažalost, dok mnoga rešenja postoje za problem sukoba oko jednog resursa, mnoge od tih "rešenja" imaju svoje konkurentne probleme kao kod zastoja kada je uključeno više od jednog resursa.

Prednosti

• Povećana primena propusno-paralelnog izvršenje istovremenih programa omogućava da se broj zadataka izvršenih u određenom vremenskom periodu poveća.
• Visoki odziv za ulaz / izlaz-ulaz / izlaz intenzivne aplikacije uglavnom čekaju ulazne ili izlazne operacije da se završe. Istovremeno programiranje omogućava vremenu koje bi se trošilo da se koristi za drugi zadatak.
• Više odgovarajućih programskih struktura-nekih problema i problema domena su dobro pogodne za zastupanje i istovremenih zadataka ili procesa.

Modeli

Postoji nekoliko modela istovremenog računarstva, koji se mogu koristiti da shvate i analiziraju istovremene sisteme. Ovi modeli obuhvataju:

• Glumac Model
  • Objekat-mogućnost modela za bezbednost
• Petri mreže
• Procesi računanja kao što su
  • Ambient račun
  • Račun komunikaciskih sistema (KZS)
  • Komunikacija Sekuential procesa (SPRS)
  • π-račun
  • Pridružite-račun
• Ulaz / izlaz automat

Implementacije

Veliki broj različitih metoda može da se koristi za implementaciju istovremenih programa, kao što je sprovođenje svakog računarskog izvršenja kao proces operativnog sistema, ili implementacije računarskih procesa kao skup niti u jednom procesu operativnog sistema.

Interakcija i komunikacija

U nekim istovremenim računarskim sistemima, komunikacija između istovremenih komponenti je sakrivena od programera (na primer, pomoću budućnosti), dok se u drugima to mora eksplicitno rukovati. Eksplicitne komunikacija se mogu podeliti u dve klase:

Zajednička memorija komunikacije

Paralelne komponente komuniciraju menjanjem sadržaja zajedničkih memorijskih lokacija (kao na primer Java i S #). Ovaj stil istovremenog programiranja obično zahteva primenu nekog oblika zaključavanja (npr muteks, semafori, ili monitora) da koordinira između niti. Program koji pravilno sprovodi bilo koji od njih je bezbedna nit.

Poruka prolaznosti komunikacija

Paralelne komponente komuniciraju razmenom poruka (kao na primer Scala, Erlangova i Okkam). Razmena poruka može se sprovesti asinhrono, ili može koristiti sinhroni "Rendezvous" stil u kome se pošiljalac blokira dok je poruka primljena. Asinhrona poruka prolaznosti može biti pouzdana ili nepouzdana (ponekad se naziva "slanje i molite"). Poruka-prolazi konkurencija teži da mnogo lakše razmišlja o odnosu shared-memorije konkurencija, a obično se smatra više robustan oblik istovremenog programiranja. ^(Uredi) Raznovrsnost matematičkih teorija za poruke-prolaznosti sistema razumevanja i analiziranja su na raspolaganju, uključujući glumca modela i raznih procesa kalkulusa. Poruka donošenja se može efikasno implementirati na simetrični multiprocesor, sa zajedničkom koherentnom memorijom ili bez nje.

Zajednička memorija i poruka prolaznosti konkurencije imaju različite karakteristike performansi. Tipično (mada ne uvek), per-procesu memorija iznad i zadatak prebacivanja preopterećenja je niža u poruci prolaznosti sistema, ali iznad za poruke prolaznosti sama je veća nego za procedure poziva. Ove razlike su često preplavljene od drugih faktora učinka.

Istorija

Uporedno računarstvo se razvilo iz ranijeg rada pruga i telegrafa, iz 19. i početkom 20. veka, a neki termini potiču iz ovog perioda, kao što je semafor. Nastojao je da se pozabavi pitanjem kako da rukuje sa više vozova na istom železničkom sistemu (izbegavanje sudara i maksimalne efikasnosti) i kako da rukuje na više prenosa preko određenog skupa žica (poboljšanje efikasnosti), kao što je vreme-Division Multipleking (1870s ).

Akademske studije istovremenih algoritama su počele 1960, Dijkstra (1965) je zaslužan za prvi rad u ovoj oblasti, identifikovanje i rešavanje međusobnog isključivanja.

Učestalost

Paralelnost je sveprisutna u računarstvu, javlja se iz niskog nivoa hardvera na jednom čipu na svetskim mrežama. Primeri.

Na nivou programskog jezika:

• Kanal
• Coroutine
• Budućnost i obećanja

Na nivou operativnog sistema:

• Računar multitasking, uključuje oba zadružni multitasking i preventivni multitasking
  • Vreme deljenje, koje je zamenio sekvencijalnu seriju procesiranja poslova sa istovremenim korišćenjem sistema
• Proces
• Navoj

Na nivou mreže, umreženi sistemi su generalno istovremeni po svojoj prirodi, jer se sastoje od posebnih uređaja.

Jezici koji ga podržavaju

Paralelni programski jezici su programski jezici koji koriste jezičke konstrukcije za konkurenciju. Ovi konstrukti mogu da uključe multi-threading, podršku sa distribuiranog računarstva, poruka prolazi, zajedničke resurse (uključujući deljene memorije) ili budućnosti i obećanja. Takvi jezici se ponekad opisuju kao paralelno orijentisani jezici ili paralelno orijentisano programiranje jezika (COPL).

Danas, najčešće korišćeni programski jezici koji imaju specifične konstrukcije za konkurenciju su Java i S #. Oba ova jezika u osnovi koriste deljene memorije konkurencijskih modela, sa zaključavanjem i obezbeđivanjem od monitora (mada modeli Message-prolazu mogu i sprovedeni na vrhu osnovi deljene memorije modela). Od jezika koji koriste porukeu prolaska konkurenciju modela, Erlangova se verovatno najviše koristi u industriji u ovom trenutku. ^(Uredi)

Mnogi istovremeni programski jezici su razvijeni više kao istraživački jezici (npr Pict) nego kao jezici za proizvodne svrhe. Međutim, jezici, kao što su Erlang, Limbo, i Okkam vode u industrijskoj upotrebi u različitim vremenskim periodima u poslednjih 20 godina. Jezici na kojima konkurencija ima važnu ulogu uključuje:

• Ada - opšte namene, uz podršku za poruke donošenja i monitora na bazi konkurencije
• Alef - konkurentno, sa nitima i porukom u prolazu, za sistemsko programiranje u ranim verzijama Plan 9 iz Bell Labs
• Alisa - proširenje na Standard ML, dodaje podršku za konkurenciju preko budućnosti
• Ateji PX - proširenje Java sa paralelnim primitivcima inspirisanim od π-račun
• Akum - domen specifičan, istovremeno, na osnovu Akter modela i . NET Common Language Runtime koristeći C - kao sintaksu
• C++ - std::thread
• Cω (C Omega) - za istraživanja, prostire C #, koristi asinhronu komunikaciju
• C #, Podržava istovremeno računarstvo od verzije 5.0 koristeći bravu, prinos, asinhrone i čekaju ključne reči
• Clojure - moderna Lisp za JVM
• Istovremeno čišćenje - funkcionalno programiranje, slično Haskelu
• Named Kolekcije (CNC) - Achieves implicitno paralelizam nezavisno od memorije modela eksplicitno definiše protok podataka i kontrole
• Istovremena Haskell - lenj, čist funkcionalni jezik radi istovremenih procesa zbog deljenja memorije
• Istovremena ML - concurrent proširenje Standard ML
• Istovremena Paskal - Per Brinch Hansen 
• Kari 
• D - više paradigma jezičkog sistema programiranja sa eksplicitnom podrškom za istovremeno programiranje (glumac model) 
• E - koristi obećanja da se ne dopusti zastoj 
• ECMAScript - obećanja koja su dostupna u različitim bibliotekama, predložene za uključivanje u standardu u ECMAScript 6
•  Ajfel - kroz SCOOP mehanizam na osnovu koncepta projekta po ugovoru 
• Eliksir - dinamična i funkcionalna meta programiranja jezika radi na Erlangovu VM. 
• Erlang-koristi asinhroni poruku prolazi bez deljenja 
• FAUST - u realnom vremenu funkcionalan, za obradu signala, prevodilac omogućava automatsku paralelizaciju preko OpenMP ili određenim radom - krade scheduler 
• Fortran - coarrais će učiniti saglasne deo Fortran 2008 standarda
• Gou - za sistemsko programiranje, sa konkurentskim modelom programiranja na osnovu CSP
• Hume - funkcionalni, istovremeno, za ograničene za prostorne i vremenske sredine gde automata procesi su opisani od sinhroni kanala obrazaca i poruka u prolazu 
• Io - glumac - osnova konkurencije 
• Janus (programski jezik) - ima različite askers i šaltere na logičkim promenljivima, bag kanala; je čisto deklarativan
• JavaSkript - putem veb radnika, u pretraživačkom okruženju, obećanja, i callbacks. 
• JoCaml - konkurentno i distribuirano kanal na bazi proširenja OCaml, sprovodi pridružite računicu procesa Član Java konkurentno, na osnovu jezika Java 
• Džul - dataflov - osnova, komunicira porukom u prolazu 
• Džojs - konkurentno, nastava, izgrađena na konkurentnom Paskala sa karakteristikama iz SPR Per Brinch Hansen 
• LabVIEV - grafički, protok podataka, funkcije su čvorovi u grafu, podaci žice između čvorova; uključuje objektno orijentisani jezik 
• Limbo - rođak Alefa, za sistemsko programiranje u Inferno (operativni sistem)
• MultiLisp - šema varijanti proširena tako da podrži paralelizam 
• Modula - 2 - za programiranje sistema, N. Virt kao naslednik Pascal uz podršku za coroutines 
• Modula - 3 - moderan član Algol porodice sa velikim podrškom za teme, mutekes, stanje varijable 
• Nevskueak - za istraživanje, sa kanalima kao vrednostima prve klase; prethodnik Alef 
• Node.js - server-strani runtime environment za JavaScript 
• Occam uticajem teško na komuniciranje Sekuential Processes (CSP) 
  • Occam - π - moderna varijanta Occam, koja uključuje ideje iz Milner je π-računa
• ORC - veoma konkurentno, nedeterministički, na osnovu Klinijeva algebra 
• Oz - multiparadigma, podržava zajedničku državu i porukama u prolazi konkurenciju i budućnost 
  • Mocart Programiranje Sistem - multiplatformski Oz 
• ParaSail - objektno orijentisano, paralelno, bez pokazivača, trka uslova 
• Pict - u suštini izvršna primena Milner je π-računa 
• Perl sa AniEvent i Coro 
• Piton sa Tvisted Arhivirano na sajtu Wayback Machine (17. novembar 2015), greenlet i gevent 
• Reia - koristi asinhronu poruku prolazi između deljivih - nepostojećih objekata
• Crvena / Sistem - za sistem programiranja, zasnovan na Rebol 
• Rust - za programiranje sistema, fokusiran na masovnoj konkurenciji, koristeći poruku u prolazu sa promenljive semantike, zajednička nepromenljiva memorija, i podela promenljive memorije koja je dokazivo bez rase uslova. 
• SALSA - glumac na osnovu znaka dodavanja, pridruži i prvoklasnim nastavcima za distribuirano računarstvo preko interneta 
• Skala - opšte namene, dizajnirani da izraze zajedničke obrasce programiranja na koncizan, elegantan, i tip - bezbedan način
• SekuenceL - opšte namene funkcionalni, glavni ciljevi dizajna su jednostavnost programiranja, kod jasnoća - čitljivost, i automatski paralelizacija za nastup na multicore hardver, a dokazivo bez trke uslova 
• SR - za istraživanje 
• Stackless Pithon 
• StratifiedJS - kombinator zasnovan na konkurenciji, na osnovu JavaSkript 
• SuperPaskal - konkurentan, za nastavu, izgrađen na konkurentnu Paskala i Joice od  Per Brinch Hansena 
• Unikon - za istraživanje 
• Termiti Šema - adds - Erlangova kao konkurenciju na šemi 
• TNSDL - za razvoj telekomunikacionih razmena, koristi asinhroni Message Passing 
• VHDL (VHSIC Hardvare Opis Jezik) - IEEE STD-1076 
• XC - konkurencija - produženi podskup jezika, C razvio XMOS, na osnovu Komuniciranju Sekuential procesa, ugrađene konstrukcije za programiranje I / O

Mnogi drugi jezici pružaju podršku za konkurenciju u obliku biblioteka, na nivou otprilike uporedive sa gornje liste.

Vidi još

• Spisak značajnih publikacija u konkurentnom, paralelnom, i distribuiranom računarstvu
• Ču prostor 
• Kritična sekcija 
• Protok na bazi programiranja 
• Multitasking 
• Paralelno računarstvo 
• Ptolemej projekat 
• Trka uslov 
• Snop (matematika) 
• Softver transakcijski memorija 
• Obrada transakcije

Literatura

• Ben-Ari, Mordechai (2006). Principles of Concurrent and Distributed Programming (2nd izd.). Addison-Wesley. ISBN 978-0-321-31283-9. 
• Schneider, Fred B. (1997). On Concurrent Programming. Springer. str. 1. ISBN 9780387949420. 
• Patterson, David A.; Hennessy, John L. (2013). Computer Organization and Design: The Hardware/Software Interface. The Morgan Kaufmann Series in Computer Architecture and Design (5 izd.). Morgan Kaufmann. ISBN 978-0-12407886-4. 
• Dijkstra, E. W. (1965). „Solution of a problem in concurrent programming control”. Communications of the ACM. 8 (9): 569. doi:10.1145/365559.365617. 
• Herlihy, Maurice [2008]. The Art of Multiprocessor Programming. Morgan Kaufmann. 2008. ISBN 978-0-12-370591-4.
• Downey, Allen B. . [2005]. The Little Book of Semaphores (PDF). . Green Tea Press. 2005. ISBN 978-1-4414-1868-5. 
• Filman, Robert E.; Friedman, Daniel P. (1984). Coordinated Computing: Tools and Techniques for Distributed Software. New York: McGraw-Hill. str. 370. ISBN 978-0-07-022439-1. 
• Leppäjärvi, Jouni (2008). A pragmatic, historically oriented survey on the universality of synchronization primitives (PDF). University of Oulu.
• Taubenfeld, Gadi (2006). http://www.faculty.idc.ac.il/gadi/book.htm Synchronization Algorithms and Concurrent Programming]. Pearson/Prentice Hall. str. 433. ISBN 978-0-13-197259-9.  .

Spoljašnje veze

• Paralelna sistemska virtuelna biblioteka