在 Minecraft 中，造出一台计算机有多难？ 第1页

12月10日更新：

修改了部分往期更新的内容

<2020>

12月9日更新：

删去了结尾的部分个人观点

7月11日重要更新：

作者开源了作品的存档，并制作了一个数字电路的教学存档，一并放到了github上，有兴趣者可以自取。

5月23日更新：

作者有话说，补在结尾。

5月8日更新：

（已删除，原文为旧存档的获取方式，现已更新存档和链接）

5月7日二更：

上传了第二期工程视频。

5月7日更新：

发现视频不完整，现已补全，因视频时长原因，故分为两段上传。

5月5日更新：

本文已获得作者授权转载！

以下部分内容经过改编和优化，全文重新排版，以作者视角展示全部内容

文章摘自 @季文瀚 ——《基于Minecraft实现的计算机工程》

先献上视频：

（下文图片因来源问题不太清楚）

本工程基于一个叫Minecraft的游戏，我使用的版本是1.4.7。之所以使用一个游戏作为平台，是因为这个游戏可以做到实时运行超大规模集成电路模型（大于10000个逻辑门）并且提供壮观的可视化效果（三维数字电路）。

半年前我刚接触这个游戏的时候，想做一个简单的计算器。国外玩家两年前已经有人做到了，基于整数ALU和直连总线的机器。我开始规划做一个16bit的计算器，输入输出线路一样是直连的，也就是说这个计算器完全是专用的芯片，连单片机的等级都不到。后来我发现这个游戏可以实现更加复杂的东西。原因很简单，游戏只提供了“或”“非”逻辑电路，但理论上“或”“非”门可以表达一切逻辑。同时游戏提供的基于活塞机械的断路，继电器的延时时序特性以及继电器的锁存特性会让很多高级触发器成为可能。换句话说，FPGA能实现的东西这个游戏基本都能实现，区别在于这个游戏提供的是一个纯粹数学模型化的信号系统，元器件是简化的模型而不是现实中根据半导体材料设计的具有一定特性的电子元件，在线路连接的拓扑结构上也和现实中的电路不同。

在造计算器到一半的时候我打算改单片机，也就是具有“图灵完备性”的简单计算机，他可以执行一切计算机程序。我规划了指令集架构，储存器架构和指令发射方式等。随着除法器，可读写储存器，缓冲队列等重要电路结构的设计成功，我开始有了一个大胆的设想，尝试实现一个具有流水线结构，总线结构，溢出中断，堆栈，标志位寄存器，基本的分支预测和乱序执行等现代高级计算机技术的16bit RISC CPU以及一个附属的包含超越函数的单精度浮点处理器32bit FPU（目前只规划作为计算器使用）。

工程进展顺利，只是因为工程量巨大进度较慢。我已经将16bit整数计算器改成了完全时序逻辑电路控制，并且有溢出判断的计算器。这在全世界Minecraft红石电路玩家里应该是首次。这个计算器作为片外系统借用CPU的ALU部分进行运算并经过总线传输数据。目前CPU的ALU，主储存器，和寄存器等EU部分已经完工，内部环状总线已经完工，CU部分，也就是最繁琐的部分正在建设中。而FPU部分已经完成了加法器，乘法器，三角函数运算单元，开方运算单元。至此，整个工程大约有10万门以上的电路。

目前不可逾越的困难是游戏的基准单位延时t是0.1秒，加载地图最大范围是长宽1024m，高256m的范围，这就限制了计算机的运算速度以及造出来的硬件规模。特别是储存器，我的片上程序储存器只有1kb，这对于现实中的储存器容量而言太小了。所以想利用这有限的空间做一个汇编编译器，简易的操作系统实在是太困难。

对于工程的介绍我分为6部分：信号系统，硬件单元和硬件算法，储存器架构和流水线，指令集架构，总线和时钟，图形显示原理。我尽量用非专业的语言来介绍，不可避免会用一些术语。

本工程需要的专业知识基本就是微机原理，数字电路，少许编译原理和计算机图形学。

此处先贴上一张cpu架构图。

其中每一个方框都代表一个或若干个硬件单元，小一点的大约一两百个门电路，大的有几千个门电路。架构图基本是按照实际距离做的，在工程上方俯视看到的结构和架构图可以一一对应。下面的俯视图对应架构图的右半部分（Data Bus以及其围住的右下部分。

ps：目前决定把乱序执行模块取消。

一、信号系统

　　构成超大规模信号系统的逻辑等级基本如下：

　　基本信号元件→基本逻辑门→复杂逻辑门→简单功能结构：组合电路，时序电路，触发器→复合功能结构→硬件功能单元→硬件功能模块→计算机

举例如：

　　或门，非门→与门，异或门→全加器，信号长度转换器，多态选择器，储存器单元，译码器单元，求补码单元，移位器单元→可读写储存器，译码器，加法器，移位器，时钟发生器→加减法器，乘法器，除法器，可读写储存器阵列，寄存器，程序计数器→总线，ALU，CU→计算机

信号元件：

　　先从逻辑底层开始介绍，最主要的原件只有四个，如下图：

从左到右依次为：1.继电器/二极管/锁存器/延时器（同时兼有四个功能）2.红石火把（高电平信号源）3.红石粉（红石导线）4.粘性活塞（可推拉的开/通路元件）。

本工程占地大约600x600x200单位长度。

（原文这里详细介绍了这四个元件的特性，这里就不说了，红石老手都懂，不了解请自行搜索）

视觉信号与显示器：

游戏本身没有显示屏这种东西，但是玩家可以通过各种方式实现视觉上的信息传递。

　　第一种是红石灯。红石灯被充能时会亮，不充能时不亮，这两种状态即可组成图形，和计算机的bitmap一致。

　　第二种是阴影成像。即游戏中白天光照条件下浅颜色的方块凹陷处的阴影会和周围的方块形成反差，也构成了两态信号的图像。而实现方块凹陷的方式就是粘性活塞。

向上传输和BUD：

　　向上传输是游戏提供的一种信号单向向上传输的方式，可以用两种方块实现。如图，左边的萤石，本身有自然发光的作用，同时可以用图中方式向上叠放。正常的方块这样叠放肯定会挡住信号，所以正常方块向上向下传输必须螺旋盘叠，这样会占据更大的空间，于是游戏提供了单向向上传输节约空间。但是可惜游戏没有提供单向向下传输（至少我使用的1.4.7版本没有提供），可以看到如图中左边的萤石信号通路输入端在上方，下方方块的红石导线没有亮，而右边的萤石通路输入端在下方，上方方块的红石导线亮了。另一种单向向上传输的方块是“半砖”，即只占一般空间的砖头，如下左图中右边灰色的砖块。因为只有一半高度，所以这样盘叠不会挡住各自导线的连接。半砖同样只实现单向向上传输。（此处的“萤石灯”和“半砖”我认为理解为透明方块更好。透明方块：对所有不具有完整实心方块普遍特性的方块的统称。鉴别方法：充能法，卡头法，箱子法等。）

　　BUD是游戏中一类类似BUG的信号特性。但是又不能叫做BUG，因为这些特性也可以看做是信号系统的组成部分。由于游戏编程中对于方块更新的检测机制存在一定局限性，所以一些方块会被非正常激活。有一次我调试线路出现了很奇怪的错误，排查了半天才发现是BUD问题。有些时候也可以利用BUD的特性做成特定功能的线路。

实际上游戏中还是有BUG的，有一次我排查了一个多小时竟然发现某个错误的原因是这样的：两个相隔100多米毫无功能关联的继电器，当一个置于2档的时候，另一个会工作不正常。这属于游戏难免会有的BUG，但是有时候一个小BUG会导致整个计算机瘫痪。

逻辑门

游戏提供的二态信号正好对应于二进制0和1，也对应于数字电路里用高低电平表示的信号。所以二态信号系统无论其实现的载体和方式如何，规律必定都是一样的。所以可以用相同的组合和算法构造更复杂的结构。

　　有了四种信号元件如何进一步做成逻辑门呢？

非门利用红石火把被充能方块熄灭的特性，输出相反的信号。

或门更简单，“或”在逻辑上就是只要任意一个输入端（不仅仅是一共2个输入端的情况）输入信号，输出端就一定输出信号。如下左，两个橙色的方块为输入端，只要有一个放上火把，绿色的输出端就会输出信号。下右为简单的组合逻辑，4个输入端组成的或门加上输出端的非门组成的或非门。这种电路一般用于“0判断”，即输入端全为0，输出就有信号，只要有一个输入是1，输出端的红石火把就会灭。

　　可以证明只用或门和非门就能实现一切逻辑，游戏的设计者也只设计了这两种能直接实现的逻辑门，这一点和现实的晶体管电路也很符合。通过在空间上对或门和非门的组合排布就能实现更加复杂的逻辑门。

　　与非门如左，紫色为输入端，橙色为输出端，可以看出输入端连着两个红石火把是两个非门，火把中间通着导线是一个或门，真值表我就不写了，简单计算即可知这是一个与非门。常见的与非门应用也就是RS触发器了，比如右边这个基本RS触发器，低电平有效，紫色输入，橙色输出，RSQQ非就随便怎么分配了，此时图中输入端均有效，输出端无效，当输入端从01或10置为00（高电平）时会锁存。而当输入端同时从00变为11时游戏的方块刷新机制会默认选择其中一个输出端输出1，另一个输出端输出0，当然本身就不用考虑会使用这种情况。所以用与非门构造的RS触发器和现实中基本一致。

与门比与非门复杂一点，只要在与非门基础上加个非门的红石火把就可以了。如下图，下左为标准的与门，两个红色的输入端，紫色为输出端，可以看出是3个非门和一个或门组成的逻辑电路。可能读者仍然不便理解，我就将其转化为框图，如下中图。简单的计算可得只有当两个输入端同时输入1时，输出端为1，和与逻辑相同。下右两个同样为与门，只不过线路排布稍微变化即可变为空间构造不同的与门，可以用于各种不同的布线情况。

活塞断路其实也是与逻辑。广义上的“与”可以看做同时满足各自条件的若干个输入端才能使输出端输出特定信号。比如下左上面的紫色输入端输入0，下面的紫色输入端输入1才能使绿色输出端输出1，而下右活塞原本挡住橙色线路，当活塞被激活将蓝色方块推出时，会使凹下的橙色方块线路与两边联通，这时右边的紫色输入1，左边的绿色才会输出1。即这是输入端必须全为1的标准与门。

之后的复杂信号结构的介绍我都尽量简略，如果真要从头到尾讲清楚，要写一本书。其中涉及到的专业知识太多了，很难让所有读者都能理解，见谅。关于数字电路和微机原理的各种基础知识介绍我都从略。

异或门是数字电路里非常重要的一类复杂逻辑门，是构造全加器以及一切具有ALU运算器结构单元的基础。比较简单的异或门设计如下图左右两种，除了红石导线外，左边一种用到了活塞，火把和中继器，右边一种只用了火把。这两种都是国外玩家设计的，是目前设计出来的体积最小的异或门。我一开始自己设计出的异或门比这两种体积大一点。而基础逻辑门的体积对计算机建设至关重要，基础逻辑门稍微大一点整体结构就将超过地图加载范围。我的工程在设计上如果没有这些高手玩家在基础结构上的设计，是不可能实现的，因为用minecraft实现实时运算超大规模信号系统最重要的难题就是体积问题。

　　这两种异或门右边一种较好，因为游戏中的火把可以在1秒钟内承受8次信号变化才会熄灭，而活塞似乎承受不了这么多次的变化，容易在快速的信号变化中出现差错。所以我的计算机中基本都是采用右边一种异或门。两个橙色方块是输入端，紫色方块是输出端。

其他所有逻辑门都可以通过或，非门的组合得到，就不再详述。

简单功能结构

　　利用逻辑门的组合就可以设计适用于各种功能的信号结构。

　　全加器：全加器可以看做是计算机最核心的部件，之前的一个异或门相当于一个半加器，两个半加器可以组合成一个全加器。由第一种异或门组成的全加器 如下左，下右是4个相同的全加器级联。

但是这种基于活塞的全加器不稳定，所以较为好的设计是如下图的基于第二种异或门设计的全加器。两个红色为输入端，蓝色为进位端，紫色为本位输出端。下右为两个不同颜色的全加器级联。

其他的组合电路，时序电路和触发器就举几个例子。

　　前一部分已经介绍过RS触发器，实际上并不常用。常用的是一些边沿触发的时序电路。下左图为活塞开路的两种最基本的应用，两个同样的蓝色开路线路，作为输入端的红石火把左边在下，右边在上。左边的蓝色线路因为开路的节点（凹下去的地方）比开路输入端的节点更靠近火把，而4档继电器的延迟为0.4秒，活塞的延迟为0.1秒，所以第0.5秒后活塞会伸出使线路开路，这时输入端信号就传不到活塞了。而继电器里可以存下0.4秒的信号，所以再过0.5秒活塞会收回，线路又会通。然后就会这样循环的“开路-通路-开路-通路”下去，每1秒是一个循环。实际的效果就是每1秒钟内可以输出一个0.5秒的信号。右边那条线路输入端通往活塞的节点在开路节点的前面，所以不受开路影响，只要输入端有持久信号就会在0.1秒后永久开路，使得下方输出0.1秒的瞬间信号。必须等待输入端变为低电平活塞才会收回，这等价于一个上沿信号。

　　下右图是一个T触发器，左边紫色为输入端，接一个上沿信号发生器输出0.2秒短信号，右上绿色方块是输出端，T触发器储存一个信号，高电平短信号使触发器工作，效果是使原有信号翻转并储存输出。

下左为短信号转1秒信号器，实际上可以做出任意长度信号之间的转换，比如0.1秒转4秒，5秒转0.2秒等等。下右为3秒短信号轮换器，即第0秒输出短信号到A端，第3秒输出短信号到B端，第6秒输出到A端……

移位触发器，也是很常用的一种结构，可以做成单向或双向。

下左为时钟频率储存器，即长度mt的信号在长度nt为一个周期的环路中（n>m）作循环传递。时钟频率储存器和信号发生器组合可以变成计算机的时钟信号发生器。下右为短信号阻断器（名字值得吐槽，我也不知道该取什么名字= =），可以滤去0.6秒以下的短信号。

下左蓝色部分为4路选择触发器，发射信号选择其中一路并储存该状态，之后发射信号选择其他某一路会清除之前的选择并存进新的选择。下右黑色部分为总线信号清空单元，可以周期性的阻断总线信号通路。

储存器：

见继电器锁存功能的介绍。锁存单元8的并列，然后用同一根线控制锁存，再用一根线控制存储信号的开闭，就组成了一个1byte的储存器。大量储存器组成3D阵列。相邻奇偶编号储存器加上byte/word切换控制模块。最后再用统一的译码模块编码，就成了完整地储存器。

复合功能结构

　　由简单功能结构可以进一步组成复合功能结构，从而完整地实现某一功能。比如全加器级联变成加法器；异或门和加法器串联，然后级联，再加上符号信号端变成求补器等等。

硬件功能单元

　　复合功能单元能执行某一个完整的逻辑功能，比如加法器使两个补码相加，求补器使某个原码求补码。而硬件上加减法器的完整功能一般指从求补码到加减法到求原码返回寄存器或总线的完整过程。

硬件功能模块

　　功能单元足够多的时候就会形成模块。比如加减法器，乘法器，除法器，移位器，布尔逻辑单元等等组成ALU；指令缓冲队列，指令译码器，指令发射端等等组成CU；地址译码器，储存器阵列，寄存器等等组成完整的具有等级结构的储存器体系。功能单元的位置，朝向等都会大大影响布线的困难程度和延时的长短，这对整个计算机的运行效率有至关重要的影响。所以对功能模块的放置需要花很多时间计算，排列，布置。我花了很多时间不断修改，调整。

二、硬件单元及硬件算法

硬件单元列表及特性

硬件算法

　　算法对硬件设计是灵魂，好的算法设计出来的硬件单元可能要比不好的设计节省10倍的运算时间，10倍的空间，10倍的建造精力。总之算法决定ALU的一切。

　　加减法就是常见的补码加法算法，乘法就是级联串行乘法，都没什么特别的。重点介绍后面几个。

BCD/BIN转换算法

　　输入端BCD转BIN算法（这个自己想出来的）

　　想法很直接，BCD十进制码转BIN二进制码按照常规的数学运算就是十进制每一位乘上10的各自位数-1次方。比如123=1x10^2+2x10^1+3。这个反映到二进制算法上就是将BCD每一位数的四个信号乘以10的n次方的二进制值，n为该位数-1，最后所有位再加起来。重要的是这种算法在硬件上实现很简易，所以我也没找其他算法，就直接用了。

输出端BIN转BCD算法

　　这个用的是通用的算法，流程如下：

　　某二进制数一直做左移操作，每一次左移后从第一次移位进入的那个位向左每4个位切断成一组（作为BCD数），然后判断改组是否大于等于5，如果大于等于5则该组+3处理，小于5不用处理。所有组处理完后继续移位，一直移到末尾进入第一次移位的那个位。文字介绍很别扭，可以结合下面的图看。

借用mc论坛上的举例介绍：

　　把Units，Tens，Hundreds和他们所处的那一列统称为1组，另外Binary和它所在的那一列不算一组，表格一行一行看。1组数据对应一个BCD字符，2进制数有多少位就把它往左移多少位。左边的英文是操作，shift是移位，add是加。Units组的最右边一位就是上文指的“第一次移位进入的那个位”。

　　上图是以255为例，下面再以123为例的流程如下：

　　123的二进制数是0111 1011

　　我们先将其左移1位，得到1111 0110

　　目前还在binary那列里，所以继续移位

　　得到0001 1110 1100

　　组里的数字小于5，继续移

　　得到0011 1101 1000

　　继续移位

　　得到0111 1011 0000

　　可以看到Units组里的数字已经大于5了，所以把当前该组里的数据+3处理

　　到1010 1011 0000

　　继续移位

　　得到0001 0101 0110 0000

　　Units组里的数字等于5，所以再加3

　　得到0001 1000 0110 0000

　　继续移位

　　得到0011 0000 1100 0000

　　继续移位

　　得到0110 0001 1000 0000

　　这次是Tens里的数据大于5了，所以+3处理

　　得到1001 0001 1000 0000

　　因为在2进制数前面补了一个0，所以变成了8位的数据，现在还差最后一次的移位

　　得到0001 0010 0011 0000 0000

　　结束

除法算法

　　整个串行的除法器利用减法判断符号来决定上商和恢复余数。由于除法在硬件上的运算密度比较高，串行除法器如果让它完全不受时序控制直接串行推进运算会让电脑负担太大的运算量导致卡顿。这个的主要原因是信号在时间上的重叠，初始信号一开始就传送到了最后，每一行的部分积余数一算完，后面所有的信号都要全部改变一次，会导致几千个红石火把每一秒经历若干次变化（还好总数比8小不至于崩溃）。所以我又设计了一个控制运算推进的时序电路，最终卡顿的情况比原来好了许多。

　　设计出来的硬件单元前文已给出，再贴两张细节。

浮点加减法算法

　　这个也是用的通用算法。

　　按照下面几个步骤来：

　　浮点数由阶码和尾数构成，可以看做是二进制的科学计数法。阶码就相当于科学计数法的那个幂次方数，尾数就相当于有效数字的具体数值。比如0.11x2^3,其中0.11是尾数，3是阶数。IEEE754标准的浮点数规格如下

要不要用偏正值其实无所谓，只要知道单精度浮点数(single precision floating point)的位数是32bit,指数位数=8，尾数位数为=23，还有一位符号位。其中指数位数中有一位是指数的符号位即表示其范围为-127到127，不算这个符号位就是指偏正值0-255，其实含义是一样的。而单独的那个符号位是给整个浮点数用的。

　　设有两个浮点数x和y,它们分别为

　　x＝2Ex•Mx

　　y＝2Ey•My

　　其中Ex和Ey分别为数x和y的阶码,Mx和My为数x和y的尾数。

(1) 比较阶码大小并完成对阶

　　两浮点数进行加减,首先要看两数的阶码是否相同,即小数点位置是否对齐。若二数阶码相同,表示小数点是对齐的,就可以进行尾数的加减运算。反之,若二数阶码不同,表示小数点位置没有对齐,此时必须使二数阶码相同,这个过程叫作对阶。要对阶,首先应求出两数阶码Eｘ和Ey之差,即△E ＝ Ex－Ey。若△E＝0,表示两数阶码相等,即Ex＝Ey；若△E>0,表示Ex<Ey；若△E<0,表示Ex>Ey。当Ex≠Ey 时,要通过尾数的移动以改变Ex或Ey,使之相等。原则上,既可以通过Mx移位以改变Ex来达到Ex＝Ey,也可以通过My移位以改变Ey来实现Ex＝Ey。但是,由于浮点表示的数多是规格化的,尾数左移会引起最高有效位的丢失,造成很大误差。尾数右移虽引起最低有效位的丢失,但造成误差较小。因此,对阶操作规定使尾数右移,尾数右移后阶码作相应增加,其数值保持不变。显然,一个增加后的阶码与另一个阶码相等,增加的阶码的一定是小阶。因此在对阶时,总是使小阶向大阶看齐,即小阶的尾数向右移位(相当于小数点左移）每右移一位,其阶码加1,直到两数的阶码相等为止,右移的位数等于阶差△E。

(2) 尾数求和运算

　　对阶结束后,即可进行尾数的求和运算。不论加法运算还是减法运算,都按加法进行操作,其方法与定点加减法运算完全一样。我这里就照搬常用加减法器。

(3) 结果规格化

　　在浮点加减运算时,尾数求和的结果也可以得到01.ф…ф或10.ф…ф,即两符号位不等,这在定点加减法运算中称为溢出,是不允许的。但在浮点运算中,它表明尾数求和结果的绝对值大于1,向左破坏了规格化。此时将运算结果右移以实现规格化表示,称为向右规格化。规则是：尾数右移1位,阶码加1。当尾数不是1.M时需向左规格化。

(4) 舍入处理

　　在对阶或向右规格化时,尾数要向右移位,这样,被右移的尾数的低位部分会被丢掉,从而造成一定误差,因此要进行舍入处理。简单的舍入方法有两种：一种是"0舍1入"法,即如果右移时被丢掉数位的最高位为0则舍去,为1则将尾数的末位加"1"。另一种是"恒置一"法,即只要数位被移掉,就在尾数的末尾恒置"1"。

　　在IEEE754标准中,舍入处理提供了四种可选方法：

　　就近舍入 其实质就是通常所说的"四舍五入"，这是默认的常用方法。例如,尾数超出规定的23位的多余位数字是10010,多余位的值超过规定的最低有效位值的一半,故最低有效位应增1。若多余的5位是01111,则简单的截尾即可。对多余的5位10000这种特殊情况：若最低有效位现为0,则截尾；若最低有效位现为1,则向上进一位使其变为 0。

　　朝0舍入 即朝数轴原点方向舍入,就是简单的截尾。无论尾数是正数还是负数,截尾都使取值的绝对值比原值的绝对值小。这种方法容易导致误差积累。

　　朝＋∞舍入 对正数来说,只要多余位不全为0则向最低有效位进1;对负数来说则是简单的截尾。

　　朝－∞舍入 处理方法正好与 朝＋∞舍入情况相反。对正数来说,只要多余位不全为0则简单截尾;对负数来说,向最低有效位进1。

　　本浮点加减法器符合IEEE754单精度fp32浮点标准，但由于体积问题没有使用舍入法，所以精度有一定损失。

正余弦算法

　　这个用的是经典的cordic迭代算法中的旋转坐标算法。公式推导如下：

　　将平面坐标系中向量（Xi , Yi）旋转角度θ得到新向量（Xj , Yj）

　　可以看出θ如果拆成许多个小θ，即θ=θ1+θ2+θ3+…+θn，那么作n次旋转即可得到结果。

　　为了方便二进制硬件运算，现构造一个θ序列：

先不管cos θn，构造θn=arctan(1/2^n)，并且满足

Sn表示θ的正负，也就是说构造出的这列θn前面要加正负号，以反复偏大偏小的趋势逼近θ。每一步旋转的角度Zn满足如下条件

综上得

经过N次迭代后

　　这个K就是一坨cosθn的连乘，定义为增益因子。

　　取无限次迭代值为

　　P为K的倒数。Cordic算法有几种模式，这里只取旋转模式。将上述矩阵化为数列得

N次迭代后

然后就是套三角函数了，取X0=K，Y0=0，Z0=α，那么N次迭代之后

　　正余弦就算出来了。没了。

　　用在硬件上的优势是，该算法从矩阵去除cos因子之后就在尽力构造简易的二进制运算比如加减和移位。需要预先算好那个K的值精确到指定位数，还要算arctan(1/2^n)，这些都要放到储存器里。

　　其中细节不说了，最后我设计出的玩意儿就下面这货。

注：1.由于我懒得去用数学软件打公式，以上数学公式的图片均截取自一篇来自桂林电子科技大学李全，陈石平和付佃华的论文《基于CORDIC 算法的32 位浮点三角超越函数之正余弦函数的FPGA 实现》

2.我不打算让三角函数运算单元加入FPU结构了，所以没做成IEEE754标准，只给浮点计算器用。

开方算法

　　特殊函数计算器除了三角函数外另一种运算是7位操作数开方运算，输出4位开方结果和4位余数。

　　该算法在硬件上实现很简单，只需要用到加法器和移位器即可，所以在本工程中实现出来的体积不大。最终实现了一个23位开方根器，如下图直角梯形部分。

　特殊函数计算器的运行结果显示如下两图示例

　　三角函数运算输入4位定点有效数字的角度，输出sin值和cos值，运算+输出时间约为130秒输出sin值，再过10秒输出cos值，输入角限制为0-83.88度之间。开方运算输入7位有效数字，可以选择小数点在第三位或整数形式，输出结果为4位开方结果和4位余数，运算+输出时间约为50秒输出开方值，再过10秒输出余数。

三、储存器架构和流水线

　　因为还没有做完这一部分，可能还会有修改，所以就简要的介绍一下。

现代计算机都是围绕储存器为中心，因为储存器容量极其巨大，其占用的晶体管数量远远超过用于运算和指令分配的其他逻辑单元。

　　比如一颗GPU，拿GK104为例，一共30多亿晶体管，片上缓存就占了芯片面积的接近三分之一。这还只是第一级的读取机制，缓存分一二三级，后面还有主储存器（内存），还有硬盘，这些容量每一级都要比上一级大了大约两个数量级。容量大，晶体管多，电流流过的时间长，最终读取到数据的时间必然变长。但是处理器时时刻刻都在做运算，如果第一时间不能取到需要的指令和数据，流水线就会空置。现代处理器运算速度和储存器延迟的鸿沟越来越大，计算机核心技术基本都是围绕储存器开展的。为了填补这拉开的时间差所造成的瓶颈，各种流水线结构，总线结构，硬件算法孕育而生。

　　流水线技术使得整个指令流程前后重叠，能最大限度利用每一个硬件单元。早期CPU流水线级数较小，现在的CPU一般都是十几级流水线。流水线级数也不是越大越好，因为存在一些情况，比如较晚的分支预测错误，会导致流水线冒泡。

　　本工程使用Harvard结构，相对于Neumann结构。程序储存器和数据储存器分开放置。程序储存器1kb，数据储存器0.5kb。由于指令是统一的双字节，所以程序储存器只按字（双字节）存取。而数据格式可以是单字节（低8位），也可以是双字节，所以数据储存器可以按字或按字节存取。

　　寄存器方面，ALU用ACC存放X操作数和运算结果，这里的运算结果都是需要双操作数的那些逻辑运算指令比如加减乘除与或异或，另一个操作数由Y寄存器存取。除法的余数最终会输出到最靠近除法器输出端的那4个寄存器的末端一个。所以如果之后要使用余数，就要避免在转移余数之前使用该寄存器做其他事情。另外还有8个通用寄存器供自由使用，一共可自由支配的寄存器有13个，ACC+12个通用寄存器。再算上栈区的4个单元，就一共有17个。

储存器阵列是3D的，也就是具有长宽高三个向量。为了给一个长方体的每一个单元编码，我采用的是先用地址码的低4位给个面编码，再用地址码的高5位给一条线编码，一个面乘以一条线正好覆盖了整个长方体。

　　通往储存器的地址线是总线分出来的支线，数据线也是一样的。这两列线分别连到储存器的3D结构里。地址线就连到刚才说的译码高5位和低4位，数据线的16个bit每一根连到每一个储存单元的对应bit。数据线先分散后集中。

　　本工程因为体积和延时问题的特殊性，主程序储存器只有1.5kb，访存速度相对于真实的计算机快多了，所以这个并不是瓶颈，可以在相对较短的时间内取到想要的指令。所以本想借这个优势实现指令全流水，也就是依靠复杂的分支预测机制将流水线漏洞封死。后来尝试做了一下，发现问题还是很多，比如预译码，预跳转中PC的占用冲突和布线困难，前一条跳转指令和后一条跳转指令的冲突，如果想要做出来，开销过于巨大，基本上CU的体积要增加0.5倍，这对我之后的工作影响很大故弃之，改为二位动态分支预测器来执行分支预测，这样流水线会冒气泡，但是损失不大。为了最大限度的缩小流水线气泡，我前后进行了相当多细微的改进。

　　流水线：取指→预译码，预执行→译码(→间指)→执行(→写回)

　　完整的流水线，一条指令会经历如下过程：当指令缓冲队列的指令条数小于4条时，先加载已经处于载入端的下一地址的指令，然后发出一个信号往PC，PC将当前储存的地址传送至程序储存器MAR，然后PC+1，地址译码器将相应地址的指令A传送至程序储存器MDR的载入端，如果是跳转指令等需要修改PC的指令则预执行指令。意思是将程序指针类指令全部放在另一个流水线分叉上执行。如果不是跳转指令，则MDR将A指令压入指令缓冲队列。如果此时缓冲队列里有ABC三条指令按这个顺序排列，那么等待C先弹出，然后B弹出，最后轮到A弹出至IR，IR将A送往指令译码器，控制信号通完各EU单元前端。等待前面的B指令执行完了 ，然后正式执行A指令。此时如果有间指周期，则将数据地址输送至地址译码器，从寄存器或数据储存器读取数据送到相应单元。然后执行指令。执行完毕如果有写回周期则执行写回。一条指令执行完毕。期间在指令缓冲队列和IR中如果前面有一条指令是条件跳转指令并且分支预测错误，会使缓冲队列和IR清存。PC发射正确的地址重新取指。

　　蓝线是控制信号，绿线是数据信号，红色字母和橙色箭头是指令队列的顺序压进方式。

　　另：本工程的所谓内存实际上是硬盘，因为我的程序是储存在这里面的，关机的时候我不会把储存器清空。不过这个问题无关紧要。

四、指令集架构

指令格式和取指方式：

ALU Instruction Formats

　　由于CU还没做完，指令机器码可能还有较大变动，所以是暂定表，这一部分也不多介绍。其中有一些指令是我特殊设计出来为了节约代码，所以助记符不一定规范（有些缩写就是在瞎编）。

1. 数据传送指令：MOV,PUSH,POP,RIA

　　MOV指令支持除了MAR,MDR,PC和栈区之外的寄存器之间的数据传送；

　　PUSH和POP指令为压栈和弹栈，原地址和目标地址均为寄存器，当栈满时PUSH则无效，原栈区数据不变，以溢出中断处理；

　　RIA指令可实现单字节的立即数写入寄存器，设计该指令的目的是为了使寄存器赋初值等操作更灵活，节约指令周期。

2. 数据读写指令：LDB,SDB,LDW,SDW,LIB,SIB

　　LDB,SDB,LDW,SDW均为对数据储存器的读写操作，读操作均由储存器传输至ACC，写操作均由ACC至储存器；

　　LIB,SIB均为对程序储存器的读写操作，读操作均由储存器传输至ACC，写操作均由ACC至储存器；

　　这6种操作均支持4种寻址方式。

3.算术运算指令：ADD,SUB,MUL,DIV,INC,DEC

ADD,SUB,MUL,DIV均为取操作数于Y寄存器，然后与ACC进行算术运算，结果存于ACC。当寻址方式为寄存器寻址时，指令格式为

　　即该格式指令支持目标寄存器，结果由ACC存至目标寄存器；

　　INC和DEC指令只支持寄存器直接寻址。

4.逻辑运算指令：

ASH,LSH,AND,ORL,XRL,NOTASH和LSH指令只支持寄存器内数据移位操作，移位数值为立即数，取值范围-15到+15；

　　AND,OR,XOR指令和算术运算指令同格式；

　　NOT,LSH指令为单操作数指令。

　　控制转移类指令参考流水线架构。

　　关于寻址位数。因为储存器很小，我在16bit的双字节指令里正好塞下了5位的基本操作码，2位的寻址方式和9位的储存器寻址。9位寻址对应512个程序储存器单元共1kb，也正好对应了512个数据储存器单元512byte，所有可用空间都填满了。所以不能再扩充内存，也用不到像8086一样的造过于复杂的段式内存管理，那样的MMU会给系统造成很大的延迟。

五、总线和时钟

　　把总线单拉出来讲是因为本工程CPU的延迟瓶颈在总线而不是储存器。储存器体积虽然大但是立体结构使得信号传输时间相对较短。由于本工程CPU的EU部分接口太多，还都是16bit，还要考虑ALU输入输出接口朝向的问题，排了半天也很难将这些接口的距离缩短，最终变成了一个折线形排布。此时就需要总线将所有接口贯通起来。而本工程总线的一个重要特点是环状的，因为游戏用继电器实现信号传输具有二极管特性，只能单向导通（做成双向很麻烦），所以总线如果实现从任意段输入任意段输出只能走环路。环路虽然增加了一倍的距离，其延迟还在可以接受的范围内，大约5.8秒（每一个bit位的总线一共58个继电器800多米长）。最大的难题是当总线在某一周期的任务完成后，需要进行下一轮数据传输。但是因为环路的特性，继电器的储存器效应会让环路保持原有的信号。此时必须加一个开路装置将原有的信号阻断。按照平常的思路在某一个环路节点加一排活塞将线路切断，信号会在总线里拖尾5.8秒（因为继电器会储存相同长度信号，切断的节点其一边的信号会沿环路绕一大圈传输到另一边后才会最终消失）。这样的话一个周期一共要耗费11.6-12秒，这长度实在是难以接受。

　　在我本以为实在没办法解决这个延迟问题准备向其妥协的时候，突然想到了一个解决方案：总线清存也用时序逻辑控制。也就是说在总线上找若干个节点都放上一排开路活塞，每一次传输完毕后所有活塞在同一时间切断线路，那么这时需要考虑的延迟时间就是相隔最远的两个节点之间的距离差。比如最后的成品中相隔最远的两个节点是180米，那么就是1.2秒的信号拖尾，从原来的5.8秒节省到1.2秒，总的单周期时间正好是7秒。只需要加一个总线控制电路让其和系统时钟同步就可以了。而且这样设计的另一个好处马上凸显：在这1.2秒的清存时间里，指令发射端正好可以做各种调整工作，此时不需要使用总线，打了一个时间差，意味着各设备都充分利用到了时间间隙，是一个让我很惊讶的非常巧合的设计，感觉就好像有一种内在驱动力会让这一切看起来就应该是这样契合一样。

　　下图黑色方块部分为总线清存器（第一部分已经提到过一次）。图中蓝白相间的，橙灰相间的，以及深灰色的线路全是总线，蓝白相间的是高八位，橙灰相间的是低八位，深灰色的是转角处的线路。颜色不同只是为了方便识别节点和高低位，没有功能上的区别。黑色方块上有很多继电器都是时序控制电路，用于周期性的向活塞输出开路信号。每7秒输出一个1.2秒的信号将一段一段的信号阻隔直到全部消失。

　　时钟暂定为总线周期7秒，取指周期5秒。所有信号的源头都是CU的时钟信号发生器发出的。一般的指令都是1或2周期，所以一般执行一条指令需要7或14秒，乘除类的运算指令时间较长，最长的除法指令需要6个周期。所以这个计算机的运算速度根本指望不上了，一个极简单的程序就会运行几分钟。毕竟是在“计算机实时模拟计算机”，所以速度什么的已经尽力做到最快了。

PS:在最新版的DATA BUS中，我做了相当多的改进，比如互联驻存机制，每一个节点都可以储存信号，使信号可以在同一周期内一直停留在环路内。

七、图形显示原理

　　说实话，显示器是最难做的东西之一，因为完全是时序逻辑在控制还要顾及到和使用者的交互。而且图形的东西对面积体积时间等问题要求极其严格（现实中的显示器没必要考虑那么多，因为这些都不是瓶颈）。而图形处理器就更是天方夜谭了，有很多玩家会说要是在Minecraft 里造一台计算机可以玩Minecraft就吊炸天。这显然不可能，而且想做一个纯粹靠通用处理器运算来玩的小游戏都绝对不可能。比如贪吃蛇这种图像刷新率低的游戏，肯定做不出来。

　　先简单介绍一下现实中的图形处理器以及显示器是如何工作的，这对理解一些设计理念有很大帮助，也能解释为啥MC里如此难以实现标准意义上的显卡。这一部分专业术语过多，仅供做相关参考，可以直接跳过看下面本工程的图形设备的设计。

　　现实中的图形显示是按照“图形流水线”(graphic pipeline)来完成的。一般我们玩的3D游戏中，显卡是图像处理的设备。显卡的核心是GPU，CPU将应用程序的图像请求发送往GPU，GPU是图形处理器，作为协处理器。操作系统将所有的设备统一编址，并具有各自规范，所以每一个操作系统要调用GPU必须要有相应GPU的软件驱动程序。现在的GPU较为独立，CPU大部分时间不参与图形运算。GPU直接运行的是shader API，驱动程序指导GPU运行shader API，GPU的硬件结构将API编译成一条一条instruction。现在常用的shader API是OpenGL和Direct3D。由于图形运算是密集型并行运算，所以GPU内部有成百上千的unified shader ALU组成若干模块如nVIDIA GPU中的SM或者AMD GPU中的CU ，这些模块是程序员直接面对的对象，包含FPU，Load/Store Unit和SFU等等。还有TMU，Tessellator，rasterizer等等流水线上其他的功能单元，我们叫这些东西为：Fixed Function Unit。GPU的底层指令按照warp/wave的模式每一个指令周期都有成百上千条被发射，这些指令相关性小，一般都是顶点，像素，几何或纹理的shader指令。指令列队叫thread，每一个thread都会对应一个像素或顶点，若干shader ALU组成的vector单元同一时间用不同数据执行不同thread中相同的指令（因为front-end单元稀缺）。 每一个周期有成百上千个thread的某些指令被处理完，若干周期后所有thread都处理完，这时候一张画面就被初步执行完了，一般都是接近百万个像素点比如1280x720分辨率的显示器。之后图形流水线会将画面光栅化-rasterization，经过各种纹理，抗锯齿处理后，完整的具有正确几何信息和颜色信息的画面就处理完了。然后该幅画面就被送往帧缓存-framebuffer，这个是在显存中划出来的模块，等到合适的时机，该幅画面就传送往显示器输出，一张画面称为一帧。每秒钟一个GPU绘制出几十张这样的画面，人的肉眼就会看到流畅的画面。

　　GPU是典型的SIMD结构，单指令多数据的大规模并行运算。并且其运算的数据多为浮点型。GPU耗费的晶体管数量会大于CPU，需要造一大堆重复的ALU阵列和寄存器阵列。

　　下面贴三张GPU架构图，都是AMD(ATI)和nVIDIA这两年的GPU产品（2013年前后）。

　　可以很明显的看出GPU一般重复结构较多，都是SIMD阵列加上少数dispatch和其他shading pipeline结构，所以如果在minecraft中简化到极致，比如每一个模块只造一个单元确实可以造出一个具有完整结构的显卡，但是想要做一个可以持续输出流畅画面的GPU对于minecraft来说基本是不可能，光是造一个浮点ALU就要占据几百乘以几百乘以几十的体积。假若一个屏幕按照30x30的像素来计算，并且是bitmap，只有亮暗两种色彩。就算是2D的图像程序，一共900个像素，再放宽条件要求每3秒才出一帧，那么每一秒钟也要处理300个像素，按照最简单的2D指令，假若平均一个像素只需要3条指令就能得出其是亮还是暗，那么就需要300个ALU每秒运算3次。到这里也不需要考虑其他什么图形流水线了，光是ALU团簇已经这么多，造出标准意义的显卡基本不可能。很多玩家认为在minecraft里面可以造出运行minecraft的计算机，这种宏图大业是不可能完成了。就算是常用的显示程序比如操作系统界面，也没不可能造出鼠标这种东西了，因为不可能做出点控的设备。

　　然后回归正题，既然造标准意义的显卡不可能，那么就退而求其次，做一些功能弱一些的显示设备，比如说只要求显示器输出部分字符，并不要求其控制每一个像素。这样可行度会大大提高。

　　演示视频中的计算器和字符显示器都是可以控制输出字符的显示设备。那么该如何用尽量少的电路来实现这些结构并且能够让其反应迅速呢？又如何增加显示设备与玩家的交互性呢？

　　前面已经介绍过minecraft中常见的图像信号组成方式：红石灯和阴影。视频里正好展示了这两种，计算器和电子表部分用的是阴影，字符显示器用的是红石灯。为什么这样选择呢，这和方块的特性也有一定关系不过这个无关紧要。先来介绍计算器的数字显示。

　　常接触单片机的人很容易看出我用的是七段数码显示器。七段显示器顾名思义，所有十进制数字信息都可以由七个部分组成的，3横4竖。电话机，老式收银机上的数字都是用这种方式显示的。“8”这个数字是最复杂的，它把7个段都用到了。

　　那么如何用二进制电路表示十进制数呢？编码的原则是越简单越好，显然10个十进制数字可以用10个4位二进制数表示，比如3是0011, 9是1001，这就是BCD码。计算机说到底就是一堆不同种类的码来回转换的过程。要达到数字显示到屏幕上的过程，需要如下步骤：二进制码发射到A单元上，A单元将二进制码对应的十进制数连接到各数字对应的七段信息上，比如0100是数字4，而4对应的七段信息如上图是左上，右上，中，右下四个段，最后这四个段每段3个方块的活塞抽回来，则数字4就被显示出来，这整个过程译码了两次，一次是二进制码BIN转十进制码BCD一次，然后十进制码转对应的七段信息是第二次。字符显示也一样是这种原理，具体后面具体再说。

　　上面所提的A单元就是译码器。计算机里充斥了各种译码器。下图为BIN转BCD再转七段信息的译码器（橙色条形方块下面的部分）。这个译码器经过极度的体积压缩保证它占据的体积是所能实现的最小的。因为一连串字符排在一起，如果译码器较宽，一个一个排在一起会占据较大空间使数字看起来松散。实际上整个工程每一个单元的体积我都尽了最大努力将其压缩，这耗费非常大的脑力和精力。关于如何在三维结构上压缩电路也可以单拉出来写几千字。

　　计算器还需要控制端按钮转BIN译码器，多位BIN转BCD译码器和多位BCD译码器转BIN用于和CPU沟通，这些比较复杂就不多说了和显示设备无关，上面部分已经介绍过算法。

字符显示器是点阵式的，即在一个5x5像素的点阵上显示一个字符，如下图5x5显示屏单元上的字母N，和七段显示器一样，后面一长串就是BIN转字符转5x5像素译码器。

　　我使用的是自己设计的缩减版的ASCII码，只有不到64个字符，如下表，我暂时称之为ASCII X码。

　　游戏中能做到的最小像素是2x2个红石灯，之所以不能做到1个红石灯为一个像素，是因为体积上不可能做到在那么小的空间里控制每一个红石灯的亮灭。而就算2x2的红石灯为一个像素，也很难做到点控。关于这些字符译码的具体电路结构不作详述，下面贴几张字符显示器的流水线结构，视频里也有介绍：

　　做这个显示器耗费了较长的时间，我一开始的设计方案体积大概是这个的三倍，后来突发奇想解决了不少技术问题缩小了体积并改为完全的时序控制。现在还缺计算机键盘的交互式控制和其他几个模块的显示单元。

　　现在显示器的键盘也制作完毕了，可以打字，修改，光标前后左右移位等

下面用几段话回顾视频里展示的功能。

首先是计算器的功能：

1.时序控制

　　2.bit整数加减乘除，除法输出商和余数

　　3.溢出判断：输入溢出，输出溢出，除数为0：

然后是电子表功能：

　　1.关：

　　2.显示0点0分0秒到23点59分59秒

　　3.过按钮精确调整时间

关于电子表多说几句。电子表对于整个CPU而言只是一个独立的附属物，我把它当做主要的展示品是因为电子表可视化的效果比较好。原本我想再录一些关于总线技术和流水线技术的视频，但是太抽象了看着都困就作罢。电子表电路原理很简单，就是用移位触发器循环一些数字而已。重点不在原理而在电路体积大小。我花了些精力将电子表的体积压缩到如下图这样，应该是非常迷你了。

最后是字符显示器功能：

　　1.何标准储存器并输出储存器中的字符信息。

　　2.字符可换行换页。

　　3.交互式操作，单字符控制（这个还没做完所以视频里没有）。

　　视频里有个字幕写错了，有一句话里welcome没有加最后那个e，不过已经费劲千辛万苦把超清视频传到优酷里，就懒得重新压视频再传上去了。

关于工程的架构名称：Alpha21016。之所以取这个名字，是为了纪念十几年前DEC(Digital Equipment Corporation)的Alpha架构，那是一个处理器时代的传奇，可惜商业上并不成功。Alpha组的人很多后来都去了Intel和AMD，并立下了汗马功劳。

　　综合视频和日志粗略的介绍了一下工程，题目说是“技术细节”实际上还有好多没介绍的，就先不说了，真要写完估计要写一本200多页的书。具体的规划细节比如各种重要功能结构的设计，指令集的设计，硬件单元接口排布，储存器空间位置，流水线级数，动态分支预测，乱序执行，显示器控制原理等等实在写不动，这篇已经写了2万多字了（被我删的删，改的改，减的差不多了）。

最后再次感谢大家的支持！！！（这句是原文）

最新进展图（2014年8月25日）

　　目前CPU已经可以执行若干种机器指令（以MOV为主）：通用寄存器赋值，按字/字节+立即数/间接/直接寻址。

详细设置如下：

　　指令名称：数据储存器取数据至X寄存器

　　指令目标：将数据储存器中的某一字/字节数据传输至X寄存器中

　　指令格式：00001　　0/1　　0/1　　addr(9)

　　对应含义：指令码　　直接寻址/立即数寻址　　按字/按字节　　数据地址

　　备注：如果地址为奇数且为按字寻址，则改地址数据赋值到目的寄存器高8位

　　指令名称：传输MOV

　　指令目标：通用寄存器之间的数据传输

　　指令格式：1000000　　x　　reg(4)　　reg(4)

　　对应含义：指令码　　无效　　源寄存器地址　　目的寄存器地址

　　指令名称：加减乘除

　　指令目标：将被操作数取出传输至Y寄存器四则运算后储存至X寄存器

　　指令格式：00100/00101/00110/00111　　0/1 　　0/１　　addr(9)

　　对应含义：加/减/乘/除　　直接寻址/立即数寻址　　取数计算/直接计算　　数据地址

　　备注：只支持按字读取数据储存器

　　指令名称：寄存器间接寻址

　　指令目标：将某寄存器中数据作为地址传输至MAR，取数后传输到任意寄存器

　　指令格式：1000001　　0/1　　reg(4）　　reg(4)

　　对应含义： 指令码　　按字/按字节　地址寄存器地址　　目的寄存器地址

　　备注：Y寄存器不支持作为地址寄存器，其他寄存器都可以

————文末割一下，割割割割割————

2019年5月23日更新：

作者的话：

本文完成于2014年，时隔五年在知乎上因为被转载而突然火起来，并受到很多褒奖和赞美，作为作者我感到很荣幸也感到很惶恐。有一些媒体朋友联系我希望能够继续扩大传播，我在此表示，本作品因为时间和精力有限最终没有完全实现预先规划的内容，并且现在已经有很多玩家可以做出类似的作品，我觉得本作品并没有足够的分量继续在中文互联网里刷流量。实际上，一个计算机或微电子专业的本科生或研究生只要肯花时间，完全有能力做出类似的作品，只不过因为我在游戏里去实现它，在呈现方式上比较吸引人而已。我本身并不是计算机专业出身，出于对硬件的兴趣爱好做了这样一个作品。由于我本身专业基础薄弱，写的文章里难免也会有错误和疏漏，希望大家的包涵和指正。

如果我的作品可以激起更多人探索计算机科学或者其他工程科学的热情的话，就已经达到我想要的最好的目的。希望年轻一代，尤其是中国的年轻一代，以后可以涌现出更多不拘一格的技术人才，在各自的领域创造出充满想象力和创造力的作品。再次谢谢大家！

————我割，我割割割割割割————

我也想说两句：

为什么大家都要揪着延迟不放呢？只是快慢的问题而已，这不影响计算机的制造。