Rinnakkaisčotaičendu on olluh suuri uskalmo jo mondu kymmendy vuottu, yhtelläh sen käyttö on marginualistu. Ga pidäy sanuo, erähis ruadolois, kui siän ennustamises, rinnakkaisčotaičendu nygöigi on ylen tärgei. Syy rinnakkaisčotaičendan vähäh käyttöh on se, gu laitehtehniekku da algoritmiekku ei olla vastavuttu. Kačommo täs kui luadie protsessoru muga, ku ohjelmoijale olis kebjei suaja protsessoran ydimet tehokkahah käyttöh.
Hos Mooren zakonan jyttyine mielivaldaine zakon ongi hätken niärittänyh luonnonzakonoi, onhai selvy, ku muga ei voi jatkuo agjattah - eihäi transistoru voi olla pienembi atomua. Liččuandurigevys voi vie kodvan kazvua, ga tulou aigu, konzu johtoloin hoikkevus algau tuvva keral satunnazii ilmivölöi. Toine suuri probliemu, suures liččuandurigevyös da korgies čuassufrekvenzas johtui lämmöntuotando, on jo tulluh vastah. Kolmas probliemu on tiijon suandan hil'l'us. Konzu čuassufrekvenzu on 3 GHz, valgo siirdyy čuassusiklan aigan tyhjivösgi vai kymmene sentimetrua da sentäh protsesoran pidäy vuottua loitombi tulijua tieduo. Ližäkse jogahizel komponental on oma hil'l'us. Nämmien fiiziellizien rajoin ližäkse suuri, toinah kaikis suurin ravevuttu rajoittai šeikku on tiedoloinkäzittelytiijolline: kui käyttiä parahal taval kai protsessoran pindu muga kui sie olijat komponentat annettas paras hyödy čotaičendale.
Nämmä probliemat ollah tuldu protsessorutevollizuttu vastah muga vagavah, ku erähät jo ollah sanottu, ku "protsessorutevollizus on paniikas". Jokse tulijan vuon kuluttai ei sua kahtu verdua tämänvuodehistu tiedokonehtu? Hos kui ližiämäl komponentua protsesorale libo čuassufrekvenzua nostamal tiedokoneh vai ei ravene. Täs tilandehes fuabriekat ollah ruvettu rakendamah mikropiirile yhten protsesoran sijah monii protsessoruydimii muga duumaijen, ku monel protsesoral voi suaja monenkerdahizen ravevuon. On syydygi "paniikkah" sendäh, ku čotaičenduravevus ei automuattizesti kazva protsessoroin lugumiäränke. Pidäy tiediä kui panna protsesorat yhteisruadoh, ku se vai ollou mahtollistu. Sama probliemu on kaikil rinnakkaistiedokonehil: rinnakkazus avvuttau vai, ku čotaičenduproblieman voi jagua rinnakkai suoritettavih paloih. Sendäh, ku tahtonemmo enämbi tehuo tiedokonehis, pidäy ellendiä rinnakkaisčotaičendua. Rinnakkaistiedokonehet da rinnakkaine tiedoloinkäzittely ollah ajankohtazemmat kui nikonzu.
Kahten jälgimäzen vuozikymmenen aigan mikroprotsesoroin kehitys on olluh raviedu. Mikrotiedokonehien suuren kyzyndän periä protsessorutevollizuol oli dengua kehittiä nengomis tiedokonehis käytettävii protsessoroi da sendäh protsesoindutehuo algoi kaikis huogevimbal suaja standartuprotsesorois. Algavui "massiivizesti rinnakkazien" hajautettuu mustuo käyttäjien rinnakkaistiedokonehien aigukauzi. Suundua täl kehityksel näytti vuonnu 1985 rakendettu Caltech Cosmic Cube, kudamas oli 64 Intel 8086/87 protsessorua da joga protsessoral 128 KB mustuo. Protsessorat oli liitetty toine toizeh 6-ulottehizel hiperkuubikal. Yhtehisty mustuo vouse ei olluh, a ohjelmoindas pidi käyttiä viestinvälitysmallii. Cosmic Cube oli sen aijan huogei "mini-supertiedokoneh", kudaman teho oli 3 MFLOPS. Sen nygyaigazes perillizes Roadrunner -nimizes supertiedokonehes on (kezäkuus 2008) 116640 protsessorua da čotaičenduteho on 1.026 PFLOPS (P=peta=1015).
Konzu tiedoverkot kehityttih da halvenduttih, käzitys rinnakkaisčotaičendas myös leveni. Roih mahto yhtistiä joukko tehokkahii työazemii raviel lähiverkol klusterakse, kudamua ohjelmoijah viestinvälitysmallin mugahizel ohjelmukirjastol, nengomal kui MPI [mpi]. Beowulf [beowulf] on ezimerki "keyhän miehen" klusteras. Ylen jygieh čotaičendah voi käyttiä supertiedokonehii Grid-verkon yliči [grid]. Konzu nengoine hajauttamine viijäh agjassah, voi kyzyö ollahgo kai Internettah liitetyt tiedokonehet yksi suuri rinnakkaistiedokoneh. SETI projektu [seti] käyttäy hyväkse mostu rinnakkai čotaičendua. Top500-listal [Top500] nägyy, ku tehočotaičendas jälgimäzen kymmenen vuvven aigan yhtehizen muston konehien vuitti on vähendynnyh 50 protsentas läs nägymättömih, ga sežo massiivizen rinnakkazuon hajautetun muston konehiengi vuitti on pienendynyt. Klusterat ollah nostu suurimbakse.
Konzu ruvettih rakendamah tiedokonehii, kudamis on enämbi yhty protsessorua, pidi malliegi luajendua, roih PRAM (Parallel RAM) [FW78], kudamas joukko protsessoroi käyttää yhty yhtehisty mustuo, kačo Kuvua 1a. Täs mallis oletetah, ku mondu protsessorua voi yhtelaigua lugie libo kirjuttua yhty da samua mustopaikkua da nämmä operatsiet voi kerras panna toimeh vuottamattah.
Rinnakkaisalgoritmoin teorii terväh kehityi da kahteskymmenes vuvves hyvin rubeimmo ellendämäh kui jagua ruado rinnakkai suoritettavih paloih. Ylen äijän rinnakkai suoritettavua löydyygi [Ja92].
![]() |
Kuva 1. Rinnakkaisčotaičendan mallit: |
(a) Yhtehizen muston malli da (b) hajautetun muston malli |
PRAM-malli on sigäli ylen hyvä rinnakkaisčotaičendan malli, ku se on yksinkerdaine: rinnakkazuoh niškoi ohjelmoindukieleh täydyy ližätä vai yksi ohjuandurakendeh, PARDO-petlu: sen sižäl olijat käskyt suoritetah rinnakkai. PRAM-malli pädöy ozuttamah, äijängo čotaičendutehtäväs löydyy rinnakkai suoritettavua ozatehtäviä, šäijehty. Sentäh PRAM algoritmukirjallizus on bohattu [Ja92]. Toven sanuo, muudu pättäviä rinnakkaisčotaičendan teoriedu ei ni ole kui PRAM-algoritmiekku.
Konzu PRAM-malli kehityi, rinnakkaistiedokonehien suunnittelijatgi opittih luadie tiedokonehii muga kui niilöil vois suorittua PRAM-algoritmoi. New York University Ultracomputer [AG94] da SB-PRAM [BB97] ollah nengomii konehii. Tera MTA (MultiThread Architecture) rinnakkaistiedokoneh [AC90] on sigäli tärgei PRAM-arhitektuuru, ku se on viegi tuotandos CRAY XMT -nimizenny.
Mikroprotsessoroin ravien kehityksen vuozinnu tiedokonehsuunnittelun valduvirdu algoi kiändyö toizeh čurah. Kaiče yhtes mikroprotsessoras oli enämbi vägie kui suures tiedokonehjärjestelmäs. Äijän tehuo vuadijah čotaičendah oli huogei liittiä yhteh protsessoroi muistinke Kuvan 1b jyttyöh. Viestinvälitysmallin mugah ohjelmoiju lähettäy ohjelman paloi toizih protsessoinduyksikkölöih suoritettavakse. Ero idealizen välittömän mustosuandan da tovellizen tiedokonehen hil'l'an mustosuandan välil algoi kazvua liijan suurekse.
Vuvvennu 1993 jullattih LogP nimine rinnakkaisčotaičendan malli, kudamua sanottih "realistizekse", kui vastukohtannu PRAM-mallile kudamua piettih ebärealistizennu. Täs mallis kirjaimet LogP viitatah konehen ominazuksih: latensu (verkon hil'l'us), komponentoin hil'l'us, juamanlevevys da protsessoroin lugu, kudamat pidäy ottua čottah ohjelmua kirjuttajes. Malli on äijiä tarkembi kui PRAM, ga se siirdäy vastuon tehokkuos ohjelmoijale. Ku ohjelmoiju joudunnou suunnittelemah ohjelman lougiekan, jagamah ohjelman protsessoroile viestinvälityksel, da vie ottamah luguh kai nämmä parametrat, ohjelmoindu rodieu ylen vaigei.
Vähä liijoitellen voi sanuo, ku rinnakkaisčotaičendas on vai pahoi vaihtoehtoloi: PRAM-mallin mugahistu rinnakkaistiedokonehtu on helpo ohjelmoija a mahtotoi rakendua; sidä vastoi LogP-mallin da viestinvälitysmallin mugahine tiedokoneh on helpo rakendua a mahtotoi ohjelmoija. On tozi, ku massivizesti rinnakkaizii tiedokonehii da klusteroi käytetäh tehokkahasti suurih čotaičenduruadoloih, a azien toine puoli on se, ku rinnakkaisčotaičendu on marginualizoidunnuh jällekkäis-čotaičendah verraten.
Naivi PRAM-mallin kritiekku perustuu oletukseh, ku protsessoran pidäs suaja tiedo kerras mustospäi protsessorah käziteldäväkse, midä ei voi tehnillizesti todevuttua. Olis hyvä, ku ohjelmoiju vois ohjelmoija PRAM-mallin mugah, ga fiiziellizen tiedokonehen ei välttämättäh tarviče olla PRAM. Gu vai ohjelmas ollou tarbehekse toine toizis rippumattomii šäigehii, enämbi kui protsessoriloi, suoritusvuoruo vuottajat šäigehet voijah vuotanduaigannu suaja mustospäi tarvittavat tiijot, da protsessorat ollah kaiken aigua hyödykäytös. Tädä sanotah rinnakkaizen vällyön (angl. slackness) periuattehekse [Va90,Pe07]. PRAM-mallin mugahine rinnakkaisčotaičendan teorii tariččou suuren joukon algoritmoi kudamat käytetäh suurdu miäriä (virtualizii) protsessoroi. Sikse ku kai šäigehet suadas tarvittavat tiijot aijoinaijal, pidäy konehes olla tarbehekse juamanlevevytty. Protsessoroin miärän da kommunikatsiiverkon pidäy olla tazapainos [LP07].
Hos ohjelmoindas voibigi käyttiä MPI:n jyttymiä rajapindua, se on arhitektuuras rippujua da sendäh liijan vaigiedu ohjelmoijale. Toizel puolel, net oletukset kudamien mugah PRAM-malli hyllättih 1990-luvul, nygöi jo ei täyzin päitä. Keskittymine jällekkäisprotsessoran tehon nostoh on rajoitannuh tehnolougizien mahtoloin hyväksekäyttyö. Kummakas tovestus täs on se, ku hengikohtallizes tiedokonehes näytönohjaimennu voi olla graafiekkupiiri (ezim. Nvidia GeForce GTX 280, kudamas on 240 protsessorua), kudai on mondu verdua tehokkahembi rinnakkaistiedokoneh kui tiedokonehen piäprotsessoru. Nerokkahimmat halvan čotaičendutehon eččijät ruvettih "viärinkäyttämäh" graafiekkuprotsessorua rinnakkaistiedokonehennu [CUDA]. Kuibo hyvä rinnakkaisprotsessoru siidy olis roinnuh, ku se olis allus algajen suunniteldu rinnaikkaisčotaičendah niškoi? Ihan jälgiaijal moine rinnakkaisprotsessoran prototiippu (Kuva 2) ongi luajittu. Protsessoran tuatto Uzi Vishkin on käyttähyh konehes nimie "PRAM on Chip", a nygöi sil on annettu nimi "Paraleap".
![]() |
Kuva 2. Paraleap-protsessoru tiedokonehes. Kuva Vishkinan luval. |
Nygyaigazel protsessorupiiril voi olla mondu miljardua komponentua. Jälgiaijal, konzu lämmön täh jo ei voi ylen äijäl nostua čuassufrekvenzua, on ruvettu liččuamah piirile mondu protsessorua, toivehennu muga kazvattua čotaičendutehuo. Paraleap protsessoras tämä ajatus on kehitetty korgiembale - se on allus algajen luajittu suorittamah PRAM-mallin mugahistu hienoragehellizesti rinnakkastu ohjelmua.
![]() |
Kuva 3. Paraleap-protsessoran rakendeh. |
Paraleap protsessoran rakendeh nägyy Kuvas 3. MTCU (Master Thread Control Unit) vastuau jällekkäisuoritukses da kogo protsessoran toimindas, P:t ollah rinnakkaisuorituksen protsessorat (Paraleapas niidy on 64), PSU on prefiksusummuyksikkö da Reg on joukko registerilöi. Piirin sižäine verko yhtistäy prosessorit ulgopuolel olijoih mustoloih M välimustoloin C kauti. Prefiksusummuyksiköl on ylen tärgei rouli protsessoriloin ruavonjavos. PSU todevuttau operatsien
ps(R,B): R,B := B,B+Rkudai mondu kerdua jällekkäi suoritettunnu todevuttau prefiksusumman. Tottu paisten Paraleap protsessoran PSU on jällekkäine operatsii, ga se on muga ravei, ku käyttäjile ozutahes kui hyö kerras suadas pyvvetyn sluužban.
Prefiksusummu on PRAM-jyttyön rinnakkaisalgoritmiekan perusruadovehkeh, kudaman vuoh ruavon voi jagua protsessoroile. Operatsii on hyvin yksinkerdaine. Ezimerkikse lugujonon 3,1,4,1,5,9 prefiksusummu on 3,4,8,9,14,23. Jällestulii ezimerki ozuttau kui senke haldivoijah rinnakkazuttu Vektoran kompaktoindan libo nulien iärehottamizen vektoraspäi A voi luadie täl PRAM ohjelmal:
for i=0..n-1 pardo if A[i]=0 then C[i]:=0 else C[i]:=1 E := prefix-sum(C) for i=0..n-1 pardo if A[i]<>0 then B[E[i]]:=A[i]Prefiksusumman vuoh iče kompaktoindah (kaksi pardo-petlua) menöy vai O(1) aigu.
Paraleap protsessoran ohjelmoindukielel XMT-C sama ohjelmu kirjoitetah muvvos
psBaseReg x=0 spawn(0,n-1){ int e; e=1; if (A[$]!=0) { ps(e,x); B[e]=A[$]; } }Tämä on nengozennu Paraleap-tiedokonehes suoritettavu ohjelmu.
Paraleap tovelleh on fiiziellizesti olemasolii, toimii protsessoru. Se on todevutettu 75 MHz FPGA-piiril (Field Programmable Gate Array), kačo Kuvua 2. Myöhembi protsessoru ruvetah luadimah 800 MHz ASIC-piirile (Application-Specific Integrated Circuit), senke suoritus ravevuu. Prototiipan testuajoloin mugah [WV08], net kaheksa ohjelmua kudamat kuuluttih testah, ruvetah toimimah ASIC-piiril 1.6-9 kerdua raviembah kui 2.6 GHz AMD Opteron protsessoru.
Toivommo, ku Vishkinan Paraleap olis se "Kolumbuksen jäiččy", kudai hävittäy mentualizet estiet rinnakkaisčotaičendan kehityksel. PRAM ei ole mahtotoi, päinvastoi, se on lubavuksiiandai, ohjelmoijuystävälline taba ottua käyttöh protsessoran pindu nygöi, ku jällekkäissuorituksel jo ei voi ylen äijäl tehuo ližätä. PRAM algoritmiekku tariččou algoritmoi, kudamil tehtävät voijah jagua suurekse joukokse rinnakkai suoritettavii šäigehii. PRAM-protsessoru on fiizielline alustu, kudamal nämmie šäigegii voi raviezeh suorittua.
Paraleap on ehtotus, kui todevuttua rinnakkazus mikropiiril. Suures čotaičendas pidäy enämbi yhty protsessorua. Kui rakendua suuri helpoh ohjelmoidavu rinnakkaistiedokoneh? PRAM protsessorois pidäs voija rakendua suuri PRAM tiedokoneh muga ku se ozutahes ohjelmoijale yhtenny PRAM-mallin mugahizennu tiedokonehennu, kudamua voi ohjelmoija pardo-petlal. Nengoine ehtotus on ezim. [LP95,FLP96]. Tiedoloinkäzittelytiijos ohjelmoiju on ainos avainroulis. Jällekkäistiedokonehen aijal školitut ohjelmoijat on opastettu jällekkäzeh ajatteluh - ohjelmu pidäy pakoittua yhtekse jonokse jällekkäzii operatsieloi. Nengoine ajatusmalli ei päi rinnakkaistiedokonehien ohjelmoindah. Pidäy ruveta löydämäh ruavos net šäigehet, mit voijah suorittua toine toizis rippumattah rinnakkai. Erähičči rinnakkaisohjelmoindu voi olla vaigiembua kui jällekkäisohjelmoindu, toiči helpombuagi, ga erilastu. Sentäh ohjelmoijii pidäy ruveta opastamah eri luaduh.
[AG94] G.S. Almasi, A. Gottlieb. Highly Parallel Computing. Benjamin/Cummings, 1994.
[BB97] P. Bach, M. Braun, A. Formella, J. Friedrich, T. Grun, C. Lichtenau. "Building the 4 processor SB-PRAM prototype." In Proc. of the 30th Hawaii International Conference on System Sciences: Advanced Technology Track - Vol. 5, 1997.
[beowulf] http://www.beowulf.org
[CKP93] D.E. Culler, R.M. Karp, D.A. Patterson, A. Sahay, K.E. Schauser, E. Santos, R. Subramonian, T. von Eicken. "LogP: Towards a realistic model of parallel computation." In Principles Practice of Parallel Programming, pp 1-12, 1993.
[CUDA] http://www.nvidia.com/cuda
[FLP96] M. Forsell, V. Leppänen, M. Penttonen. "Efficient two-level mesh based simulation of PRAMs". International Symposium on Parallel Architectures and Networks. Peking, (I-SPAN'96), 29-35.
[FW78] S. Fortune, J. Wyllie. "Parallelism in Random Access Machines". In Proc. 10th ACM Symposium on Theory of Computing, pp 114-118, 1978.
[grid] http://www.grid.org
[Ja92] J. J'aj'a. An Introduction to Parallel Algorithms. Addison Wesley, 1992.
[LP95] V. Leppänen, M. Penttonen. "Work-Optimal Simulation of PRAM Models on Meshes" Nordic Journal of Computing 2 (1995), 51-69.
[LP07] V. Leppänen, M. Penttonen. "Sparse Networks: balance of processing and communication". Proc. Workshop on Advances in Methods of Modern Information Techology. Petrozavodsk, 2007.
[Mo65] G.E. Moore. "Cramming more components onto integrated circuits". Electronics 38(8), 1965.
[mpi] http://www.mpi-forum.org
[Pe07] M. Penttonen. "Rinnakkaisalgoritmit ja rinnakkaistietokoneet". Tietojenkäsittelytiede 26:9-21 (2007).
[seti] http://setiathome.ssl.berkeley.edu
[Top500] http://www.top500.org
[Va90] L.G. Valiant. "General Purpose Parallel Architectures". In Handbook of Theoretical Computer Science, Ed. Jan van Leeuwen, Elsevier and MIT Press, volume~1. Elsevier Science, 1990.
[WV08] X. Wen, U. Vishkin. "FPGA-based prototype of an PRAM-On-Chip processor." Computer Frontiers 2008, May 5-7, 2008.