Fra Boolean til flip-flop — digitalteknik-grundlag for softwareudviklere

Den glemte kælder

De fleste softwareudviklere arbejder i sprog, hvis abstraktioner er så tætte, at den underliggende hardware bliver fuldstændig usynlig. Hvem der udvikler i Python, JavaScript eller Java tænker i objekter, funktioner og datastrukturer — ikke i spændingsniveauer, porte eller klokflanker. Selv C-programmører, der traditionelt står tættere på hardwaren, klarer sig i dag ofte i årevis uden nogensinde at tænke over, hvad der fysisk sker i processoren, når de skriver a + b.

Denne abstraktion er en styrke. Den gør softwareudvikling produktiv og lader os skrive forretningslogik uden at bekymre os om transistorer. Men den har en pris: De fleste udviklere har ingen mental model af, hvad der sker under deres kode. Når performance-problemer dukker op, når cache-effekter overrasker, eller når kommunikationen med hardware-kollegerne går i stå, mangler grundlaget til at fortolke symptomerne.

Denne artikel slår en bro. Den fører fra den velkendte Boolean — som enhver udvikler bruger dagligt — til flip-flop, det mindste hukommelseselement i computerhardware. Målet er ikke at gøre softwareudviklere til elektroingeniører, men at bygge en robust mental model: et billede af, hvordan ens egne if-sætninger og variabler fysisk eksisterer.

Booleans, alle kender

Hvert almindeligt programmeringssprog har datatypen Boolean — en værdi, der præcis kan antage to tilstande: sand eller falsk. I de fleste sprog kombineres disse værdier med operatorer, som enhver udvikler kender i søvne: && for OG, || for ELLER, ! for IKKE, og i mange sprog ^ for eksklusivt ELLER.

En typisk betingelse i kode kunne se sådan ud:

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

Hvad der sker her, er på det konceptuelle plan ren udsagnslogik. Udtrykket evalueres til en enkelt sandhedsværdi, enten true eller false. Evalueringsrækkefølgen følger klare regler: først parentesen, så OG, til sidst if-sammenligningen.

Hvad udviklere sjældent indser: Disse operatorer er ikke en opfindelse fra det respektive programmeringssprog. De er ikke bekvemmeligheds-funktioner, som compileren tilføjer. De er den direkte repræsentation af en matematisk struktur kendt siden 1800-tallet — Boolesk algebra, opkaldt efter George Boole. Og de har en anden form for eksistens uden for koden: som fysiske kredsløb af silicium.

Fra logisk operator til port

En logisk port er et elektronisk kredsløb, der kombinerer en eller flere binære indgange til én udgang efter en fast regel. AND-porten leverer for eksempel kun et logisk 1 ved udgangen, hvis begge indgange er 1 — nøjagtig den samme sandhedstabel, som &&-operatoren implementerer. OR-porten gør det samme for ||, NOT-porten (også kaldet inverter) for !, XOR-porten for ^.

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

Denne tabel er ikke kun et abstrakt logiker-spil. Den er den nøjagtige specifikation af et fysisk kredsløb. Når en chip-designer integrerer en AND-port i en CPU, garanterer de via halvlederfysik, at kredsløbet opfører sig præcis som disse fire linjer i sandhedstabellen.

En særligt elegant egenskab ved Boolesk algebra er NAND-fuldstændighed: Med kun én porttype — NAND-porten, altså negationen af AND — kan enhver mulig logisk funktion bygges. En inverter er en NAND, hvor begge indgange er forbundet. En AND er en NAND efterfulgt af endnu en NAND som inverter. En OR kan også sammensættes af tre NAND-porte. Denne erkendelse er ikke kun akademisk: Nogle halvlederteknologier kan producere NAND-porte særligt effektivt, hvilket har ført til en udbredt standardisering omkring denne byggesten.

Hvor bittet fysisk lever

En bit i kode er abstrakt — et 0 eller et 1. I hardwaren er det en spænding. Den almindelige konvention i dag: En spænding nær 0 V repræsenterer et logisk 0, en spænding nær forsyningsspændingen (typisk 3,3 V, 1,8 V, 1,2 V eller endda lavere i moderne processorer) repræsenterer et logisk 1. En bit er altså intet andet end „spænding ved punkt X over eller under en tærskel“.

Komponenten, der skifter disse spændinger, er transistoren. Den dominerende type i logiske kredsløb i dag er MOSFET (Metal-Oxide-Semiconductor Field-Effect Transistor). Til den mentale model er en forenklet betragtning tilstrækkelig: En transistor er en elektronisk kontakt med tre tilslutninger. To af dem er omskifter-strækningen, den tredje er styre-elementet („gaten“). Når en tilstrækkelig spænding ligger på gaten, bliver omskifter-strækningen ledende; uden den blokerer den. Kontakten betjenes altså ikke mekanisk, men elektrisk.

Af to eller fire sådanne transistorer kan man bygge en port. Af flere tusinde porte en aritmetisk regneenhed. Af flere hundrede millioner porte en moderne CPU. En aktuel smartphone-processor indeholder i størrelsesordenen 15 til 20 milliarder transistorer på et areal mindre end en tommelnegl. Hver enkelt af disse transistorer er en kontakt, der kan tændes og slukkes flere milliarder gange i sekundet.

Fra port til nyttigt kredsløb

Enkelte porte alene er endnu ikke noget, man kan regne med. Først deres samkobling skaber de byggesten, der gør et program rent faktisk brugbart. Det enkleste meningsfulde eksempel er addition af to bits.

Når man adderer to bits A og B, er der fire mulige indgangskombinationer. Tre af dem giver et étcifret resultat (0+0=0, 0+1=1, 1+0=1), den fjerde en tocifret sum (1+1=10, altså sum 0 med mente 1). Summen svarer præcis til en XOR af indgangene, menten svarer præcis til en AND. Dette kredsløb — XOR plus AND — kaldes en halvadder.

En halvadder kan dog kun håndtere det laveste bit i en addition, fordi den ikke tager højde for en indkommende mente. Til de højere cifre brugen man en fuldadder, der har tre indgange: A, B og en indkommende mente fra cifret nedenunder. En fuldadder er i bund og grund bygget af to halvaddere og en OR-port.

Sætter man n fuldaddere i kæde, så menten føres videre til den næste fuldadder, får man en n-bit-adder. Det er præcis sådan, hardware-addition er bygget i enhver moderne CPU, med forskellige optimeringer for hastighed (såsom carry-lookahead-addere), men i sin kerne: kaskaderede fuldaddere af AND-, XOR- og OR-porte.

Når en softwareudvikler skriver a + b i sin kode, kører dette kredsløb til sidst — en række fuldaddere af AND-, XOR- og OR-porte, af transistorer, fremstillet af doteret silicium.

Den samme logik bygger også multipleksere (udvælgelses-kredsløb, der er allestedsnærværende i busser og hukommelsesadressering), dekodere, komparatorer og skifteregistre. Byggestenene i en processor er alle samlet efter dette mønster: mange små, simple porte, klogt sammenkoblede til komplekse funktioner.

Hardwarens hukommelse: flip-flops

Indtil nu har alle de præsenterede kredsløb været kombinatoriske: Udgangen afhænger kun af indgangenes aktuelle tilstand, uden nogen hukommelse. Sådanne kredsløb kan regne, men ikke gemme noget. For at en processor kan holde variabler, har den brug for sekventielle kredsløb — kredsløb med tilstand, hvis udgang ikke kun afhænger af de aktuelle indgange, men også af deres historie.

Det enkleste sekventielle element er flip-flop. En flip-flop gemmer præcis én bit. Den har to stabile tilstande — sat (Q=1) og nulstillet (Q=0) — og kan skiftes mellem dem via sine indgange. Grundvarianten, SR-flip-flop, kan bygges af to krydskoblede NAND-porte. Den variant, der oftest bruges i moderne CPU'er, er D-flip-flop med en data-indgang D, en klok-indgang og en udgang Q. Ved hver stigende klokflanke overtager flip-flop'en værdien af D til Q og holder den der, indtil næste flanke kommer.

En enkelt flip-flop gemmer én bit. 64 flip-flops, der klokkes sammen, danner et 64-bit-register. En moderne CPU indeholder mange sådanne registre: de generelle regneregistre, programtælleren, statusregistrene med deres flag. Alle er intet andet end bundtet sammenkoblede flip-flops.

Når en lokal int-variabel lever i din kode, lever den med stor sandsynlighed fysisk i præcis 32 eller 64 flip-flops i et CPU-register — så længe den ikke spildes til hovedhukommelsen.

Større hukommelser bruger andre, tættere lagerceller — SRAM (statisk RAM, brugt til cache) anvender flip-flop-lignende strukturer med seks transistorer per celle, DRAM (hovedhukommelse) gemmer bits som ladning i ganske små kondensatorer. Men den mentale model „ét lagerelement = én flip-flop“ bærer gennem alle abstraktionsniveauer. En 1 MB cache er konceptuelt intet andet end otte millioner individuelle bit-lagre, der kan adresseres parallelt.

Forbindelsen til teorien: endelige automater

Så snart hardware har tilstand, kan dens opførsel beskrives som en endelig automat (Finite State Machine, FSM) — en matematisk model med en endelig mængde af tilstande, overgange mellem dem og et indgangs-alfabet, der udløser overgangene. Dette er ingen tilfældighed: Netop denne teori er det naturlige værktøj til at beskrive sekventiel hardware.

Det er bemærkelsesværdigt, hvor selvfølgeligt programmører bruger endelige automater hver dag uden at bruge begrebet:

• En TCP-forbindelse gennemløber en tilstandsmaskine med tilstande som LISTEN, SYN_SENT, ESTABLISHED, FIN_WAIT, CLOSED.
• En compiler-lexer er i sin kerne en endelig automat, der grupperer tegn til tokens.
• Et regulært udtryk bliver internt kompileret og udført som en endelig automat.
• Et UI-arbejdsforløb med tilstandene „input“, „validering“, „bekræftelse“, „succes“, „fejl“ er også en FSM.

Programmører arbejder dagligt med denne abstraktion. Hardware-udviklere bruger den blot mere direkte: De bygger automater som kredsløb ved at gemme en tilstandskodning i flip-flops og forbinde overgangene gennem kombinatorisk logik af porte. Når man én gang har set broen, genkender man den overalt — og bemærker, at teorien om endelige automater har sit mest naturlige hjem i hardware.

Hvorfor det er værd at vide

Softwareudviklere kan udføre deres arbejde også uden denne viden. Men hvem der én gang har gennemgået buen, drager fordele på flere niveauer:

Bedre mentale modeller for performance. Cache-effekter bliver plausible, når det er klart, at en cache-linje på 64 byte simpelthen er 512 flip-flop-lignende lagerceller, der adresseres som blok. Branch-prediction bliver konkret, når man ved, at hvert betinget hop kan ramme en pipeline med ti eller flere trin. SIMD-instruktioner bliver mindre mystiske, når man forstår, at hardwaren simpelthen har 4 eller 8 eller 16 parallelle addere, der kører samtidig med en enkelt instruktion.

Bedre kommunikation med hardware-kolleger. Hvem der én gang har arbejdet i et blandet team af software- og hardware-udviklere, kender friktionen ved grænsefladen: Software-personen forstår ikke, hvorfor „bare at vende én bit“ tager en halv dag; hardware-personen forstår ikke, hvorfor man ikke bare kan tilføje et par linjer kode. Et fælles ordforråd, der inkluderer register, flip-flop og klokdomæne, fjerner en stor del af denne friktion.

Solidt grundlag for embedded, IoT og FPGA. Hvem der planlægger at gå ind i et af disse felter, kommer ikke uden om dette grundlag. Embedded-C uden forståelse af den underliggende hardware forbliver tasten i tågen. FPGA-programmering er i sin kerne direkte kredsløbsdesign på port- og flip-flop-niveau.

Og endelig: Det er simpelthen sjovt at forstå, på hvilke niveauer ens egen kode kører. En if-sætning er ikke kun et stykke kildekode — det er en elegant abstraktion på tværs af flere oversættelseslag, til sidst forankret i fysiske spændinger, der flyder gennem silicium.