Flynni taksonoomia

Flynni taksonoomia on kategooriseerimissüsteem, mille pakkus välja Michael J. Flynn 1966. aastal. Selle süsteemi eesmärk on kirjeldada arvutisüsteemide paralleelsuse taset ja tüüpi, jaotades arvuti arhitektuure vastavalt käsuvoogude (Instructions Stream) ja andmevoogude (Data Stream) käsitlemisele. Flynni klassifikatsioonil on neli kategooriat:

• SISD (Single Instruction Stream – Single Data Stream)
• SIMD (Single Instruction Stream – Multiple Data Stream)
• MISD (Multiple Instruction Stream – Single Data Stream)
• MIMD (Multiple Instruction Stream – Multiple Data Stream)

Flynni taksonoomia võimaldab tõhusalt võrrelda paralleelarvuteid.

Ajalugu

ILLIAC IV arvuti muuseumis Computer History Museum.

1960ndad olid arvutustehnika jaoks kiire arengu periood. Arvutid muutusid järjest võimsamaks ja neid hakati rakendama keerukamate teaduslike ja insenertehniliste probleemide lahendamiseks. Kuna taktsageduse tõstmisest enam ei piisanud siis hakati tegelema uute lahenduste väljatöötamisega — komistati toru ja paralleelsuse otsa. Seetõttu pakkus Michael J. Flynn 1966. aastal välja oma klassifikatsioonisüsteemi töös “Very High-Speed Computing Systems”, et selgemalt määratleda, kuidas erinevad arvutiarhitektuurid käsitlevad paralleelsust.

Tollal eksisteerisid juba mitmed katselised süsteemid, mis proovisid käsitleda rohkem kui ühte käsku või andmeühikut korraga. Flynni klassifikatsiooni välja pakkumisega samal aastal alustati ILLIAC IV superarvuti arendust — see oli üks esimesi massiliselt paralleelseid arvuteid. Arvuti pidi sisaldama kümneid protsessoreid, mis töötleksid samaaegselt suuri andmemahtusid, eelkõige sõjaväe ja teaduslike simulatsioonide jaoks. Kuigi  ILLIAC IV ei saadud tööle enne 1972. aastat, kehastas see arvuti Flynni tuvastatud SIMD põhimõtteid.

Mida aastaid edasi seda tavapärasemaks muutusid paralleelarvutusega masinad, mistõttu tekkis vajadus läbi mõtestatud raamistikuks, mis aitaks erinevaid arhitektuure võrrelda, hinnata ja selgitada. Flynni taksonoomia andis sellele vajadusele selge ja lihtsa struktuuri, jagades arhitektuurid nelja klassi vastavalt käsu- ja andmevoogude kogusele. 1972. aastal täiustas Flynn SIMD kategooriat lisades kolm alamkategooriat.

Klassifikatsioonid

Flynni taksonoomia SISD arhitektuur: üks andmevoog ja üks käsuvoog. Töötlemiselement täidab käsku.

SISD (Single Instruction Stream – Single Data Stream)

Süsteemil on korraga ühe käsu- ja ühe andmevoo töötlemiseks loodud riistvara. Iga instruktsioon võetakse ette üksi ja rakendatakse ühele andmeelemendile, ilma et käsud või andmed paralleelselt töötleks. Üldisemalt võttes käivad arvutused Flynni taksonoomia kohaselt töötlemiselemendis (PU - processing unit), millel on ka võimalus andmeid ajutiselt hoiustada. Spetsiifilisemalt öeldes on tegemist aritmeetika-loogikaseadmega (ALU - arithmetic logic unit) ja registritega.

Sama süsteemiga töötab ka Von Neumanni arhitektuuriga arvutid, kus andmeid ja käske hoitakse primaarmälus, mistõttu andmete edastus protsessorisse käib läbi ühe siini. Selle tagajärg on pudelikaela efekt (von Neumann bottleneck), kus protsessor ootab pidevalt, kuna talle uusi andmeid/käske antakse.

Vaatame konkreetset näidet avaldise varal:

$y={\frac {6\cdot (4-x)}{5}}$, kui $x=3$.

SISD-mudelis kulgeb arvutus jadamisi:

1. Lahendame sulgudes: $4-3=1$
2. Korrutame: $6\cdot 1=6$
3. Jagame: ${\frac {6}{5}}=1.2$

Kui meil oleks aga massiiv $x=[x_{1},x_{2},...,x_{n}]$, siis iga $x_{i}$ ​korral korratakse neid samme järjestikku — paralleeltöötlus puudub. Ehedaim näide SISD-arhitektuuriga komponendist on protsessori tuumad.

Flynni taksonoomia SIMD arhitektuur: mitu andmevoogu ja üks käsuvoog. Töötlemiselemendid täidavad käsku.

SIMD (Single Instruction Stream – Multiple Data Streams)

SIMD-i puhul rakendatakse ühte käsku mitme andmevoo puhul samaaegselt ehk tuuakse mängu paralleelsus. See tähendab ka, et andmetele võib ligi pääseda plokkidena, kuna protsessor suudab mitut andmevoogu korraga töödelda.

Võtame näiteks sama avaldise:

$y={\frac {6\cdot (4-x)}{5}}$

Olgu meil massiiv $x=[x_{1},x_{2},...,x_{n}]$ ja soovime arvutada avaldist kõigi $x_{i}$-de jaoks. SIMD-arhitektuuris laetakse korraga näiteks 4 või 8 järjestikust $x_{i}$​ väärtust registritesse ja rakendatakse ühte käsujada (“lahuta 4-st”, “korruta 6-ga”, “jaga 5-ga”) kõigi nende väärtuste peal paralleelselt. Tulemuseks on mitu $y_{i}$ väärtust saadud ühes tsüklis, selle asemel, et teha iga arvutus jadamisi nagu SISD-mudelis.

Flynni poolt 1972. aastal väljastatud paber "Some Computer Organizations and Their Effectiveness" jaotas SIMD-kategooria omakorda kolmeks:

1. Massiiviprotsessor (Array processor) - töödeldakse ühte käsku, kuid iga paralleelne töötlemiselement (ALU - arithmetic logic unit) omab eraldiseisvat mälu ja registrifaili, mis võimaldab andmeid ja tulemusi lokaalselt hoida. Eesmärk on kiiresti opereerida vektoried (ühe dimensionaalne tensor).
2. Toru protsessor (Pipeline processor) - iga töötlemiselement on mõeldud kindla operatsiooni täitmiseks. Andmeid saadakse ühest tsentraalsest primaarmälust ning pärast oma osa rehkendamist kirjutatakse tulemuse tagasi mällu.
3. Assotsiatiivne protsessor (Associative processor) - saab samuti ühtse käsu, kuid iga töötlemiselement teeb teistest sõltumatu otsuse tuginedes oma registri andmetele — kas täita käsku või mitte. See hoiab aega kokku, kuna siis ei pea tingimuslausete jaoks andmeid primaarmälust võtma vaid neid hoiustatakse registrites.

Tänapäeval ei ole eraldi massiiviprotsessoreid või assotsiatiivseid protsessoreid — kõik need kolm tüüpi on üldjuhul integreeritud ühte riistvarasse. SIMD arhitektuur on enim levinud GPU-des.

Flynni taksonoomia MISD arhitektuur: üks andmevoog ja mitu käsuvoogu. Töötlemiselemendid täidavad käsku.

MISD (Multiple Instruction Streams – Single Data Stream)

MISD on üks paralleelarvutuse arhitektuure, kus ühe andmevooga täidetakse mitut erinevat operatsiooni. Konteptuaalselt on MISD masinal mitu protsessorit, kus igaüks täidaks erinevat käsku samade andmetega, kuid Flynni sõnul on see ebapraktiline. Ainuke koht, kus see kasutust leiaks on tulemuse kontrollimine.

Aritmeetiline näide:

$y_{1}=0.75\cdot (2-x)$

$y_{2}=1.5-0.75x$

$y_{3}={\frac {3\cdot (2-x)}{4}}$

Käsuvooks on avaldised ning andmevooks on $x=3$. Kõikide avaldiste väärtuseks teoorias tuleb $y=-0.75$.

Ehe näide selle kasulikkusest on kosmoselennunduses — kanderaketisüsteemi pardal olevad arvutid võivad radiatsiooni tõttu esitada valesid andmeid, mistõttu on oluline teha tehe mitu korda läbi, et tagada korrektne vastus juhul, kui üks peaks valesti arvutama.

Flynni taksonoomia MIMD arhitektuur: mitu andmevoogu ning mitu käsuvoogu. Töötlemiselemendid täidavad käsku.

MIMD (Multiple Instruction Streams – Multiple Data Streams)

MIMD arhitektuuriga seadmed suudavad erinevaid käske erinevate andmega täita — kasutusele tulevad lõimed ning asükroonsus. Tänapäeval on mitme operatsiooni täitmine lahendatud mikroprotsessoritega, kus igaüks on mõeldud oma ülesannet lahendama olles täiesti sõltumatu teistest protsessoritest.

MIMD masinaid saab vastavalt mälualale jaotada kaheks:

1. Jagatud mälualaga (shared memory) - kõikidel protsessoritel on sama kättesaadav mälu, kas tarkvaraliselt või riistvaraliselt. Need võivad olla näiteks UMA (uniform memory access), COMA (cache-only memory access), NUMA (non-uniform memory access) tüüpi.
2. Eraldatud mälualaga (distributed memory) - igal protsessoril on oma lokaalne mälu ning andmete jagamiseks kasutatakse sõnumedastust (MPI - message passing interface).

2018. aasta seisuga on enamus kesktöötlusseadmed MIMD arhitektuuriga, sisaldades mitut tuuma ning võimekust erinevaid käske erinevate andmetega samaaegselt täita.

Veel klassifikatsioone

Järgnevad klassifikatsioonid on edasiarengud Flynni välja pakutud arhitektuuritüüpidest.

SIMT (Single Instruction Stream – Multiple Threads)

SIMT on mudel, mida kasutatakse paralleelarvutustel, kus SIMD ja mitmelõimelisus on kokku pandud. Kõik lõimed (threads) täidavad sama käsku korraga, aga igaühel on oma register ja programmiloendur. See tähendab, et kui üks lõim takerdub või peaks töötamise lõpetama siis protsess ei peatu, kuna teine vaba lõim saab töö üle võtta. See tähendab, et mäluviivitused on peidetud.

SPMD (Single Program – Multiple Data Streams)

SPMD on üks MIMD-i alamkategooria. SPMD kasutatakse arvutusmudelite kirjeldamiseks, kus mitu erinevat protsessorit suhtlevad omavahel, et ühte programmi täita. Sarnaneb kõige rohkem MIMD arhitektuurile, kuna suhtlus protsessorite vahel toimub sõnumedastusena (MPI), seetõttu ka on kasutusel eraldatud mäluala.

MPMD (Multiple Programs – Multiple Data Streams)

MPMD on teine MIMD-i alamkategooria, kus erinevad protsessorid täidavad erinevaid programme erinevate andmevoogudega. Näiteks kui on vaja modelleerida laiaulatuslikku keskkonda siis võivad erinevad protsessorid simuleerida erinevaid aspekte — üks arvutab õhuvoolu dünaamikat ja teine veevoolu mustreid.

Vaata ka

• Feng’s classification
• Duncan’s taxonomy