丨乘法器如何像搭樂高一樣電路下

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