Informatika paralele

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ë : niveli bit, niveli i instruksionit, paralelizmi i të dhënave dhe paralelizmi i kontrollit. Paralelizmi ka qenë i përdorur për shumë vite, kryesisht në informatikën e performancës së lartë, por interesi në të është rritur kohët e fundit për shkak se kufizimet fizike parandalojnë shkallën e frekuencave ^[2]. Si pasojë e konsumit të energjisë (dhe për rrjedhojë gjenerimi i nxehtësisë) nga kompjuterët, ë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 shumë bërthamorë^[4].

Kompjuterët paralel mund të klasifikohen afërsisht sipas shkallës në të cilën hardueri mbështet paralelizmin, me kompjuterë që kanë më-shumë-procesorë me më-shumë-bërthama që kanë elemente të shumta të përpunimit brenda një makine të vetme, ndërsa kompjuterët grupore, masiive, dhe rrjetete përdorin shumë kompjuterë për të punuar të njëjtën punë. Arkitekturat kompjuterike paralele të specializuara ndonjëherë përdoren së bashku me procesorë të zakonshëm, për përshpejtimin e detyrave specifike.

Shpejtësia e një programi si rezultat i paralelizmit është jepet sipas Ligjit të Amdahl.

Përmbledhje

Zakonisht, 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 ^[5].

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 ^[5].

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 ^[6].

Megjithatë, konsumi i energjisë nga një çip jepet nga ekuacioni P = C × V² × 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ë) ^[7]. 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 Jayhawk të Intel-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 ^[8].

Ligji i Moore është vëzhgimi empirik që tregon se dendësia e tranzitorit në një mikroprocesor dyfishohet çdo 18-24 muaj ^[9]. 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

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.

Në mënyrë optimale, rritja 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 ^[10]. 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 ^[11].

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 ^[12]. 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

Paralelizmi i nivelit-bit

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 ^[13].

Paralelizmi i nivelit të instruksionit

Artikulli kryesor: Paralelizmi i nivelit të instruksionit

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 ^[14].

Paralelizmi i të dhënave

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

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

Memoria dhe komunikimi

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 ) ^[15]. 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

Kompjuterët paralel mund të klasifikohen sipas shkallës në të cilën mbështet paralelizmi harduerik (Transclusion error: {{En}} is only for use in File namespace. Use {{lang-en}} or {{in lang|en}} instead. 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ë

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

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" ^[16].

Burimi

^ Almasi, G.S. and A. Gottlieb (1989). Highly Parallel Computing. Benjamin-Cummings publishers, Redwood City, CA.
^ S.V. Adve et al. (November 2008). "Parallel Computing Research at Illinois: The UPCRC Agenda" Arkivuar 9 dhjetor 2008 tek Wayback Machine (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."
^ 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".
^ 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."
^ ^a ^b Barney, Blaise. "Introduction to Parallel Computing". Lawrence Livermore National Laboratory. Arkivuar nga origjinali më 29 qershor 2013. Marrë më 2007-11-09. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Hennessy, John L. and David A. Patterson (2002). Computer Architecture: A Quantitative Approach. 3rd edition, Morgan Kaufmann, p. 43. ISBN 1-55860-724-2.
^ Rabaey, J. M. (1996). Digital Integrated Circuits. Prentice Hall, p. 235. ISBN 0-13-178609-1.
^ Flynn, Laurie J. "Intel Halts Development of 2 New Microprocessors". The New York Times, May 8, 2004. Retrieved on April 22, 2008.
^ Moore, Gordon E. (1965). "Cramming more components onto integrated circuits" (PDF). Electronics Magazine. fq. 4. Arkivuar nga origjinali (PDF) më 18 shkurt 2008. Marrë më 2006-11-11. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ 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.
^ Brooks, Frederick P. Jr. The Mythical Man-Month: Essays on Software Engineering. Chapter 2 – The Mythical Man Month. ISBN 0-201-83595-9
^ Reevaluating Amdahl's Law Arkivuar 23 qershor 2012 tek Wayback Machine (1988). Communications of the ACM 31(5), pp. 532–33.
^ 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.
^ Culler et al. p. 15.
^ Patterson and Hennessy, p. 713.
^ Hennessy and Patterson, p. 549.

Lidhjet e jashtme

Informatika paralele në Open Directory Project Transclusion error: {{En}} is only for use in File namespace. Use {{lang-en}} or {{in lang|en}} instead.
Laboratori Kombëtar i Lawrence Livermore: Hyrje në informatikën paralele Arkivuar 10 qershor 2013 tek Wayback Machine Transclusion error: {{En}} is only for use in File namespace. Use {{lang-en}} or {{in lang|en}} instead.
Projektimi dhe Ndërtimi i programeve paralele, nga Ian Foster Transclusion error: {{En}} is only for use in File namespace. Use {{lang-en}} or {{in lang|en}} instead.
Arkiva e Informatikës paralele në Internet Transclusion error: {{En}} is only for use in File namespace. Use {{lang-en}} or {{in lang|en}} instead.
Përpunimi paralel në fushën e IEEE Informatika e shpërndarjes Online Transclusion error: {{En}} is only for use in File namespace. Use {{lang-en}} or {{in lang|en}} instead.
Parallel Computing Works Free On-line Book Arkivuar 27 korrik 2011 tek Wayback Machine Transclusion error: {{En}} is only for use in File namespace. Use {{lang-en}} or {{in lang|en}} instead.
Frontiers of Supercomputing Free On-line Book Covering topics like algorithms and industrial applications Transclusion error: {{En}} is only for use in File namespace. Use {{lang-en}} or {{in lang|en}} instead.
Qendra e kërkimit universal të informatikës paralele Transclusion error: {{En}} is only for use in File namespace. Use {{lang-en}} or {{in lang|en}} instead.
Kursi në Programim paralele në Columbia University (në bashkëpunim me projektin e IBM TJ Watson X10) Transclusion error: {{En}} is only for use in File namespace. Use {{lang-en}} or {{in lang|en}} instead.

[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" Arkivuar 9 dhjetor 2008 tek Wayback Machine (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".

[View-Power-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."

[llnltut-5] Barney, Blaise. "Introduction to Parallel Computing". Lawrence Livermore National Laboratory. Arkivuar nga origjinali më 29 qershor 2013. Marrë më 2007-11-09. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[6] Hennessy, John L. and David A. Patterson (2002). Computer Architecture: A Quantitative Approach. 3rd edition, Morgan Kaufmann, p. 43. ISBN 1-55860-724-2.

[7] Rabaey, J. M. (1996). Digital Integrated Circuits. Prentice Hall, p. 235. ISBN 0-13-178609-1.

[8] Flynn, Laurie J. "Intel Halts Development of 2 New Microprocessors". The New York Times, May 8, 2004. Retrieved on April 22, 2008.

[Moore1965paper-9] Moore, Gordon E. (1965). "Cramming more components onto integrated circuits" (PDF). Electronics Magazine. fq. 4. Arkivuar nga origjinali (PDF) më 18 shkurt 2008. Marrë më 2006-11-11. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[10] 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.

[11] Brooks, Frederick P. Jr. The Mythical Man-Month: Essays on Software Engineering. Chapter 2 – The Mythical Man Month. ISBN 0-201-83595-9

[12] Reevaluating Amdahl's Law Arkivuar 23 qershor 2012 tek Wayback Machine (1988). Communications of the ACM 31(5), pp. 532–33.

[13] 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.

[14] Culler et al. p. 15.

[PH713-15] Patterson and Hennessy, p. 713.

[HP549-16] Hennessy and Patterson, p. 549.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]