Paralleelarvutus

Paralleelarvutus (inglise parallel computing) on arvutamise tüüp, kus paljud arvutused toimuvad samaaegselt.^[1] See tugineb põhimõttel, et tihtipeale saab suured probleemid jagada väikesteks osadeks, mida saab omakorda samaaegselt lahendada.

Parallelismi on rakendatud juba pikka aega, kuid huvi selle vastu on hiljuti kasvanud, sest protsessorite kiirustel tuleb füüsiline piir ette.^[2] Kuna protsessori kiiruse tõstmisel kasvab ka voolu tarbimine (ja seetõttu ka soojuseraldus)^[3], on paralleelarvutus saanud arvutiarhitektuuris domineerivaks paradigmaks – peamiselt mitmetuumaliste protsessorite näol.^[4]

Teoreetiline ülempiir, kui palju saab programmi paralleelarvutuse teel kiirendada, on määratud Amdhali seadusega.

Taustainfo

Tavaliselt on arvutitarkvara kirjutatud jadamisi arvutusteks. Arvutuse lahendamiseks moodustatakse algoritm, mida rakendatakse, kasutades ühte käskude jada. Need käsud käitatakse arvutis keskprotsessoril. Korraga saab käitada vaid üht käsu – kui see käsk saab täidetud, käitatakse järgmine.^[5]

Samas paralleelarvutuses kasutatakse korraga mitut protsessorit samaaegselt. Seda tehakse, jagades probleemi sõltumatuteks osadeks, et iga protsessor saaks oma osa paralleelselt teistega käitada. Need protsessorid võivad olla mitmekülgsed, näiteks arvuti mitme protsessoriga (või mitmetuumalise protsessoriga), mitu võrku ühendatud arvutit (vaata Hajusarvutus) või siis kombinatsioon neist.^[5]

Taktsageduse suurendamine oli valdav põhjus arvuti jõudluse parandamiseks 1980. aastate keskpaigast kuni 2004. aastani. Programmi käitusaeg on võrdne käskude arv korrutatud keskmise käsutäitmisajaga. Hoides muud parameetrid konstantsena ja suurendades taktsagedust, lühendame keskmist käsutäitmisaega.^[6]

Siiski, võimsuse tarbimine on määratud võrrandiga P= C × U² × F, kus C on mahtuvus, mida lülitatakse igal taktil, U on pinge ja F on protsessori taktsagedus (tsüklit sekundis).^[7] Seega taktsagedust tõstes tarbitav võimsus kasvab. Tarbitava võimsuse kasv viis 8. mail 2004 Inteli Tejas ja Jayhawk protsessorite arenduse lõpetamiseni, mida nimetatakse sageduse tõstmise kui valdava arvutiarhitektuuri paradigma lõpuks.^[8]

Amdahli seadus

Pikemalt artiklis Amdahli seadus

Amdahli seadus on informaatikas arvutiteadlase Gene Amdahli koostatud eeskiri, mis ennustab ligikaudselt, kui palju arvutiprogramm kiireneb juhul, kui osa programmist optimeeritakse.

Sõltuvused

Andmesõltuvusest (ingl k data dependency) aru saamine on fundamentaalne rööpalgoritmide implementeerimiseks. Ükski programm ei saa joosta kiiremini selle kõige pikemast sõltuvate arvutuste ahelast, sest eelmiste tehete tulemustest sõltuvad arvutused peavad olema käitatud jadamisi. Siiski – enamik algoritme ei koosne ühest pikast ahelast sõltuvatest arvutustest, vaid algoritmi osi on võimalik ka rööbiti käitada.

Võidujooksu olukord, vastastikune eraldamine, sünkroonimine ja paralleelne aeglustus

Alamülesandeid paralleelprogrammis kutsutakse lõimedeks. Lõimed peavad tihti uuendama mingit muutujat, mis on jagatud nende vahel. Käskude täitmise järjekord lõimede vahel pole teada. Seetõttu võib tekkida olukordi, kus üks lõim kirjutab muutujasse valel ajal ning seetõttu on väljundiks valed andmed. Kui kaks lõime tahavad samal ajal ühte muutujasse kirjutada, siis seda nimetatakse võidujooksu olukorraks (ingl k race condition). Programmeerija peab kasutama lukustamist, et tagada vastastikune eraldamine (ingl k mutual exclusion). Lukustamine on programmeerimisvõte, kus üks lõim võtab endale ühe muutuja ning ei lase teistel lõimedel sealt lugeda ega sinna kirjutada kuni ta oma operatsiooni on lõpetanud.

Võib tekkida ka lõimede vahel ummik (ingl k deadlock), kus üks lõim lukustab ühe ja teine teise muutuja ning seetõttu kumbki lõim ei saa enda käske lõpuni viia.

Paljud paralleelprogrammid nõuavad, et nende alamülesanded käiksid sünkroonis. Selleks kasutatakse tõkkeid (ingl k barrier). Tõkked tavaliselt implementeeritakse, kasutades tarkvaralisi lukustusi.

Alati rööbitamine ei tee programmi kiiremaks. Mida väiksemateks osadeks programm läheb, seda rohkem suureneb see osakaal, mil lõimed veedavad aega üksteisega suheldes. Lõpuks tuleb hetk, kus programm veedab rohkem aega suheldes, kui ülesannet täites ja edasine lõhestamine suurendab programmi käitusaega. Seda kutsutakse paralleelseks aeglustuseks (ingl k parallel slowdown).

Parallelismi tüüpe

Bititasemel parallelism

Väga-suure-mastaabi lõimingu (ingl k very-large-scale integration) arvutikiipide tootmise tehnoloogia sünnist saati 1970. aastatest kuni aastani 1986, arvutiarhitektuuri kiirendamine käis, duubeldades sõna suurust – infohulk, mida protsessor suudab töödelda ühes tsüklis.^[9] Sõna suurendamine vähendab käske, mida protsessor peab käitama, et opereerida muutujatega, mille väärtused on suurem kui sõna pikkus. Näiteks, kui 8-bitine protsessor peab liitma kaks 16-bitist täisarvu, siis protsessor peab alguses liitma alumised 8 bitti mõlemast täisarvust, kasutades tavalist liitmistehet ning seejärel peab liitma 8 ülemist bitti, kasutades ülekandega liitmise käsku ning ülekandebitti alumist järku liitmisest. Seega 8-bitine protsessor vajab kahte käsku, et ühte tehet teha, kus 16-bitine protsessor saaks selle tehte teha ühe käsuga.

Ajalooliselt, 4-bitised mikroprotsessorid asendati 8-bitiste, siis 16-bitiste, siis 32-bitiste mikroprotsessoritega. See mood sai läbi 32-bitiste protsessorite tulekuga, mis on olnud standardiks tavaarvutites juba kaks kümnendit. Alles hiljuti (u 2003–2004), x86-64 arhitektuuri sünniga, on 64-bitised protsessorid tavakasutusse tulnud.

Käsutasemel parallelism

Arvutiprogramm on loomu poolest käsuvoog, mis käitakse protsessori poolt. Ilma käsutasemel parallelismita saab protsessor käitada vähem kui üht käsu tsüklis. Need käsud saab ümber tõsta ning jagada gruppidesse, mida saab omakorda jooksutada rööbiti, muutmata programmi väljundit.

Ülesande parallelism

Ülesande parallelism on paralleelprogrammide omadus, kus täiesti erinevaid arvutusi saab teostada sama või erinevate andmehulkade peal. Ülesande parallelism koosneb ülesande jagamisest alamülesanneteks, mis seejärel rööbiti (ja tihti koostöös) käitakse.

Riistvara

Mälu ja suhtlus

Põhimälu paralleelarvutis on kas jagatud mälu (jagatud kõikide protsessorite vahel ühises aadressiruumis või hajutatud mälu (igal protsessoril on oma kohalik aadressiruum).^[10] Hajutatud mälu viitab sellele, et mälu on loogiliselt hajutatud, kuid tihtipeale ka füüsiliselt. Hajutatud jagatud mälu (ingl k Distributed Shared Memory) ja mälu virtualiseerimine ühendavad kaks lähenemist, kus protsessoril on oma kohalik mälu ning ligipääs mittelokaalsele mälule (mälu teistel protsessoritel). Juurdepääs lokaalsele mälule on enamasti kiirem, kui mittelokaalsele mälule.

Paralleelarvutite klassid

Paralleelarvuteid saab üldiselt klassifitseerida taseme järgi, kus parallelism riistvaraliselt toimub.

Mitmetuumaline arvutamine

Pikemalt artiklis Mitmetuumaline protsessor

Mitmetuumaline protsessor on kahe või enama tuumaga protsessor. Igal tuumal on oma täiturmootor, mis suudavad täita antud käske korraga. Tuumi võib vaadata kui mitut protsessorit, aga nad on omavahel ühenduses (võivad olla mitme kiibi peal): nad võivad üksteisega suhelda ja infot vahetada.

Sümmeetriline multitöötlus

Pikemalt artiklis Sümmeetriline multitöötlus

Sümmeetriline multiprotsessor (ingl k symmetric multiprocessor (SMP)) on arvutisüsteem, kus on mitu samasugust protsessorit, mis ühenduvad ja jagavad mälu siini kaudu.^[11] Siini kasutuspiirangute tõttu SMP-d ei koosne tavaliselt rohkem kui 32 protsessorist.

Hajusarvutus

Pikemalt artiklis Hajusarvutus

Hajusarvutus on töömahukate arvutusülesannete lahendamine, kasutades kahte või enamat arvutivõrku ühendatud arvutit.

Klasterarvutus

Pikemalt artiklis Klaster_(infotehnoloogia)

Klastriks nimetatakse infotehnoloogias gruppi omavahel ühendatud arvuteid, mis töötavad ühtse kogumina.

Massiivselt paralleelne arvutus

Massiivselt paralleelne protsessor (MPP) on üks arvuti paljude võrku ühendatud protsessoritega. MPP-del on suures osas samad omadused, mis klastritel, aga MMPdel on spetsiaalsed vastastikku seotud võrguühendused. MPP-d on ka reeglina suuremad kui klastrid, omades tavaliselt üle 100 protsessori. MPP-s iga keskprotsessor omab isiklikku mälu ja koopiat operatsioonisüsteemist ning programmist. Iga alamsüsteem suhtleb teistega kiire sisevõrguühenduse kaudu.^[12]

Võrkandmetöötlus

Pikemalt artiklis Võrkandmetöötlus

Võrkandmetöötlus ehk hajatöötlus (vahel ka võrkraalindus) on paljude võrku ühendatud arvutite üheaegne kasutamine ühe ülesande lahendamiseks.

Vektorprotessorid

Pikemalt artiklis Vektorprotsessor

Vektorprotsessor on keskprotsessor või arvutisüsteem, mis saab käitada sama käsku suurtel andmehulkadel.

Tarkvara

Paralleelprogrammeerimiskeeled

Samaaegsed programmeerimiskeeled, teegid ja mudelid on loodud, et programmeerida paralleelarvuteid.

Automaatne rööbitamine

Automaatne rööbitamine kompilaatori poolt on paralleelarvutuse püha graal. Hoolimata teadlaste kümnete aastate pikkusest tööst, automaatsel rööbitamisel on olnud vaid piiratud edu.

Programmi kontrollpunktid

Mida keerukamaks läheb arvutisüsteem, seda tihemini tekivad vead. Programmi kontrollpunktide loomine on võte, kus süsteem võtab hetktõmmise programmist, mida saab kasutada, et taastada programm juhul kui arvuti peaks üles ütlema.

Ajalugu

IBM tutvustas oma IBM 704 arvutit aastal 1954 läbi projekti, milles Gene Amdahl oli üks peaarhitektidest. Sellest sai esimene masstootmises arvuti, mis suutis käitada täisautomaatselt ujukomaarvudega aritmeetilisi käske.^[13]

Aprillis 1958, Stanley Gill arutles siirete ja ootamise vajaduse üle arvutustes.^[14] Samuti 1958. aastal, IBM-i teadlased John Cocke ja Daniel Slotnick arutasid esimest korda parallelismi kasutamist numbrilistes arvutustes.^[15] Burroughs Corporation tutvustas oma mudelit D825 aastal 1962 – nelja protsessoriga arvuti, mis suutis suhelda kuni 16 mälumooduliga.^[16] Aastal 1967, Amdahl ja Slotnick avaldasid debati paralleeltöötluse teostatavusest Ameerika Infotöötluseühingu Föderatsiooni konverentsil.^[15] Selle debati ajal võeti käsitlusse, et Amdahli seadus piirab parallelismi kaudu programmi kiirendamise.

Aastal 1969, firma Honeywell tutvustas enda esimest Multics-i süsteemi – sümmeetriline multiprotsessor, mis oli võimeline jooksutama rööbiti 8 protsessorit.^[15] C.mmp – 1970ndate multiprotsessori projekt Carnegie Melloni ülikoolis oli esimeste hulgas, millel oli rohkem kui mõni protsessor.^[17]

Vaata ka

Viited

↑ Gottlieb, Allan; Almasi, George S. (1989). Highly parallel computing. Redwood City, Calif.: Benjamin/Cummings. ISBN 0-8053-0177-1.
↑ 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."
↑ 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 limits."
↑ ^5,0 ^5,1 Barney, Blaise. "Introduction to Parallel Computing". Lawrence Livermore National Laboratory. Vaadatud 9. september 2007.
↑ Hennessy, John L.; Patterson, David A. (2002). Computer architecture / a quantitative approach (3rd ed.). San Francisco, Calif.: International Thomson. Lk 43. ISBN 1-55860-724-2.
↑ Rabaey, Jan M. (1996). Digital integrated circuits : a design perspective. Upper Saddle River, N.J.: Prentice-Hall. Lk 235. ISBN 0-13-178609-1.
↑ Flynn, Laurie J. (8. mai 2004). "Intel Halts Development Of 2 New Microprocessors". New York Times. Vaadatud 5. juuni 2012.
↑ Singh, David Culler ; J.P. (1997). Parallel computer architecture ([Nachdr.] ed.). San Francisco: Morgan Kaufmann Publ. Lk 15. ISBN 1-55860-343-3.
↑ Patterson and Hennessy, p. 713.
↑ Hennessy and Patterson, p. 549.
↑ MPP Definition. PC Magazine. Retrieved on November 7, 2007.
↑ da Cruz, Frank (2003). "Columbia University Computing History: The IBM 704". Columbia University. Vaadatud 8. jaanuar 2008.
↑ Parallel Programming, S. Gill, The Computer Journal Vol. 1 #1, pp2-10, British Computer Society, April 1958.
↑ ^15,0 ^15,1 ^15,2 Wilson, Gregory V (1994). "The History of the Development of Parallel Computing". Virginia Tech/Norfolk State University, Interactive Learning with a Digital Library in Computer Science. Vaadatud 8. jaanuar 2008.
↑ Anthes, Gry (19.11.2001). "The Power of Parallelism". Originaali arhiivikoopia seisuga 31.01.2008. Vaadatud 8. jaanuar 2008.
↑ Patterson and Hennessy, p. 753.

[ukUnp-1] Gottlieb, Allan; Almasi, George S. (1989). Highly parallel computing. Redwood City, Calif.: Benjamin/Cummings. ISBN 0-8053-0177-1.

[BAAqr-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."

[R5eNQ-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 limits."

[llnltut-5] 5,0 ^5,1 Barney, Blaise. "Introduction to Parallel Computing". Lawrence Livermore National Laboratory. Vaadatud 9. september 2007.

[oP9cS-6] Hennessy, John L.; Patterson, David A. (2002). Computer architecture / a quantitative approach (3rd ed.). San Francisco, Calif.: International Thomson. Lk 43. ISBN 1-55860-724-2.

[vbeod-7] Rabaey, Jan M. (1996). Digital integrated circuits : a design perspective. Upper Saddle River, N.J.: Prentice-Hall. Lk 235. ISBN 0-13-178609-1.

[61vw7-8] Flynn, Laurie J. (8. mai 2004). "Intel Halts Development Of 2 New Microprocessors". New York Times. Vaadatud 5. juuni 2012.

[PJlQF-9] Singh, David Culler ; J.P. (1997). Parallel computer architecture ([Nachdr.] ed.). San Francisco: Morgan Kaufmann Publ. Lk 15. ISBN 1-55860-343-3.

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

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

[fi2JF-12] MPP Definition. PC Magazine. Retrieved on November 7, 2007.

[AKcnq-13] Cruz, Frank (2003). "Columbia University Computing History: The IBM 704". Columbia University. Vaadatud 8. jaanuar 2008.

[2jX5q-14] Parallel Programming, S. Gill, The Computer Journal Vol. 1 #1, pp2-10, British Computer Society, April 1958.

[G_Wilson-15] 15,0 ^15,1 ^15,2 Wilson, Gregory V (1994). "The History of the Development of Parallel Computing". Virginia Tech/Norfolk State University, Interactive Learning with a Digital Library in Computer Science. Vaadatud 8. jaanuar 2008.

[Dzp5h-16] Anthes, Gry (19.11.2001). "The Power of Parallelism". Originaali arhiivikoopia seisuga 31.01.2008. Vaadatud 8. jaanuar 2008.

[PH753-17] Patterson and Hennessy, p. 753.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]