【逻辑门的奇妙冒险】第8篇 整个大仓库：访存指令

本篇目标：

1.设计访存指令格式；

2.修改译码模块；

3.完成对RAM的控制，实现访存指令；

4.利用访存指令遍历数组；

5.算法进阶：素数筛。

 

上一篇我们介绍并实现了分支指令，使得我们的处理器可以不再按序执行指令了，可以飘逸一些，跳着执行。基于这个特性，我们的处理器可以运行更加丰富一些的程序。本篇我们将继续拓展我们的指令和处理器，添加访存指令，允许处理器访问内存。本篇之后我们的处理器就基本完备了，麻雀虽小，五脏俱全。

 

1.设计访存指令格式；

简单回顾一下我们现在有了什么，首先是我们的一步一步用与或非基础逻辑门搭建起来的电路，一个玩具型CPU：

该CPU目前可执行加法减法异或和分支等7条指令，可以执行一些简单的任务，这是指令的格式：

我们不难注意到，这里的waddr和两个raddr都是3比特的，也就是说，我们的寄存器文件一共有8个寄存器，多了就不行了。但是有些任务需要比较大的空间，比如说我们需要给100个数排序，那我们至少得有地方放下100个数吧。这个电路就8个寄存器肯定是办不了的。于是，很自然地，我们需要一个“大仓库”——数据存储器。

 

这个大仓库理论上可以是类似寄存器文件的那种样子，只不过不是8个寄存器地址端口3位，而是256个，地址端口8位，或者65536个，地址端口16位，又或者是42亿个，地址端口32位……实际上呢，我们需要的空间比较大，而寄存器这个玩意又比较贵，所以我们的大仓库并非是用寄存器搭建的，而是用其他的存储。但是它们的行为逻辑和寄存器文件是类似的。在逻辑上把我们要的仓库看做是RegFile问题也不大。它的外部封装的这样的：

它和大RegFile的功能是类似的，只是他的读写端口就一个，不能同时进行读写，只能干一个，要么读，要么写。OK，我们接受这个预设，问题不大。因此，很自然地，在指令设计上，我们需要两条指令，一条往仓库里面存东西的STORE指令，一条去仓库里面取东西的LOAD指令，我们找到两个尚未被使用过的编码来表示这两条指令：

STORE：0001

LOAD：0010

这里有一个细节，就是这两条指令都需要指明范围仓库的地址。这里我们故意把仓库地址设计成16位，而我们的RegFile中的寄存器也是16位。这样，我们就正好可以用某一个寄存器来存储地址信息，指令在访问的时候，就不需要指明具体地址，只要指明寄存器号既可。这里我们约定STORE和LOAD指令的要去访问仓库的那个地址寄存器号是raddr1。同时，LOAD指令需要把仓库里取回来的值写回RegFile，所以LOAD指令需要waddr来指示取回到哪一个寄存器。STORE就不需要了waddr，毕竟它是往仓库里面存东西的，不需要写回，但是STORE需要告诉仓库，要存什么呀。这里我们约定STORE是要把某一个寄存器的值存进仓库，所以STORE需要raddr2来指示要去存哪一个寄存器的值。综述上，我们的STORE和LOAD指令就是这样的：

诶，为什么STORE和LOAD还需要立即数呀？这里其实小小地修改了我们关于访问仓库的地址的那个约定：访问地址等于基址加上偏移量。

基址就是raddr1指向的寄存器，也就是我们刚刚说的那个。偏移量就是立即数IMM。为什么要这样呢？要回答好这个问题，需要编程与编译方面的一些前置知识，要在这里把它讲清楚有那么点小困难。就让我留一个坑吧，我们直接接受这个预设既可，就是访问地址需要寄存器的值加上立即数的值得到，运算有点类似于ADDI，只不过算出来的结构不是写回RegFile而是拿去访问大仓库的了。这一细节将在后两篇详细解释。

 

我们不妨先写两条指令熟悉熟悉，比如说：

STORE x1 0(x2)

LOAD x1 0(x2)

第一条STORE指令的意思就是把1号寄存器的值写入大仓库，写入仓库的什么地方呢？就是2号寄存器加上0指向的那个地方；相应的，第二条LOAD的意思就是去大仓库取出来一个数放到1号寄存器，去仓库的什么地方呢？就是2号寄存器加上0指向的那个地方。这两条指令的二进制机器码和十六进制机器码分别是：

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

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

2.修改译码模块；

我们的访存指令设计好了，需要在译码模块中添加对它们的支持，才能正确地执行。首先是识别出这是STORE指令或LOAD指令，类似的实现方式扩展一下既可，就像这样：

就是那指令的最高4比特出来判断一下。比较简单，接下来我们需要给SOTRE和LOAD指令生成正确的S、waddr、raddr等信息。要怎么做呢？老套路，先填一下表（新增信息为红色）：

由于地址需要寄存器和立即数相加得到，因此S应该是ALU内部加法的编码011；waddr和两个raddr按照之前的设计填写；他们都需要立即数，因此imm都是1；LOAD需要写回，因此wen是1。根据新的要求，我们开始修改译码模块，变成这样：

相应的，译码模块的外部封装就变成这样的：

3.完成对RAM的控制，实现访存指令；

接下来我们就要把大仓库，一般称作RAM，意思是随机访问存储器，还有我们新设计的译码模块加入到电路中来了，具体的操作是：（1）RAM的时钟clock和复位信号reset与处理器本身的一致，直接连接既可；（2）RAM的访问地址A，应该是ALU的输出结果，也是直接对接既可；（3）RAM的读取结果rdata，如果当前是LOAD，那就应该接回RegFile,，因此它和ALU的输出结果一起进复用器，LOAD信号用作选择信号；（4）RAM的写入数据wdata，应该是raddr2读取出来的RegFile第二个输出，将它们连接；（5）RAM的写使能信号wen，如果是STORE指令则为1，因此它和STORE信号直连。于是我们的电路就是这样的：

我们在上一篇的加载10000的快速幂算法后面写一个简单的STORE和LOAD指令，看看是否符合预期：

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）

运行结果的这样的：

4.利用访存指令遍历数组；

有了访存指令之后，我们就有了一个大仓库可以倒腾。我们先试试和分支指令结合起来，尝试一个数组玩玩。比如说，把1到100用STORE指令写入大仓库里面的100个连续的格子，再用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）

上机运行的结果：

得到5050，完美符合预期，鼓掌~

 

5. 算法进阶：素数筛。

最后，我们来玩一个好玩的，让我们的机器，这台由与或非逻辑门搭建出来的简易的CPU，运行我们直接编写的程序，计算小于10000的素数有多少个？（预期结果1229）

 

要怎么计算呢？我们简单介绍一个筛法：首先一个最简单的思路就是，在大仓库里面划10000一个格子，全都填上1，然后把2的倍数，也就是偶数格子里的1改成0，然后是3的倍数，4的倍数，5的倍数，6的倍数……最后剩下的，没有被改成0的格子的编号，就是素数。

 

进一步地，我们琢磨一下这个筛法的运行，我们注意到到，第一次去掉2的倍数，应该是这样的：

然后第二轮去掉3的倍数，应该是这样，有些重叠的，有些没有：

接下来第四轮去掉4的倍数，诶，我们发现，完全重叠，对吼，没毛病，但凡是4的倍数的，一定都是2的倍数，之前就已经筛掉了：

接下来是去掉5的倍数，有些重叠有些没有：

去掉6的倍数，哦吼，也是，6的倍数肯定在之前都筛掉了：

于是，我们可以改进一下算法：如果当前这个数，已经被改过了，那就不用筛它的倍数了，它的倍数肯定都被筛过了。OK，很有效的改进，我们接下来熟练一下代码，首先是加载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,，用的就是简单循环：

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）

然后是筛法的主体算法，是一个双层循环。但是我们判断这个格子是否被筛过，若是，下一个循环就不开始，直接下一个数。这里一个彩蛋是，主循环只需要数到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）

最后一步是计数，我们要计算一下还有多少个格子没有被筛，也是简单循环，一个一个累加起来既可：

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） 

上机运行结果：

Excellent~

 

最后一小步，我们的取指模块实在有点丑，而且这个结构限制了指令只能有32条。一个很自然地想法，也可以用大仓库来存储指令：

Logisim这个软件允许我们以文本形式读入指令，我们只要想这样提前把指令准备好，然后Load Image：

可以看到指令已经成功读入：

最后运行的效果是一致的：

事实上，我们上面介绍的算法是埃式筛法，其实，有一个欧式筛法会更快，它可以做到每一个合数都自被筛掉一次，只会它的最小分解的那个素数筛掉，可以说是相当精妙了。但是它理解起来也会比较复杂，正确性证明和时间复杂度证明都没有很直观，需要小绕一下，感兴趣的读者自行搜索学习。其实主要是教算法这个事，让我写高级语言还行，至少来个C吧，要让我手写汇编手撸机器码可太折磨人了（哪有人教算法用汇编的，摔键盘.jpg）