Algoritm paralel
În informatică , un algoritm paralel , spre deosebire de algoritmii secvențiali tradiționali , este un algoritm care poate fi implementat în părți pe multe dispozitive de calcul diferite, urmat de combinarea rezultatelor obținute și obținerea rezultatului corect.
Unii algoritmi sunt destul de ușor de descompus în bucăți executabile independent. De exemplu, distribuirea muncii de verificare a tuturor numerelor de la 1 la 100.000 pentru a vedea care dintre ele sunt prime se poate face prin atribuirea fiecărui procesor disponibil a unui subset de numere și apoi combinând seturile rezultate de numere prime (de exemplu, proiectul GIMPS este implementat într-un mod similar ).
Pe de altă parte, majoritatea algoritmilor cunoscuți pentru calcularea valorii lui pi nu permit împărțirea în părți paralele, deoarece necesită rezultatul iterației anterioare a algoritmului. Metodele numerice iterative , cum ar fi, de exemplu, metoda lui Newton sau problema cu trei corpuri , sunt, de asemenea, algoritmi pur secvenţiali. Câteva exemple de algoritmi recursivi sunt destul de greu de paralelizat. Un exemplu este căutarea în profunzime pe grafice .
Algoritmii paraleli sunt foarte importanți datorită îmbunătățirii constante a sistemelor multiprocesor și a creșterii numărului de nuclee în procesoarele moderne. De obicei, este mai ușor să proiectați un computer cu un procesor rapid decât unul cu multe procesoare lente (presupunând că se obține aceeași performanță ). Cu toate acestea, performanța procesoarelor crește în principal datorită îmbunătățirii procesului tehnic (reducerea standardelor de producție), care este împiedicată de restricțiile fizice privind dimensiunea elementelor de microcircuit și disiparea căldurii. Aceste limitări pot fi depășite prin trecerea la multiprocesare, care este eficientă chiar și pentru sistemele de calcul mici.
Complexitatea algoritmilor secvenţiali este exprimată în cantitatea de memorie utilizată şi în timpul (numărul de cicluri ale procesorului) necesar executării algoritmului. Algoritmii paraleli necesită luarea în considerare a utilizării unei alte resurse: subsistemul de comunicații între diferite procesoare. Există două moduri de a comunica între procesoare: memorie partajată și transmitere de mesaje.
Sistemele de memorie partajată necesită introducerea de blocări suplimentare pentru datele în curs de prelucrare, impunând anumite restricții atunci când se folosesc procesoare suplimentare.
Sistemele de mesagerie folosesc conceptele de canale și blocuri de mesaje, ceea ce creează trafic suplimentar pe autobuz și necesită memorie suplimentară pentru a pune mesaje în coadă. În proiectarea procesoarelor moderne, pot fi prevăzute comutatoare speciale (bare transversale) pentru a reduce impactul schimbului de mesaje asupra timpului de execuție a unei sarcini.
O altă problemă asociată cu utilizarea algoritmilor paraleli este echilibrarea sarcinii . De exemplu, căutarea numerelor prime în intervalul de la 1 la 100000 este ușor de distribuit între procesoarele disponibile, dar unele procesoare pot obține mai multă muncă, în timp ce altele vor termina procesarea mai devreme și vor rămâne inactiv. Problemele de echilibrare a încărcăturii sunt exacerbate și mai mult atunci când se utilizează medii de calcul eterogene în care elementele de calcul diferă semnificativ în performanță și disponibilitate (de exemplu, în sistemele de rețea ).
O varietate de algoritmi paraleli, numiți algoritmi distribuiți , sunt special dezvoltați pentru utilizare pe clustere și în sisteme de calcul distribuite , ținând cont de o serie de caracteristici ale unei astfel de procesări.