本篇目標(biāo)：

1.設(shè)計(jì)分支指令格式；

2.設(shè)計(jì)譯碼模塊；

3.完成對(duì)PC的控制，實(shí)現(xiàn)分支指令；

4.利用分支指令實(shí)現(xiàn)乘法；

5.算法入門：快速冪。

?

上一篇我們連接了RegFile和ALU，整理了幾個(gè)輸出，設(shè)計(jì)了輸入組合，定義了“指令”，并且設(shè)計(jì)了一個(gè)計(jì)數(shù)器和復(fù)用器的模塊，使得指令可以被自動(dòng)化地執(zhí)行，誕生了第一個(gè)“程序”。接下來我們就要豐富指令的類型，添加分支指令，以支持更豐富的程序。

?

1.設(shè)計(jì)分支指令格式

我們首先回顧一下，上一篇中出現(xiàn)的4種指令，有的是寄存器之間的加法，有的是寄存器加立即數(shù)的，有的是寄存器之間的減法，最好介紹原地交換兩個(gè)數(shù)的時(shí)候，引入了一個(gè)寄存器間的異或，整理如下：

我們的機(jī)器目前可以識(shí)別這些指令，如果把它們按序接入復(fù)用器，就可以自動(dòng)執(zhí)行這些指令?，F(xiàn)在的問題是，執(zhí)行的永遠(yuǎn)是線性的，就是從復(fù)用器的第一個(gè)輸入直到最后一個(gè)輸入。我們想，能不能不那么線性，運(yùn)行取指令的時(shí)候，飄逸一點(diǎn)，跳躍一點(diǎn)。

?

這就需要設(shè)計(jì)分支指令了，它的功能是，如果滿足分支條件，那么那個(gè)計(jì)數(shù)器就就不在是加一，而是加上我們指定的值，或者減去我們指定的值。因此，很自然的，我們需要指定某些值，所以需要用到IMM，同時(shí)我們也需要設(shè)計(jì)分支的條件，這個(gè)一般用的是寄存器之間比較大小?；叵肫饋砦覀兊腁LU有三種判斷，相等、小于、和大于等于。正好，我們就可以設(shè)計(jì)借此出三條分支指令：

這個(gè)BEQ的意思就是branch if equal，相應(yīng)的，BLT就是branch if less than，而BGE自然是branch if great or equal。很顯然，這里的比大小，就是兩個(gè)源寄存器之間比了。我們?nèi)绻@么寫：

BEQ x1 x0 -2

意思就是如果x1和x0相等，則下一次計(jì)數(shù)器減去2。它的二進(jìn)制碼和應(yīng)該是：

101 1 001 000 111110

好勒，我們的分支指令初步設(shè)計(jì)完成。

?

2.設(shè)計(jì)譯碼模塊；

我們不難注意到，現(xiàn)在的這個(gè)機(jī)器的連線，開始有點(diǎn)復(fù)雜了，我們看：

接下來，分支指令的加入又會(huì)變得更加復(fù)雜，比如說，分支指令需要兩個(gè)數(shù)去比大小，但是這倆源寄存器號(hào)的位置和先前指令的位置不太一樣，我們連線的時(shí)候就需要多調(diào)整一下。進(jìn)一步地，分支指令并不需要寫回RegFile，所以寄存器文件的寫回使能wen信號(hào)，不能再是常量1了，我們需要根據(jù)當(dāng)前指令是否要寫回RegFile而動(dòng)態(tài)地給出正確的wen值。這話一說，我們猛然發(fā)現(xiàn)，RegFile的raddr1和radd2還有waddr，也是需要?jiǎng)討B(tài)給出的。因此，我們有必要整理一下我們的電路。

?

首先梳理一下，我們的這個(gè)電路需要多少控制信號(hào)呢？首先是ALU的選擇信號(hào)、然后是兩個(gè)源寄存器號(hào)、接著是否需要IMM參與運(yùn)算以及IMM是多少、最后是是否需要寫回RegFile和寫回寄存器號(hào)。我們可以整理出這樣一個(gè)表：

表中的括號(hào)表示指令本身的第幾位到第幾位。我們現(xiàn)在橫過來看，比如說radd2這行的意思就是：

當(dāng)指令是ADD時(shí)，raddr2等于指令的第5位到第3位；

當(dāng)指令是ADDI時(shí)，raddr2是無所謂的；

當(dāng)指令是SUB和XOR時(shí)，raddr2還是指令的第5位到第3位；

當(dāng)指令是BEQ/BLT/BGE時(shí)，raddr2等于指令的第8位到第6位。

其他的行同理可得。由此，我們就可以為這些信號(hào)設(shè)計(jì)電路了，一個(gè)最簡(jiǎn)易的方案是這樣的：

既然xxx表示無所謂，那么我們就可以取任意值來簡(jiǎn)化電路，例如IMM可以全部都是(5,0)，waddr也可以全都都是(11,9)。同時(shí)，我們也注意到，此時(shí)的S正好等價(jià)于指令的高3位（顯然是設(shè)計(jì)指令的時(shí)候故意的），imm正好等價(jià)于指令的12位（顯然也是故意的），因此可以直連，很有效地簡(jiǎn)化了電路。

?

這就叫做譯碼電路，但是現(xiàn)在還有點(diǎn)小問題。這個(gè)電路下邊的指令分類要怎么得到呢？其實(shí)我們可以觀察一下我們?cè)O(shè)計(jì)出來的指令：

真巧，每一條指令的高四位都不一樣（顯然也是故意設(shè)計(jì)的），我們就可以根據(jù)高四位的值來判斷當(dāng)前是什么指令，現(xiàn)在我們把判斷邏輯加上去，看看新的譯碼電路：

OK，現(xiàn)在我們把這個(gè)譯碼電路封裝成譯碼模塊，這個(gè)一般也叫譯碼器Decoder：

我們把它安裝到之前的處理器電路上，看看效果：

很OK，沒毛病~

3.完成對(duì)PC的控制，實(shí)現(xiàn)分支指令；

接下來我們就要實(shí)現(xiàn)分支指令了，這里的關(guān)鍵顯然在于控制那個(gè)取指令的計(jì)數(shù)器。其實(shí)那個(gè)計(jì)數(shù)器是有名字的，它叫程序計(jì)數(shù)器，Program Counter，一般簡(jiǎn)稱PC。

?

我們可以這樣做：準(zhǔn)備兩套PC的更新方式，一個(gè)是傳統(tǒng)的PC累加一，另一個(gè)就是加上IMM了，具體選擇哪一個(gè)方式更新，取決于當(dāng)前是否是分支指令且分支條件成立了。PC更新的電路可以這樣的：

這里我們把PC擴(kuò)展成5位了，現(xiàn)在最多有32條指令。同時(shí)Decoder模塊需要拉出一個(gè)是否是分支的判斷信號(hào)，這個(gè)也比較簡(jiǎn)單，可以是下面這樣：

左邊是Decoder模塊的內(nèi)部實(shí)現(xiàn)，多出了一個(gè)輸出口，右邊是它的外部封裝。接下來我們需要把這個(gè)東西接回處理器電路，在合適的時(shí)候啟用不一樣的PC更新方式，具體說來就是當(dāng)前是否是分支指令，并且分支條件是否成立，分支條件就是ALU的輸出是不是1：

接下來我們?cè)囼?yàn)一下，寫幾個(gè)分支指令試試我們的電路是否正確執(zhí)行了，是否真的跳轉(zhuǎn)了？我們的程序可以是這樣的：

ADDI x1 x0 31（011 1 001 000 011111）（0x721f）

ADDI x2 x0 21（011 1 010 000 010101）（0x7415）

BGE x1 x2 4（111 0 001 010 000100）（0xe284）

XOR x1 x1 x2（010 0 001 001 010000）（0x4250）

XOR x2 x1 x2（010 0 010 001 010000）（0x4450）

XOR x1 x1 x2（010 0 001 001 010000）（0x4250）

這個(gè)程序在交換兩個(gè)數(shù)之前，先判斷一下1號(hào)寄存器的值是否大于等于2號(hào)寄存器的，如果是，那就跳過交換。這是電路是執(zhí)行情況：

果然跳過去了，沒有觸發(fā)交換。我們不妨再試試往回跳，看看能不能成功，這次程序是這樣的：

ADDI x1 x0 31（011 1 001 000 011111）（0x721f）

ADDI x2 x0 21（011 1 010 000 010101）（0x7415）

XOR x1 x1 x2（010 0 001 001 010000）（0x4250）

XOR x2 x1 x2（010 0 010 001 010000）（0x4450）

XOR x1 x1 x2（010 0 001 001 010000）（0x4250）

BLT x1 x2 -3（110 0 001 010 111100）（0xc2bd）

首先加載1號(hào)31，2號(hào)21，然后交換，最后看一下如果1號(hào)寄存器的值小于2號(hào)的，那就往回跳三條指令，再交換回來。因此程序最后應(yīng)該還1號(hào)31，2號(hào)21。我們?cè)囈幌拢?/p>

OK，沒問題~

4.利用分支指令實(shí)現(xiàn)乘法；

有了分支指令之后，我們的程序就可以豐富一些了，最直觀的一個(gè)應(yīng)用就是我們可以做軟件乘法了。我們知道7乘以6，可以看做是6個(gè)7相加。具體到電路上，一個(gè)累加一個(gè)計(jì)數(shù)既可。比如說我們寫這樣一個(gè)程序：

ADDI x7 x0 1（011 1 111 000 000001）（0x7e01）

ADDI x1 x0 6（011 1 001 000 000110）（0x7206）

ADDI x2 x0 7（011 1 010 000 000111）（0x7407）

ADD x3 x3 x2（011 0 011 011 010000）（0x66d0）

SUB x1 x1 x7（100 0 001 001 111000）（0x8278）

BLT x0 x1 -2（110 0 000 001 111110）（0xc07e）

它的功能就是把7乘以6的值放到了3號(hào)寄存器，我們?cè)囘\(yùn)行一下

沒有問題~更進(jìn)一步地，我們的乘法還可以套娃。畢竟我們的立即數(shù)只有6位，放不下很大的數(shù)。加載大數(shù)可以用乘法來湊。比如說我們想要讓一個(gè)寄存器的值等于10000，又因?yàn)?0000等于25乘以25乘以16，我們準(zhǔn)備兩層循環(huán)就可以做到了，代碼是這樣的：

ADDI x7 x0 1（011 1 111 000 000001）（0x7e01）

ADDI x5 x0 25（011 1 101 000 011001）（0x7a19）

ADDI x1 x0 16（011 1 001 000 010000）（0x7210）

ADDI x2 x0 25（011 1 010 000 011001）（0x7419）

ADD x6 x6 x5（011 0 110 110 101000）（0x6da8）

SUB x2 x2 x7（100 0 010 010 111000）（0x84b8）

BLT x0 x2 -2（110 0 000 010 111110）（0xc0be）

SUB x1 x1 x7（100 0 001 001 111000）（0x8278）

BLT x0 x1 -5（110 0 000 001 111011）（0xc07b）

運(yùn)行起來是這樣的

這里我們還添加了一個(gè)時(shí)鐘計(jì)數(shù)器，就是計(jì)算這個(gè)程序運(yùn)行了多少個(gè)時(shí)鐘周期完成。同時(shí)因?yàn)檫\(yùn)行周期數(shù)比較多，軟件仿真的時(shí)候，需要加快時(shí)鐘頻率，為了操作方便我們添加了一條停機(jī)指令HALT，全0編碼，一旦遇到這條指令，PC就停止變化，完成停機(jī)操作。

?

5.算法入門：快速冪。

我們注意到，乘法套娃確實(shí)可以加載很大的數(shù)，但是這個(gè)運(yùn)行周期就有點(diǎn)多了，加載10000至少1000周期以上了，很明顯這個(gè)方法并不高明。有什么更加漂亮的做法呢？

?

我們注意到，ADD指令其實(shí)可以輕松做到乘以2的操作，如果只要設(shè)定一個(gè)初值，然后一直自己加自己寫回自己，就是一次乘以2的操作了。這樣，我們就可以得到連串2的整數(shù)次冪，也就是2、4、8、16、32、64、128……進(jìn)一步地，我們注意到，任何數(shù)都可以用2的整數(shù)次冪累加而成，比方說10000，它就是8192+1024+512+256+16。所以，加載10000，我們可以這么做：

????????ADDI x6 x0 16（011 1 110 000 010000）（0x7c10）//16

????????ADD x1 x0 x6（011 0 001 000 110000）（0x6230）//x1=16

????????ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//32

????????ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//64

????????ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//128

????????ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//256

????????ADD x2 x0 x6（011 0 010 000 110000）（0x6430）//x1=256

????????ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//512

????????ADD x3 x0 x6（011 0 011 000 110000）（0x6630）//x3=512

????????ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//1024

????????ADD x4 x0 x6（011 0 100 000 110000）（0x6830）//x4=512

????????ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//2018

????????ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//4096

????????ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//8192

????????ADD x6?x6?x1（011 0 110 110 001000）（0x6d88）

????????ADD x6?x6?x2（011 0 110 110 010000）（0x6d90）

????????ADD x6?x6?x3（011 0 110 110 011000）（0x6d98）

????????ADD?x6 x6?x4（011 0 110 110 100000）（0x6da0）

上機(jī)器運(yùn)行一下試試，OK沒問題，我們數(shù)一下用了多少時(shí)鐘周期:

只要18周期，這顯然是要比乘法套娃要快很多。這個(gè)算法就叫做快速冪算法。

?

再進(jìn)一步地，這個(gè)其實(shí)也還不夠好，我們其實(shí)可以根據(jù)10000這個(gè)數(shù)量身定制一個(gè)快速冪。我們知道我們可以現(xiàn)在乘以2了，所以，只要得到了5000，那么一步就可以到10000。那要怎么得到5000呢？只要我們得到2500，那么5000也就有了。那要怎么得到2500呢？只要1250。然后是要625。到了這里625就不是偶數(shù)，不好拆了，這里可以扭一下，我們認(rèn)為625是有600加上25得到的，我們真正需要的是600。繼續(xù)，那要怎么得到600呢，只要300……以此類推，我們的算法步驟就清晰了，順著捋一遍就是加50、加25、乘2、乘2、乘2、加25、乘2、乘2、乘2、乘2，代碼是這樣的：

ADDI x6 x0 50（011 1 110 000 110010）（0x7c32）

ADDI x6 x6 25（011 1 110 110 011001）（0x7d99

ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）

ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）

ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）

ADDI x6 x6 25（011 1 110 110 011001）（0x7d99）

ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）

ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）

ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）

ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）

上機(jī)運(yùn)行，沒問題，而且更快了，只要10個(gè)周期，甚至占用的空間也更少了:

最后，預(yù)告一下，下一篇引入訪存指令之后，我們的機(jī)器就比較完備了，到時(shí)候就可以給大家介紹稍微進(jìn)階一點(diǎn)的算法了。