本篇目標(biāo)：

1.設(shè)計(jì)訪存指令格式；

2.修改譯碼模塊；

3.完成對RAM的控制，實(shí)現(xiàn)訪存指令；

4.利用訪存指令遍歷數(shù)組；

5.算法進(jìn)階：素?cái)?shù)篩。

?

上一篇我們介紹并實(shí)現(xiàn)了分支指令，使得我們的處理器可以不再按序執(zhí)行指令了，可以飄逸一些，跳著執(zhí)行?；谶@個特性，我們的處理器可以運(yùn)行更加豐富一些的程序。本篇我們將繼續(xù)拓展我們的指令和處理器，添加訪存指令，允許處理器訪問內(nèi)存。本篇之后我們的處理器就基本完備了，麻雀雖小，五臟俱全。

?

1.設(shè)計(jì)訪存指令格式；

簡單回顧一下我們現(xiàn)在有了什么，首先是我們的一步一步用與或非基礎(chǔ)邏輯門搭建起來的電路，一個玩具型CPU：

該CPU目前可執(zhí)行加法減法異或和分支等7條指令，可以執(zhí)行一些簡單的任務(wù)，這是指令的格式：

我們不難注意到，這里的waddr和兩個raddr都是3比特的，也就是說，我們的寄存器文件一共有8個寄存器，多了就不行了。但是有些任務(wù)需要比較大的空間，比如說我們需要給100個數(shù)排序，那我們至少得有地方放下100個數(shù)吧。這個電路就8個寄存器肯定是辦不了的。于是，很自然地，我們需要一個“大倉庫”——數(shù)據(jù)存儲器。

?

這個大倉庫理論上可以是類似寄存器文件的那種樣子，只不過不是8個寄存器地址端口3位，而是256個，地址端口8位，或者65536個，地址端口16位，又或者是42億個，地址端口32位……實(shí)際上呢，我們需要的空間比較大，而寄存器這個玩意又比較貴，所以我們的大倉庫并非是用寄存器搭建的，而是用其他的存儲。但是它們的行為邏輯和寄存器文件是類似的。在邏輯上把我們要的倉庫看做是RegFile問題也不大。它的外部封裝的這樣的：

它和大RegFile的功能是類似的，只是他的讀寫端口就一個，不能同時進(jìn)行讀寫，只能干一個，要么讀，要么寫。OK，我們接受這個預(yù)設(shè)，問題不大。因此，很自然地，在指令設(shè)計(jì)上，我們需要兩條指令，一條往倉庫里面存東西的STORE指令，一條去倉庫里面取東西的LOAD指令，我們找到兩個尚未被使用過的編碼來表示這兩條指令：

STORE：0001

LOAD：0010

這里有一個細(xì)節(jié)，就是這兩條指令都需要指明范圍倉庫的地址。這里我們故意把倉庫地址設(shè)計(jì)成16位，而我們的RegFile中的寄存器也是16位。這樣，我們就正好可以用某一個寄存器來存儲地址信息，指令在訪問的時候，就不需要指明具體地址，只要指明寄存器號既可。這里我們約定STORE和LOAD指令的要去訪問倉庫的那個地址寄存器號是raddr1。同時，LOAD指令需要把倉庫里取回來的值寫回RegFile，所以LOAD指令需要waddr來指示取回到哪一個寄存器。STORE就不需要了waddr，畢竟它是往倉庫里面存東西的，不需要寫回，但是STORE需要告訴倉庫，要存什么呀。這里我們約定STORE是要把某一個寄存器的值存進(jìn)倉庫，所以STORE需要raddr2來指示要去存哪一個寄存器的值。綜述上，我們的STORE和LOAD指令就是這樣的：

誒，為什么STORE和LOAD還需要立即數(shù)呀？這里其實(shí)小小地修改了我們關(guān)于訪問倉庫的地址的那個約定：訪問地址等于基址加上偏移量。

基址就是raddr1指向的寄存器，也就是我們剛剛說的那個。偏移量就是立即數(shù)IMM。為什么要這樣呢？要回答好這個問題，需要編程與編譯方面的一些前置知識，要在這里把它講清楚有那么點(diǎn)小困難。就讓我留一個坑吧，我們直接接受這個預(yù)設(shè)既可，就是訪問地址需要寄存器的值加上立即數(shù)的值得到，運(yùn)算有點(diǎn)類似于ADDI，只不過算出來的結(jié)構(gòu)不是寫回RegFile而是拿去訪問大倉庫的了。這一細(xì)節(jié)將在后兩篇詳細(xì)解釋。

?

我們不妨先寫兩條指令熟悉熟悉，比如說：

STORE x1 0(x2)

LOAD x1 0(x2)

第一條STORE指令的意思就是把1號寄存器的值寫入大倉庫，寫入倉庫的什么地方呢？就是2號寄存器加上0指向的那個地方；相應(yīng)的，第二條LOAD的意思就是去大倉庫取出來一個數(shù)放到1號寄存器，去倉庫的什么地方呢？就是2號寄存器加上0指向的那個地方。這兩條指令的二進(jìn)制機(jī)器碼和十六進(jìn)制機(jī)器碼分別是：

STORE x1 0(x2)（000 1 010 001 000000）（0x1440）

LOAD x1 0(x2)（001 1 001 010 000000）（0x3280）

2.修改譯碼模塊；

我們的訪存指令設(shè)計(jì)好了，需要在譯碼模塊中添加對它們的支持，才能正確地執(zhí)行。首先是識別出這是STORE指令或LOAD指令，類似的實(shí)現(xiàn)方式擴(kuò)展一下既可，就像這樣：

就是那指令的最高4比特出來判斷一下。比較簡單，接下來我們需要給SOTRE和LOAD指令生成正確的S、waddr、raddr等信息。要怎么做呢？老套路，先填一下表（新增信息為紅色）：

由于地址需要寄存器和立即數(shù)相加得到，因此S應(yīng)該是ALU內(nèi)部加法的編碼011；waddr和兩個raddr按照之前的設(shè)計(jì)填寫；他們都需要立即數(shù)，因此imm都是1；LOAD需要寫回，因此wen是1。根據(jù)新的要求，我們開始修改譯碼模塊，變成這樣：

相應(yīng)的，譯碼模塊的外部封裝就變成這樣的：

3.完成對RAM的控制，實(shí)現(xiàn)訪存指令；

接下來我們就要把大倉庫，一般稱作RAM，意思是隨機(jī)訪問存儲器，還有我們新設(shè)計(jì)的譯碼模塊加入到電路中來了，具體的操作是：（1）RAM的時鐘clock和復(fù)位信號reset與處理器本身的一致，直接連接既可；（2）RAM的訪問地址A，應(yīng)該是ALU的輸出結(jié)果，也是直接對接既可；（3）RAM的讀取結(jié)果rdata，如果當(dāng)前是LOAD，那就應(yīng)該接回RegFile,，因此它和ALU的輸出結(jié)果一起進(jìn)復(fù)用器，LOAD信號用作選擇信號；（4）RAM的寫入數(shù)據(jù)wdata，應(yīng)該是raddr2讀取出來的RegFile第二個輸出，將它們連接；（5）RAM的寫使能信號wen，如果是STORE指令則為1，因此它和STORE信號直連。于是我們的電路就是這樣的：

我們在上一篇的加載10000的快速冪算法后面寫一個簡單的STORE和LOAD指令，看看是否符合預(yù)期：

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）

STORE x6 0(x0)（000 1 000 110 000000）（0x1180）

LOAD x1 0(x0)（0011001000000000）（0x3200）

運(yùn)行結(jié)果的這樣的：

4.利用訪存指令遍歷數(shù)組；

有了訪存指令之后，我們就有了一個大倉庫可以倒騰。我們先試試和分支指令結(jié)合起來，嘗試一個數(shù)組玩玩。比如說，把1到100用STORE指令寫入大倉庫里面的100個連續(xù)的格子，再用LOAD指令把它們讀出去累加。程序可以是這樣的：

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

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

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

STORE x6 0(x6)（000 1 110 110 000000）（0x1d80）

SUB x6 x6 x7（100 0 110 110 111000）（0x8db8）

BLT x0 x6 -2（110 0 000 110 111110）（0xc1be）

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

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

LOAD x1 0(x7)（001 1 001 111 000000）（0x33c0）

ADD x2 x2 x1（011 0 010 010 001000）（0x6488）

ADDI x7 x7 1（011 1 111 111 000001）（0x7fc1）

BGE x6 x7 -3（111 0 110 111 111101）（0xedfd）

上機(jī)運(yùn)行的結(jié)果：

得到5050，完美符合預(yù)期，鼓掌~

?

5.?算法進(jìn)階：素?cái)?shù)篩。

最后，我們來玩一個好玩的，讓我們的機(jī)器，這臺由與或非邏輯門搭建出來的簡易的CPU，運(yùn)行我們直接編寫的程序，計(jì)算小于10000的素?cái)?shù)有多少個？（預(yù)期結(jié)果1229）

?

要怎么計(jì)算呢？我們簡單介紹一個篩法：首先一個最簡單的思路就是，在大倉庫里面劃10000一個格子，全都填上1，然后把2的倍數(shù)，也就是偶數(shù)格子里的1改成0，然后是3的倍數(shù)，4的倍數(shù)，5的倍數(shù)，6的倍數(shù)……最后剩下的，沒有被改成0的格子的編號，就是素?cái)?shù)。

?

進(jìn)一步地，我們琢磨一下這個篩法的運(yùn)行，我們注意到到，第一次去掉2的倍數(shù)，應(yīng)該是這樣的：

然后第二輪去掉3的倍數(shù)，應(yīng)該是這樣，有些重疊的，有些沒有：

接下來第四輪去掉4的倍數(shù)，誒，我們發(fā)現(xiàn)，完全重疊，對吼，沒毛病，但凡是4的倍數(shù)的，一定都是2的倍數(shù)，之前就已經(jīng)篩掉了：

接下來是去掉5的倍數(shù)，有些重疊有些沒有：

去掉6的倍數(shù)，哦吼，也是，6的倍數(shù)肯定在之前都篩掉了：

于是，我們可以改進(jìn)一下算法：如果當(dāng)前這個數(shù)，已經(jīng)被改過了，那就不用篩它的倍數(shù)了，它的倍數(shù)肯定都被篩過了。OK，很有效的改進(jìn)，我們接下來熟練一下代碼，首先是加載10000的代碼，用快速冪算法（這里面的x5保存了100，算是一個彩蛋）：

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

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

ADDI x5 x6 25（011 1 101 110 011001）（0x7b99）//x5*x5=10000

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）//x6 = Max = 10000

接下來是初始化10000個格子，全都寫入1,，用的就是簡單循環(huán)：

ADDI x2 x0 2（011 1 010 000 000010）（0x7402）// set i = 2

STORE x1 0(x2)（000 1 010 001 000000）（0x1440）

ADDI x2 x2 1（011 1 010 010 000001）（0x7481）// i++

BLT x2 x6 -2（110 0 010 110 111110）（0xc5be）

然后是篩法的主體算法，是一個雙層循環(huán)。但是我們判斷這個格子是否被篩過，若是，下一個循環(huán)就不開始，直接下一個數(shù)。這里一個彩蛋是，主循環(huán)只需要數(shù)到100既可，為什么呢？留給讀者自證，提示一下，100是10000的平方根。下面是篩法的主體：

ADDI x2 x0 2（011 1 010 000 000010）（0x7402）// set i = 2, start

LOAD x1 0(x2)（001 1 001 010 000000）（0x3280）// x1 = flag[i]

BEQ x1 x0 6（101 0 001 000 000110）（0xa206）// if(x1 == 0) continue

ADD x3 x2 x2（011 0 011 010 010000）（0x6690）// j = i + i

BGE x3 x6 4（111 0 011 110 000100）（0xe784）// if(j >= 10000) end

STORE x0 0(x3)（000 1 011 000 000000）（0x1600）// flag[j] = 0

ADD x3 x3 x2（011 0 011 011 010000）（0x66d0）// j += i

BEQ x0 x0 -3（101 0 000 000 111101）（0xa03d）

ADDI x2 x2 1（011 1 010 010 000001）（0x7481）// i++

BLT x2 x5 -8（110 0 010 101 111000）（0xc578）

最后一步是計(jì)數(shù)，我們要計(jì)算一下還有多少個格子沒有被篩，也是簡單循環(huán)，一個一個累加起來既可：

ADDI x2 x0 2（011 1 010 000 000010）（0x7402）// set i = 2, count

LOAD x1 0(x2)（001 1 001 010 000000）（0x3280）// x1 = flag[i]

ADD x7 x7 x1（011 0 111 111 001000）（0x6fc8）// cnt += x1

ADDI x2 x2 1（011 1 010 010 000001）（0x7481）// i++

BLT x2 x6 -3（110 0 010 110 111101）（0xc5bd）

最后，完整的代碼如下：

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

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

ADDI x5 x6 25（011 1 101 110 011001）（0x7b99）//x5*x5=10000

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）//x6 = Max = 10000

ADDI x1 x0 1（011 1 001 000 000001）（0x7201）// store data = 1, init?????????????

ADDI x2 x0 2（011 1 010 000 000010）（0x7402）// set i = 2

STORE x1 0(x2)（000 1 010 001 000000）（0x1440）

ADDI x2 x2 1（011 1 010 010 000001）（0x7481）// i++

BLT x2 x6 -2（110 0 010 110 111110）（0xc5be）

ADDI x2 x0 2（011 1 010 000 000010）（0x7402）// set i = 2, start

LOAD x1 0(x2)（001 1 001 010 000000）（0x3280）// x1 = flag[i]

BEQ x1 x0 6（101 0 001 000 000110）（0xa206）// if(x1 == 0) continue

ADD x3 x2 x2（011 0 011 010 010000）（0x6690）// j = i + i

BGE x3 x6 4（111 0 011 110 000100）（0xe784）// if(j >= 10000) end

STORE x0 0(x3)（000 1 011 000 000000）（0x1600）// flag[j] = 0

ADD x3 x3 x2（011 0 011 011 010000）（0x66d0）// j += i

BEQ x0 x0 -3（101 0 000 000 111101）（0xa03d）

ADDI x2 x2 1（011 1 010 010 000001）（0x7481）// i++

BLT x2 x5 -8（110 0 010 101 111000）（0xc578）

ADDI x2 x0 2（011 1 010 000 000010）（0x7402）// set i = 2, count

LOAD x1 0(x2)（001 1 001 010 000000）（0x3280）// x1 = flag[i]

ADD x7 x7 x1（011 0 111 111 001000）（0x6fc8）// cnt += x1

ADDI x2 x2 1（011 1 010 010 000001）（0x7481）// i++

BLT x2 x6 -3（110 0 010 110 111101）（0xc5bd）

HALT（000 0 000 000 000000）（0x0000）?

上機(jī)運(yùn)行結(jié)果：

Excellent~

?

最后一小步，我們的取指模塊實(shí)在有點(diǎn)丑，而且這個結(jié)構(gòu)限制了指令只能有32條。一個很自然地想法，也可以用大倉庫來存儲指令：

Logisim這個軟件允許我們以文本形式讀入指令，我們只要想這樣提前把指令準(zhǔn)備好，然后Load Image：

可以看到指令已經(jīng)成功讀入：

最后運(yùn)行的效果是一致的：

事實(shí)上，我們上面介紹的算法是埃式篩法，其實(shí)，有一個歐式篩法會更快，它可以做到每一個合數(shù)都自被篩掉一次，只會它的最小分解的那個素?cái)?shù)篩掉，可以說是相當(dāng)精妙了。但是它理解起來也會比較復(fù)雜，正確性證明和時間復(fù)雜度證明都沒有很直觀，需要小繞一下，感興趣的讀者自行搜索學(xué)習(xí)。其實(shí)主要是教算法這個事，讓我寫高級語言還行，至少來個C吧，要讓我手寫匯編手?jǐn)]機(jī)器碼可太折磨人了（哪有人教算法用匯編的，摔鍵盤.jpg）