Booleanista flip-flopiin — digitaalitekniikan perusteet ohjelmistokehittäjille

Unohdettu kellari

Useimmat ohjelmistokehittäjät työskentelevät kielillä, joiden abstraktiot ovat niin tiheitä, että alla oleva laitteisto muuttuu täysin näkymättömäksi. Pythonia, JavaScriptiä tai Javaa kehittävä ajattelee olioissa, funktioissa ja tietorakenteissa — ei jännitetasoissa, porteissa tai kellosignaalin reunoissa. Jopa C-ohjelmoijat, jotka perinteisesti seisovat lähempänä laitteistoa, pärjäävät nykyään usein vuosia ajattelematta koskaan, mitä fyysisesti tapahtuu suorittimen sisällä, kun he kirjoittavat a + b.

Tämä abstraktio on vahvuus. Se tekee ohjelmistokehityksestä tuottavaa ja antaa meidän kirjoittaa liiketoimintalogiikkaa huolehtimatta transistoreista. Mutta sillä on hintansa: useimmilla kehittäjillä ei ole ajattelumallia siitä, mitä koodin alla tapahtuu. Kun suorituskykyongelmia ilmenee, kun välimuistivaikutukset yllättävät tai kun kommunikaatio laitteistokollegoiden kanssa katkeaa, oireiden tulkitsemiseen tarvittava perusta puuttuu.

Tämä artikkeli rakentaa sillan. Se johtaa tutusta Booleanista — jota jokainen kehittäjä käyttää päivittäin — flip-flopiin, tietokonelaitteiston pienimpään muistielementtiin. Tavoitteena ei ole tehdä ohjelmistokehittäjistä sähköinsinöörejä, vaan rakentaa vankka ajattelumalli: kuva siitä, miten omat if-lauseet ja muuttujat ovat fyysisesti olemassa.

Booleanit, jotka kaikki tuntevat

Jokaisessa yleisessä ohjelmointikielessä on tietotyyppi Boolean — arvo, joka voi saada täsmälleen kaksi tilaa: tosi tai epätosi. Useimmissa kielissä näitä arvoja yhdistetään operaattoreilla, jotka jokainen kehittäjä tuntee unissaan: && JA:lle, || TAI:lle, ! EI:lle ja monissa kielissä ^ poissulkevalle TAI:lle.

Tyypillinen ehto koodissa voisi näyttää tältä:

if (user.isLoggedIn && (user.isAdmin || user.hasPermission)) {
    showAdminPanel();
}

Mitä tässä tapahtuu, on käsitteellisellä tasolla puhdasta lauselogiikkaa. Lauseke arvioidaan yhdeksi totuusarvoksi, joko true tai false. Arviointijärjestys noudattaa selkeitä sääntöjä: ensin sulkeet, sitten JA, lopuksi if-vertailu.

Mitä kehittäjät harvoin tajuavat: nämä operaattorit eivät ole kyseisen ohjelmointikielen keksintöä. Ne eivät ole kääntäjän lisäämiä mukavuusominaisuuksia. Ne ovat suora esitys matemaattisesta rakenteesta, joka on tunnettu 1800-luvulta lähtien — Boolen algebra, nimetty George Boolen mukaan. Ja niillä on toinenkin olemassaolomuoto koodin ulkopuolella: fyysisinä piireinä piistä.

Loogisesta operaattorista porttiin

Logiikkaportti on elektroninen piiri, joka yhdistää yhden tai useamman binäärisen tulon yhdeksi lähdöksi kiinteän säännön mukaan. AND-portti antaa esimerkiksi loogisen 1:n lähtöön vain ja ainoastaan silloin, kun molemmat tulot ovat 1 — täsmälleen sama totuustaulu, jonka &&-operaattori toteuttaa. OR-portti tekee saman ||:lle, NOT-portti (myös invertteri) !:lle, XOR-portti ^:lle.

A	B	A AND B	A OR B	A XOR B
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

Tämä taulukko ei ole vain abstraktia logiikkojen leikkiä. Se on fyysisen piirin tarkka spesifikaatio. Kun piirisuunnittelija integroi AND-portin suorittimeen, hän takaa puolijohdefysiikan kautta, että piiri käyttäytyy täsmälleen kuten nämä neljä riviä totuustaulua.

Erityisen tyylikäs Boolen algebran ominaisuus on NAND-täydellisyys: vain yhdellä porttityypillä — NAND-portilla, joka on AND:n negaatio — voidaan rakentaa jokainen mahdollinen looginen funktio. Invertteri on NAND, jonka molemmat tulot on yhdistetty. AND on NAND ja sen jälkeen toinen NAND invertterinä. OR voidaan myös koota kolmesta NAND-portista. Tämä havainto ei ole vain akateeminen: jotkut puolijohdeteknologiat voivat tuottaa NAND-portteja erityisen tehokkaasti, mikä on johtanut laajaan standardointiin tämän rakennuspalikan ympärille.

Missä bitti fyysisesti elää

Bitti koodissa on abstrakti — 0 tai 1. Laitteistossa se on jännite. Nykyisin käytössä oleva sopimus: jännite lähellä 0 V edustaa loogista 0:aa, jännite lähellä syöttöjännitettä (tyypillisesti 3,3 V, 1,8 V, 1,2 V tai jopa vähemmän nykyaikaisissa suorittimissa) edustaa loogista 1:tä. Bitti ei siis ole muuta kuin „jännite pisteessä X kynnyksen yläpuolella tai alapuolella“.

Komponentti, joka kytkee näitä jännitteitä, on transistori. Logiikkapiireissä nykyään hallitseva tyyppi on MOSFET (Metal-Oxide-Semiconductor Field-Effect Transistor). Ajattelumallin kannalta yksinkertaistettu näkemys riittää: transistori on elektroninen kytkin, jossa on kolme liitintä. Kaksi niistä on kytkentäreitti, kolmas on ohjauselementti („portti“). Kun porttiin syötetään riittävä jännite, kytkentäreitti muuttuu johtavaksi; ilman sitä se estää. Kytkintä ei siis käytetä mekaanisesti vaan sähköisesti.

Kahdesta tai neljästä tällaisesta transistorista voidaan rakentaa portti. Useista tuhansista porteista aritmeettinen laskentayksikkö. Useista sadoista miljoonista porteista nykyaikainen suoritin. Nykyaikainen älypuhelinsuoritin sisältää suuruusluokassa 15–20 miljardia transistoria pinta-alalla, joka on pienempi kuin peukalonkynsi. Jokainen näistä transistoreista on kytkin, joka voidaan kytkeä päälle ja pois useita miljardeja kertoja sekunnissa.

Portista hyödylliseen piiriin

Yksittäiset portit yksin eivät ole vielä mitään, millä voi laskea. Vasta niiden yhdistäminen tuottaa rakennuspalikat, jotka tekevät ohjelmasta todella käyttökelpoisen. Yksinkertaisin mielekäs esimerkki on kahden bitin yhteenlasku.

Kun lisätään kaksi bittiä A ja B, on neljä mahdollista tulokombinaatiota. Kolme niistä antaa yksinumeroisen tuloksen (0+0=0, 0+1=1, 1+0=1), neljäs kaksinumeroisen summan (1+1=10, eli summa 0 muistinumerolla 1). Summa vastaa täsmälleen tulojen XOR:ia, muistinumero vastaa täsmälleen AND:ia. Tätä piiriä — XOR plus AND — kutsutaan puoliadderiksi.

Puoliadderi voi kuitenkin käsitellä vain yhteenlaskun alimman bitin, koska se ei ota huomioon tulevaa muistinumeroa. Korkeampia numeroita varten tarvitaan kokoadderi, jossa on kolme tuloa: A, B ja muistinumerotulo alemmasta bitistä. Kokoadderi rakennetaan periaatteessa kahdesta puoliadderista ja yhdestä OR-portista.

Kun n kokoadderia ketjutetaan peräkkäin niin, että muistinumero välitetään aina seuraavalle kokoadderille, saadaan n-bittinen adderi. Juuri näin laitteiston yhteenlasku rakennetaan jokaisessa nykyaikaisessa suorittimessa, erilaisilla nopeusoptimoinneilla (kuten carry-lookahead-adderit), mutta ytimessään: ketjutettuja kokoaddereita AND-, XOR- ja OR-porteista.

Kun ohjelmistokehittäjä kirjoittaa koodissaan a + b, lopulta tämä piiri ajetaan — sarja kokoaddereita AND-, XOR- ja OR-porteista, transistoreista, valmistettu seostetusta piistä.

Sama logiikka rakentaa myös multiplekserit (valintapiirit, jotka ovat kaikkialla väylissä ja muistiosoitteistuksessa), dekooderit, vertailijat ja siirtorekisterit. Suorittimen rakennuspalikat on koottu kaikki tämän kuvion mukaan: paljon pieniä, yksinkertaisia portteja, taitavasti yhdistettynä monimutkaisiin toimintoihin.

Laitteiston muisti: flip-flopit

Toistaiseksi kaikki esitellyt piirit ovat olleet kombinatorisia: lähtö riippuu vain tulojen nykyisestä tilasta, ilman mitään muistia. Tällaiset piirit voivat laskea, mutta eivät tallentaa mitään. Jotta suoritin voi pitää muuttujia, se tarvitsee sekventiaalisia piirejä — piirejä, joilla on tila, joiden lähtö ei riipu vain nykyisistä tuloista vaan myös niiden historiasta.

Yksinkertaisin sekventiaalinen elementti on flip-flop. Flip-flop tallentaa täsmälleen yhden bitin. Sillä on kaksi vakaata tilaa — asetettu (Q=1) ja nollattu (Q=0) — ja sitä voidaan vaihtaa niiden välillä tulojensa kautta. Perusvariantti, SR-flip-flop, voidaan rakentaa kahdesta ristiin kytketystä NAND-portista. Nykyaikaisissa suorittimissa yleisimmin käytetty variantti on D-flip-flop, jossa on datatulo D, kellotulo ja lähtö Q. Jokaisella nousevalla kellopulssin reunalla flip-flop ottaa D:n arvon Q:hun ja pitää sen siellä seuraavaan reunaan asti.

Yksittäinen flip-flop tallentaa yhden bitin. 64 yhdessä kellotettua flip-flopia muodostavat 64-bittisen rekisterin. Nykyaikainen suoritin sisältää monia tällaisia rekistereitä: yleisrekisterit, ohjelmalaskurin, tilarekisterit lippuineen. Kaikki ovat vain niputettuja flip-flopeja.

Kun paikallinen int-muuttuja elää koodissasi, se elää erittäin todennäköisesti fyysisesti täsmälleen 32 tai 64 flip-flopissa suorittimen rekisterissä — niin kauan kuin sitä ei ole vuodatettu päämuistiin.

Suuremmat muistit käyttävät muita, tiheämpiä muistisoluja — SRAM (staattinen RAM, käytetään välimuisteissa) käyttää flip-flop-tyyppisiä rakenteita, joissa on kuusi transistoria solua kohden, DRAM (päämuisti) tallentaa bitit varauksena pieniin kondensaattoreihin. Mutta ajattelumalli „yksi muistielementti = yksi flip-flop“ kantaa kaikkien abstraktiotasojen läpi. 1 MB:n välimuisti on käsitteellisesti vain kahdeksan miljoonaa yksittäistä bittimuistia, jotka voidaan osoittaa rinnakkain.

Yhteys teoriaan: äärelliset automaatit

Heti kun laitteistolla on tila, sen käyttäytymistä voidaan kuvata äärellisenä automaattina (Finite State Machine, FSM) — matemaattisena mallina, jossa on äärellinen tilojen joukko, siirtymät niiden välillä ja tuloaakkosto, joka laukaisee siirtymät. Tämä ei ole sattumaa: juuri tämä teoria on luonnollinen työkalu sekventiaalisen laitteiston kuvaamiseen.

Huomionarvoista on, kuinka itsestäänselvästi ohjelmoijat käyttävät äärellisiä automaatteja päivittäin tuntematta termiä:

• TCP-yhteys kulkee tilakoneen läpi, jossa on tilat kuten LISTEN, SYN_SENT, ESTABLISHED, FIN_WAIT, CLOSED.
• Kääntäjän lekseri on ytimeltään äärellinen automaatti, joka ryhmittelee merkkejä tokeneiksi.
• Säännöllinen lauseke käännetään ja suoritetaan sisäisesti äärellisenä automaattina.
• Käyttöliittymän työnkulku tiloilla „syöttö“, „validointi“, „vahvistus“, „onnistuminen“, „virhe“ on myös FSM.

Ohjelmoijat työskentelevät päivittäin tämän abstraktion kanssa. Laitteistokehittäjät käyttävät sitä vain hieman suoremmin: he rakentavat automaatteja piireinä tallentamalla tilakoodauksen flip-flopeihin ja johdottamalla siirtymät porttien kombinatoriseen logiikkaan. Kun on kerran nähnyt sillan, tunnistaa sen kaikkialla — ja huomaa, että äärellisten automaattien teorialla on luonnollisin kotinsa laitteistossa.

Miksi tämä kannattaa tietää

Ohjelmistokehittäjät pystyvät tekemään työnsä myös ilman tätä tietoa. Mutta jokainen, joka on kerran jäljittänyt tämän kaaren, hyötyy useilla tasoilla:

Paremmat ajattelumallit suorituskyvylle. Välimuistivaikutukset muuttuvat uskottaviksi, kun on selvää, että 64 tavun välimuistirivi on yksinkertaisesti 512 flip-flop-tyyppistä muistisolua, jotka osoitetaan lohkona. Haarautumisennustus muuttuu konkreettiseksi, kun tietää, että jokainen ehdollinen hyppy voi osua kymmeneen tai useampaan vaiheeseen pipelinessa. SIMD-käskyt muuttuvat vähemmän mystisiksi, kun ymmärtää, että laitteistossa on yksinkertaisesti 4 tai 8 tai 16 rinnakkaista adderia, jotka toimivat yhdellä käskyllä yhtä aikaa.

Parempi viestintä laitteistokollegoiden kanssa. Jokainen, joka on koskaan työskennellyt sekoitetussa ohjelmisto/laitteistotiimissä, tuntee kitkan rajapinnassa: ohjelmistoihminen ei ymmärrä, miksi „yhden bitin kääntäminen“ kestää puoli päivää; laitteistoihminen ei ymmärrä, miksi ei voi yksinkertaisesti lisätä muutamaa riviä koodia. Yhteinen sanasto, joka sisältää rekisterin, flip-flopin ja kellotaajuusalueen, poistaa suuren osan tästä kitkasta.

Vankka perusta sulautetuille järjestelmille, IoT:lle ja FPGA:lle. Kuka suunnittelee siirtyvänsä jollekin näistä alueista, ei pärjää ilman tätä perustaa. Sulautettu C ilman alla olevan laitteiston ymmärrystä jää sumussa hapuilemiseksi. FPGA-ohjelmointi on ytimeltään suoraa piirisuunnittelua porttien ja flip-flopien tasolla.

Ja lopulta: on yksinkertaisesti hauskaa ymmärtää, millä tasoilla oma koodi toimii. if-lause ei ole vain palanen lähdetekstiä — se on tyylikäs abstraktio useiden käännöskerrosten yli, lopulta maadoitettu fyysisiin jännitteisiin, jotka virtaavat piin läpi.