Procesimi paralel

Njohuri të përgjithshme për mikroprocesorët

Shfrytëzimi i mikroprocesorëve për punë paralele kërkon që sadopak të njihet edhe organizimi i brendshëm i tyre. Por, me qëllim të kuptimit më të mirë të mundësive të mikroprocesorëve dhe kufizimeve me të cilat janë ballafaquar prodhuesit e tyre, këtu fillimisht do të prezentohen shkurtimish problemet që e kanë përcjellur prodhimin e tyre.

• Forma dhe pamja e një procesori
  Forma dhe pamja e një procesori

Zhvillimi i mikroprocesorëve

Në histiorinë e zhvillimit tejet dinamik të procesorëve, të cilët për shkak të madhësisë së tyre (aktualisht madhësia është rreth dy centimetra katrorë) quhen edhe mikroprocesorë, mund të dallohen dy etapa karakteristike, ajo e procesorëve pa bërthama procesorike dhe tjetra - me disa bërthama procesorike brenda tyre . Mikroprocesorët e parë janë prodhuar si qarqe të integruara (angl. integrated circuits), pa opcionet komplekse brenda tyre, në drejtim të mundësive për punë paralele. Shpejtësia e punës së mikroprocesorëve, një kohë të gjatë është mbështetur kryesisht në frekuencën e punës së tyre, ose siç thuhet ndryshe - në taktin e punës. Por, kjo shpejtësi ndërlidhet edhe me madhësinë e numrave me të cilat ato janë në gjendje të operojnë njëkohësisht, përkatësisht se sa bitësh janë. Kështu, mikroprocesorët e parë janë prodhuar si qarqe të integruara 8-bitëshe, gjë që e nënkupton, p.sh. mundësinë e kryerjes direkte të operacioneve aritmetikore me numra tejet të vegjël. Kurse për operim me numra më të mëdhenjë është dashur të shfrytëzohen takte plotësuese të operimit. Zhvillimi i mikroprocesorëve është orientuar në drejtim të: Shtimit të numrit të bitave për operim të njëkohshëm, Rritjes së taktit të punës së tyre dhe Përfshirjes së memories interne në procesor.

Mikroprocesorët shumbitësh

Operimi me numra të mëdhenjë ndikon direkt në rritjen e shpejtësisë së punës të mikroprocesorëve. Për këtë qëllim, pas mikroprocesorëve 8-bitësh është vazhduar fillimisht me prodhimin e mikroprocesorëve 16-bitësh dhe 32-bitësh, pastaj edhe të atyre 64-bitësh dhe 128-bitësh. Si rezultat i prodhimit të mikroprocesorëve shumëbitësh, është rritur kompleksiteti i brendshëm i tyre, gjë që ndërlidhet edhe me rritjen e numrit të tranzistorëve, si komponentë kryesore në të cilën mbështetet ndërtimi i mikroprocesorëve. Takti i punës së mikroprocesorëve Me taktin, përkatësisht frekuencën e punës së mikroprocesorëve, nënkuptohet shpejtësia e punës së tyre, përkatësisht numri i operacioneve elementare të cilat janë në gjendje t'i kryejnë brenda një sekonde. Kjo frekuencë në fakt e përcakton edhe shpejtësinë e punës së vetë kompjuterit, përkatësisht me shpejtësinë e punës së mikroprocesorit nënkuptohet shpejtësia e punës së kompjuterit. Sa më e madhe që është frekuenca e punës, aq më i madh është numri i operacioneve elementare të cilat kompjuteri është në gjendje t'i kryejë brenda një sekonde. Kështu, mikroprocesorët aktualë kryejnë edhe disa miliarda operacione elementare brenda një sekonde, gjë që është njëra ndër komponentat kryesorë që e përcakton shpejtësinë e ekzekutimit të programeve në kompjuter.

Memoria interne

Mikroprocesorët, gjatë punës së tyre e shfrytëzojnë memorien për t'i ruajtuar rezultatet që u nevojiten në punën e mëtejshme. Për këtë qëllim, mikroprocesorët fillimisht e kanë përdorur memorien kryesore të kompjuterit (memorien RAM). Por, mbështetja në përdorimin e kësaj memorie e zvogëlon dukshëm shpejtësin e punës së tyre, sepse kjo memorie është e vendosur në pllakën amë të kompjuetrit, e cila, krahasuar me shpejtësinë e punës së mikroprocesorëve, është tejet e ngadalshme.

• 
  Memoria RAM

Prandaj, me kohë mikroprocesorëve u është shtuar edhe një memorie interne (angl. internal memory), e cila njihet edhe si memorie kesh (angl. cache memory) . Meqë kjo memorie përfshihet në brendinë e mikroprocesorëve, qasja në te është direkte dhe shumë e shpejtë.

Numri i tranzistorëve

Prodhimi i mikroprocesorëve shumbitësh, si dhe rritja e memories interne ka ndikim në shtimin e madhë të numrit të tranzistorëve në strukturën e mikroprocesorëve. Ky numër veçanërisht është rritur me prodhimin e mikroprocesorëve me më shumë bërthama, si dhe me shtimin e kapacitetit të memories kesh. Si rezultat i kësaj, aktualisht prodhohen mikroprocesorë te të cilët numri i tranzistorëve shkon edhe në disa miliardë. Mikroprocesorët shumbërthamësh Gjeneratat e para të kompjuterëve personal janë prodhuar duke shfrytëzuar procesorë të zakonshëm. Me qëllim të gjetjes së zgjidhjes për kompjuter më të fuqishëm, të cilët do të kryejnë llogaritje më komplekse matematikore, janë prodhuar kompjuterë me dy mikroprocesorë të vendosur në një pllakë amë (angl. motherboard), ku pranë procesorit të zakonshëm është vendosur edhe një procesor matematikor, i cili njihej edhe si koprocesor matematikor. Por, njëkohësisht janë dizajnuar dhe shfrytëzuar edhe kompjuter personal, në pllakën amë të të cilëve janë vendosur dy ose më shumë procesorë të zakonshëm, gjë që ka pasur ndikim në punën paralele të kompjuterëve. Me kohë është parë se idea për vendosjen e disa procesorëve në pllakën amë të kompjuterit, të cilët do të punojnë njëkohësisht përmes punës paralele, si pengesë kryesore e ka shpejtësinë e pllakës amë, meqë komunikimi i mikroprocesorëve duhet të realizohet përmes rrugëve që gjenden në te, gjë që e ngadalson pa masë shpejtësinë e punës së mikroprocesorëve si dhe të kompjuterëve. Puna paralele e mikroprocesorëve ka pasur një ndikim të madh në shpejtësinë e kompjuterëve, gjë që e ka bë të mundur përdorimin e kompjuterëve gjatë : Komunikimit masiv përmes internetit të një numri në rritje të përdoruesve, Kërkimeve të ndryshme në internet (në Ueb), Dekodimit të gjeneve njerzore, Lojrave të ndryshme tredimensionale në kompjuter etj. Gjithashtu, rritja e shpejtësisë së kompjuterëve ndërlidhet edhe me nevojën për: Përpunimin të informatave të ndryshme biometrike, Njohjen e fytyrave dhe gishtrinjëve, me qëllim të ndjekjes automatike të lëvizjes së personave të caktuar, Përcjelljen në kohë reale të ndryshimeve klimatike, Kërkime të ndryshme shkencore në të gjitha sferat e veprimit njerëzor, etj.

Me qëllim të rritjes së fuqisë përpunuese të kompjuterëve, është rritur takti i punës së tyre i cili ka ndikim direkt në shpejtësinë e ekzekutimit të operacioneve elementare, si dhe kapaciteti i memories kryesore dhe periferike. Por, vendimtare në këtë drejtim ka qenë prodhimi i mikroprocesorëve të cilëve u është shtuar edhe memoria interne (memoria kesh), si dhe përfshirja e më shumë bërthamave procesorike brenda vetë procesorit . Mikroprocesorët me disa bërthama procesorike, për dallim nga mikroprocesorët konvencional që mund të quhen edhe njëbërthamësh, përmbajnë më pak transistorë, përkatësisht kanë strukturë më të thjeshtë dhe janë në gjendje të punojnë paralelisht. Të gjitha bërthamat vendosen në një çip dhe qarku i integruar i tillë quhet mikroprocesor shumbërthamësh (angl. multicore microprocessor). Çdo bërthamë në fakt paraqet një njësi procesorike të veçantë (një CPU). Koncepti shumbërthamësh fillimisht është zhvilluar duke i vendosur dy njësi procesorike (angl. processing units), përkatësisht dy bërthamave, në një çip. Komunikimi i këtyre dy bërthamave të veçanta realizohet brenda vet çipit, pa e shfrytëzuar si ndërmjetësuese pllakën amë, gjë që siguron shpejtësi optimale të punës së tyre të përbashkët . Përveç kësaj, kjo e bën të mundur zvogëlimin e shpenzimeve të prodhimit të më shumë procesorëve si bërthama të veçanta, si dhe vendosjen e tyre në pllakën amë të kompjuterit duke e shfrytëzuar vetëm një bazament, gjë që nënkupton edhe vetëm një ftohës të mikroprocesorit. Vendosja e më shumë bërthamave në një çip, lejon shfrytëzimin e memories interne nga të gjitha bërthamat që përfshihen brenda çipit të procesorit. Kur dihet se për prodhimin e memorieve të tilla me kapacite më të mëdha shfrytëzohet një numër i madh tranzistorësh, atëherë lehtë mund të konstatohet thjeshtimi i bërthamave procesorike të veçanta. Bërthamat procesorike që përfshihen në brendi të një mikroprocesori ndryshe njihen edhe si procesor fizik. Por, gjatë punës së kompjuterit, sistemi operativ në mënyrë fiktive shfrytëzon edhe të ashtuquajtur procesor logjik, të cilët aktualisht janë në numër sa dyfishi i procesorëve fizik (çdo procesor fizik mund të deklarohet si dy procesorë logjik). Kështu, p.sh., kur te një kompjuter shkruan se përmban "2 dual-core processor", kjo duhet të nënkuptohet se përmban 2 procesorë dybërthamësh, përkatësisht 4 bërthama fizke (4 procesorë fizik), të cilët mund të punojnë edhe si 8 procesorë logjik. Memoria kesh Siç u theksua edhe më sipër, mikroprocesorët në punën e tyre kanë nevojë për memorie në të cilën i ruajnë të dhënat që janë duke i përpunuar, si dhe rezultatet e fituara. Meqë shfrytëzimi i memories kryesore të kompjuterit nga ana e mikroprocesorëve e zvogëlon shumë shpejtësinë e punës së tyre (sepse gjendet në pllakën amë, e cila është shumë e ngadalshme krahasuar me mikroprocesorin), si zgjidhje optimale është imponuar përfshirja e memorieve kesh në mikroprocesor dhe në bërthamat e veçanta . Këto memorie kanë një rëndësie të veçantë gjatë punës paralele të bërthamave procesorike, përkatësisht pa to është e pamundur puna optimale paralele e kompjuterit. Mënyrat e ekzekutimit të programeve Programet të cilët shkruen për t'u ekzekutuar në kompjuterë konvencional, me një procesor dhe pa mundësi të ekzekutimit të menjëhershëm të më shumë instrukcioneve, në fakt mund të quhen programe serike (angl. serial programs) a (do të përdoret edhe termi programe sekuenciale). Nga ana tjetër, programet e shkruara për ekzekutim në kompjuter duke i shfrytëzuar njëkohësisht më shumë mikroprocesorë, ose më shumë bërthama procesorike, njihen si programe paralele (angl. paralel programs) . Programet serike nuk janë në gjendje ta njohin prezencën e mikroprocesorëve shumëbërthamësh dhe kompjuteri i ekzekuton duke e shfrytëzuar vetëm një bërthamë procesorike. Meqë mikroprocesori në një moment të caktuar është në gjendje të ekzekutojë vetëm një instrukcion, kjo do të thotë se për punë paralele në programe ndryshëm, koha e punës së tij do të duhej t'u ndahet bërthamave të veçanta. Programet paralele Gjatë ekzekutimit të instrukcioneve që përfshihen në një program, te programet parlele, fillimisht për çdo mikroprocesor krijohen vargje të instrukcioneve serike, të cilat pastaj ekzekutohen me rradhë në procesorët e veçantë. Nëse duam që programet serike të ekzekutohen si programe paralele, ato duhet të rishkruhen ashtu që të paralelizohet procesi llogaritës brenda tyre, duke e marrë parasysh konceptin e punës paralele të mikroprocesorëve. Ka pasur tentativa që të dizajnohen përkthyes të cilët do të jenë në gjendje që t'i konvertojnë programet serike në programe paralele. Por, siç duket një përkthim i tillë ka qenë i rëndë dhe me pak sukses. Kjo do të thotë se aktualisht programerët janë të detyruar që t'i rishkruajnë programet serike ekzistuese, përkatësisht t'i konvertojn ato në programe paralele, duke i shtuar brenda tyre metodat që kanë të bëjnë me ekzekutimin paralel të pjesëve të caktuara të tyre .

Puna paralele e kompjuterëve

Kompjuterët e parë, në një moment të caktuar kanë mundur të ekzekutojnë vetëm një program, përkatësisht për ta vazhduar punën në programin vijues është dashur që ta përfundojnë komplet ekzekutimin e programit paraprak. Puna paralele e kompjuterëve nuk është diçka që paraqitet sot. Ajo është përdorur shumë më herët dhe si e tillë takohet te kompjuterët që janë shfrytëzuar në laboratore të ndryshme për hulumtime shkencore, të cilët njiheshin edhe si superkompjuterë . Nënkuptohet se për këtë qëllim, është dashur të shkruhen programe speciale komplekse ashtu që të bëhet i mundur ekzekutimi paralel i disa instrukcioneve elementare. Për ekzekutimin e njëkohshëm të disa programeve, më vonë është shfrytëzuar koncepti i ndarjes së kohës (angl. timesharing) së procesorit, duke u caktuar copëza kohore për punë të pjesëve të veçanta të programeve që ekzekutohen. Gjatë kësaj, çdo program që ekzekutohet, për kompjuterin nënkuptohet edhe si një punë ose task (angl. task), kurse mënyra e ekzekutimit të programeve në këtë rast njihet si multitasking. Sistemi operativ, çdo programi që ekzekutohet i rezervon memorie dhe variabla të veçanta. Në këtë rast, shfrytëzuesi i kompjuterit e ka përshtypjen se njëkohësisht ekzekutohen disa programe, gjë që realisht nuk ndodh. Shfrytëzohet edhe koncepti i ekzekutimit të njëkohshëm i më shumë thredave (angl. threads), i cili njihet si multithreading . Në këtë mënyrë, njëkohësisht ekzekutohen pjesët elementare të programeve, të cilët njihen si threda. Për dallim nga koncepti multitasking, gjatë shfrytëzimit të konceptit multithreding, për thredat e veçantë sistemi operativ nuk rezervon memorie dhe variabla të veçanta. Aktualisht, gjatë shkruarjes së programeve për punë paralele të bërthamave procesorike, për ndarjen e punëve shfrytëzohet paralelizimi i detyrave (angl. task-parallelism) dhe paralelizimi i të dhënave (angl. data-parallelism), gjë që do të thotë se ndahen punët nëpër bërthama, por edhe mund të ndahen të dhënat. Për shfrytëzimin e njëkohshëm të punës së disa bërthamave procesorike, çdo problem duhet të ndahet në pjesë të pavarura , me çka mundësohet që njësitë procesorike t'i ekzekutojnë pjesët përkatëse të algoritmit, duke punuar njëkohësisht me njësitë tjera procesorike . Programet, përkatësisht aplikacionet gjatë ekzekutimit të tyre ndahen në procese (angl. pesses) . Proceset në fakt paraqesin pjesët e programeve që aktualisht ekzekutohen dhe njihen edhe si detyra (angl. task). Për t'u ekzekutuar në mikroprocesor, proceset pastaj ndahen më tutje në copëza (angl. slice) elementare të instrukcioneve që mund të ekzekutohen në mikroprocesor, që siç u tha më sipër njihen si threda (angl. threads). Çdo proces në vedi përmban së paku një thred që ekzekutohet në mikroprocesor. Proceset janë të pavarur, kurse thredat janë pjesë përbërëse të proceseve . Sistemi operativ për çdo proces i rezervon resurset e nevojshme, siç është hapësira e memories, mikroprocesorin, etj., përkatësisht e ndanë hapësirën memoruese, kurse thredet e shfrytëzojnë hapësirën memoruese që u është ndarë proceseve përkatëse. Proceset mund të komunikojnë mes vedi, kurse thredat mund të komunikojnë mes vedi vetëm me thredat e një procesi. Programet shkruhen duke i shfrytëzuar metodat e një gjuhe programuese, në bazë të algoritmit për zgjidhje të problemit . Kurse gjatë ekzekutimit të instrukcioneve që përfshihen në një program ato copëtohen në procese (angl. processes). Te mikroprocesorët me më shumë bërthama procesorike, disa threda (angl. multiple threads) mund të ekzekutohen njëkohësisht (nga nji thred në çdo bërthamë).

Proceset ekzekutohen në kompjuter pasi të ndahen si detyra (angl. task). Detyrat në vete përmbajnë një grumbull instrukcionesh. Kurse, gjatë ekzekutimit të tyre, sistemi operativ i ndan ato në njësi elementare ekzekutive, të cilat njihen edhe si threda (angl. thread). Thredi në fakt paraqesin sekuenca më e vogël e instrukcioneve që mund të menaxhohen nga sitemi operativ. Thredi përfshihet brenda nji procesi, ose brenda nji tasku, përkatësisht procesi ose tasku përmban më shumë threda. Te kompjuterët me nji procesor, përmes ndarjes së kohës ekzekutohen threda të ndryshëm (në një moment ekzekutohet vetëm një thred). Shfrytëzuesi e ka përshtypjen se ekzekutohen njëkohësisht. Te mikroprocesorët me më shumë bërthama, disa threda mund të ekzekutohen njëkohësisht. Në këtë rast flitet për multithreading ose multitasking. Numri i thredave varet nga numri i bërthamave procesorike dhe çdo bërthame fizike sistemi operativ i ndan një thred. Por, edhe procesorëve logjik mund t'u ndahet për ekzekutim nga një thred. Kjo do të thotë se çdo procesori fizik sistemi operativ mund t'i ndajë dy threda për ekzekutim të njëkohshëm. Thredave u ndahen për ekzekutim detyra-punë elementare (tasqe). Por, nëse thredi nuk ka më punë për ekzekutim, ai i huazon punët e thredave tjerë (i merr ato që janë duke pritur më gjatë). Por, nëse thredat shfrytëzojnë resurse të njëjta (p.sh. memorien), puna e tyre duhet të jetë e sinkronizuar (jo e pavarur). Për këtë qëllim futet në përdorim funkcioni i mbylljes (angl. lock) të thredave . Paralelizimi i programeve

Procesimi paralel

Gjatë shkruarjes së programeve për punë paralele, përdoren termet llogaritje paralele (angl. parallel computing) dhe llogaritja konkurrente (angl. concurrent computing) , me të cilët nënkuptohet shfrytëzimi i punës paralele të mikroprocesorëve. Nga ana tjetër, termi llogaritje e distribuar (angl. distributet computing) përdoret në rastet kur për punë paralele shfrytëzohen kompjuterë që gjenden dikund në distancë.

Dizajnimi i një aplikacioni paralel fillon me përcaktimin e nivelit të paralelizimit . Në fakt, fillimisht duhet të analizohet se a është i mundur paralelizimi i punës, përkatësisht a kemi përfitime prej tij, ose mos ndoshta më shumë e komplikojmë procesin e zgjidhjes së problemit.

Implementimi i programimit paralel duhet të fillohet me përcaktimin e pjesëve brenda programit të cilat mund të dekompozohen (ndahen-copëtohen) për tu ekzekutuar paralelisht. Te disa programe dekompozimi mund të jetë mjaft natyror , por në disa të tjerë kjo nuk mund të bëhet lehtë.

Copëtimi i programeve

Për ta kuptuar më mirë mënyrën e copëtimit të një programi me qëllim që pjesët përbërëse të tij të ekzeklutohen paralelisht, n

       static void Main()
       {
           int i;
           const int n = 100;
           int[] A = new int[n];

          // Pjesa parë: Formimi dhe shtypja në ekran e vektorit A

           int k;
           Random r = new Random();
           for (i = 0; i < n; i++)
           {
               k = r.Next(0, 2);        // Numra mes vlerave 0 dhe 1
               if (k == 1)
                   A[i] = r.Next(1, n); // Numra mes vlerave 1 dhe n-1
               else
                   A[i] = -r.Next(1, n);
           }
           for (i = 0; i < n; i++)
               Console.WriteLine("  {0}", A[i]);

          // Pjesa e dytë: Gjetja e enëtarit maksimal të vektorit A

           int x;
           x = Math.Abs(A[0]);
           for (i = 1; i < n; i++)
               if (Math.Abs(A[i]) > x)
                   x = Math.Abs(A[i]);
           Console.WriteLine("\n Vlera maksimale x={0}\n", x);

          // Pjesa e tretë: Numërimi i anëtarëve negativ të vektorit A

           int m;
           m = 0;
           for (i = 0; i < n; i++)
               if (A[i] < 0)
                   m = m + 1;
           Console.WriteLine("\n Anëtarë negativ m={0}", m);

       }

Në programin e dhënë dallohen qartë 3 tërësi të pavarura të tij, të cilat mund të ekzekutohen edhe paralelisht. Pjesa e parë e programit shfrytëzohet për gjenerimin e vlerave të anëtarëve të vektorit A, si numra të rastit mes vlerave 1 dhe n-1. Gjatë kësaj, me qëllim që një pjesë e anëtarëve të tij të mbushen me vlera negative, parashenja është zgjedhur duke gjeneruar numra të rastit mes vlerave 0 dhe 1, përkatësisht duke i marrë si negativ anëtarët vijues për të cilët k=0. Në pjesën e dytë të programit gjendet vlera absolute e vektorit A, e cila ruhet te variabla x. Kurse në pjesën e tretë të tij, numërohen anëtarët negativ të vektorit (variabla m). Ekzekutimi paralel i programeve

Sistemet operative, p.sh. siç është ai Microsift Windows, mund të ekzekutojnë njëkohësisht (angl. simultaneous execution) më shumë programe, edhe në rastet kur kompjuteri ka vetëm nji procesor. Mënyra e punës së kompjuterit e cila e lejon ekzekutimin e njëkohshëm të më shumë punëve, ose siç quhen ndryshe detyrave (angl. task) njihet si multitasking (angl. multitasking). Meqë tasqet (detyrat) paraqesin procese (angl. processes), kjo mënyrë e punës quhet edhe multiprocesim (angl. multiprocessing). Gjatë ekzekutimit të tasqeve, sistemi operativ e përgatit orarin e shfrytëzimit të njëkohshëm të resurseve, siç janë memoria dhe bërthamat procesorike.

Varësia zinxhirore në programe

Niveli i implementimit të punës paralele në një program ndërlidhet me varësinë që kanë të dhënat që shfrytëzohen gjatë llogaritjeve të ndryshme. Nëse në pjesë të caktuara të algoritmit mbi të cilin mbështetet programi nuk ka varësi zinxhirore, përkatësisht llogaritjet e veçanta nuk varen nga rezultaet që fitohen gjatë llogaritjeve paraprake, atëherë në këto pjesë të pavarura të programit mund të aplikohet puna paralele.

Metodat për paralelizim

Në këtë punim, për të eksperimentuar me programeve për ekzekutim paralel të pjesëve të tyre është shfrytëzuar gjuha programuese C# , e cila përfshihet në pakon programuese Microsoft Visual Studio 10 .NET, nën sistemin operativ Microsoft Windows 7. Në këtë gjuhë, për paralelizim të ekzekutimit të pjesëve të programeve shfrytëzohen bibliotekat për punë paralele: Task Parallel Library (shkurt TPL) dhe Parallel LINQ (shkurt PLINQ). Derisa PLINQ përdoret kryesisht për parlelizim të pyetsorëve te bazat me të dhëna, metodat që përfshihen në bibliotekën TPL e mundësojnë automatizimin e punës paralele te kompjuterit me më shumë bërthama procesorike. Përmes tyre, me pak ndryshime mund të paralelizohen pjesë të caktuara të programeve serike. Metodat që përfshihen në bibliotekën TPL mund të shfrytëzohen për paralelizim të të dhënave dhe paralelizim të punëve. Me procesin e paralelizimit të të dhënave nënkuptohet copëtimi i fushave me të dhëna (vektorëve, matricave) në tërësi të pavarura, me qëllim të operimit mbi ta duke i shfrytëzuar unazat. Kurse gjatë paralelizimi të detyrave, problemet coptohen në pjesë përbërëse të cilat janë të pavarura mes veti dhe si të tilla mund të ekzekutohen paralelisht.