Mokslo ir technologijų pasaulis

Skaičiavimo mašinų istorija: kur yra pati silpniausia daugumos šiuolaikinių procesorių vieta, kaip atsirado ir kas negerai su von Neumanno architektūra ir ką tokio ekspertai surado Intel procesoriuose?
Publikuota: 2019-09-15

Kas yra barzdaskučio paradoksas, kuo skiriasi Prinstono architektūra nuo Harvardo ir kur silpniausia daugumos šiuolaikinių procesorių vieta?

Pavyzdžiui, XIX amžiaus pradžioje Vengrijoje dirbo János Bolyai. Ir su savo tėvu jie vystė tai, kas vėliau pavadinta neeuklidine geometrija, ir tai, kas vadinama „Lobačevskio (hiperboline) geometrija“. Tada jie sukūrė klasikinius šios srities darbus. Gerokai vėliau, XIX–XX amžių sandūroje, ten dirbo Alfréd Haar. Jis atliko tai, kas „iššovė“ tik po šimto metų. Jis sugalvojo vadinamąją „Haaro vilnelę“. Vilnelė — speciali funkcija, o Haaro vilnelė — labai paprasta vilnelė, plačiai naudojama skaitmeniškai apdorojant signalą. Jo garbei taip pat pavadintos Haaro kaskados. Ir praktiškai visi užsiimantieji mašininiu matymu, žino, kad naudojant Haaro kaskadas, sukurtas Viola-Jones algoritmas, esantis bet kuriame fotoaparate, kur apie veidą nupiešiamas kvadratėlis. Tai įmanoma dėl Haaro kaskadų ir jo šimto metų senumo išradimo.

Taip pat galima atsiminti, ko gero, daugiausiai nuveikusį visų laikų ir tautų mokslininką — Paul Erdős, kuris darbavosi XX amžiaus viduryje ir antroje pusėje. Jis garsus tuo, kad yra labiausiai cituojamas žmogus Žemėje. Jo ir Israel Gelfand mokinys Endre Szemerédi 2012 metais buvo apdovanotas Abelio premija už diskretinės matematikos, skaičių teorijos ir informatikos vystymą. Kai kurie jo atradimai naudojami ir dabar. Tai – irgi vengrų mokslininkas.

Pažymėtina, kad Erdős ir Szemerédi buvo Budapešto universiteto absolventai. Ir tą patį universitetą 1926 metais baigė John von Neumann, tik tada ji buvo ne Džonas, o Janošas. Ir čia norėčiau stabtelėti. Disertaciją jis apgynė 1926 metais. Jo disertacija buvo labai charakteringa, nes joje nagrinėtas labai svarbus matematikos aspektas. 1880 metais Georg Cantor pasiūlė aibių teoriją — tai, kas dabar vadinama „naiviąja aibių teorija“. Ir šis atradimas, žinoma, buvo svarbus proveržis, nes aibių teorija žadėjo suvienyti visą matematiką. Tai buvo nelyginant „visko teorija“ fizikoje. Šioje teorijoje teigiama, kad praktiškai bet kokį matematinį objektą galima sukonstruoti iš aibių. Ką bepaimtumėme, — figūra, funkcija — visa tai yra aibės. Tiesiog reikia tai teisingai aprašyti kaip aibes.

Ir tai buvo gan revoliucingas matematinis atradimas. Tačiau amžių sandūroje Bertrandas Russellas suformulavo Russello paradoksą, kurį dauguma žino kaip „barzdaskučio paradoksą“. Jis skamba taip: barzdaskutys skuta visus, kurie nesiskuta patys. Ar skutasi barzdaskutys? Nes jeigu jis skutasi, – jis skuta tą, kuris skutasi pats. O jis to daryti negali pagal sąlygą. Lygiai taip formuluojamas ir aibių teorijos paradoksas. Jeigu yra aibės, kuriose jų pačių nėra, galima jas surinkti, sukurti iš jų aibę ir paklausti: štai šioje aibėje, kurioje yra kitos aibės, ji pati yra ar ne? Jeigu yra, tada ji netekina jos elementams keliamo reikalavimo. O jeigu joje jos pačios nėra, tada, akivaizdu, ji nėra pilna, nes ji yra būtent tokia aibė. Šis paradoksas labai smarkiai supurtė aibių teorijos padėtį. Ir mokslininkai metėsi gelbėti aibių teoriją, nes tai – labai geras instrumentas, kurį būtų gaila prarasti. Ir XX amžiaus pradžioje buvo stengiamasi aksiomatizuoti aibių teoriją taip, kad šio paradokso kaip nors būtų galima išvengti. Ir amžiaus pradžioje tuo užsiėmė E. Zermelo ir A. Fraenkel. Jie sugalvojo aksiomų sistemą, tapusią aibių teorijos aksiomitizacijos pagrindu. O pats J. von Neumannas 1926 metais apgynė disertaciją, kurioje pasiūlė du aibių teorijos gelbėjimo būdus. Ir vienu iš tų būdų buvo pagrindo aksioma. Jos esmė tokia: negalime tvirtinti, kad kažkas yra aibė, jei negalime to nuosekliai sukonstruoti, naudodamiesi žinomomis aksiomomis.

Tai yra, prieš sukurdami kokią nors aibę, privalome nueiti visą kelią iki jos, tiesiog konstruodami ją nuo pat paprasčiausių elementų, nuo tuščios aibės ir esančių aksiomų. Jei to atlikti negalime, tada tai ir nėra aibė. Negalime teigti, kad ji egzistuoja.

Kaip antrą būdą jis pasiūlė tai, ką vadiname aibe, padalinti. Nes G. Cantor padarė klaidą: jis pasiūlė gan silpną aibės apibrėžimą, buvo neaišku, kas ji tokia. „Kokia nors objektų esatis“. Ir von Neumannas pasiūlė atskirti aibę nuo klasės. Klasė — irgi elementų rinkinį apibrėžianti sąvoka, tačiau ji negali būti kitose aibėse. Pavyzdžiui, toks rinkinys yra visų aibių aibė, jos negalima įdėti į ją pačią. Taigi, von Neumanno disertacijoje buvo du tokie darbai.

Baigęs universitetą, jis dirbo Berlyne ir 1930 metais išvyko į JAV, kur ėmė dirbti Prinstono universitete. Ten jis dirbo vos trejetą metų, ir bandė aksiomatizuoti jau sudėtingesnes kvantinės mechanikos užduotis. Tai yra, jis sugalvojo kvantinės mechanikos matematiką. 1933 metais von Neumannas sutiko dirbti visai neseniai, 1930 m., įkurtame Prinstono Pažangiųjų tyrimų institute. Šiame institute dirbo A. Einšteinas, A. Turingas, K. Gödelis, daugybė garsių matematikų ir fizikų, todėl tai tapo savotiška emigravusių mokslininkų Meka. Ketvirtajame ir penktajame XX amžiaus dešimtmetyje daug jų išvyko iš Europos ir šiame institute rasdavo sau vietą.

Pažangiųjų tyrimų institute Johnas von Neumannas irgi sprendė aibių teorijų užduotis, tarp kurių – jo įrodytas atskiras penktos Hilberto problemos atvejis. Hilberto problemos — 23 Davido Hilberto XX amžiaus pradžioje iškeltos problemos, kurios, pasak jo, bus sprendžiamos visą amžių. Ir von Neumannas įrodė vienos iš tų problemų atskirą atvejį. O paskui jo interesų ratas šiek tiek pakito.

Antroje ketvirto dešimtmečio pusėje tame pačiame institute dirbo Alanas Turingas, užsiėmęs skaičiavimo problemomis. Reikia pasakyti, kad skaičiavimo problemos tuo metu buvo itin svarbi matematikos sritis, nes šiokios tokios skaičiavimo mašinos jau egzistavo. Jos buvo gana siauros specializacijos ir sprendė konkrečias užduotis, dažniausiai karines: pavyzdžiui, skaičiavo balistinių raketų trajektorijas. Ir penktojo dešimtmečio pradžioje daugelis mokslininkų grupių suvokė, kad reikia universalios mašinos, galinčios spręsti ne konkrečius uždavinius, o kuri galėtų būti užprogramuota spręsti bet kokius uždavinius.

Tuo pat metu kaip ir institutas, kuriame dirbo Johnas von Neumannas, šias užduotis Vokietijoje sprendė Konradas Zuse'as. Ir jis sukūrė savo mašinas – Z1, Z2 ir taip toliau, kurios irgi buvo universaliomis skaičiavimo mašinomis. Penktajame dešimtmetyje vienu iš karinių projektų, vėliau labiausiai išgarsėjusių,  tapo ENIAC mašinos kūrimas. Tai buvo pirmoji mašina, turėjusi tapti universaliu skaičiuotuvu. Johnas von Neumannas prisidėjo prie šios mašinos kūrimo kaip konsultantas. Jis nebuvo pagrindinis kūrėjas, tačiau nuveikė svarbų darbą: išanalizavo tokios mašinos problemas, ir parašė „Pirmąjį universalios skaičiavimo mašinos EDVAC sukūrimo projektą“. Tai – antroji mašina, kuri turėjo būti sukurta, atsižvelgiant į pirmos mašinos kūrimo klaidas.

Ir tikriausiai būtent šis Johno von Neumanno dokumentas išgarsino jį visame pasaulyje. Šis dokumentas tapo pagrindu sąvokų, imtų vadinti von Neumanno architektūra. Čia reikėtų pažymėti, kad iš tiesų von Neumannui priskirti šios idėjos autorystę nebūtų tikslu, nes toje ataskaitoj suformuluotos tezės, — visų projekto bendradarbių ir dalyvių idėjų lydinys. Ir jis, kaip sudarytojas, savo vardą paliko tituliniame lape, o kadangi šis dokumentas sparčiai plito, visuomenėje jis sukėlė didelį ažiotažą. Ir tiesiog buvo paprasčiau sakyti „tai von Neumanno dokumentas“. Taip jis ir pavirto „von Neumanno architektūra“.

Taigi, kokia tai architektūra? Ką von Neumannas ir jo kolegos pasiūlė, siekdami sukurti gerą universalią skaičiavimo mašiną? Visų pirma (tuo laiku tai buvo neakivaizdu), jis pasiūlė dvejetainio kodavimo principą. Reikia pasakyti, kad mums tai dabar tiesiog duotybė – žinome, kad visa informacija koduojama dvejetainiu kodu. Tačiau penktajame dešimtmetyje buvo ir alternatyvių būdų, pavyzdžiui, trejetainė logika: 0, -1, +1. Ir tokių mašinų buvo. Tačiau atliekant kai kurias paprastas operacijas, būtent dvejetainis kodavimas buvo iš esmės pranašesnis. Pavyzdžiui, dvejetainius skaičius labai patogu sudėti. Ir paaiškėjo, kad ateityje įsitvirtino būtent šis, dvejetainio kodavimo, būdas.



Dvejetainė sistema – labai paprasta, ir ja galima atlikti skaičiavimus, pavyzdžiui, sudėti skaičius, netgi domino kauliukais.

Kitas von Neumanno architektūros principas – adresavimas. Jei turite kažkokią atminties sritį, galite kreiptis į ją, naudodami tam skaičius. Visada galite pasirinkti skaičių ir gauti to adreso reikšmę.

Paskui buvo labai paprastas nuoseklaus vykdymo principas: jei procesorius vykdo programą ir atlieka komandą, tegul – jei nenurodyta kitaip – ima komandą iš kito atminties laukelio. Tokia architektūra labai supaprastino mašinų programavimą. Procesorius žinojo, ką jam daryti bet kokiu atveju, jei nenurodoma kitaip. Pavyzdžiui, tas „kitaip“ — besąlygiško perėjimo komanda. Arba išsišakojimo komanda, kai procesoriui nurodoma: „Palūkėk, kita komanda bus ne čia, o kitoje operatyvinės atminties vietoje“.

Ir ketvirtoji von Neumanno architektūros idėja, tapusi, ko gero, didžiausia šių taisyklių perlu, — duomenys ir programos laikomos kartu (tai bendro saugojimo principas) ir niekuo nesiskiria. Ir kai žvelgiate į atmintį, negalite vienareikšmiškai pasakyti, duomenys tai ar programa. Ši ypatybė iš tiesų yra itin revoliucinga, nes būtent dėl jos įmanoma sukurti efektyvius kompiliatorius, tai yra, programas, kurios ima programos išeities kodą, kuris iš esmės yra paprastas tekstas ir duomenys, ir toje pačioje atmintyje paversti juos vykdomuoju kodu. Antra vertus, tapo įmanoma kurti kompiuterinius virusus, išnaudojančius pažeidžiamumą, kad įmanoma parašyti kokiu nors duomenis, o paskui juos įvykdyti kaip programą. Tai – esminis kompiuterių virusų principas. Ir šis taisyklių rinkinys tapo daugumos mūsų planetoje veikiančių skaičiavimo mašinų de facto standartu.

Reikia pasakyti, kad pats Johnas von Neumannas po darbų su ENIAC, grįžo į Pažangiųjų tyrimų institutą (Institute of advanced studies – IAS) ir tęsė darbą su pagal tuos pačius principus kuriama mašina. Tai yra, lygiagrečiai buvo kuriamos EDVAC ir IAS mašinos. Tai buvo dvi skirtingos, tačiau vadovaujantis panašiais principais kuriamos mašinos.
Prinstono, arba von Neumanno, architektūros antipodas – Harvardo architektūra. Ji ketvirtą principą postuluoja visiškai priešingai: duomenis ir programas saugosime atskiroje atmintyje, o ją pasiekti galima bus skirtingais kanalais, skirtingomis magistralėmis. Harvardo architektūra naudojama, pavyzdžiui, šiuolaikiniuose mikrokontroleriuose. Dauguma kitų skaičiavimo įrenginių kuriami pagal von Neumanno (Prinstono) architektūrą. Ir kokios von Neumanno architektūros naudojimo pasekmės šiuolaikiniame pasaulyje? Įdomu, kad neatsižvelgėme į vieną itin svarbų momentą: jei duomenys ir programos saugomi toje pačioje vietoje, tai ir nuskaityti juos teks tuo pačiu būdu. Ir tai, kas vadinama magistrale (angl. – bus) – procesorių ir atmintį jungiantys laidai, tapo silpnąja von Neumanno architektūros vieta. Paaiškėjo, kad duomenų ir komandų pasiekimas, lyginant su procesoriaus veikimo sparta — labai ilga operacija. Ir todėl kartais tenka itin ilgai laukti, kol duomenys pateikiami skaičiavimui.

Tokią problemą, aišku, reikėjo kažkaip spręsti. Tačiau kadangi sistemos vystosi, kompiuterių pasaulyje labai daug, ją reikia spręsti iteratyviai. Kaip ją išspręsti pasiūlė inžinieriai? Nagi, sugalvokime specialią, vadinamą podėliavimo, atmintį. Ji veiks procesoriuje, bus trumpalaikė ir lengvai pasiekiama mūsų duomenų, pavyzdžiui, esančių standžiajame diske, kopija operatyvioje atmintyje. Podėliavimo atmintyje esančius dažnai naudojamus duomenis galima greitai pasiekti. Ir būtent todėl, kad duomenys ir komandos dažnai būna skirtingose atminties srityse, buvo pasiūlyta podėliavimo atmintį padalinti į duomenų atmintį ir komandų atmintį. Tai yra, von Neumanno architektūros problemos sprendimas buvo Harvardo architektūros panaudojimas — atminties padalinimas į dviejų paskirčių atmintį. Tokia štai įdomi situacija.

Ir taip sugebėjome paspartinti mašinas. O 2017 metais įvyko labai įdomus įvykis: tyrėjai daugumoje šiuolaikinių procesorių aptiko du labai nemalonius pažeidžiamumus – Meltdown ir Spectre. Jie būtent ir remiasi tuo, kas buvo panaudota von Neumanno architektūros problemos sprendimui, — podėliavimo atminimi. Idėja tokia: daugumoje šiuolaikinių procesorių yra realizuotas „spekuliatyvusis vykdymas“: jei vykdote kokią nors programą ir reikia sulaukti duomenų iš operatyviosios atminties, galima programą pradėti vykdyti šiek tiek iš anksto – kol pasiekiate tą programos vietą, kurioje prisireikia duomenų, jie jau būna spėję ten atkeliauti. Spekuliatyvus vykdymas turi problemą – kai atsiduriate programos išsišakojime, jis nežino, kuria atšaka eiti. Ir tenka kažkaip rinktis, perėjimus prognozuoti. Dažnai gali paaiškėti, kad tai ne jums reikalinga atšaka. Ir paaiškėjo, kad tik Intel kompanijos procesoriuose spekuliatyviam vykdymui prieš pasukant į atšaką, nėra tikrinamos prieigos teisės, tai yra, ar programa turi leidimą šią atmintį pasiekti.

O antrasis pažeidžiamumas – universalus, todėl, kad niekaip nesusijęs su procesorių problemomis. Jis remiasi vien tik podėliavimo atminties koncepcija. Jei galima naudotis podėliavimo atmintimi, tai galima, matuojant atminties pasiekties laiką, paskaičiuoti, ar kokia nors informacija yra podėlyje, ar ne, programa ją skaitė ar ne. Naudojantis šiomis žiniomis, galima atkurti, kokius duomenis programa pasiekė. Ir netgi nebūtina žinoti, kokie tai duomenys. Naudojantis šiuo pažeidžiamumu, galima pabandyti gauti kokius nors slaptažodžius, net neturint jokių teisių.

Šie pažeidžiamumai, savaime suprantama, gerokai nuvertino Intel akcijas ir sukūrė precedentą, kurį reikia nedelsiant spręsti. Daugelis kompanijų šią problemą sprendžia, išleisdami programinius pataisymus. Tai greitas ir „purvinas“ būdas, nes išspręsdamas saugumo problemą, sumažina procesorių našumą. Ir tikriausiai akivaizdu, kad tinkamas sprendimas – nauji procesorių kūrimo sprendimai ar netgi nauja architektūra. Jau dabar, pavyzdžiui, skaičiavimams toli gražu ne visada naudojami klasikiniai Intel ar AMD procesoriai. Daugelis mokslininkų skaičiavimams naudoja grafikos procesorius. Google kompanija kuria tenzorinius procesorius, greitai dauginančius matricas. Žiūrint bendrai, procesoriai vis labiau specializuojasi. Ir visai įmanoma, kad greitai išvysime kokias nors naujas architektūras, kurios smarkiai skirsis nuo von Neumanno ir Harvardo architektūros.


Fizikos-matematikos mokslų kandidatas S. Protasov:

Kai buvau studentas, knygų turgelyje į rankas pateko knygelė „Mažoji matematikos enciklopedija“. Knyga buvo išleista Budapešte, ir gerokai nustebau, kad ji buvo išleista rusiškai ir kaip gerai joje parinkta medžiaga. Pamaniau: „Kas tokio yra Budapešte, kad jame leidžiamos tokios matematikos knygos?“ O vėliau sužinojau, kad Vengrija — itin stiprių matematikų kalvė.