Paralleelarvutus

Paralleelarvutus (inglise "parallel computing") on arvutamise tüüp, kus paljud arvutused toimuvad samaaegselt.
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.
Kuna protsessori kiiruse tõstmisel kasvab ka voolu tarbimine (ja seetõttu ka soojuseraldus), on paralleelarvutus saanud arvutiarhitektuuris domineerivaks paradigmaks – peamiselt mitmetuumaliste protsessorite näol.
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.
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.
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.
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). 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.
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. 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). Hajutatud mälu viitab sellele, et mälu on loogiliselt hajutatud, kuid tihtipeale ka füüsiliselt. Hajutatud jagatud mälu (ingl k ) 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.
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.
Sümmeetriline multiprotsessor (ingl k on arvutisüsteem, kus on mitu samasugust protsessorit, mis ühenduvad ja jagavad mälu siini kaudu. Siini kasutuspiirangute tõttu SMP-d ei koosne tavaliselt rohkem kui 32 protsessorist.
Hajusarvutus.
Hajusarvutus on töömahukate arvutusülesannete lahendamine, kasutades kahte või enamat arvutivõrku ühendatud arvutit.
Klasterarvutus.
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.
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.
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.
Aprillis 1958, Stanley Gill arutles siirete ja ootamise vajaduse üle arvutustes. Samuti 1958. aastal, IBM-i teadlased John Cocke ja Daniel Slotnick arutasid esimest korda parallelismi kasutamist numbrilistes arvutustes.
Burroughs Corporation tutvustas oma mudelit D825 aastal 1962 – nelja protsessoriga arvuti, mis suutis suhelda kuni 16 mälumooduliga.
Aastal 1967, Amdahl ja Slotnick avaldasid debati paralleeltöötluse teostatavusest Ameerika Infotöötluseühingu Föderatsiooni konverentsil. 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. C.mmp – 1970ndate multiprotsessori projekt Carnegie Melloni ülikoolis oli esimeste hulgas, millel oli rohkem kui mõni protsessor.