Informatika paralele

Nga Wikipedia, enciklopedia e lirë
Shko te: navigacion, kërko
QSicon Kand.svg
Ky artikull është kandidat për artikull të mirë. Artikulli i shfaqur duhet të pasqyrojë punën më të mirë në Wikipedia dhe duhet të plotësojë disa kritere. Ju lutemi ndjehuni të lirë dhe komentoni.

Paralelizmi në informatikë është formë e llogaritjes në të cilën shumë llogaritje bëhen në të njëjtën kohë [1], që veprojnë në parimin se problemet e mëdha shpesh mund të ndahen në më të vogla, të cilat pastaj zgjidhen njëkohësisht (paralelisht). Ka disa forma të ndryshme të paralelizmit në informatikë : bit-niveli, niveli i instruksionit, të dhënat dhe paralelizmi i kontrollit. Paralelizmi ka qenë i përdorur për shumë vjet, kryesisht në informatikë me performancë të lartë, por interesi në të është rritur kohët e fundit për shkak se kufizimet fizike parandalojnë shkallën e frekuencave [2]. Si konsumi i energjisë (dhe si pasojë e gjenerimit të ngrohjes) nga kompjuterat është bërë një shqetësim në vitet e fundit [3], paralelizmi është bërë paradigmë dominuese në arkitekturën e kompjuterit, kryesisht në formën e procesorëve shumbërthamor [4].

Kompjuterët paralel mund të klasifikohen përafërsisht sipas shkallës në të cilën mbështet paralelizëmi i hardverit me multi-core dhe multi-procesor kompjutera që ka elemente të shumta të përpunimit brenda një makinë e vetme, ndërsa grup, masiv, dhe rrjetet përdorin shumë kompjuterë për të punuar në të njëjtën detyrë. Arkitekturat kompjuterike paralele të specializuara janë përdorur ndonjëherë së bashku me procesorë tradicionale, për përshpejtimin e detyrave specifike.

Programet kompjuterike paralele janë më të vështirë për të shkruar se sa ato sekuincial [5] [6], Sepse njëkohësisht fut disa klasa të reja të mundshme bug software. Komunikimi dhe sinkronizimi ndërmjet nëndetyrave të ndryshme janë tipike një nga pengesat më të mëdha në marrjen e mirë punës paralele të programit.

Shpejtësia e një programi si rezultat i paralelizmit është konstatuar si Ligji i Amdahl.

Përmbledhje[redakto | redakto tekstin burimor]

Tradicionalisht, programet kompjuterike janë shkruar për llogaritjen rendore (serike). Për të zgjidhur një problem, është ndërtuar dhe zbatuar një algoritëm si një rrjedhë serike e instruksioneve. Këto instruksione janë ekzekutuar në një njësi qendror të përpunimit në një kompjuter. Vetëm një instruksion mund të ekzekuthet në një kohë—pasi që instruksioni është i përfunduar, instruksioni tjetër ekzekutohet [7].

Paralelizmi, në anën tjetër, përdor elemente të shumta të përpunimit në të njëjtën kohë për të zgjidhur një problem. Kjo është arritur duke thyer problemin në pjesë të pavarura në mënyrë që çdo element i përpunuar të mund të ekzekutoj pjesën e saj të algoritmit në të njëjtën kohë me të tjerët. Elementet e përpunuara mund të jenë të ndryshëm dhe mund të përfshijnë burime të tilla si një kompjuter me shumë procesorë, disa kompjuterë rrjeti, pajisje të specializuara, ose ndonjë kombinim i burimeve të mësipërme [7].

Shkalla e frekuencave ishte arsyeja mbizotëruese për përmirësime në punën e kompjuterit nga mesi i viteve 1980 deri 2004. Koha e ekzekutimit të një programi është e barabartë me numrin e instruksioneve shumëzuar me kohën mesatare për instruksion. Ruajtja konstante e çdo gjëje, rritja e frekuencës së orës zvogëlon kohën mesatare që duhet për të ekzekutuar një instruksion. Një rritje në frekuencën në këtë mënyrë zvogëlon kohën e ekzekutimit për të gjitha programet e llogaritjes së kufizuar [8].

Megjithatë, konsumi i energjisë nga një çip jepet nga ekuacioni P = C × V2 × F, ku P eshte fuqia, C vëllimi që kalon në ciklin e kohës (në proporcion me numrin e transistorëve të cilëve u ndryshojn të dhënat), V, tensioni, dhe F është frekuenca e procesorit (cikle për sekondë) [9]. Rritja në frekuencë rrit sasinë e energjisë të përdorur në një procesor. Rritja e konsumit të energjisë së procesorit çoi përfundimisht në anullimin e procesorit Tejas dhe JayhawkIntel-it në maj 2004, e cila është përmendur në përgjithësi si një fund i shkallës së frekuencës si paradigmë dominuese e arkitekturës kompjuterike [10].

Ligji i Moore është vëzhgimi empirik që tregon se dendësia e tranzitorit në një mikroprocesor dyfishohet çdo 18-24 muaj [11]. Pavarësisht nga çështjet e konsumit të energjisë, si dhe parashikimet e të përsëritura në fund të saj, ligji i Moore është ende në fuqi. Me përfundimin e shkallës të frekuencave, këto transistorë shtesë (të cilat nuk janë më të përdorura për shkallën e frekuencës) mund të përdoret për të shtuar ekstra hardware për paralelizëm.

Ligji i Amdahl dhe Ligji i Gustafson[redakto | redakto tekstin burimor]

Paraqitja grafike e ligjit të Amdah. Shpejtësia e nje programi nga paralelizmi është e kufizuar nga sa prej atij programit mund të paralelizohet. Për shembull, në qoftë se 90% e programit mund të paralelizohet, shpejtësia maksimale teorike-duke përdorur paralelizmin do të bëhet 10x hetë më shpejt pa marrë parasysh sa shumë procesorë janë përdorur.

Mënyrë optimale, rritje e shpejtësisë nga paralelizmi do të jetë lineare, dyfishon numrin e elementeve të përpunimit duke përgjysmuar kohën e ekzekutimit, dhe e dyfishon për herë të dytë përsëri, përgjysmon kohën e ekzekutimit. Megjithatë, shumë pak algoritme paralele arrijnë shpejtësin optimale. Shumica prej tyre kanë një rritje lineare të shpejtësisë për një numër të vogël të elementeve të përpunimit, të cilat sheshohen në një vlerë të vazhdueshme për një numër të madh të elementeve të përpunimit.

Potenciali i rritjes së shpejtësisë së një algoritmi në një platformë kompjuterike paralele është dhënë me ligjin e Amdahl, formuluar fillimisht nga Gene Amdahl në vitet 1960 [12]. Ky ligj thekson se një pjesë e vogël e programit, i cili nuk mund të paralelizohet do ta kufizojnë shpejtësin e përgjithshme në dispozicion nga paralelizmi. Madhësitë matematikore ose problemet inxhinierike zakonisht përbëhen nga disa pjesë të paralelizuara dhe disa pjesë jo-paralelizuara (sekuenciale). Kjo marrëdhënie jepet nga ekuacioni:

S = \frac{1}{1 - P}

ku S është shpejtësia e programit (si një faktor i ekzekutimit sekuencial), si dhe P është pjesë që është paralelizuar. Nëse pjesa e vijues e një programi është 10% e kohës së ekzekutimit, ne mund të marrim jo më shumë se 10× herë rritje të shpejtësisë, pa marrë parasysh sa procesorë janë shtuar. Kjo e vendos një kufizim lartë në dobi të më shumë pjesëve ë ekzekutuara njëkohësisht. Kur një detyrë nuk mund të ndahet për shkak të kufizimeve sekenciale, aplikimi i më shumë përpjekjeve nuk ka efekt në program. "Sjellja e fëmijës merr nëntë muaj, pa marrë parasysh sa shumë gra janë caktuar [13].

Ligji i Gustafson është një ligj tjetër në inxhinierin kompjuterike, i lidhur ngushtë me ligjin e Amdahl. Ai mund të formulohet si:

Supozojmë se një detyrë e ka dy pjesë të pavarura, A dhe B. B merr afërsisht 25% të kohës së llogaritjes e tërë. Me përpjekje, një programues mund të jetë në gjendje për të bërë këtë pjesë pesë herë më shpejt, por kjo vetëm redukton kohën për llogaritjen e së gjithës nga pak. Kjo do të bëjë llogaritjen më shpejt se nga pjesët B të optimizuara, edhe pse B merrë një shpejtësi më të madhe (5× kundrejt 2×)


 S(P) = P - \alpha(P-1) \,

ku P është numri i procesorëve, S është shpejtësia, dhe α - pjesët jo të paralelizuara të procesit [14]. Ligji Amdahl e merr një madhësi të caktuar të problemit dhe kjo madhësi e seksionin sekuencial është e pavarur nga numri i procesorëve, ndërsa ligji i Gustafson nuk ka bërë këto supozime.

Llojet e paralelizmit[redakto | redakto tekstin burimor]

Paralelizmi i nivelit-bit[redakto | redakto tekstin burimor]

Red right arrow.svg
 Artikulli kryesor: Paralelizmi i nivelit bit.

Nga ardhja e teknologjisë së prodhimit të mikroprocesorëve kompjuterik me shumë-shkallë të gjerë ë integrimit në vitet 1970 deri në vitet 1986, shpejtësi deri në arkitekturë kompjuterike u bë nga dyfishimi i madhësive të fjalëve në kompjuter-shumën e informacionit procesori mund ta manipulojë në cikël [15].

Paralelizmi i nivelit të instruksionit[redakto | redakto tekstin burimor]

Një pipeline me 5 faza në makinë RISC (IF = Gjetja e Instruksionit, ID = Dekodimi i Instruksionit, EX = Ekzekutimi, MEM = Qasja në memorje, WB = Register write back)

Një program kompjuterik është, në thelb, një lumë instruksionesh të ekzekutuara nga një procesor. Këto instruksione mund të jenë të ri-drejtuara dhe të bashkohen në grupe të cilat janë ekzekutuar paralelisht pa ndryshuar rezultatin e programit. Kjo është e njohur si paralelizmi i nivelit të instruksionit. Përparimet në paralelizmin e nivelit të instruksionit dominuan arkitekturën kompjuterike nga mesi i viteve 1980 deri në mes të viteve 1990 [16].

Paralelizmi i të dhënave[redakto | redakto tekstin burimor]

Red right arrow.svg
 Artikulli kryesor: Paralelizmi i të dhënave.

Paralelizmi i të dhënave është paralelizmi i pandarë i unazës së programit, i cili fokusohet në shpërndarjen e të dhënave nëpër nyje informatikë të ndryshme që do të përpunohen në mënyrë paralele.

Paralelizmi i punës[redakto | redakto tekstin burimor]

Red right arrow.svg
 Artikulli kryesor: Paralelizmi i punës.

Paralelizmi i punës është karakteristika e një programi paralel që "llogaritje krejtësisht të ndryshme mund të kryhen të dyja në grupin e të dhënave ose në grupe të ndryshme". Ky kontrast me të dhënat paralele, ku përllogaritja e njëjtë kryhet në grupe të njëjta ose të ndryshme të të dhënave. Paralelizmi i punës zakonisht nuk shkallëzon madhësinë e një problemi.

Hardware[redakto | redakto tekstin burimor]

Memoria dhe komunikimi[redakto | redakto tekstin burimor]

Pamja logjike e arkitekturës së Qasjes Jo-Uniforme në Memori.

Memoria (kujtesa) kryesore në një kompjuter paralele është memorje e përbashkët (ndahet në mes të gjitha elementeve që përpunohen në një adresë të vetme), ose memorje e shpërndarë (në të cilën çdo element i përpunuar ka hapsirën e saj të adresës lokale ) [17]. Memoria e shpërndarë i referohet faktit se memoria(kujtesa) është shpërndarë logjikisht, por shpesh nënkupton se ajo është shpërndarë edhe fizikisht. Shpërndarja e memorjes së përbashkët dhe Memoria virtuele kombinimi i dy qasjeve, ku elementi i përpunuar ka memorien e saj lokale dhe qasjen në memorie mbi procesorin jo-lokale. Qasjet në memorien lokale janë zakonisht më të shpejt se qasjet në memorien e jo-lokale.

Klasat e kompjuterëve paralele[redakto | redakto tekstin burimor]

Kompjuterët paralel mund të klasifikohen sipas shkallës në të cilën mbështet paralelizmi harduerik ((Anglisht) hardware parallelism). Ky klasifikim është gjerësisht analog me distancën midis nyjeve informatike. Këto nuk janë reciprokisht ekskluzive, për shembull, grupe të multiprocessors simetrik janë relativisht të zakonshme.

Multicore në informatikë[redakto | redakto tekstin burimor]

Red right arrow.svg
 Artikulli kryesor: Multi-core (informatikë).

Një procesor multicore është një procesor që përfshin shumë njësi ekzekutimi ("berthama") në të njëjtën "chip".

Multiprocesimet simetrike[redakto | redakto tekstin burimor]

Red right arrow.svg
 Artikulli kryesor: Multiprocesimet simetrike.

Një multiprocessor simetrik është një sistem kompjuterik me procesorë të shumta të cilët e ndajnë memorien e njëjtë dhe të lidheni përmes një linje "bus" [18].


Burimi[redakto | redakto tekstin burimor]

  1. ^ Almasi, G.S. and A. Gottlieb (1989). Highly Parallel Computing. Benjamin-Cummings publishers, Redwood City, CA.
  2. ^ S.V. Adve et al. (November 2008). "Parallel Computing Research at Illinois: The UPCRC Agenda" (PDF). Parallel@Illinois, University of Illinois at Urbana-Champaign. "The main techniques for these performance benefits – increased clock frequency and smarter but increasingly complex architectures – are now hitting the so-called power wall. The computer industry has accepted that future performance increases must largely come from increasing the number of processors (or cores) on a die, rather than making a single core go faster."
  3. ^ Asanovic et al. Old [conventional wisdom]: Power is free, but transistors are expensive. New [conventional wisdom] is [that] power is expensive, but transistors are "free".
  4. ^ Asanovic, Krste et al. (December 18, 2006). "The Landscape of Parallel Computing Research: A View from Berkeley" (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. "Old [conventional wisdom]: Increasing clock frequency is the primary method of improving processor performance. New [conventional wisdom]: Increasing parallelism is the primary method of improving processor performance ... Even representatives from Intel, a company generally associated with the 'higher clock-speed is better' position, warned that traditional approaches to maximizing performance through maximizing clock speed have been pushed to their limit."
  5. ^ Program sekuencial ekzekutohet në mënyrë të një-pas-njëshme dmth nuk ekzekutohen dy instruksione njëkohësisht por një-pas-një
  6. ^ Patterson, David A. and John L. Hennessy (1998). Computer Organization and Design, Second Edition, Morgan Kaufmann Publishers, p. 715. ISBN 1-55860-428-6.
  7. ^ a b Barney, Blaise: Introduction to Parallel Computing. Lawrence Livermore National Laboratory. Vizituar në 9 Nëntor 2007.
  8. ^ Hennessy, John L. and David A. Patterson (2002). Computer Architecture: A Quantitative Approach. 3rd edition, Morgan Kaufmann, p. 43. ISBN 1-55860-724-2.
  9. ^ Rabaey, J. M. (1996). Digital Integrated Circuits. Prentice Hall, p. 235. ISBN 0-13-178609-1.
  10. ^ Flynn, Laurie J. "Intel Halts Development of 2 New Microprocessors". The New York Times, May 8, 2004. Retrieved on April 22, 2008.
  11. ^ Gordon E. Moore (1965): Cramming more components onto integrated circuits (PDF). Electronics Magazine S. 4. Vizituar në 11 Nëntor 2006.
  12. ^ Amdahl, G. (April 1967) "The validity of the single processor approach to achieving large-scale computing capabilities". In Proceedings of AFIPS Spring Joint Computer Conference, Atlantic City, N.J., AFIPS Press, pp. 483–85.
  13. ^ Brooks, Frederick P. Jr. The Mythical Man-Month: Essays on Software Engineering. Chapter 2 – The Mythical Man Month. ISBN 0-201-83595-9
  14. ^ Reevaluating Amdahl's Law (1988). Communications of the ACM 31(5), pp. 532–33.
  15. ^ Culler, David E.; Jaswinder Pal Singh and Anoop Gupta (1999). Parallel Computer Architecture - A Hardware/Software Approach. Morgan Kaufmann Publishers, p. 15. ISBN 1-55860-343-3.
  16. ^ Culler et al. p. 15.
  17. ^ Patterson and Hennessy, p. 713.
  18. ^ Hennessy and Patterson, p. 549.


Lidhjet e jashtme[redakto | redakto tekstin burimor]