Pět píšu, jedna si pamatuju
Sčítání pod sebou má dvě části. Číslici, kterou napíšete, a jedničku, kterou si pamatujete do dalšího sloupce. Procesor dělá přesně totéž a ta zapamatovaná jednička je jediné, co je na sčítání doopravdy práce.
Tohle je čtvrtý díl série Jak funguje počítač. Od jediného drátu v ní poskládáme celý počítač a skončíme u toho, proč provoz umělé inteligence stojí, co stojí. Každý díl vysvětlí jednu věc a staví na předchozím.
Napište si pod sebe 47 a 38 a sečtěte to tak, jak vás to učili. Začnete vpravo. Sedm a osm je patnáct, pětku napíšete pod čáru a jedničku si necháte. Pak čtyři a tři je sedm, plus ta zapamatovaná jednička osm. Vyjde 85.
Všimněte si, že jste v tom pravém sloupci vyrobili dvě věci. Číslici, která zůstala dole, a jedničku, která se musela přestěhovat o sloupec doleva. Ta druhá je důvod, proč se sloupce nedají spočítat všechny naráz: než se pustíte do dalšího, musíte vědět, co vypadlo z předchozího.
Té zapamatované jedničce se říká přenos a je o ní celý dnešní díl. Všechno ostatní na sčítání je snadné.
Minulý díl skončil u dvou hradel, ze kterých jaksi mimochodem vypadlo, že 1 + 1 je 10. Dneska z nich postavíme sčítačku na osmibitová čísla a nebude k tomu potřeba žádná nová součástka. Dvojkový zápis, ve kterém se 10 čte jako dvě, zavedl první díl.
Přepínejte A a B, dokud nebudou vyplněné všechny čtyři řádky tabulky. Horní žárovku čtěte jako první číslici výsledku, dolní jako druhou.
Projděte si ty čtyři řádky jako čtyři příklady. 0 + 0 je nula, 0 + 1 i 1 + 0 je jedna a 1 + 1 je dvě, což se dvojkově píše 10. Dole tedy má být jednička právě tehdy, když se vstupy liší, a to je přesně tabulka hradla XOR. Nahoře má být jednička jedině při obou vstupech zapnutých, a to je AND. Obě hradla znáte z minulého dílu.
Minule jsme si řekli, že jakékoli pravidlo, které umíte napsat jako tabulku, se dá postavit z hradel. Sčítání jednoho sloupce je takové pravidlo a ta tabulka má čtyři řádky. Počítání tedy nikdo do součástek dodávat nemusel. Je to jenom jedno z těch pravidel a patří k těm prostším.
Téhle dvojici hradel se říká půlsčítačka. Chybí jí totiž třetí vstup: nemá kam přijmout přenos, který by na ni přišel zprava. V nejpravějším sloupci žádný takový přenos neexistuje, protože vpravo od něj nic není. Tam půlsčítačka stačí. V každém dalším sloupci je k ničemu.
Sloupec, do kterého vede třetí drát
Zpátky ke sčítání pod sebou. Do každého sloupce kromě toho úplně vpravo vedou tři dráty: číslice z prvního čísla, číslice z druhého a přenos, který přišel zprava. Nejvíc, co z nich může vyjít, je 1 + 1 + 1, tedy tři, a tři se dvojkově píše 11. Na výstupu proto pořád stačí dva dráty jako u půlsčítačky. Sloupec nikdy nevyrobí přenos větší než jedna, ať se sčítají čísla jakkoli velká.
Na téhle vlastnosti celé sčítání stojí. Kdyby ze sloupce někdy vypadl přenos dva, musel by do sousedního vést další drát, ten by mohl vyrobit ještě větší přenos a celá stavba by se rozsypala. Takhle je hranice pevná, takže všechny sloupce vypadají úplně stejně a dají se vyrobit podle jedné šablony.
Osm řádků, protože tři dráty se dají nastavit osmi způsoby. Projděte je všechny a sledujte, kterou cestou se přenos dostane ven.
Krabičce, která tohle umí, se říká úplná sčítačka a složí se ze dvou půlsčítaček. První sečte obě číslice. Druhá k jejímu výsledku přičte přenos zprava. Přenos přitom může vzniknout v kterékoli z nich, takže se jejich výstupy spojí hradlem OR, které dá jedničku, když ho ohlásí aspoň jedna.
Proč na dva přenosy stačí hradlo OR
Obě půlsčítačky sice přenos vyrobit mohou, ale nikdy ne obě naráz. Když ho ohlásí první z nich, znamená to, že A i B byly jedničky, a její součet je tedy nula. Druhá půlsčítačka z té nuly vychází a z nuly a přenosu zprava už přenos nevznikne, ať je zprava cokoli. Místo OR by proto stejně dobře posloužilo XOR.
Ve skutečné knihovně součástek se ale úplná sčítačka ze dvou půlsčítaček nestaví. Tahle stavba je výborná na vysvětlení, protože ukazuje, že nic nového není potřeba, jenže na křemíku je zbytečně dlouhá: signál v ní musí projít třemi hradly za sebou. Buňka se proto navrhuje rovnou na úrovni tranzistorů jako jeden obvod a navrhuje se tak, aby se k přenosu dospělo co nejrychleji.
Osm sloupců vedle sebe
Osmibitová sčítačka je osm úplných sčítaček vedle sebe a propojí se jediným způsobem, jaký dává smysl. Každá dostane na starost jeden sloupec, tedy číslici z prvního čísla a číslici z druhého, obě ze stejného místa zápisu. Zespodu z ní vypadne číslice výsledku a přenos jde doleva do sousední krabičky. Do té úplně vpravo žádný přenos nevede, takže se její vstup pro přenos natrvalo připojí na nulu.
Tím je sčítačka hotová. Nic dalšího v ní není a ta samá stavba platí pro osm bitů stejně jako pro čtyřiašedesát. Jen se přidají další krabičky do řady. Od téhle chvíle ji budu kreslit jako jednu krabičku s plusem, podobně jako minule zmizely tranzistory dovnitř hradel. Je to další patro: z tranzistorů hradla, z hradel sčítačka.
Ještě k těm místům v zápisu. Z prvního dílu se jim říká váhy: krajní pravý sloupec má váhu jedna a každý krok doleva ji zdvojnásobí, takže osm sloupců pokryje čísla od nuly do 255.
Zbývá jedna potíž a je to ta samá, kvůli které jste u 47 a 38 nemohli počítat oba sloupce zároveň.
Nastavte si dvě čtyřbitová čísla a klikejte na Krok. Pak zkuste tlačítko s 1111 + 0001 a projděte sloupce znovu.
To klikání vám ale nesmí nic namluvit. Sčítačka nemá kroky ani povely. Všechna hradla v ní jsou zapojená pořád a pracují současně, žádné nečeká, až na něj přijde řada. Tlačítko Krok posouvá čas, nic jiného. Z minulého dílu víte, že hradlo nepřepne okamžitě, a dokud do sloupce nedorazí správný přenos, sloupec poctivě počítá s tím, co na jeho vstupech zrovna je, a ukazuje nesmysl.
Na obrazovce to vypadá jako postup zprava doleva. Uvnitř čipu to žádný postup není, jen vlna změn, která se šíří drátem a za sebou nechává ustálené hodnoty. Nikdo ji neřídí. Prostě to tím směrem trvá déle.
U 1111 + 0001 se to projeví nejhůř. Přenos vznikne úplně vpravo a musí se prokousat všemi sloupci až na druhý konec, takže se výsledek ustálí až po čtyřech zpožděních za sebou. U čtyřiašedesátibitové sčítačky postavené tímhle způsobem je to šedesát čtyři zpoždění v řadě. Proto se jí říká sčítačka s postupným přenosem a proto ji v procesoru nenajdete.
Minule jsem v jednom z boxů psal, že o taktu čipu rozhoduje nejdelší cesta signálu mezi dvěma místy, kde se hodnota ukládá. Tohle je přesně ona. Sčítačka bývá na téhle nejdelší cestě, protože skoro nic jiného v procesoru nemá tak dlouhý řetěz hradel za sebou. Zrychlit sčítačku proto neznamená zrychlit sčítání, ale zvednout takt celého čipu. Proto je návrh sčítaček jedna z nejprobádanějších kapitol číslicového návrhu a proto o něm pořád vycházejí nové práce.
Jak se sčítačka zrychlí, když na přenos nečeká
O každém sloupci se dá říct dvě věci dřív, než se ví, co přijde zprava. Když jsou obě číslice jedničky, sloupec přenos vyrobí, ať se děje co se děje. Když je jednička právě jedna z nich, sloupec přenos propustí, tedy pošle doleva přesně to, co dostal zprava. A když nejsou jedničky ani jedna, nepošle doleva nic.
Obě ta zjištění vzniknou ve všech sloupcích naráz, protože každý se dívá jen na své dvě číslice a na nic nečeká. Z nich se pak dají přenosy pro celou sčítačku dopočítat společně, místo aby jeden putoval přes druhý. Říká se tomu předvídaný přenos a zpoždění s počtem bitů neroste přímo úměrně, ale mnohem pomaleji. Platí se za to plochou, spotřebou a podstatně složitějším zapojením.
Myšlenka není nová. Popsali ji Weinberger a Smith v IBM v roce 1958, ale víc než sto let před nimi na ni narazil Charles Babbage u svého mechanického počítacího stroje. Nazval ji anticipating carriage, tedy předvídající přenos, patřila k nejtěžším problémům, se kterými se u svých strojů potýkal, a její vyřešení považoval za zlom. Mechanismus uměl provést všechny přenosy ve všech řádech jediným pohybem, místo aby je posílal kolečko po kolečku. Přenos je nejpomalejší místo sčítačky bez ohledu na to, jestli ji pohánějí ozubená kola, nebo tranzistory.
Kde všude se v počítači sčítá
Jedno sečtení vypadá jako málo. Sčítačka je přitom jeden z nejpoužívanějších obvodů v celém procesoru a většina toho, co spočítá, nevypadá jako počítání.
Když posunete prstem seznam v telefonu, musí se pro každý řádek spočítat, kde v paměti leží jeho text, a to je sečtení. Program, který projíždí tabulku s objednávkami, se od jedné k druhé posouvá přičítáním. A cokoli, co běží dokola, si drží číslo, ke kterému po každém kole přičte jedničku. Takového sčítání, které obsluhuje jen běh programu, je v procesoru mnohem víc než toho, které jste si objednali vy.
Odčítání se dělá na téže sčítačce, takže pro ně žádný druhý obvod není potřeba. Jak přesně, to si necháme na díl o přesnosti čísel, protože k tomu je potřeba zapsat záporné číslo, a ten zápis si zaslouží vlastní místo. Násobení je pak řada sečtení a posunů, tedy zase ta samá sčítačka, jen použitá víckrát za sebou.
Devátá číslice, která nemá kam jít
Napište dvě čísla do 255. Tabulka pod schématem je obyčejné sčítání pod sebou, jen dvojkové a s řádkem přenosů nahoře. Zkuste 255 + 1.
255 + 1 dá nulu. Všech osm sloupců vyrobilo přenos, každý ho poslal doleva a ten poslední už neměl komu. Osmibitová sčítačka má přesně osm drátů na výsledek a devátá číslice se do nich nevejde. Znáte to z mechanického tachometru, který po 999 999 kilometrech ukáže samé nuly, protože sedmé kolečko tam není.
Počítač o tom ví. Přenos z posledního sloupce je obyčejný drát jako každý jiný a dá se přečíst, takže si ho procesor odloží jako příznak, že se výsledek nevešel. Jestli si toho program všimne, je docela jiná otázka.
Co přetečení natropilo v praxi
Americký letecký úřad nařídil v květnu 2015 všem provozovatelům Boeingu 787, aby letadlům pravidelně vypínali elektrické napájení. Důvod: řídicí jednotky generátorů měly vnitřní čítač, který po 248 dnech nepřetržitého provozu přetekl, a všechny čtyři se tím naráz přepnuly do nouzového režimu. Letadlo by přišlo o veškeré střídavé napájení, a to v jakékoli fázi letu.
Příkaz sám šířku toho čítače neuvádí. Je ale nápadné, že 248,5 dne je přesně doba, za kterou čítač tikající stokrát za vteřinu dojde k číslu 2 147 483 648, tedy k hranici, na které přeteče dvaatřicetibitové celé číslo se znaménkem.
Důsledek je ten z prvního dílu, jen z druhé strany. Kolik drátů na co vyhradíte, se rozhoduje jednou a dopředu. Dokud se do nich vejdete, nepoznáte, že nějaká hranice existuje. V okamžiku, kdy ji přerostete, se nedozvíte „je to moc“, ale dostanete klidně vypadající, úplně špatné číslo.
Zkuste teď v té poslední animaci přepsat jedno z čísel. Výsledek se změní dřív, než stihnete zvednout prst. V té krabičce totiž není nic, co by si minulou hodnotu podrželo. Hradla pořád dokola vyhodnocují dráty, které do nich vedou, a když se vstupy změní, starý výsledek beze stopy zmizí.
Sčítačce to nevadí, ta svou práci odvedla. Chybí jí ale místo, kam výsledek odložit. Zkuste si sečíst delší sloupec čísel pod sebou: po každém řádku si mezivýsledek musíte někam zapsat, abyste k němu mohli přičíst další. Sčítačka takové místo nemá a hradlo, ze kterého je postavená, taky ne.
Potřebovali bychom obvod, který na svém výstupu udrží jedničku i poté, co na vstupu zmizela. Hradlo se ale dívá jen na to, co má na vstupech právě teď, a jakmile se změní, je po předchozí hodnotě.
Zbývá tedy postavit paměť z něčeho, co si ze své podstaty nic nepamatuje.
