Calcul distribuit

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Calculul distribuit este un domeniu al informaticii care studiază sistemele distribuite , adică sistemele care constau din numeroase computere autonome care interacționează / comunică între ele printr-o rețea pentru a atinge un obiectiv comun (un software care rulează într-un sistem distribuit se numește program distribuirea , și programarea distribuită este procesul de scriere a unui astfel de software).

Un exemplu tipic de aplicare a calculelor distribuite este utilizarea sistemelor distribuite pentru a rezolva probleme de calcul cu o anumită complexitate: în acest context, o problemă este la rândul ei împărțită în multe sub-sarcini, fiecare dintre ele fiind rezolvată de un singur computer .

Istorie

Utilizarea proceselor concurente care comunică cu transmiterea mesajelor își are rădăcinile în arhitecturile sistemelor de operare studiate în anii 1960. Primul sistem distribuit pe scară largă a fost rețeaua locală, cum ar fi Ethernet, care a fost inventată în anii 1970.

Arpanet , predecesorul internetului , a fost introdus la sfârșitul anilor 1960, iar e-mailul ARPANET a fost inventat la începutul anilor 1970. E-mailul a devenit cea mai de succes aplicație a ARPANET și este probabil primul exemplu de aplicație distribuită. scară. Pe lângă ARPANET și succesorul său, Internetul, alte prime rețele de calculatoare din întreaga lume au fost Usenet și Fidonet din anii 1980, ambele fiind utilizate pentru a sprijini sistemele de discuții distribuite.

Studiul informaticii distribuite a devenit în mod corespunzător o ramură a informaticii la sfârșitul anilor 1970 și începutul anilor 1980. Prima conferință din domeniul „Simpozionul principiilor informaticii distribuite” datează din 1980 și omologul său european „Simpozionul internațional privind computerele distribuite” a avut loc pentru prima dată în 1985.

Descriere

Cuvântul distribuit în termeni precum „sistem distribuit”, „programare distribuită” și „ algoritm distribuit ” se referea inițial la rețele de calculatoare în care computerele individuale erau distribuite fizic în anumite zone geografice. Termenii sunt acum folosiți într-un sens mai larg, chiar și atunci când se referă la procese autonome care rulează pe același computer fizic și interacționează între ele prin trecerea mesajelor.

Deși nu există o definiție unică a sistemului distribuit, sunt utilizate în mod obișnuit următoarele proprietăți:

  • Există multe entități de calcul autonome, fiecare dintre ele având propria sa memorie locală.
  • Entitățile comunică între ele prin transmiterea mesajelor .

În această discuție, entitățile de calcul vor fi denumite computere sau noduri .

Un sistem distribuit poate avea un scop comun, cum ar fi rezolvarea unei mari probleme de calcul. Alternativ, fiecare computer poate avea propriul utilizator cu nevoi individuale, iar scopul sistemului distribuit este de a coordona utilizarea resurselor partajate sau de a oferi servicii de comunicații utilizatorului.

Alte proprietăți tipice ale sistemelor distribuite sunt următoarele:

  • Sistemul tolerează defecțiunile unui singur computer.
  • Structura sistemului (topologia rețelei, latența rețelei, numărul de computere) nu este cunoscută în prealabil, sistemul poate consta din diferite tipuri de computere și conexiuni de rețea și se poate modifica în timpul execuției programului distribuit.
  • Fiecare computer are doar o vizualizare limitată și incompletă a sistemului. Fiecare computer cunoaște doar o parte din intrare.

Calcul paralel sau distribuit?

Termenii „calcul simultan”, „ calcul paralel ” și „calcul distribuit” au multe suprapuneri și nu există o distincție clară între ei. Același sistem poate fi caracterizat atât ca „paralel”, cât și ca „distribuit”; procesoarele dintr-un sistem distribuit tipic procesează simultan în paralel. Calculul paralel poate fi văzut ca o formă particulară strâns legată de calculul distribuit, iar calculul distribuit poate fi văzut ca o formă particulară strâns asociată cu calculul paralel. Cu toate acestea, este posibilă clasificarea sistemelor concurente ca „paralele” sau „distribuite” utilizând următoarele criterii:

  • În paralel, toate procesoarele trebuie să acceseze memoria partajată . Memoria partajată poate fi utilizată pentru schimbul de informații între procesoare.
  • În calculul distribuit, fiecare procesor are propria sa memorie privată ( memorie distribuită ). Informațiile sunt schimbate prin transmiterea mesajelor între procesoare.

Imaginea din dreapta ilustrează diferența dintre sistemele distribuite și sistemele paralele.

(a) - (b) Sistem distribuit. (c) Sistem paralel.

Figura (a) este o vedere schematică a unui sistem tipic distribuit: sistemul este reprezentat ca un grafic în care fiecare nod (vârf) este un computer și fiecare rând (linie între două noduri) este o legătură de comunicație. Figura (b) prezintă același sistem distribuit în detaliu: fiecare computer are propria sa memorie locală, iar informațiile pot fi schimbate numai prin trecerea mesajelor de la un nod la altul folosind nodurile de comunicație disponibile. Figura (c) prezintă un sistem paralel în care fiecare procesor are acces direct la memoria partajată.

Situația este în continuare complicată de utilizările tradiționale ale termenilor algoritm paralel și distribuit care nu corespund definiției sistemelor paralele și distribuite. Cu toate acestea, ca regulă generală, calculul paralel de înaltă performanță cu memorie partajată multiprocesor utilizează algoritmi paraleli în timp ce algoritmii distribuiți sunt utilizați pentru coordonarea sistemelor distribuite la scară largă.

Fundamente teoretice

Modele

Multe sarcini pe care am dori să le automatizăm folosind computerul sunt tipuri de întrebări și răspunsuri: punem o întrebare și computerul ar trebui să dea răspunsul. În informatică aceste sarcini se numesc probleme de calcul. În mod formal, o problemă de calcul constă în instanțe, împreună cu o soluție pentru fiecare instanță. Instanțele sunt întrebări pe care le putem pune, iar soluțiile sunt răspunsurile dorite la aceste întrebări.

Informatica încearcă să înțeleagă care probleme de calcul pot fi rezolvate folosind un computer ( teoria calculabilității ) și cât de eficient ( teoria complexității de calcul ). În mod tradițional, este ca și cum ați spune că o problemă poate fi rezolvată folosind un computer dacă putem scrie un algoritm care produce o soluție corectă pentru orice instanță dată. Un astfel de algoritm poate fi implementat ca un software care rulează pe un computer generic: programul citește instanța problemă dintr-o intrare , efectuează calcule și produce soluția ca ieșire. Formalisme precum mașinile cu acces aleatoriu sau mașinile universale Turing pot fi utilizate ca modele abstracte ale unui computer generic secvențial care rulează un astfel de algoritm.

Domeniul calculelor simultane și distribuite studiază întrebări similare în cazul multor computere sau al unui computer care rulează o rețea de procese interacționale: ce probleme de calcul pot fi rezolvate într-o astfel de rețea și cu ce eficiență? Cu toate acestea, nu este atât de evident ce înseamnă rezolvarea unei probleme în cazul sistemelor concurente sau distribuite: de exemplu, care este sarcina proiectantului algoritmului și care este echivalentul simultan și / sau distribuit pentru un computer generic ?

Discuția de mai jos se concentrează pe cazul multor computere, dar în orice caz multe dintre aceste probleme sunt aceleași pentru procesele simultane care rulează pe un singur computer.

Există trei cazuri frecvent utilizate:

Algoritmi paraleli în modele de memorie partajată

  • Toate computerele au acces la memoria partajată. Proiectantul algoritmului alege programul pe care îl rulează fiecare computer.
  • Un model teoretic este mașina cu acces paralel aleatoriu (PRAM) . Cu toate acestea, modelul clasic PRAM presupune acces sincron la memoria partajată.
  • Un model care este mai aproape de comportamentul mașinilor multiprocesor din lumea reală ia în considerare utilizarea instrucțiunilor mașinii, cum ar fi Compare-and-swap (CAS), care este cea a memoriei asincrone partajate.

Algoritmi paraleli în modelul de transmitere a mesajelor

  • Proiectantul algoritmului alege structura rețelei, precum și programul pe care îl rulează fiecare computer
  • Sunt utilizate modele precum circuitele booleene și rețelele de sortare. Un circuit boolean poate fi văzut ca o rețea de calculatoare: fiecare poartă este un computer care rulează un program extrem de simplu. În mod similar, o rețea de comandă poate fi văzută și ca o rețea de calculatoare: fiecare comparator este un computer.

Algoritmi distribuiți în modelul de transmitere a mesajelor

  • Proiectantul algoritmului alege doar programul. Toate computerele rulează același program. Sistemul trebuie să funcționeze corect indiferent de structura rețelei.
  • Un model utilizat în mod obișnuit este graficul cu o mașină cu stări finite pe nod.

În cazul algoritmilor distribuiți, problemele de calcul sunt de obicei legate de grafice. Adesea, graficul care descrie structura rețelei de calculatoare este instanța problemei. Acest caz este ilustrat în exemplul următor.

Un exemplu

Luați în considerare problema de calcul a găsirii unei colorări a unui grafic dat G. Diferite sectoare ar putea urma următoarele abordări:

Algoritmi centralizați

  • Graficul G este codificat ca un șir, iar șirul este dat ca intrare într-un computer. Programul găsește o colorare a graficului, codifică colorarea ca un șir și dă rezultatul la ieșire.

Algoritmi paraleli

  • Din nou, graficul G este codificat ca un șir. Cu toate acestea, mai multe computere pot accesa același șir în paralel. Fiecare computer se poate concentra pe o parte a graficului și poate produce o culoare pentru acea parte.
  • Accentul principal se pune pe calculul de înaltă performanță, care valorifică puterea de procesare a mai multor calculatoare în paralel.

Algoritmi distribuiți

  • Graficul G este structura rețelei de calculatoare. Există un computer pentru fiecare nod al lui G și o legătură pentru fiecare capăt al lui G. Inițial, fiecare computer își cunoaște doar vecinii imediați din graficul G; Calculatoarele trebuie să își transmită mesaje reciproc pentru a afla mai multe despre structura lui G. Fiecare computer trebuie să producă propria culoare ca ieșire.
  • Accentul principal se pune pe coordonarea operațiunii pe un sistem distribuit arbitrar.

În timp ce câmpul algoritmilor paraleli are o caracterizare diferită de câmpul algoritmilor distribuiți, există interacțiuni diferite între cele două câmpuri. De exemplu, algoritmul Cole - Vishkin pentru colorarea graficelor a fost inițial prezentat ca un algoritm paralel, dar aceeași tehnică poate fi utilizată direct ca algoritm distribuit.

Mai mult, un algoritm paralel poate fi implementat atât într-un sistem paralel (folosind memoria partajată), cât și într-un sistem distribuit (folosind transmiterea mesajelor). Granița tradițională dintre algoritmi paraleli și distribuiți (alegerea unei rețele potrivite față de rularea în fiecare rețea) nu este ca granița dintre sistemele paralele și distribuite (memoria partajată vs transmiterea mesajelor).

Măsuri de complexitate

Un algoritm centralizat este eficient dacă nu necesită mult timp (număr de pași de calcul) sau spațiu (cantitate de memorie). Această măsură de complexitate dă naștere unor clase de complexitate precum P (probleme de decizie rezolvabile în timp polinomial) și PSPACE (probleme de decizie rezolvabile în spațiul polinomial) .

În algoritmi paraleli, o altă resursă în plus față de timp și spațiu este numărul de computere. De fapt, există adesea un echilibru între timpul de execuție și numărul de computere: problema poate fi rezolvată rapid dacă există mai multe computere care procesează în paralel. Dacă o problemă de decizie poate fi rezolvată în timp polilogaritmic folosind un număr polinomial de procesoare, atunci se spune că problema se află în clasa NC. Clasa NC poate fi definită la fel de bine folosind formalismul PRAM sau circuitele booleene. Mașinile PRAM pot simula în mod eficient circuitele booleene și invers.

În analiza algoritmilor distribuiți, se acordă de obicei mai multă atenție comunicării operațiilor decât pașilor de calcul. Poate că cel mai simplu model de calcul distribuit este un sistem sincron în care toate nodurile funcționează ca un bloc. În timpul fiecărei runde de comunicare, toate nodurile din paralel (1) primesc ultimele mesaje de la vecinii săi, (2) efectuează calcule locale arbitrare și (3) trimit mesaje noi vecinilor lor. În astfel de sisteme, o măsură centrală a complexității este numărul de schimbări de comunicare sincronă necesare pentru a finaliza sarcina.

Această măsură a complexității este strâns legată de diametrul rețelei. Fie D diametrul rețelei. Pe de o parte, orice problemă de calcul poate fi rezolvată trivial într-un sistem sincron distribuit în schimburi de comunicare aproximativ 2D: pur și simplu pentru a colecta toate informațiile într-un singur punct (schimbări D), pentru a rezolva problema și pentru a informa fiecare nod despre soluție ( D schimburi).

Pe de altă parte, dacă timpul de execuție al algoritmului este mult mai mic decât D schimburi de comunicare, atunci nodurile rețelei trebuie să își producă rezultatele fără a avea posibilitatea de a obține informații despre părțile îndepărtate ale rețelei. Cu alte cuvinte, nodurile trebuie să ia decizii globale pe baza informațiilor disponibile în vecinătatea lor. Se știe că mulți algoritmi distribuiți au un timp de rulare mult mai scurt decât schimbările D, iar înțelegerea problemelor care pot fi rezolvate prin astfel de algoritmi este unul dintre obiectivele centrale de cercetare din acest domeniu.

O altă măsură frecvent utilizată este numărul total de biți transmiși prin rețea (complexitatea comunicării).

Alte probleme

Problemele de calcul constau, în general, în a pune o întrebare unui computer (sau unui sistem distribuit), care procesează întrebarea pentru o vreme și, în cele din urmă, produce un răspuns și se oprește. Cu toate acestea, există și probleme în care dorim ca sistemul să nu se oprească niciodată. Exemple de astfel de probleme includ problema filozofilor la cină și alte probleme similare de excludere reciprocă . În aceste probleme, sistemul distribuit ar trebui să coordoneze în mod constant utilizarea resurselor partajate fără prezența conflictelor sau blocajelor .

Există, de asemenea, provocări fundamentale care sunt unice pentru calculul distribuit. Primul exemplu este provocarea în ceea ce privește toleranța la erori. Exemple de probleme conexe includ probleme de consens, toleranța la defecțiuni bizantine și auto-stabilizare.

Multe cercetări se concentrează, de asemenea, pe înțelegerea naturii asincrone a sistemelor distribuite:

  • Sincronizatoarele pot fi utilizate pentru a rula algoritmi sincroni în sistemele asincrone.
  • Ceasul logic oferă o ordine a evenimentelor în ordinea apariției.
  • Algoritmii de sincronizare a ceasului oferă acum consistență fizică generală a timbrului.

Proprietățile sistemelor distribuite

Până în prezent, accentul a fost pus pe proiectarea unui sistem distribuit care rezolvă o anumită problemă. O problemă complementară de cercetare este studierea proprietăților unui sistem distribuit dat.

Problema de terminare este un exemplu analog cu domeniul calculelor centralizate: ni se oferă software și sarcina este de a decide dacă se oprește sau se oprește pentru totdeauna. Problema de terminare este indecidabilă în cazul general și, desigur, înțelegerea comportamentului unei rețele de calculatoare este cel puțin la fel de dificilă ca înțelegerea comportamentului unui computer.

Cu toate acestea, există multe cazuri speciale interesante care se pot decide. În special, este posibil să ne gândim la comportamentul unei rețele de mașini cu stare finită. Un exemplu este să spunem dacă o rețea interacționată dată de mașini cu stare finită (asincronă și nedeterministă) poate ajunge într-un blocaj. Această problemă este PSPACE completă, este decisă, dar este puțin probabil să existe un algoritm eficient (centralizat, paralel sau distribuit) care să rezolve problema în cazul unei rețele mari.

Arhitecturi

Diverse arhitecturi hardware și software sunt utilizate pentru calculul distribuit. La un nivel scăzut este necesar să interconectați mai multe procesoare cu un fel de rețea, indiferent dacă rețeaua este tipărită pe un circuit sau compusă din dispozitive și cabluri. Pe de altă parte, la un nivel înalt este necesar să interconectați procesele efectuate pe aceste CPU-uri cu un fel de sistem de comunicații.

Programarea distribuită se încadrează de obicei în unul dintre mai multe elemente sau categorii arhitecturale de bază: client-server, arhitectură pe 3 niveluri, arhitectură pe niveluri N, obiecte distribuite, cuplare liberă, cuplare strânsă.

  • Client-server - Codul clientului contactează serverul pentru date, pe care le formată și le afișează utilizatorului. Intrările de date către client sunt trimise la server atunci când reprezintă date permanente.
  • Arhitectură pe 3 niveluri - Sistemul pe 3 niveluri mută inteligența clientului la un nivel intermediar, astfel încât să poată fi utilizat clientul fără stat. Acest lucru facilitează mutarea aplicațiilor. Majoritatea aplicațiilor web sunt pe 3 niveluri.
  • N-tier architecture - N-tier se referă de obicei la aplicațiile web care își trimit cererile către alte servicii. Acest tip de aplicație contribuie major la succesul aplicațiilor server.
  • Strâns cuplat (grupat) - De obicei se referă la un grup de mașini care lucrează împreună executând un proces partajat în paralel. Sarcina este împărțită în părți care sunt elaborate individual de fiecare și apoi trimise înapoi împreună pentru a compune rezultatul final.
  • Peer-to-peer - O arhitectură în care nu există anumite mașini care furnizează un serviciu sau gestionează resursele de rețea. În schimb, toate responsabilitățile sunt împărțite uniform între toate mașinile cunoscute sub numele de „colegi”. Colegii pot funcționa atât ca client, cât și ca server.
  • Bazat pe spațiu - Se referă la o infrastructură care creează iluzia (virtualizarea) unui singur spațiu de adrese. Datele sunt reproduse în mod transparent în funcție de nevoile aplicațiilor.

Un alt aspect de bază al arhitecturilor de calcul distribuit este metoda de comunicare și coordonare a lucrărilor între procese concurente. Prin diferite protocoale de schimb de mesaje, procesele pot comunica direct între ele, de obicei cu o relație master / slave. Alternativ, o arhitectură centrală a bazei de date ar putea face calcule distribuite efectuate fără nicio formă de comunicare între procese, utilizând o bază de date partajată.

Aplicații

Există două motive principale pentru utilizarea sistemelor distribuite și a calculelor distribuite. În primul rând, natura aplicației poate necesita utilizarea unei rețele de comunicații care conectează mai multe computere. De exemplu, datele sunt produse într-o anumită locație fizică și sunt necesare într-o altă locație.

În al doilea rând, există multe cazuri în care utilizarea unui singur computer ar fi posibilă în principiu, dar utilizarea unui sistem distribuit este avantajoasă din motive practice. De exemplu, poate fi mai eficient să se atingă nivelul de performanță dorit folosind un cluster de mai multe computere low-end, comparativ cu un sistem nedistribuit și nu există puncte unice de eșec. În plus, un sistem distribuit poate fi mai ușor de extins și de administrat decât un sistem monolitic uniprocesor.

Exemple de sisteme distribuite și aplicații de calcul distribuite sunt incluse mai jos:

Notă

Cărți

  • Andrews, Gregory R. (2000), Fundamentele programării multithreaded, paralele și distribuite, Addison - Wesley, ISBN 0-201-35752-6 .
  • Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity - A Modern Approach, Cambridge, ISBN 978-0-521-42426-4 .
  • Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990), Introducere în algoritmi (prima ediție), MIT Press, ISBN 0-262-03141-8 .
  • Dolev, Shlomi (2000), Auto-stabilizare, MIT Press, ISBN 0-262-04178-2 .
  • Elmasri, Ramez; Navathe, Shamkant B. (2000), Fundamentals of Database Systems (ediția a 3-a), Addison - Wesley, ISBN 0-201-54263-3 .
  • Ghosh, Sukumar (2007), Sisteme distribuite - o abordare algoritmică, Chapman & Hall / CRC, ISBN 978-1-58488-564-1 .
  • Lynch, Nancy A. (1996), Algoritmi distribuiți, Morgan Kaufmann, ISBN 1-55860-348-4 .
  • Herlihy, Maurice P.; Shavit, Nir N. (2008), The Art of Multiprocessor Programming, Morgan Kaufmann, ISBN 0-12-370591-6 .
  • Papadimitriou, Christos H. (1994), Complexitate computațională, Addison - Wesley, ISBN 0-201-53082-1 .
  • Peleg, David (2000), Distributed Computing: A Locality-Sensitive Approach, SIAM, ISBN 0-89871-464-8

Articole

  • Cole, Richard; Vishkin, Uzi (1986), „Aruncarea monedei deterministă cu aplicații pentru clasarea optimă a listelor paralele”, Information and Control 70 (1): 32–53, doi: 10.1016 / S0019-9958 (86) 80023-7.
  • Keidar, Idit (2008), „Coloana de calcul distribuită 32 - Anul în revizuire”, ACM SIGACT News 39 (4): 53–54
  • Linial, Nathan (1992), „Locality in distribution graph algorithms”, SIAM Journal on Computing 21 (1): 193–201, doi: 10.1137 / 0221015.
  • Naor, Moni; Stockmeyer, Larry (1995), „Ce se poate calcula local?”, SIAM Journal on Computing 24 (6): 1259–1277, doi: 10.1137 / S0097539793254571.

Site-uri web

Elemente conexe

Alte proiecte

linkuri externe

Controlul autorității Tezaur BNCF 3277 · LCCN (EN) sh85042293 · GND (DE) 7545389-7 · BNF (FR) cb11932111w (dată) · BNE (ES) XX545920 (dată)
Telematică Portal telematic : accesați intrări Wikipedia care vorbesc despre rețele, telecomunicații și protocoale de rețea
Adus de la „ https://it.wikipedia.org/w/index.php?title=Distributed_Calculation&oldid=122122615 ”