"Parallelism kui paralleelse andmetöötluse meetod"

Kotovsk 2010

Sissejuhatus

Teaduse kiire areng ja inimmõtte tungimine üha uutele valdkondadele koos varem püstitatud probleemide lahendamisega tekitab pidevalt küsimuste voogu ja seab uusi, tavaliselt keerulisemaid ülesandeid. Esimeste arvutite ajal tundus, et nende kiiruse suurendamine 100 korda lahendab enamiku probleemidest, kuid tänapäevaste superarvutite gigaflop-jõudlus on paljudele teadlastele ilmselgelt ebapiisav. Elektri- ja hüdrodünaamika, seismilised uuringud ja ilmaennustused, keemiliste ühendite modelleerimine, virtuaalreaalsuse uuringud – see ei ole täielik loetelu teadusvaldkondadest, mille uurijad kasutavad kõiki võimalusi oma programmide elluviimise kiirendamiseks.

Kõige lootustandvam ja dünaamilisem suund rakendusprobleemide lahendamise kiiruse suurendamiseks on paralleelsuse ideede laialdane juurutamine arvutussüsteemide töösse. Tänaseks on projekteeritud ja testitud sadu erinevaid arvuteid, mille arhitektuuris on kasutatud üht või teist paralleelset andmetöötlust. Teaduskirjandusest ja tehnilisest dokumentatsioonist võib leida üle tosina erineva nimetuse, mis iseloomustavad vaid paralleelsete masinate toimimise üldpõhimõtteid: vektor-pipeline, massiliselt paralleelsed, laia käsusõnaga arvutid, süstoolsed massiivid, hüperkuubikud, eriprotsessorid ja multiprotsessorid, hierarhilised ja kobararvutid, andmevoog, maatriksarvutid ja paljud teised. Kui kirjelduse täiendamiseks lisame andmed selliste oluliste parameetrite kohta nagu näiteks mälu korraldus, protsessoritevahelise suhtluse topoloogia, üksikute seadmete töö sünkroniseerimine või aritmeetiliste toimingute sooritamise meetod, siis erinevate arhitektuuride arv muutub täiesti arusaamatuks.

Katsed kogu arhitektuurikomplekti süstematiseerida algasid pärast seda, kui M. Flynn avaldas 60. aastate lõpus arvutussüsteemide klassifikatsiooni esimese versiooni ja jätkub pidevalt tänapäevani. Klassifitseerimine on uuritava ainevaldkonna paremaks mõistmiseks väga oluline, kuid eduka klassifikatsiooni leidmisel võib olla mitmeid olulisi tagajärgi.

Klassifikatsiooni põhiküsimust - millest selle aluseks võtta - saab lahendada erinevalt, sõltuvalt sellest, kelle jaoks see klassifikatsioon luuakse ja millise probleemi lahendamisele see on suunatud. Seega võimaldab sageli kasutatav arvutite jaotus personaalarvutiteks, tööjaamadeks, miniarvutiteks, suurarvutiteks, minisuperarvutiteks ja superarvutiteks ehk ligikaudselt hinnata arvuti maksumust. See aga ei vii kasutajat lähemale arusaamisele, mida temalt nõutakse, et kirjutada programm, mis töötab paralleelarvuti jõudluse piiril, s.t. milleks ta otsustas seda kasutada.

Klassifikatsioon peaks aitama mõista, mis on iga arhitektuur, kuidas need on omavahel seotud, mida tuleb tõeliselt tõhusate programmide kirjutamiseks arvesse võtta või millisele arhitektuuriklassile tuleks sihtida, et vajaliku klassi probleeme lahendada. Samas võiks edukas klassifikatsioon soovitada võimalikke viise arvutite täiustamiseks ja selles mõttes peaks see olema üsna mõttekas. Raske on loota mittetriviaalsete „pimenurkade” leidmist näiteks maksumuse järgi klassifitseerimisel, kuid programmeerimise lihtsuse ja valmistatavuse aspektist võimalikule taksonoomiale mõtlemine võib olla äärmiselt kasulik uute otsingute suundade määramisel. arhitektuurid.

1. Paralleelsed arvutussüsteemid

Paralleelarvutussüsteemid on füüsilised arvuti- ja tarkvarasüsteemid, mis rakendavad ühel või teisel viisil paralleelset andmetöötlust paljudes andmetöötlussõlmedes.

Rööparvutuse idee põhineb ideel, et enamikku probleeme saab jagada väiksemateks probleemideks, mida saab üheaegselt lahendada. Tavaliselt nõuab paralleelarvutus koordineerimist. Paralleelne andmetöötlus esineb mitmel kujul: bititaseme paralleelsus, käsutaseme paralleelsus, andmete paralleelsus ja ülesannete paralleelsus. Rööparvutust on kasutatud juba aastaid, peamiselt kõrgjõudlusega andmetöötluses, kuid viimasel ajal on huvi selle vastu suurenenud, kuna protsessorite taktsageduste kasvule on seatud füüsilised piirangud. Paralleelarvutus on muutunud arvutiarhitektuuris domineerivaks paradigmaks, peamiselt mitmetuumaliste protsessorite näol.

Paralleelsete süsteemide jaoks on programmide kirjutamine keerulisem kui järjestikuste jaoks, kuna konkurents ressursside pärast toob kaasa uue potentsiaalsete tarkvaravigade (vigade) klassi, mille hulgas on kõige levinumad võistlustingimused. Protsessidevaheline suhtlus ja sünkroniseerimine on suureks takistuseks paralleelsüsteemides kõrge jõudluse saavutamisel. Viimastel aastatel on hakatud mõtlema ka paralleelarvutite energiatarbimise küsimusele. Paralleliseerimise tagajärjel tekkiva programmi kiiruse suurenemise olemust selgitab Amdahli seadus.

Kui arvutus ei hõlma tsüklilisi (korduvaid) toiminguid, ei teosta N arvutusmoodulit kunagi tööd N korda kiiremini kui üks arvutusmoodul.

Näiteks massiivi kiireks sortimiseks kahe protsessoriga masinas saate massiivi pooleks jagada ja iga poole sortida eraldi protsessoris. Iga poole sortimine võib võtta erineva aja, seega on sünkroonimine vajalik.

2. Paralleelsuse tüübid

2.1 Bititaseme paralleelsus

See paralleelsuse vorm põhineb masinsõna suuruse suurendamisel. Masinasõna suuruse suurendamine vähendab toimingute arvu, mida protsessor vajab toimingute tegemiseks muutujatega, mille suurus ületab masinasõna suurust. Näiteks: 8-bitise protsessori puhul peate lisama kaks 16-bitist täisarvu. Selleks tuleb esmalt lisada numbrite alumised 8 bitti, seejärel lisada ülemised 8 bitti ja lisada nende liitmise tulemusele ülekandelipu väärtus. Kokku 3 juhist. 16-bitise protsessoriga saate seda toimingut teha ühe käsuga.

Ajalooliselt asendati 4-bitised mikroprotsessorid 8-bitiste mikroprotsessoritega, millele järgnesid 16-bitised ja 32-bitised mikroprotsessorid. 32-bitised protsessorid on juba pikka aega olnud igapäevase andmetöötluse standard. Tehnoloogia x86–64 tulekuga hakati nendel eesmärkidel kasutama 64-bitiseid protsessoreid.

2.2 Käsutasandi paralleelsus

Arvutiprogramm on sisuliselt protsessori poolt täidetavate juhiste voog. Kuid saate muuta nende juhiste järjekorda, jagada need rühmadesse, mida täidetakse paralleelselt, ilma kogu programmi tulemust muutmata. Seda tehnikat tuntakse käsutaseme paralleelsusena. Edusammud arvutiarhitektuuri juhiste taseme paralleelsuse arendamisel toimusid 1980. aastate keskpaigast 1990. aastate keskpaigani.

Kaasaegsetel protsessoritel on mitmeastmeline juhiste konveier. Konveieri iga etapp vastab konkreetsele toimingule, mille protsessor selles juhises selles etapis teeb. N konveieriastmega protsessoril võib korraga olla kuni N erinevat käsku erinevatel täielikkuse tasemetel. Konveierprotsessori klassikaline näide on RISC-protsessor, millel on 5 etappi: käsu toomine (IF), käsu dekodeerimine (ID), käsu täitmine (EX), juurdepääs mälule (MEM), tulemuse registritesse kirjutamine (WB). Pentium 4 protsessoril on 35-astmeline torujuhe.

Mõnel protsessoril on lisaks torujuhtmete kasutamisele võimalus täita mitut käsku samaaegselt, mis annab käsu tasemel täiendava paralleelsuse. Seda meetodit on võimalik rakendada superskalaarsuse abil, kus käske saab paralleelseks täitmiseks rühmitada (kui neil pole andmete sõltuvusi). Võimalikud on ka rakendused, mis kasutavad selgesõnalist käsutaseme paralleelsust: VLIW ja EPIC.

2.3 Andmete paralleelsus

Andmete paralleelsusel põhineva lähenemisviisi põhiidee seisneb selles, et andmemassiivi kõigi elementidega tehakse korraga üks toiming. Sellise massiivi erinevaid fragmente töödeldakse vektorprotsessoril või paralleelmasina erinevatel protsessoritel. Programm jagab andmeid protsessorite vahel. Vektoriseerimine või paralleelsus tehakse sel juhul kõige sagedamini kompileerimisetapis - programmi lähteteksti tõlkimine masinkäskudeks. Programmeerija roll taandub sel juhul tavaliselt kompilaatori vektor- või paralleelse optimeerimise sätete määramisele, paralleelse kompileerimise direktiividele ja spetsiaalsete keelte kasutamisele paralleelseks andmetöötluseks.

2.4 Ülesande paralleelsus (mitmelõimeline)

Ülesande paralleelsusel põhinev programmeerimisstiil eeldab, et arvutusülesanne on jagatud mitmeks suhteliselt sõltumatuks alamülesandeks ja igale protsessorile laaditakse oma alamülesanne.

2.5 Hajutatud operatsioonisüsteemid

Jaotatud OS, jaotades töö dünaamiliselt ja automaatselt töötlemiseks süsteemi erinevate masinate vahel, paneb võrguga ühendatud masinate komplekti toimima virtuaalse üheprotsessorina. Hajutatud OS-i kasutajal pole üldiselt teavet selle kohta, millise masinaga tema tööd tehakse.

Hajutatud OS eksisteerib ühe operatsioonisüsteemina kogu arvutisüsteemis. Iga hajutatud OS-i kasutav võrgus olev arvuti täidab osa selle globaalse OS-i funktsioonidest. Hajutatud OS ühendab kõik võrgus olevad arvutid selles mõttes, et nad töötavad üksteisega tihedas koostöös, et kasutada tõhusalt kõiki arvutivõrgu ressursse.

Töö lisati saidi veebisaidile: 2016-06-20

">Loeng " xml:lang="en-US" lang="en-US">6

">Andmetöötlus paralleelselt

">Paralleelsus on võime sooritada samaaegselt mitut aritmeetilist, loogilist või teenindustehtet. Lisaks võivad tehted olla nii suure- kui ka väikeseplokilised.

Paralleelne töötlemine võib põhineda erinevatel põhimõtetel:

Ruumiline paralleelsus;

Ajaline paralleelsus:

1. Torustik.
2. ">Vektoriseerimine.
3. ">Maatriks.
4. ">Süstoolne.
5. ">Andmevoo töötlemise struktuuri korraldus.
6. ">Süsteemi korraldus hüperkuubi struktuuri alusel.
7. ">Lennuki struktuuri dünaamiline ümberkorraldamine.

">Iga algoritmi kirjeldus on hierarhiline, lähtudes pesastusomadusest. Programmeerimisel eristatakse pesastustasemeid: ülesanded, ülesanded, alamülesanded (protsessid), makrooperatsioonid, toimingud.

">1. Algoritmi astmeline paralleelvorm

">Algoritmide esitusviisi kõige üldisem vorm on algoritmi info-juhtgraaf. Spetsiifilisem ülesande paralleelsuse kujutamise vorm on astmelise paralleelvormi aparaat (LPF).

">Tasaparalleelsel kujul olev algoritm on esitatud tasandite kujul ja nulltasand sisaldab üksteisest sõltumatuid operaatoreid (harusid).

">Graafikul saate määrata üleminekuid, mis tähendab primitiivse toimingu arvutamise tulemuste ülekandmist ühelt astmelt järgmise astme toimingusse. Tasemed on jagatud üleminekutega. Võib esineda tühje üleminekuid ja tühje primitiivseid üleminekuid. operatsioonid.

">NFP-de koostamisel toetuvad nad algsete operatsioonide põhikomplektile (BNO). Tasapinnalist paralleelset vormi iseloomustavad järgmised parameetrid:

">1. Graafiku pikkus (tasandite arv)" xml:lang="en-US" lang="en-US">L">.

">2. Laius " xml:lang="en-US" lang="en-US">i">th tasand - " xml:lang="en-US" lang="en-US">b;vertical-align:sub" xml:lang="en-US" lang="en-US">i">.

">3. Mitmetasandilise paralleelgraafiku laius" xml:lang="en-US" lang="en-US">B">= " xml:lang="en-US" lang="en-US">max">(" xml:lang="en-US" lang="en-US">b;vertical-align:sub" xml:lang="en-US" lang="en-US">i">).

">4. NAP-graafiku V keskmine laius;vertical-align:sub">cf "> ">.

">5. Täitetegur" xml:lang="en-US" lang="en-US">i">ndas astmes " xml:lang="en-US" lang="en-US">k;vertical-align:sub" xml:lang="en-US" lang="en-US">i"> – ">.

">6. Tehte dispersioonikoefitsient graafikus -" xml:lang="en-US" lang="en-US">Q;vertical-align:super" xml:lang="en-US" lang="en-US">j;vertical-align:sub" xml:lang="en-US" lang="en-US">i"> – ">, " xml:lang="en-US" lang="en-US">j">BNO, kus ">- kogus " xml:lang="en-US" lang="en-US">j">ndat tüüpi toimingud aastal" xml:lang="en-US" lang="en-US">i">ndas astmes.

">7. Minimaalne nõutav arv arvuteid (BNO-st), et rakendada YAPF-is selle graafikuga kujutatud algoritmi.

">8. Algoritmi minimaalne lahendusaeg (arvutite reageerimisaegade summa koos maksimaalse arvutuste arvuga iga astme kohta) T;vertical-align:sub" xml:lang="en-US" lang="en-US">min">.

">9. Algoritmi ühenduvus (vahetulemuste arv, mis tuleb salvestada algoritmi rakendamisel) C.

">2. Automaatne samaaegsuse tuvastamine

">Paralleelalgoritmi koostamiseks on kaks võimalust: otse ülesandepüstitusest või järjestikuse algoritmi teisendamise teel.

">Jadaalgoritmi paralleelse konstrueerimise meetodid põhinevad järjestikuses algoritmis tüüpiliste, sageli esinevate konstruktsioonide tuvastamisel, mis teatud reeglite kohaselt asendatakse paralleelsete konstruktsioonidega.

Vaatamata sellele, et paralleelalgoritmi koostamisel järjestikusest teisendamise teel saavutatakse madalam paralleelsus, kasutatakse seda meetodit laialdaselt, kuna see annab võimaluse kasutada järjestikuse ODS-i jaoks välja töötatud ja silutud kalleid rakendusprogramme.

">Järgnevas programmis eristatakse selgesõnalist ja varjatud paralleeltöötlust.

">Programmi analüüsimisel konstrueeritakse andmevoo graafik. Protsesside ilmse paralleelsuse tuvastamiseks analüüsitakse sisend- (loetud) muutujate komplekte" xml:lang="en-US" lang="en-US">R"> ja väljund (kirjutatud) muutujad" xml:lang="en-US" lang="en-US">W"> iga protsessi kohta.

">Varjatud paralleeltöötlus nõuab järjestikuse programmi jaoks mingit teisendusprotseduuri, et oleks võimalik seda paralleelselt käivitada. Teisendus võib olla järgmine:

">a) aritmeetiliste avaldiste puude kõrguse vähendamine (joonis 6.3);

">b) lineaarsete kordussuhete teisendamine;

">c) operaatorite asendamine;

">d) tingimuslike üleminekute ja silmuste plokkide teisendamine kanoonilisse vormi;

">e) tsüklite jaotus.

">Paralleelarhitektuurid saavutavad suure jõudluse, kui paralleelsuse teisendamisel võetakse arvesse selle arvutiarhitektuuri omadusi, millel algoritm peaks toimuma.

">Mälu paigutuse arvestamise näitena võtame diagonaaladresseerimisega mälu. Maatriksite paralleelse töötlemise tagamiseks tuleb nende ridade ja veergude elemendid jaotada protsessori salvestusseadmete vahel selliselt, et neid saaks lugeda ja töödelda samaaegselt. Sel juhul salvestatakse maatriks nihkega (joonis 6.4).

">Iga algoritm sisaldab järjestikuseid (skalaarseid) lõike. On tõestatud, et nende skalaarsete lõikude pikkus on määravaks teguriks algoritmi rakendamisel paralleelarvutis.

">3. Paralleelsuse aste ja tasemed

Paralleelsuse aste"> (" xml:lang="en-US" lang="en-US">D">) "> see on paralleelselt töötavate seadmete arvu järjekord süsteemis ülesande algoritmi realiseerimisel eeldusel, et protsessorite (töötlusseadmete) arv ei ole piiratud.

">1) Madal aste: 2 kuni 10 protsessorit.

">2) Keskmine aste: 10 kuni 100 protsessorit.

">3) Kõrge aste: 100 kuni 10;vertical-align:super">4 "> protsessorit.

">4) Ülikõrge aste: alates 10;vertical-align:super">4 "> kuni 10 ;vertical-align:super">6 "> protsessorit.

">Parameetri graafiline esitus" xml:lang="en-US" lang="en-US">D">(" xml:lang="en-US" lang="en-US">t">) aja funktsioonina nimetatakse programmi paralleelsuse profiiliks.Joonis 6.5 näitab tüüpilist paralleelsuse profiili.

">Rakendusprogrammides on palju potentsiaalset paralleelsust. Arvutusmahukates programmides saab igas tsüklis paralleelselt sooritada 500 kuni 3500 aritmeetilist tehtet, kui selleks on olemas olemasolev arvutuskeskkond. Samas ka korralikult disainitud superskalaar protsessor toetab 2 kuni 5,8 käsku tsükli kohta. See langus on peamiselt tingitud side- ja süsteemikuludest.

Paralleelsuse tase mõjutab arvuti jõudlust tugevamini kui paralleelsuse aste.

Arvesse võetakse paralleelsuse algoritmilisi ja vooluahela tasemeid.

Eristatakse järgmisi paralleelsuse algoritmilisi tasemeid:

1. Ülesande tase:

a) ülesannete vahel;

b) ülesande faaside vahel.

2. Tarkvara tase:

a) programmi osade vahel;

b) tsüklite jooksul.

3. Käsu tase (käsu täitmise faaside vahel).

4. Aritmeetika ja bititase:

">a) vektortehte elementide vahel;

">b) ALU loogilistes ahelates.

">Iga tasandit iseloomustavad teatud omadused, mille põhjal on välja töötatud arvutusvahendite spetsiaalsed struktuurid. Käsu tase on rakendatud kõigis kaasaegsetes arvutites, sealhulgas personaalarvutites.

">Riistvaraline paralleeltase on riistvaratase, millel teostatakse andmetöötluse paralleelsus või paralleelarvutuste korraldamine.

">Paralleeltöötlust saab rakendada järgmistel vooluahela tasemetel:

">1. Loogikaväravate ja mäluelementide tasemel (joon. 6.6).

">2. Loogikaahelate ja lihtautomaatide tase mäluga (joon. 6.7).

">3. Registrite ja mälu integraallülituste tase (joonis 6.8).

4. Elementaarsete mikroprotsessorite tase (joon. 6.9).

">5. Suuri operatsioone realiseerivate makroprotsessorite tase (joonis 6.10).

6. Arvutite, protsessorite ja programmide tase (joon. 6.11).

">4. Paralleelsuse liigid

">4.1. Loomulik paralleelsus ja

">mitme objekti paralleelsus

Infograafikul saab tuvastada “vertikaalsed” sõltumatud alamgraafid, mis ei kasuta vastastikku mingeid vahetulemusi, mis on saadud mõne teise alamgraafi primitiivsete operatsioonide rakendamisel. Seda tüüpi paralleelsust nimetatakse iseseisvate ülesannete loomulikuks parallelismiks.

Probleemil on loomulik paralleelsus, kui see on algses sõnastuses taandatud tehtele mitmemõõtmeliste vektoritega, mitmemõõtmeliste maatriksite või võrefunktsioonidega (joonis 6.12).

Mitme objekti paralleelsus on loomuliku paralleelsuse erijuht. Selle tähendus seisneb selles, et ülesandeks on töödelda informatsiooni erinevate, kuid sarnaste objektide kohta, mida töödeldakse sama või peaaegu sama programmi abil (joonis 6.13).

">Siin omavad nn integraaltehted suhteliselt vähe kaalu. Mitme objekti paralleelsestamisel tuleb sagedamini ette olukordi kui üldjuhul, kus üksikuid arvutuslõike tuleb erinevate objektide puhul erinevalt sooritada.

">4.2. Iseseisvate harude paralleelsus

Sõltumatute harude paralleelsuse olemus seisneb selles, et ülesande lahendamise programmis saab eristada iseseisvaid osi, mida nimetatakse harudeks. Kui arvutil on vastav riistvara, saab harusid teostada paralleelselt (joonis 6.14).

">Programmi haru Y ei sõltu harust X, kui:

"> - nende vahel puuduvad funktsionaalsed seosed, s.t ükski haru Y sisendmuutujatest ei ole haru X ega ühegi X-st sõltuva haru väljundmuutuja;

"> - nende vahel puudub ühendus töömäluväljade kaudu;

"> - need tuleb käivitada erinevate programmide abil;

"> - on juhtimises sõltumatud, st haru Y täitmise tingimus ei tohiks sõltuda haru X või sellest sõltuva haru täitmisel genereeritud omadustest.

">4.3. Seotud toimingute paralleelsus või

">kohalik paralleelsus

Kõrvutitehte paralleelsus ilmneb siis, kui jooksvate toimingute sisendandmed saadakse arvutamise varasemates etappides ja arvutusvahendite konstrueerimine võimaldab kombineerida mitme väljundandmete ja tulemustega omavahel mitteseotud toimingu sooritamist.

Programmide lokaalne optimeerimine seisneb mitmete järjestikuste täitmiskäskude läbivaatamises ja osade järjekorra muutmises, võimalusel registrite ja mälurakkude arvu muutmises, et tagada kõrvuti tehtavate toimingute maksimaalne võimalik paralleelsus.

Enamikul juhtudel ei sõltu külgnevate toimingute ühenduvuse näitaja mitte niivõrd probleemist, kuivõrd kohaliku optimeerimise kvaliteedist.

">5. Probleemi mudel

Probleemi mudel on koostatud paralleelsete arvutite struktuuride võrdlevaks analüüsiks. Seetõttu peaks see olema oma olemuselt üsna üldine ja kirjeldama ainult paralleelsuse vormide koostist ja seoste liike.

Reeglina on mis tahes probleemimudel üles ehitatud modelleeritud probleemide klassi analüüsi põhjal. Analüüsi tulemuste põhjal teisendatakse algoritmid paralleelvormile. Uuritavat algoritmi saab esitada programmina, mis koosneb kolme tüüpi osade jadast (joonis 6.15):

1. skalaarlõiked (SC);
2. iseseisvate harude paralleelsusega lõigud (BT);
3. vektorlõiked (VC).

Ülesandemudel on paralleelprogrammi iseloomustav parameetrite kogum

Ülesande mudeli koostamisel on peamine eesmärk määrata selle täitmise suhteline aeg, kui seda uuritav algoritm realiseerib.

">Joonis 6.15. Arvutuste koguarvu suhe algoritmi erinevate osade kohta probleemimudelis

" xml:lang="en-US" lang="en-US">W">sk

" xml:lang="en-US" lang="en-US">Ww

" xml:lang="en-US" lang="en-US">W">vk

" xml:lang="en-US" lang="en-US">m;vertical-align:sub">sk

" xml:lang="en-US" lang="en-US">m;vertical-align:sub" xml:lang="en-US" lang="en-US">tu

" xml:lang="en-US" lang="en-US">m;vertical-align:sub">vk

" xml:lang="en-US" lang="en-US">A

" xml:lang="en-US" lang="en-US">В

" xml:lang="en-US" lang="en-US">C

arvutuste maht

suhteline pikkus

1.2 Paralleelne andmetöötlus

1.2.1 Paralleeltöötluse põhimõtteline võimalus

Peaaegu kõik praeguseks välja töötatud algoritmid on järjestikused. Näiteks avaldise a + b × c hindamisel tuleb esmalt sooritada korrutamine ja alles siis liitmine. Kui elektroonilistes arvutites on liitmis- ja korrutamissõlmed, mis võivad töötada samaaegselt, siis sel juhul jääb liitmissõlm jõude ootama, kuni korrutamissõlm oma töö lõpetab. On võimalik tõestada väidet, et on võimalik ehitada masin, mis töötleb antud algoritmi paralleelselt.

Võimalik on ehitada m protsessorit, mis samaaegsel kasutamisel annavad soovitud tulemuse arvuti ühe taktitsükli jooksul.

Selliseid "mitmeprotsessorilisi" masinaid saaks teoreetiliselt ehitada iga konkreetse algoritmi jaoks ja näiliselt "mööda" algoritmide järjestikusest olemusest. Kõik pole aga nii lihtne – spetsiifilisi algoritme on lõpmatult palju, mistõttu ülal välja töötatud abstraktne arutluskäik ei ole nii otseselt seotud praktilise tähtsusega. Nende väljatöötamine veenis meid paralleelsuse võimalikkuses, pani aluse piiramatu paralleelsuse kontseptsioonile ja võimaldas üldisest perspektiivist vaadelda nn arvutuskeskkondade rakendamist - mitme protsessoriga süsteeme, mis on dünaamiliselt konfigureeritud konkreetse algoritmi jaoks.

1.2.2 Abstraktsed paralleelarvutusmudelid

Paralleelarvutusmudel pakub kõrgetasemelist lähenemist erinevate programmide täitmisaegade iseloomustamiseks ja võrdlemiseks, võttes samal ajal ära riistvara ja täitmise üksikasjad. Esimene oluline paralleelarvutusmudel oli Parallel Random Access Machine (PRAM), mis pakub ühismälumasina abstraktsiooni (PRAM on RAM-i laiendus – Random Access Machine mudel). BSP (Bulk Synchronous Parallel) mudel ühendab nii jagatud kui ka hajutatud mälu abstraktsioonid. Eeldatakse, et kõik protsessorid täidavad käske sünkroonselt; sama käsu täitmise korral on PRAM abstraktne SIMD masin (SIMD - Single Instruction stream / Multiple Data stream - üks käsuvoog koos mitme andmevooga), kuid protsessorid võivad täita erinevaid käske. Peamised käsud on mälust lugemine, mällu kirjutamine ning tavalised loogilised ja aritmeetilised toimingud.

PRAM-i mudel on idealiseeritud selles mõttes, et iga protsessor pääseb igal ajal juurde mis tahes mäluelemendile (ühe protsessori tehtud kirjutustoimingud on nähtavad kõigile teistele protsessoritele nende sooritamise järjekorras, kuid erinevate protsessorite poolt tehtavad kirjutamistoimingud võivad olla nähtav mis tahes järjekorras). Näiteks võib iga PRAM-i protsessor lugeda andmeid mäluelemendist või kirjutada andmeid samasse lahtrisse. Päris paralleelsetes masinates seda muidugi ei juhtu, kuna füüsilisel tasemel mälumoodulid korraldavad juurdepääsu samale mäluelemendile. Veelgi enam, mälule juurdepääsu ajad erinevad tegelikes masinates vahemälu olemasolu ja mälumoodulite võimaliku hierarhilise korralduse tõttu.

PRAM-i põhimudel toetab samaaegset (selles kontekstis paralleelset) lugemist ja kirjutamist. On teada PRAM-i alammudelid, mis võtavad arvesse reegleid, vältimaks konfliktsituatsioone, kui mitu protsessorit pääseb samaaegselt ühismälu juurde.

Brenti teoreem võimaldab modelleerida funktsionaalsete elementide ahelaid paralleelsete juhusliku juurdepääsu masinate (PRAM) abil. Funktsionaalsed elemendid võivad olla kas 4 põhielementi (teostavad loogilisi tehteid EI, JA, VÕI, XOR - vastavalt eitus, loogiline JA, loogiline VÕI ja välistav VÕI), keerukamad NAND ja NOR (AND-NOT ja OR-NOT), ja mis tahes keerukusest.

Järgnevalt eeldatakse, et viivitus (st reageerimisaeg - aeg, mille möödudes ilmuvad elemendi väljundisse kavandatud signaali väärtused pärast sisendite väärtuste kindlaksmääramist) on sama. kõik funktsionaalsed elemendid.

Käsitleme funktsionaalsete elementide ahelat, mis on ühendatud ilma tsüklite moodustamiseta (eeldame, et funktsionaalsetel elementidel on suvaline arv sisendeid, kuid täpselt üks väljund - mitme väljundiga elementi saab asendada mitme ühe väljundiga elemendiga). Sisendite arv määrab elemendi sisendvõimsuse ja sisendite arv, millega elemendi väljund on ühendatud, määrab selle väljundvõimsuse. Tavaliselt eeldatakse, et kõigi kasutatavate elementide sisendvõimsused on ülalt piiratud, kuid väljundvõimsused võivad olla mis tahes. Ahela suurus viitab selles olevate elementide arvule suurimat arvu elemente teedel ahela sisenditest elemendi väljundini nimetatakse selle elemendi sügavuseks (ahela sügavus on võrdne; selle koostisosade sügavustest suurim).

Joonis 1. 15. suuruse ja 5. sügavusega vooluringi simulatsioon kahe protsessoriga, kasutades paralleelset suvapöördusmasinat (PRAM-seade)

Joonisel 1 on kujutatud ahela suuruse (protsessorite koguarv) n=15 modelleerimise tulemust ahela sügavusega (maksimaalne elementide arv igal sügavustasemel) d=5 protsessorite arvuga p=2 (samaaegselt simuleeritud elemendid on kombineeritud ristkülikukujuliste alade kaupa rühmadesse ja iga rühma jaoks on näidatud selle elementide modelleerimise samm, mis toimub järjestikku ülalt alla sügavuse suurenemise järjekorras, igal sügavusel p tükki korraga. Brenti teoreemi kohaselt ei võta sellise skeemi modelleerimine rohkem kui ceil(15/2+1)=9 sammu.

Vene Föderatsiooni haridus- ja teadusministeerium

FSBEI HPE "Brjanski osariigi inseneri- ja tehnoloogiateadus

akadeemia"

Infotehnoloogia osakond

Info järjestikune ja paralleelne töötlemine

Arvutus- ja graafiline töö nr 1

distsipliini järgi

"Teabetöötlustehnoloogiad"

Variant nr 16

RGR-02068025.230400.084

Brjansk 2015

Sissejuhatus 3

Paralleelne teabetöötlus 4

Jagatud mälusüsteemid 6

SQL-i paralleelne töötlemine 7

Järjestikune teabetöötlus 9

10 lihtsat partiisüsteemi

Viited 13

Sissejuhatus

See arvutuslik ja graafiline uuring uurib järjestikust ja paralleelset teabetöötlust. Igaühe kohta on toodud näited.

Info järjestikune töötlemine on teabe järjestikune ülekanne sisendist väljundisse teisenduste seeria (etappide) kaudu, nii et igal ajaperioodil (antud ploki spetsiifiline) toimub teisendus ainult ühes funktsionaalplokis ja teave tuleb selle juurde alles eelmisest plokist.

Paralleelne infotöötlus on infotöötluse mudel, mille kohaselt info läbib teatud funktsionaalplokkides rea teisendusi, nii et igal ajahetkel töödeldakse seda samaaegselt (paralleelselt) mitmes plokis.

Paralleelne infotöötlus

Paralleelsel andmetöötlusel, mis hõlmab mitme toimingu samaaegse teostamise ideed, on kaks varianti: konveier ja paralleelsus.

Paralleelne töötlemine. Kui teatud seade teeb ühe toimingu ajaühikus, siis teeb see tuhandes ühikus tuhat toimingut. Kui eeldada, et on olemas viis identset sõltumatut seadet, mis on võimelised samaaegselt töötama, siis viiest seadmest koosnev süsteem suudab teha sama tuhat toimingut mitte tuhande, vaid kahesaja ajaühikuga. Samamoodi teeb N seadmest koosnev süsteem sama tööd 1000/N ajaühikus. Sarnaseid analooge võib ka elus leida: kui üks sõdur kaevab aia üles 10 tunniga, siis viiekümneliikmeline samaaegselt töötav samade võimetega sõdurikompanii saab sama tööga hakkama 12 minutiga - paralleelsuse printsiip tegevuses!

Konveieri töötlemine. Mida on vaja kahe ujukoma kujul esitatud reaalarvu liitmiseks? Palju pisitoiminguid, nagu tellimuste võrdlemine, tellimuste joondamine, mantisside lisamine, normaliseerimine jne. Esimeste arvutite protsessorid sooritasid kõik need “mikrooperatsioonid” iga argumendipaari jaoks üksteise järel, kuni jõudsid lõpptulemuseni, ja alles siis asusid töötlema järgmist terminipaari.

Torujuhtme töötlemise idee on eraldada üldise toimingu sooritamise üksikud etapid ja iga etapp, olles oma töö lõpetanud, edastaks tulemuse järgmisele, saades samal ajal uue osa sisendandmetest. Varem vahedega operatsioone kombineerides saame töötlemise kiiruse ilmse kasvu. Oletame, et ühes toimingus on viis mikrooperatsiooni, millest igaüks sooritatakse ühes ajaühikus. Kui on üks jagamatu jadaseade, töötleb see 500 ühikus 100 paari argumente. Kui iga mikrooperatsioon on eraldatud konveierseadme eraldi etapiks (või teisiti nimetatakse etapiks), siis viiendal ajaühikul, sellise seadme töötlemise erinevates etappides, paiknevad esimesed viis argumentide paari. , ja kogu sajast paarist koosnev komplekt töödeldakse 5 + 99 = 104 ajaühikuga - kiirendus võrreldes jadaseadmega on peaaegu viis korda suurem (vastavalt konveieri etappide arvule).

Näib, et torujuhtme töötlemist saab edukalt asendada tavalise paralleelsusega, mille jaoks dubleerime põhiseadet nii mitu korda, kui torujuhtme etappide arv peaks olema eraldatud. Tegelikult töötlevad eelmise näite viis seadet 100 paari argumente 100 ajaühiku jooksul, mis on kiirem kui konveierseadme tööaeg! Seega suurendame seadmete arvu viiekordselt suurendades oluliselt nii seadmete mahtu kui ka nende maksumust. Kujutage ette, et autotehas otsustas konveieri eemaldada, säilitades samal ajal autode tootmise kiiruse. Kui varem oli konveieril korraga tuhat autot, siis analoogselt eelmise näitega on vaja värvata tuhat meeskonda, millest igaüks suudab auto algusest lõpuni täielikult kokku panna, sooritades sadu erinevat tüüpi toiminguid ja tehke seda samal ajal, kui auto oli varem koosteliinil.

Tänapäeval üllatab paralleelsus arvutiarhitektuuris väheseid inimesi. Kõik kaasaegsed mikroprotsessorid kasutavad mingit paralleeltöötlust. Pentium 4 tuumas saab üheaegselt erinevatel täitmise etappidel olla kuni 126 mikrooperatsiooni. Samas tekkisid need ideed ise väga kaua aega tagasi. Algselt rakendati neid oma aja kõige arenenumates ja seega üksikutes arvutites. Siis läksid nad pärast tehnoloogia korralikku arendamist ja odavamat tootmist keskklassi arvutiteni ning lõpuks on tänapäeval kõik see täielikult kehastatud tööjaamades ja personaalarvutites.

Paljude ühe protsessoriga arvutisüsteemides töötavate rakenduste jõudlust saab paralleeltöötlustööriistade kasutamisega oluliselt parandada. Järgnevalt tutvustatakse paralleeltöötluse ja mitme protsessoriga arvutiarhitektuuri põhimõisteid.

Kui mitu rakendust taotlevad oma tööde töötlemist ühe protsessoriga arvutis, peab selle üks protsessor tegema kogu töö. Paralleelse töötlemise eesmärk on tavaliselt rakenduse jõudluse parandamine. Kui rakendus saadab mitme protsessoriga arvutile töötaotluse, jagab arvuti töö loogilisteks alamülesanneteks ja seejärel töötleb neid paralleelselt mitut protsessorit kasutades, mis vähendab töö lõpetamiseks kuluvat aega. Alamülesannete arvu, mis tuleneb ühe suure ülesande jagamisest, nimetatakse paralleelsuse astmeks . Ülesande täitmiseks kuluva infotöötlusaja vähenemine on otseselt võrdeline paralleelsuse astmega. Nad püüavad paralleeltöötlusega süsteemide jõudlust tõsta nii, et oleks tagatud süsteemi iga protsessori maksimaalne jõudlus.

Lihtsad arvutused näitavad, et selliste süsteemide konfiguratsioonid võivad maksta rohkem kui miljon USA dollarit – lihtsalt nalja pärast mõelge välja, kui palju maksab näiteks ainult 4 TB RAM-i? Tekib mitmeid loomulikke küsimusi: millised ülesanded on nii olulised, et nende jaoks on vaja mitme miljoni dollariseid arvuteid? Või millised ülesanded on nii keerulised, et heast Pentiumist ei piisa? Nendele ja sarnastele küsimustele tahaksin leida mõistlikke vastuseid.

Praktikas lahendatavate probleemide keerukuse hindamiseks võtame konkreetse teemavaldkonna, näiteks õlitootmisprotsessi optimeerimise. Meil on maa-alune naftareservuaar, kus on teatud arv puurkaevu: üks pumpab õli maapinnale, teine ​​pumpab vett tagasi. Naftavarude hindamiseks või täiendavate puuraukude vajaduse mõistmiseks on vaja simuleerida olukorda antud veehoidlas.

Aktsepteerime lihtsustatud skeemi, kus modelleeritud ala kaardistatakse kuubiks, kuid piisab, kui hinnata vajalike aritmeetiliste toimingute arvu. Mõistlikud kuubiku suurused, mille puhul on võimalik saada usutavaid tulemusi, on 100*100*100 punkti. Kuubi igas punktis on vaja arvutada 5 kuni 20 funktsiooni: kolm kiiruse, rõhu, temperatuuri, komponentide kontsentratsiooni komponenti (vesi, gaas ja õli - see on minimaalne komponentide komplekt; realistlikumates mudelites, näiteks vaadeldakse õli erinevaid fraktsioone). Lisaks leitakse funktsioonide väärtused mittelineaarsete võrrandite lahendamisel, mis nõuab 200 kuni 1000 aritmeetilist tehtet. Ja lõpuks, kui uuritakse mittestatsionaarset protsessi, s.t. sa pead aru saama, kuidas see süsteem ajas käitub, siis tehakse 100-1000 ajasammu. Mis juhtus:

10 6 (ruudustiku punktid) * 10 (funktsioonid) * 500 (toimingud) * 500 (aja sammud) = 2,5 * 10 12

2500 miljardit aritmeetilisi tehteid vaid ühe arvutuse tegemiseks! Aga mudeli parameetrite muutmine? Kuidas on lood praeguse olukorra jälgimisega, kui sisendandmed muutuvad? Selliseid arvutusi tuleb teha mitu korda, mis seab kasutatavate arvutussüsteemide jõudlusele väga ranged nõuded.

Superarvutite kasutamise näiteid võib leida mitte ainult naftatööstusest. Siin on vaid väike loetelu inimtegevuse valdkondadest, kus superarvutite kasutamine on tõesti vajalik:

• autotööstus
• nafta ja gaasi tootmine
• farmakoloogia
• ilmaennustus ja kliimamuutuste modelleerimine
• seismiline uuring
• elektroonikaseadmete disain
• uute materjalide süntees
• ja paljud, paljud teised

1995. aastal muudeti Nissan Maxima kere tänu Cray superarvuti kasutamisele 10% tugevamaks (The Atlanta Journal, 28. mai 1995). Tema abiga leiti mitte ainult keha nõrgad kohad, vaid ka kõige tõhusam viis nende eemaldamiseks.

Mark Milleri (Ford Motor Company) sõnul oleks Fordil vaja kokkupõrketestide tegemiseks, kus reaalsed autod põrkuvad vastu betoonseina, samal ajal vajalikke parameetreid mõõtes, filmides ja seejärel tulemusi töödelda, 10 kuni 150 uute mudelite prototüüpi kogukulud ulatuvad 4 miljonist kuni 60 miljoni dollarini. Superarvutite kasutamine on vähendanud prototüüpide arvu kolmandiku võrra.

Väga värske näide on maailma ühe suurima broneerimissüsteemi Amadeus arendamine, mida kasutavad tuhanded agentuurid 180 000 terminaliga enam kui sajas riigis. Kahe 12 protsessoriga Hewlett-Packard T600 serveri paigaldamine võimaldas tõsta kesksüsteemi töökäideldavuse 99,85%ni praeguse koormuse juures umbes 60 miljonit päringut päevas.

Ja sarnaseid näiteid võib leida igalt poolt. Omal ajal otsisid DuPonti teadlased klorofluorosüsinikule asendust. Oli vaja leida materjal, millel on samad positiivsed omadused: mittesüttivus, korrosioonikindlus ja madal toksilisus, kuid millel pole kahjulikku mõju Maa osoonikihile. Ühe nädalaga tehti vajalikud arvutused superarvutis, mille kogumaksumus oli umbes 5 tuhat dollarit. DuPonti ekspertide hinnangul nõuaks traditsiooniliste eksperimentaalsete uurimismeetodite kasutamine umbes kolm kuud ja 50 tuhat dollarit ning see ei võta arvesse aega, mis kulub vajaliku koguse aine sünteesimiseks ja puhastamiseks.

Mille tõttu arvuti jõudlus suureneb?

Miks superarvutid nii kiiresti arvutavad? Vastusevariante võib olla mitu, mille hulgas on selge eelis kahel: elemendibaasi arendamine ja uute lahenduste kasutamine arvutiarhitektuuris.

Proovime välja mõelda, milline neist teguritest on rekordtulemuse saavutamiseks määrav. Pöördugem tuntud ajalooliste faktide juurde. Ühes maailma esimestest arvutitest - EDSAC, mis ilmus 1949. aastal Cambridge'is ja mille kellaaeg oli 2 mikrosekundit (2 * 10-6 sekundit), oli võimalik sooritada 2 * n aritmeetilisi tehteid 18 * n millisekundi jooksul. , see tähendab keskmiselt 100 aritmeetilist tehet sekundis. Võrdleme nüüdisaegse Hewlett-Packard V2600 superarvuti ühe arvutussõlmega: kellaaeg on ligikaudu 1,8 nanosekundit (1,8 * 10-9 sekundit) ja maksimaalne jõudlus on umbes 77 miljardit aritmeetilist operatsiooni sekundis.

Mis juhtub? Poole sajandi jooksul on arvuti jõudlus kasvanud rohkem kui seitsesada miljonitüks kord. Samal ajal on jõudluse suurenemine, mis on seotud kella tsükli aja vähendamisega 2 mikrosekundilt 1,8 nanosekundile, vaid umbes 1000 korda. Kust ülejäänud tuli? Vastus on ilmne – uute lahenduste kasutamine arvutiarhitektuuris. Peamise koha nende seas hõivab paralleelse andmetöötluse põhimõte, mis kätkeb endas mitme toimingu samaaegse (paralleelse) teostamise ideed.

Paralleelne andmetöötlus arvutis

Paralleelsel andmetöötlusel, mis hõlmab mitme toimingu samaaegse teostamise ideed, on kaks varianti: konveier ja tegelik paralleelsus. Mõlemad paralleeltöötluse tüübid on intuitiivsed, seega teeme vaid väikeseid selgitusi.

Paralleelne töötlemine. Kui teatud seade teeb ühe toimingu ajaühikus, siis teeb see tuhandes ühikus tuhat toimingut. Kui eeldada, et on olemas viis identset sõltumatut seadet, mis on võimelised samaaegselt töötama, siis viiest seadmest koosnev süsteem suudab teha sama tuhat toimingut mitte tuhande, vaid kahesaja ajaühikuga. Samamoodi teeb N seadmest koosnev süsteem sama tööd 1000/N ajaühikus. Sarnaseid analoogiaid võib leida ka elust: kui üks sõdur kaevab aia 10 tunniga üles, siis viiekümneliikmeline samade võimetega sõdurikompanii, samaaegselt töötav, saab sama tööga hakkama 12 minutiga – paralleelsuse printsiip tegevuses!

Muide, andmevoogude paralleeltöötluse pioneer oli akadeemik A. A. Samarsky, kes tegi 50ndate alguses tuumaplahvatuste simuleerimiseks vajalikud arvutused. Samarsky lahendas selle probleemi, istutades laudadesse mitukümmend noort daami koos masinatega. Noored daamid edastasid üksteisele andmeid lihtsalt sõnadega ja panid liitmismasinatele üles vajalikud numbrid. Seega arvutati välja eelkõige plahvatuslaine areng. Tööd oli palju, noored daamid olid väsinud ja Aleksander Andrejevitš kõndis nende seas ja julgustas neid. Võib öelda, et see oli esimene paralleelsüsteem. Kuigi vesinikupommi arvutused viidi läbi meisterlikult, oli nende täpsus väga madal, kuna kasutatavas ruudustikus oli vähe sõlmpunkte ja arvutusaeg liiga pikk.

Konveieri töötlemine. Mida on vaja kahe ujukoma kujul esitatud reaalarvu liitmiseks? Palju pisitoiminguid, nagu tellimuste võrdlemine, tellimuste joondamine, mantisside lisamine, normaliseerimine jne. Esimeste arvutite protsessorid sooritasid kõik need “mikrooperatsioonid” iga argumendipaari jaoks üksteise järel, kuni jõudsid lõpptulemuseni, ja alles siis asusid töötlema järgmist terminipaari.

Torujuhtme töötlemise idee on eraldada üldise toimingu sooritamise üksikud etapid ja iga etapp, olles oma töö lõpetanud, edastaks tulemuse järgmisele, saades samal ajal uue osa sisendandmetest. Varem vahedega operatsioone kombineerides saame töötlemise kiiruse ilmse kasvu. Oletame, et ühes toimingus on viis mikrooperatsiooni, millest igaüks sooritatakse ühes ajaühikus. Kui on üks jagamatu jadaseade, töötleb see 500 ühikus 100 paari argumente. Kui iga mikrooperatsioon on eraldatud konveierseadme eraldi etapiks (või teisiti nimetatakse etapiks), siis viiendal ajaühikul, sellise seadme töötlemise erinevates etappides, paiknevad esimesed viis argumentide paari. , ja kogu sajast paarist koosnev komplekt töödeldakse 5 + 99 = 104 ajaühikuga - kiirendus võrreldes jadaseadmega on peaaegu viis korda suurem (vastavalt konveieri etappide arvule).

Näib, et torujuhtme töötlemist saab edukalt asendada tavalise paralleelsusega, mille jaoks dubleerime põhiseadet nii mitu korda, kui torujuhtme etappide arv peaks olema eraldatud. Tegelikult töötlevad eelmise näite viis seadet 100 paari argumente 100 ajaühiku jooksul, mis on kiirem kui konveierseadme tööaeg! Mis viga? Vastus on lihtne: viiekordistades seadmete arvu, suurendame oluliselt nii seadmete mahtu kui ka nende maksumust. Kujutage ette, et autotehas otsustas konveieri eemaldada, säilitades samal ajal autode tootmise kiiruse. Kui varem oli konveieril korraga tuhat autot, siis analoogselt eelmise näitega on vaja värvata tuhat meeskonda, millest igaüks (1) suudab auto algusest peale täielikult kokku panna. lõpetada, tehes sadu erinevat tüüpi toiminguid ja (2) teha seda samal ajal, kui auto oli varem koosteliinil. Kas kujutate ette sellise auto maksumust? Ei? Nõus, see on raske, välja arvatud see, et Lamborghini tuleb meelde, kuid seepärast tekkis konveieri töötlemine ...

Arvutiarhitektuuris paralleelsuse tekkimise lühiajalugu

Tänapäeval üllatab paralleelsus arvutiarhitektuuris väheseid inimesi. Kõik kaasaegsed mikroprotsessorid, olgu selleks Pentium III või PA-8700, MIPS R14000, E2K või Power3, kasutavad üht või teist tüüpi paralleeltöötlust. Pentium 4 tuumas saab üheaegselt erinevatel täitmise etappidel olla kuni 126 mikrooperatsiooni. Uute kiipide esitlustel ja ettevõtete pressiteadetes esitletakse seda kui tehnoloogia uusimat sõna ja teaduse tipptasemel ning see on tõepoolest nii, kui arvestada nende põhimõtete rakendamist ühe kiibi miniatuursetes piirides. .

Samas tekkisid need ideed ise väga kaua aega tagasi. Algselt rakendati neid oma aja kõige arenenumates ja seega üksikutes arvutites. Siis läksid nad pärast tehnoloogia korralikku arendamist ja odavamat tootmist keskklassi arvutiteni ning lõpuks on tänapäeval kõik see täielikult kehastatud tööjaamades ja personaalarvutites.

Veendumaks, et kõik peamised uuendused kaasaegsete protsessorite arhitektuuris on reaalselt kasutusel olnud ajast, mil ei eksisteerinud ei mikroprotsessoreid ega superarvutite kontseptsiooni, teeme väikese ekskursi ajalukku, alustades peaaegu esimeste arvutite sünnist. .

IBM 701 (1953), IBM 704 (1955): bit-paralleelmälu, bitiparalleelaritmeetika.
Kõikidel kõige esimestel arvutitel (EDSAC, EDVAC, UNIVAC) oli bitimälu, millest loeti sõnu järjestikku bittide kaupa. Esimene kaubanduslikult saadaolev bit-paralleelmälu (CRT-l) ja bitparalleelaritmeetikat kasutav arvuti oli IBM 701 ja populaarseim mudel IBM 704 (müüdud 150 eksemplari), mis lisaks eelmainitutele oli esimene. kasutada ferriitmälu ja riistvaralist ujukomavõimendit.

IBM 709 (1958): sõltumatud I/O protsessorid.
Esimeste arvutite protsessorid juhtisid sisendit/väljundit ise. Kiireima välisseadme, mis tol ajal oli magnetlint, kiirus oli aga 1000 korda väiksem protsessori kiirusest, mistõttu protsessor oli I/O toimingute ajal sisuliselt jõude. 1958. aastal Arvuti IBM 704 külge kinnitati 6 sõltumatut sisend/väljundprotsessorit, mis peale käskude saamist võisid põhiprotsessoriga paralleelselt töötada ning arvuti ise sai nimeks IBM 709. See mudel osutus üllatavalt edukaks, kuna umbes 400. koopiaid müüdi koos modifikatsioonidega, viimane lülitati välja 1975. aastal - 20 aastat eksisteerimist!

IBM STRETCH (1961): ettevaade, mälu triibud.
1956. aastal sõlmib IBM Los Alamose teaduslaboriga lepingu STRETCH-arvuti väljatöötamiseks, millel on kaks põhimõtteliselt olulist omadust: ettevaatus juhiste toomiseks ja mälu jaotamine kahte panka, et kohandada madalat mälu taastamise kiirust ja täitmiskiirust.

ATLAS (1963): käsukonveier.
Käskude täitmise konveieri põhimõtet kasutati esmakordselt Manchesteri ülikoolis välja töötatud masinas ATLAS. Käskude täitmine jaguneb neljaks etapiks: käsu toomine, operandi aadressi arvutamine, operandi toomine ja operatsiooni täitmine. Pipelining võimaldas vähendada käsu täitmise aega 6 μs-lt 1,6 μs-le. Sellel arvutil oli tohutu mõju nii arvuti arhitektuurile kui ka tarkvarale: see oli esimene, mis kasutas virtuaalmälu ja katkestussüsteemi kasutamisel põhinevat mitmeprogrammilist OS-i.

CDC 6600 (1964): sõltumatud funktsionaalsed seadmed.
Control Data Corporation (CDC) toodab ühe asutaja Seymour R. Cray otsesel osalusel arvutit CDC-6600 – esimest arvutit, mis kasutas mitut sõltumatut funktsionaalset seadet. Võrdluseks tänapäevaga on siin mõned arvuti parameetrid:

• kellaaeg 100n,
• jõudlus 2-3 miljonit toimingut sekundis,
• RAM on jagatud 32 pangaks 4096 60-bitise sõnaga,
• mälutsükkel 1 µs,
• 10 sõltumatut funktsionaalset üksust.

Masinat saatis teadusturul tohutult edu, tõrjudes aktiivselt IBM-i masinaid välja.

CDC 7600 (1969): konveierist sõltumatud funktsionaalsed seadmed.
CDC annab välja arvuti CDC-7600, millel on kaheksa sõltumatut konveierfunktsionaalset üksust – paralleelse ja konveiertöötluse kombinatsioon. Peamised parameetrid:

• Kell 27,5 ns,
• 10–15 miljonit operatsiooni sekundis,
• 8 konveieriüksust,
• 2-tasemeline mälu.

ILLIAC IV (1974): maatriksprotsessorid.

Projekt: 256 protsessori elementi (PE) = 4 kvadranti 64PE, ümberkonfigureeritavus: 2 kvadrant 128PE või 1 kvadrant 256PE, taktsagedus 40ns, jõudlus 1Gflop;

tööd alustati 1967. aastal, 1971. aasta lõpuks valmistati 1 kvadrandist koosnev süsteem, 1974. a. see võeti kasutusele, peenhäälestust tehti kuni 1975. aastani;

keskosa: juhtseade (CU) + maatriks 64 PE;

• Juhtseade on lihtne väikese jõudlusega arvuti, mis juhib PE-maatriksit; kõik PE maatriksid töötasid sünkroonrežiimis, täites igal hetkel sama juhtseadmelt saadud käsku, kuid oma andmetel;
• PE-l oli oma ALU täieliku juhiste komplektiga, OP - 2Kwords 64 bitti, mälutsükkel 350n, igal PE-l oli otsene juurdepääs ainult oma OP-le;
• andmeedastusvõrk: kahemõõtmeline torus horisontaalse nihkega 1 piki piiri;

Vaatamata tulemusele võrreldes projektiga: maksumus on 4 korda kõrgem, tehakse ainult 1 kvadrant, kella tsükkel on 80 ns, tegelik tootlikkus on kuni 50 Mflop - sellel projektil oli tohutu mõju järgnevate masinate arhitektuurile. sarnane põhimõte, eriti: PEPE, BSP, ICL DAP.

Mälu hierarhia.
Mälu hierarhia ei ole otseselt paralleelsusega seotud, kuid kindlasti viitab see arvutiarhitektuuri nendele omadustele, millel on suur tähtsus nende jõudluse suurendamisel (protsessori kiiruse ja mälu juurdepääsuaja erinevuse tasandamine). Peamised tasemed: registrid, vahemälu, RAM, kettamälu. Mälutasemete diskreetimisaeg kettamälust registritesse väheneb, 1 sõna (baidi) hind suureneb. Praegu toetatakse sellist hierarhiat isegi personaalarvutites.

Mida maailmas praegu kasutatakse?

Millistes suundades kõrgjõudlusega arvutustehnoloogia arendamine praegu käib? Põhisuundi on neli.

Oletame, et teie programmis on järjestikku sooritatavate operatsioonide murdosa f, kus 0

Kui 9/10 programmist täidetakse paralleelselt ja 1/10 on endiselt järjestikune, siis on põhimõtteliselt võimatu saavutada suuremaid kui 10-kordseid kiirusi, sõltumata koodi paralleelse osa rakendamise kvaliteedist ja kasutatud protsessorite arv (selge, et 10 saadakse ainult juhul, kui paralleelse osa täitmisaeg on 0).

Vaatame probleemi teisest küljest: millist osa koodist on vaja kiirendada (ja seega ka eelnevalt uurida), et määratud kiirendus saada? Vastuse võib leida ühest Amdahli seadusest: et kiirendada programmi täitmist q korda on vaja kiirendada mitte vähem kui q korda mitte vähem kui (1-1/ q) programmi osa. Seega, kui soovite programmi kiirendada 100 korda võrreldes selle järjestikuse versiooniga, peate vähemalt 99,99% koodist, mis peaaegu alati moodustab olulise osa programmist, kiirendama mitte vähem!

Siit ka esimene järeldus – enne paralleelarvutile üleminekuks koodi põhjalikku ümbertöötamist (ja eriti iga superarvuti on selline), peate hoolikalt mõtlema. Kui pärast programmi manustatud algoritmi hindamist mõistsite, et järjestikuste toimingute osakaal on suur, siis ei saa te ilmselgelt loota märkimisväärsele kiirendusele ja peate mõtlema algoritmi üksikute komponentide asendamisele.

Mõnel juhul pole algoritmi järjestikust olemust nii raske muuta. Oletame, et programmis on n arvu summa arvutamiseks järgmine fragment:

S = 0 Do i = 1, n s = s + a(i) EndDo (sama saab teha mis tahes muus keeles)

Oma olemuselt on see rangelt järjestikune, kuna tsükli i-ndal iteratsioonil on nõutav tulemus (i-1)-ndast ja kõik iteratsioonid sooritatakse üksteise järel. Meil on 100% järjestikused toimingud, mis tähendab, et paralleelarvutite kasutamine ei mõjuta. Samas on väljapääs ilmselge. Kuna enamikus reaalsetes programmides (küsimus: miks enamikus ja mitte kõigis?) pole numbrite lisamise järjekorras olulist erinevust, valime erineva liitmisskeemi. Esiteks leiame naaberelementide paaride summa: a(1)+a(2), a(3)+a(4), a(5)+a(6) jne. Pange tähele, et selle skeemi abil saab kõik paarid korraga lisada! Järgmistes sammudes toimime täpselt samamoodi, saades paralleelalgoritmi versiooni.

Näib, et sel juhul on kõik probleemid lahendatud. Kuid kujutage ette, et teile kättesaadavad protsessorid on oma jõudluses heterogeensed. See tähendab, et saabub hetk, mil mõned neist veel töötavad, teised aga on juba kõik ära teinud ja seisavad asjatult ootamas. Kui arvuti jõudluse dispersioon on suur, on kogu süsteemi efektiivsus ühtlase protsessorikoormusega äärmiselt madal.

Kuid läheme kaugemale ja eeldame, et kõik protsessorid on ühesugused. Kas probleemid on möödas? Jälle ei! Protsessorid on oma töö lõpetanud, aga summeerimise jätkamiseks tuleb tulemus teisele üle kanda... ja ülekanne võtab aega... ja sel ajal on protsessorid jälle jõude...

Ühesõnaga, paralleelarvutussüsteemi või superarvuti konkreetse programmiga maksimaalse efektiivsusega tööle panemine pole ausalt öeldes lihtne ülesanne, kuna programmide ja algoritmide struktuur tuleb hoolikalt kooskõlastada paralleelse arhitektuuri omadustega. arvutisüsteemid.

Viimane küsimus. Kas teie arvates vastab tõele väide: mida võimsam on arvuti, seda kiiremini suudab see antud probleemi lahendada?

Lõplik vastus. Ei, see pole tõsi. Seda saab seletada lihtsa igapäevase näitega. Kui üks kaevaja kaevab 1 tunniga augu 1m*1m*1m, siis kaks samasugust kaevajat teevad seda 30 minutiga - võite seda uskuda. Kui kaua võtab selle töö tegemiseks aega 60 kaevajat? 1 minuti pärast? Muidugi mitte! Alates teatud punktist segavad nad üksteist lihtsalt, mitte kiirendades, vaid aeglustades protsessi. Arvutites on samamoodi: kui ülesanne on liiga väike, siis kulub meil rohkem aega töö jaotamisele, protsesside sünkroonimisele, tulemuste kokkupanemisele jne, kui otseselt kasuliku töö tegemisele.

On täiesti selge, et kõik pole nii lihtne...

Paralleelsete infotehnoloogiate labor, Teadusarvutuskeskus MSU