Višejezgarni procesori i paralelno programiranje

Pojava višejezgarnih procesora povukla je kompletnu softversku scenu i u prvi plan dospeva pomalo zaboravljeno paralelno programiranje

Do pre samo nekoliko godina, sa velikom pažnjom pratili smo nadmetanje dva najveća proizvođača procesora za personalne računare, kompanije Intel i AMD, u tome ko će svetu ponuditi brži proizvod. Bilo je tu velikih uspeha i krahova, fantastičnih marketinških poteza, prepucavanja preko medija i tužbi za kršenje patenata. Intel se oslanjao na radnu frekvenciju, dostižući nekada zapanjujućih 3,4 GHz, dok je AMD, koristeći napredne tehnologije integracije memorijskog kontrolera na pločicu procesora, isticao performanse po vatu (W) potrošnje električne energije. Rezultati testova više su služili za potkusurivanje fanova jednog i drugog tabora, nego kao argument u izboru procesora najboljih opštih performansi. A onda, postajemo svedoci potpunog zaokreta koji je poveo tehnologiju u pravcu razvoja ne jedne ultrabrze procesorske jedinice, već u početku dve, zatim četiri, a u najavi su i kombinacije do 80 jezgara na samo jednom čipu. Ovakav potez za sobom je povukao kompletnu softversku scenu, nateravši je da se promeni, ustanovi nova pravila igre i postigne željene performanse. U prvi plan dospeva pomalo zaboravljeno paralelno programiranje.

Zašto više jezgara

Dostizanje visokih radnih frekvencija do skora je bio jedini način da proizvođač unapredi postojeću mikroarhitekturu. Kako je taj princip došao do fizičkog zida koji predstavljaju ograničenja u proizvodnom procesu, ali i pitanja potrošnje električne energije, bilo je potrebno naći potpuno drugačije rešenje.

Ako pogledamo u superačunare, kako one iz prošlosti, tako i savremene, videćemo da su napravljeni na principu višeprocesorskih sistema. Najjednostavnije gledano, veliki broj ploča sa procesorima povezano u odgovarajući niz čini osnovu superačunara. Logično je bilo pomisliti da udruživanjem procesora možemo dobiti bolje performanse. Takvih implementacija bilo je dosta, ponajviše iz Intela. Setimo se Dual Xeon serverskih mašina koje su, praktično, na ploči imale dva podnožja. Ipak, za običnog korisnika ovo nije zgodno rešenje. Revolucionarni dizajn bilo je postavljanje više procesorskih jezgara na jednu pločicu, a za prvi komercijalni uspeh zaslužan je IBM svojom serijom Power4 procesora.

Poštujući Murov zakon (Moore’s Law, Gordon Moore), broj tranzistora udvostručuje se svakih 12–24 meseci. Tako je, recimo, Pentium II 1997. godine imao 7,5 miliona tranzistora, dok je Itanium 2 iz 2004. godine imao 592 miliona, od čega većinu čini keš memorija. Ako pogledamo unapređenja kroz godine, videćemo da se sami procesori nisu mnogo promenili, a da je porast u broju tranzistora išao uglavnom umnožavanjem delova dizajna u cilju dodavanja veće količine keša. Naravno, i ovde postoje granice, te možete ići najdalje do one količine keša potrebne da smestite čitav radni set (kontekst) procesa. Dodavanje keša posle ove tačke nema nikakvog smisla.

Izrada višejezgarnih procesora deluje jednostavno, ali to zapravo nije tako. Dodavanje velikog broja jezgara, ma koliko ona bila prosta, mnogostruko povećava potrošnju električne energije. Iako su najveći proizvođači teoretski u mogućnosti da naprave pločicu sa više stotina jezgara, bila bi potrebna lična elektrana da bi je pokrenula, dok bi za njeno hlađenje bila potrebna ogromna količina tečnog azota. Jasno je da je za običnog korisnika ovo neprihvatljivo.

Kako funkcioniše

Slika 1

Najlakši primer na kojem se može videti rad višejezgarnog procesora jeste multitasking, to jest pokretanje više poslova (procesa) u istom trenutku. Na procesoru sa samo jednim jezgrom, može biti aktivan samo jedan proces u jednom trenutku. Ukoliko je pokrenuto više procesa, procesor koristi raspoređivač (scheduler) sa preuzimanjem (preemptive scheduling), koji odlučuje kako da rasporedi aktivne procese na osnovu posebnog algoritma.

Slika 2

Kod dvojezgarnog procesa, na primer, multitasking je olakšan jer sada na raspolaganju imamo dve procesorske jedinice koje mogu da izvršavaju procese u paraleli. Na taj način, moguće je, u isto vreme, recimo, surfovati Internetom u omiljenom pretraživaču, dok antivirusni program radi duboko skeniranje – sve to bez gubitka performansi.

U višejezgarnim procesorima još jedan bitan pojam dobija na snazi, a to je multithreading. Korišćenjem ove tehnologije jedan proces (aplikacija) deli se na više manjih koje se nazivaju nitima (threads). Niti dele adresni prostor procesa roditelja i jednostavno i brzo razmenjuju rezultate svoga rada. Na ovaj način, povećava se konkurentnost u radu, efikasnije se koriste jezgra i sistem je pouzdaniji. Osnovni dobitak u brzini izvršavanja vidljiv je kroz smanjenje čekanja na rezultat neke operacije (najčešće ulazno-izlazne, u komunikaciji sa periferijama). Pre nekoliko godina, u mikroarhitekturi Netburst (Pentium 4), Intel je uveo Hyperthreading, tehnologiju koja poboljšava rad sa nitima. Ova tehnologija ima osobinu da se u operativnom sistemu procesor vidi kao dve „logičke” procesorske niti, i tako omogućava izvršavanje dva procesa u paraleli. Performanse procesora koji koriste ovu tehnologiju povećane su za 15–30 odsto u odnosu na starije koji je ne poseduju.

Uloga operativnih sistema

Uspostavljanje višejezgarnih procesora kao dominantog tehnološkog trenda sa sobom je povuklo i softversku revoluciju o kojoj smo pisali u SK 9/2007. Izazovi koji su postavljeni pred programere u velikoj meri mogu biti olakšani uvođenjem podrške operativnog sistema na kojem se izvršavaju.

Postoje tri osnovna modela takve podrške:

• Asimetrično (Asymmetric multiprocessing, AMP)

• Simetrično (Symmetric multiprocessing, SMP)

• Vezano (Bound multiprocessing, BMP)

Asimetrično multiprocesiranje podrazumeva da se na svakom jezgru izvršava poseban operativni sistem, dok simetrično podrazumeva da jedan operativni sistem upravlja istovremeno svim jezgrima, pri čemu se aplikacije mogu izvršavati na bilo kom jezgru. Vezano procesiranje jeste kombinacija prva dva; i kod njega jedna instanca OS-a upravlja svim jezgrima, ali je svakoj aplikaciji dodeljeno tačno jedno jezgro. Kao i uvek, svaki od modela ima svoje prednosti i nedostatke.

AMP omogućava okruženje slično konvencionalnim jednoprocesorskim sistemima koje najveći broj softverskih inženjera dobro poznaje i razume. Istovremeno, ovaj model pruža mogućnost gotovo potpune kontrole svakog jezgra i korišćenja standardnih alata za projektovanje i debug. AMP, prema tipu OS-a, može biti homogen ili heterogen. Homogeni AMP ima operativne sisteme istog tipa i verzije, a heterogeni raznorodne. Korišćenjem homogenog tipa AMP-a i izborom odgovarajućeg OS-a, aplikacije (procesi) koje se izvršavaju na različitim jezgrima mogu transparentno da komuniciraju. Ukoliko koristi heterogeni AMP, programer mora ili da napiše odgovarajuće parče softvera za interprocesorsku komunikaciju (IPC), ili da koristi operativne sisteme sa sličnom infrastrukturom. Da bi se izbegli konflikti, operativni sistemi moraju da koriste standardizovane mehanizme pristupa deljenim resursima.

Slika 3

Recimo, ukoliko imamo dvojezgarni procesor, gde se na jednom jezgru izvršava operativni sistem GNU/Linux a na drugom QNX, među njima mora da postoji odgovarajući standardizovani protokol IPC, koji bi u ovom slučaju bio Transparent Inter-Process Communication Protocol (TIPC). U AMP modelu, proces će se uvek izvršavati na jednom jezgru, čak i kada je drugo u stanju mirovanja, što za rezultat ima činjenicu da je jedno jezgro ili previše ili premalo iskorišćeno. Rešavanje ovog problema svodi se na dozvoljavanje dinamičkog transfera aplikacija sa jezgra na jezgro, ali je takva mogućnost komplikovana za programiranje, pogotovu na različitim operativnim sistemima – u heterogenom tipu.

Najveći problem u programiranju operativnih sistema za višejezgarne procesore jeste alokacija resursa, s obzirom na to da su komponente softvera nesvesne potreba drugih delova, zbog raširenosti po jezgrima. Simetrično multiprocesiranje ovaj problem rešava tako što, zahvaljujući istom operativnom sistemu na jezgrima, može da se osloni upravo na OS da sam alocira resurse. Upravo je osobina operativnih sistema da bez veće komunikacije sa ostatkom sistema u svakom trenutku mogu alocirati potreban prostor za svaki nadolazeći proces. U ovom modelu, out-of-the-box (gledano spolja) izgled je kao da postoji samo jedan, veliki, operativni sistem koji vrši alokaciju. Ovako se i lakše prati rad sistema i mnogo bolje iskorišćavaju hardverski resursi, što se postiže omogućavanjem programerima da koriste POSIX sistemske pozive, posebno pthread API (Application Programming Interface), skup funkcija koji omogućava paralelno programiranje na Unix kompatibilnim sistemima, sa izuzetno dobrom dokumentacijom, i to je često u upotrebi. Neki operativni sistemi, poput QNX Neutrino, nude mogućnost da isti POSIX kôd bude korišćen i na jednojezgarnim i višejezgarnim procesorima. U ovom modelu, nitima je dozvoljeno da se dinamički preraspoređuju i izvršavaju na bilo kom jezgru, što umnogome povećava konkurentnost.

BMP multiprocesiranje nudi jednostavnost i transparentnost SMP-a, sa mogućnošču zaključavanja jednog procesa na jedno jezgro. Ovakav način rada omogućava da se aplikacije, pisane za jednojezgarni procesor, koriste bez modifikacija. Takođe, ovim je zagarantovana i podrška za legacy aplikacije i njihov suživot sa onima koje će moći da iskoriste pun potencijal višejezgarne tehnologije. Ovaj model garantuje izostanak problema u keš memoriji, s obzirom na to da se sve dešava na samo jednom jezgru, kompletan kontekst nije rasprostranjen u više keševa, već samo u jednom.

Koji model izabrati, pitanje je koje svaki programer treba sebi da postavi. Odgovor je da, u zavisnosti od potreba računara na kojem se kôd izvršava, treba izabrati odgovarajući model, ali i što robusniji operativni sistem, bilo da se radi o asinhronom ili sinhronom multiprocesiranju.

Paralelizam

Osnovu programiranja za višejezgarne procesore čini paralelizam. Bilo na nivou instrukcija procesora, bilo na nivou podataka, ova tehnika je od suštinske važnosti za raspodelu poslova za pojedinačna jezgra.

Slika 4

Na instrukcijskom nivou, paralelno izvršavanje moguće je ukoliko ne postoje zavisnosti po podacima između dve instrukcije koje posmatramo. Ukoliko razvijemo sve instrukcije date u sistemu u poseban aciklični graf zavisnosti po podacima, pri čemu grana između dva čvora postoji ukoliko postoji zavisnost, zavisnost po podacima u ovom slučaju jeste direktna prava zavisnost, a ona postoji ukoliko jedna operacija neposredno koristi rezultat druge operacije. Njihov redosled ne možemo promeniti upravo zbog zavisnosti među njima. Ukoliko uspemo da ustanovimo sve zavisnosti u određenom kodu, tada možemo napraviti graf i uvideti koje instrukcije mogu da se izvršavaju paralelno a koje moraju sekvencijalno. Ove informacije ključne su za funkcionisanje paralelizma na nivou instrukcija u jednojezgarnom procesoru, dok se u višejezgarnom mogućnosti proširuju.

Slika 5

Još jedna tehnika koja je posebno zgodna u upotrebi višejezgarnih procesora jeste paralelizam na nivou podataka. Srž ove tehnike čini cepanje velikih skupova podataka u manje koji se mogu obrađivati u paraleli. Nakon obrade, rezultati se kombinuju u celinu. Korišćenjem ovog metoda, programeri mogu aplikaciju koja jako slabo koristi više jezgara, da izmene i naprave je takvom da može da iskoristi jezgro više.

Pokazaćemo rezultate ove tehnike na primeru množenja matrica (vidi tabelu na kraju teksta).

Slika 6

Tehnika koju odavno koristimo, a koja dobija na značaju jeste i pajplajn (pipeline). Osnovni koncept ove ideje jeste da se svaka instrukcija podeli u faze. Jednostavnosti radi, pretpostavimo da se sve instrukcije jednog procesora mogu podeliti u četiri faze: dohvatanje, analiziranje, izračunavanje i zapisivanja rezultata. Ukoliko posedujemo četvorojezgarni procesor, možemo praktično izvršiti specijalizaciju svakog jezgra da se ono bavi samo dohvatanjem ili samo analizom. Tada, u paraleli možemo izvršavati četiri instrukcije (slika 6). U sekvencijalnom, ne-pajplajn sistemu, vreme izvršavanja bilo bi jednako zbiru vremena izvršavanja pojedinačnih aplikacija, dok je u pajplajn sistemu ono mnogo kraće. Zato su inženjeri procesora često koristili dugačke pajplajne, poput Pentiuma 4. Ipak, mnogo pažnje treba posvetiti balansiranju faza u pajplajnu – ukoliko postoje previše dugačke faze, performanse padaju.

Plima informacija

Koliko je samo tema programiranja za višejezgarne procesore popularna pokazuje i količina pretraga za ovim pojmom na najvećem web pretraživaču. Kriva koja opisuje interesovanje za ovu temu ima brži rast i od pojma „globalno zagrevanje”.

Količina informacija raste skoro eksponencijalno, a potpuni bum doživljava upravo u periodu od 2005. godine do danas. Dok je za vreme 2006. godine na ovu temu postovano nešto preko 300 blogova, u samo jednom mesecu u ovoj godini napiše se skoro 500 blogova koji opisuju ili ispituju neki aspekt ovog pojma. Svi veliki igrači na svetskom tržištu shvatili su ovu poruku i stoga ćete primetiti da Internet bruji od simpozijuma, promocija i predavanja na temu kako programirati za višejezgarne procesore.

• • •

Stručnjaci su do sada bili jedini koji su slobodno krstarili morem paralelnog programiranja, ali došlo je vreme da svoje kapetanske kape ustupe mladim dizajnerima softvera koje, uistinu, čekaju velike i burne oluje, teško savladive paradigme i algoritmi. Sve što je rečeno ide u prilog tome da je nužno da se promeni način gledanja na svet softvera i da se preduzmu svi neophodni koraci, od pisanja literature do uvođenja odgovarajućih kurseva na fakultetima, kako bismo mogli da pratimo vrtoglavi trend rasta broja jezgara na procesorskoj pločici. Samo u sprezi, hardver i softver garantuju pouzdanost i efikasnost koja nam je toliko bitna u vremenu u kojem živimo.

Momir ĐEKIĆ