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äitakse arvutis keskprotsessoril. Korraga saab käitada vaid ühe käsu – kui see käsk saab täidetud, käitakse 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.
Sageduse tõstmine oli valdav põhjus arvuti jõudluse parandamiseks 1980ndate keskpaigast kuni 2004. aastani. Programmi käitusaeg on võrdne käskude arv korrutatud keskmise käsutäitmisajaga. Hoides muud parameetrit konstantsena, suurendades taktsagedust, vä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.

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).

Bititasemel parallelism

Väga-suure-mastaabi lõimingu (ingl k very-large-scale integration) arvutikiipide tootmise tehnoloogia sünnist saati 1970ndatest 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 ühe 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.

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 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.

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.

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.