丨乘法器如何像搭樂(lè)高一樣電路下

從列出豎式的過(guò)程中，你會(huì)發(fā)現(xiàn)，二進(jìn)制的乘法有個(gè)很大的優(yōu)點(diǎn)，就是這個(gè)過(guò)程你不需要背九九乘法口訣表了。因?yàn)閱蝹€(gè)位置上，乘數(shù)只能是0或者1，所以實(shí)際的乘法，就成了位移和加法。在13×9這個(gè)例子里面，被乘數(shù)13表示成二進(jìn)制是1101，乘數(shù)9在二進(jìn)制里面是1001。最右邊的個(gè)位是1，所以個(gè)位乘以被乘數(shù)，就是把被乘數(shù)1101下來(lái)。因?yàn)槎缓退奈欢际?，所以乘以被乘數(shù)都是0，那么保留下來(lái)的都是0000。乘數(shù)的八位是1，我們?nèi)匀恍枰驯怀藬?shù)1101下來(lái)。不過(guò)這里和個(gè)位位置的單純有一點(diǎn)小小的差別，那就是要把好的結(jié)果向左側(cè)移三位，然后把四位單獨(dú)進(jìn)行乘法加位移的結(jié)果，再加對(duì)應(yīng)到我們之前講的數(shù)字電路和ALU，你可以看到，最后一步的加法，我們可以用上一講的加法器來(lái)實(shí)現(xiàn)。乘法因?yàn)橹挥小?”和“1”兩種情況，所以可以做成輸入輸出都是4個(gè)開(kāi)關(guān)，中間用1開(kāi)關(guān)，同時(shí)來(lái)控8開(kāi)關(guān)的方式，這就實(shí)現(xiàn)了二進(jìn)制下的單位的乘我們可以用一個(gè)開(kāi)關(guān)來(lái)決定，下面的輸出是完全輸入，還是將輸出全部設(shè)置 位置去接就好了。如果要左移一位，就錯(cuò)開(kāi)一位接線；如果要左移兩位，就錯(cuò)開(kāi)兩位接線把對(duì)應(yīng)的線路錯(cuò)位連接，就可以起到位移這樣，你會(huì)發(fā)現(xiàn)，我們并不需要引入任何新的、更復(fù)雜的電路，仍然用最基礎(chǔ)的電路，只用不同的接線方式，就能夠?qū)崿F(xiàn)一個(gè)“列豎式”的乘法。而且，因?yàn)槎M(jìn)制下，只有0和1，為了節(jié)約一點(diǎn)開(kāi)關(guān)，也就是晶體管的數(shù)量。實(shí)際上，像13×9這樣兩個(gè)四位數(shù)的乘法，我起來(lái)。因?yàn)檫@樣做，需要很多組開(kāi)關(guān)，如果我們計(jì)算一個(gè)32位的整數(shù)乘法，就要32組開(kāi)我們先拿乘數(shù)最右側(cè)的個(gè)位乘以被乘數(shù)，然后把結(jié)果寫(xiě)入用來(lái)存放計(jì)算結(jié)果的開(kāi)關(guān)里面，然后，把被乘數(shù)左移一位，把乘數(shù)右移一位，仍然用乘數(shù)去乘以被乘數(shù)，然后把結(jié)果加到剛才的結(jié)果上。反復(fù)重復(fù)這一步驟，直到不能再左移和右移位置。這樣，乘數(shù)和被乘數(shù)就像兩列相向而駛的列車(chē)，僅僅需要簡(jiǎn)單的加法器、一個(gè)可以左移一位的電路和一個(gè)右移一位的電路，就能完成整個(gè)乘法。乘法器硬件結(jié)構(gòu)示意制左移、右移以及重新計(jì)算乘法和加法的時(shí)機(jī)。我們還是以計(jì)算13×9，也就是二進(jìn)制的1101×1001來(lái)具體看。這個(gè)計(jì)算方式雖然節(jié)約電路了，但是也有一個(gè)很大的缺點(diǎn)，那就是你應(yīng)該很容易就能發(fā)現(xiàn)，在這個(gè)乘法器的實(shí)現(xiàn)過(guò)程里，我們其實(shí)就是把乘法展開(kāi)，變了“加法+位移”來(lái)實(shí)現(xiàn)。我們用的是4位數(shù)，所以要進(jìn)行4組“位移+加法”的操作。而且這4組操作還不能同時(shí)進(jìn)行。因?yàn)橄乱唤M的加法要依賴(lài)上一組的加法后的計(jì)果，下一組的位移也要依賴(lài)上一組的位移的結(jié)果。這樣，整個(gè)算法是“順序”的，每一組加所以，最終這個(gè)乘法的計(jì)算速度，其實(shí)和我們要計(jì)算的數(shù)的位數(shù)有關(guān)。比如，這里 位，就需要4次加法。而我們的現(xiàn)代CPU常常要用32位或者是64位來(lái)表示整數(shù)，那對(duì)應(yīng)就需要32次或者64次加法。比起4位數(shù)，要多花上8倍乃至16倍的時(shí)間復(fù)雜度是O(N)。這里的N，就是乘法的數(shù)里面的位數(shù)。希望能夠把O(N)的時(shí)間復(fù)雜度，降低到O(logN)。辦法還真的有。和軟件開(kāi)發(fā)里面改算法一樣，在涉及CPU和電路的時(shí)候，我們可以改電路。32位數(shù)雖然是32次加法，但是我們可以讓很多加法同時(shí)進(jìn)行。回到這一講開(kāi)始，我們把位移和乘法的計(jì)算結(jié)果加到中間結(jié)果里的方法，32位整數(shù)的乘法，其實(shí)就變成了32個(gè)整前面順序乘法器硬件的實(shí)現(xiàn)辦法，就好像體育比賽里面的單敗淘汰賽。只有一個(gè)擂臺(tái)會(huì)存下的計(jì)算結(jié)果。每一場(chǎng)新的比賽就來(lái)一個(gè)新的選手，實(shí)現(xiàn)一次加法，實(shí)現(xiàn)完了剩下的還是原來(lái)那個(gè)守擂的，直到其余31個(gè)選手都上來(lái)比過(guò)一場(chǎng)。如果一場(chǎng)比賽需要一天，那么一共要比31場(chǎng)，也就是31目前的乘法實(shí)現(xiàn)就像是單敗淘加速的辦法，就是把比賽變成像賽那樣的淘汰賽，32個(gè)球隊(duì)捉對(duì)廝殺，同時(shí)開(kāi)賽。這樣一天一下子就淘汰了16支隊(duì)，也就是說(shuō)，32個(gè)數(shù)兩兩相加后，你可以得到16個(gè)結(jié)果。后面的比賽也是一樣同時(shí)開(kāi)賽捉對(duì)廝殺。只需要5天，也就是Olog2N)的時(shí)間，就能得到計(jì)算的結(jié)果。但是這種方式要求我們得有16個(gè)球場(chǎng)。因?yàn)樵谔蕴惖牡谝惠啠覀冃枰?6場(chǎng)比賽同時(shí)進(jìn)行。對(duì)應(yīng)到我們CPU的硬件上，就是需要的晶體管開(kāi)關(guān)，來(lái)通過(guò)并聯(lián) ALU，加上的寄存器，我們也能加速乘上面我們說(shuō)的并行加速的辦法，看起來(lái)還是有點(diǎn)兒笨。我們回頭來(lái)做一個(gè)抽象的思考。之所以我們的計(jì)算會(huì)慢，原因其實(shí)是“順序”計(jì)算，也就是說(shuō)，要等前面的計(jì)算結(jié)果完成之后，我們才能得到后面的計(jì)算結(jié)果。最典型的例子就是我們上一講講的加法器。每一個(gè)全加器，都要等待上一個(gè)全加器，把對(duì)應(yīng)的進(jìn)入輸入結(jié)果算出來(lái)，才能算下一位的輸出。位數(shù)越多，越往走，等待前面的步驟就越多，這個(gè)等待的時(shí)間有個(gè)專(zhuān)門(mén)的名詞，叫作門(mén)延遲（GaeDelay）。它取一個(gè)“T”作為符號(hào)。一個(gè)全加器，其實(shí)就已經(jīng)有了3T的延遲（進(jìn)位需要經(jīng)過(guò)3個(gè)門(mén)電路）。而4位整數(shù)，最的計(jì)算需要等待前面三個(gè)全加器的進(jìn)位結(jié)果，也就是要等9T的延遲。如果是64位整數(shù)，那就要變成63×3=189T的延遲。這可不是個(gè)小數(shù)字啊！除了門(mén)延遲之外，還有一個(gè)問(wèn)題就是時(shí)鐘頻率。在上面的順序乘法計(jì)算里面，如果我們想要用更少的電路，計(jì)算的中間結(jié)果需要保存在寄存器里面，然后等待下一個(gè)時(shí)鐘周期的到來(lái)，控制測(cè)試信號(hào)才能進(jìn)行下一次移位和加法，這個(gè)延遲比上面的門(mén)延遲更可觀。那么，我們有什么辦法可以解決這個(gè)問(wèn)題呢？實(shí)際上，在我們進(jìn)行加法的時(shí)候，如果相加的兩個(gè)數(shù)是確定的，那是否會(huì)進(jìn)位其實(shí)也是確定的。對(duì)于我們?nèi)藖?lái)說(shuō)，我們本身去做計(jì)算都是順序執(zhí)行的，所以要一步一步計(jì)算進(jìn)位。但是，計(jì)算機(jī)是連結(jié)的各種線路。我們不用讓計(jì)算機(jī)模擬人腦的思考方式，來(lái)連結(jié)線路。那怎么才能把線路連結(jié)得復(fù)雜一點(diǎn)，讓和低位的計(jì)算同時(shí)出？怎樣才能讓不需要等待低位的進(jìn)位結(jié)果，而是把低位的所有輸入信號(hào)都放進(jìn)來(lái)，直接計(jì)算出的計(jì)算結(jié)我們只要把進(jìn)位部分的電路完全展開(kāi)就好了。我們的半加器到全加器，再到加法器，都是用最基礎(chǔ)的門(mén)電路組合而成的。門(mén)電路的計(jì)算邏輯，可以像我們做數(shù)學(xué)里面的多項(xiàng)式乘法一樣完全展開(kāi)。在展開(kāi)之后呢，我們可以把原來(lái)需要較少的，但是有較多層前后計(jì)算依賴(lài)關(guān)系的門(mén)電路，展開(kāi)成需要較多的，但是依賴(lài)關(guān)系更少的門(mén)電路。我在這里畫(huà)了一個(gè)示意圖，展示了一下我們加法器。如果我們完全展開(kāi)電路，的進(jìn)位和計(jì)算結(jié)果，可以和低位的計(jì)算結(jié)果同時(shí)獲得。這個(gè)的原因是電路是天然并行的，一個(gè)輸C4是前4位的計(jì)算結(jié)果是否進(jìn)位的門(mén)電如果一個(gè)4位整數(shù)最是否進(jìn)位，展開(kāi)門(mén)電路圖，你會(huì)發(fā)現(xiàn)，我們只需要3T的延遲就可以拿到是否進(jìn)位的計(jì)算結(jié)果。而對(duì)于64位的整數(shù)，也不會(huì)增加門(mén)延遲，只是從上往下無(wú)論是這里把對(duì)應(yīng)的門(mén)電路邏輯進(jìn)行完全展開(kāi)以減少門(mén)延遲，還是上面的乘法通過(guò)并行計(jì)算多個(gè)位的乘法，都是把我們完成一個(gè)計(jì)算的電路變復(fù)雜了。而電路變復(fù)雜了，也就意味著晶體管變多了。之前很多同學(xué)在我們討論計(jì)算機(jī)的性能問(wèn)題的時(shí)候，都提到，為什么晶體管的數(shù)量增加可以?xún)?yōu)化計(jì)算機(jī)的計(jì)算性能。實(shí)際上，這里的門(mén)電路展開(kāi)和上面的并行計(jì)算乘法都是很好的例子。我們通過(guò)的晶體管，就可以拿到更低的門(mén)延遲，以及用更少的時(shí)鐘周期完成一個(gè)計(jì)算指令。講到這里，相信你已經(jīng)發(fā)現(xiàn)，我們通過(guò)之前兩講的ALU和門(mén)電路，搭建出來(lái)了乘法器。如果愿意的話(huà)，我們可以把很多在生活中不得不順序執(zhí)行的事情，通過(guò)簡(jiǎn)單地連結(jié)一下線路，就變成并行執(zhí)行了。這是因?yàn)?，硬件電路有一個(gè)很大的特點(diǎn)，那就是信號(hào)都是實(shí)時(shí)傳輸?shù)摹Ｎ覀円部吹搅?，通過(guò)精巧地設(shè)計(jì)電路，用較少的門(mén)電路和寄存器，就能夠計(jì)算完成乘法這樣相對(duì)復(fù)雜的運(yùn)算。是用更少更簡(jiǎn)單的電路，但是需要更長(zhǎng)的門(mén)延遲和時(shí)鐘周期；還是用更復(fù)雜的電路，但是更短的門(mén)延遲和時(shí)鐘周期來(lái)計(jì)算一個(gè)復(fù)雜的指令，這之間的權(quán)衡，其實(shí)就是計(jì)算機(jī)體系結(jié)構(gòu)中RISC和CIC的經(jīng)典歷史路線之爭(zhēng)。如果還有什么細(xì)節(jié)你覺(jué)得還沒(méi)有徹底弄明白，我推薦你看一看《計(jì)算機(jī)組成與設(shè)計(jì)：硬件軟件接口》的3.3這一講里，我為你講解了乘法器是怎么實(shí)現(xiàn)的。那么，請(qǐng)你想，如果我們想要用電路實(shí)現(xiàn)一個(gè)除法器，應(yīng)該怎么做呢？需要