巴马腕表批发销售联盟

如何在《我的世界(Minecraft)》打造可以运行的计算机(二)

EETOP2018-07-19 09:41:38


《我的世界(Minecraft)》是一款风靡世界的游戏,这个大部分人都知道。最近,小编上小学的儿子迷上了这款游戏,有时间就在游戏里鼓捣一些奇形怪状的建筑等等,因此又引起了小编的兴趣。这款游戏相当灵活,居然还可以打造包括中央处理器CPU在内的计算机,并且可以模拟运行,相信大家早已有所耳闻,但是具体怎么做的,应该很多人也不是很清楚。所以为大家找来的一个详细教程,有兴趣的同学可以看一下。该教程节选自两年前由季文瀚所写的《基于Minecraft实现的计算机工程》一文。由于微信字数限制本文分了两个部分。


以下正文: 


如何在《我的世界(Minecraft)》打造计算机(二)


硬件算法

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

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

BCD/BIN转换算法

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

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

输出端BIN转BCD算法:

  这个用的是通用的算法,流程如下:

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

  借用MC论坛上的举例介绍:(http://www.mcbbs.net/thread-97108-1-1.html)

  把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

  结束

  最终设计出的硬件结构如下图,是一个15bit的BIN转BCD转换器。

除法算法

  除法用的是恢复余数的加减交替算法,流程举例如下:

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

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

  下图右上灰色部分是最终恢复的余数输出端,右下红绿相间的加法器是除数输入端,被圈出来的蓝色方块从上到下一共15个是被除数输入端,被圈出来的那个是最低位,它下方偏右的那个是最高位。

  下图是换了一侧看除法器,图中绿色的一共15个是商输出端

浮点加减法算法

  这个也是用的通用算法。

  按照下面几个步骤来:

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

  这是WIKI上的表格,要不要用偏正值其实无所谓,只要知道单精度浮点数(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) 比较阶码大小并完成对阶

  两浮点数进行加减,首先要看两数的阶码是否相同,即小数点位置是否对齐。若二数阶码相同,表示小数点是对齐的,就可以进行尾数的加减运算。反之,若二数阶码不同,表示小数点位置没有对齐,此时必须使二数阶码相同,这个过程叫作对阶。要对阶,首先应求出两数阶码Ex和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)

  参数意义如下图,β是初始角,θ是旋转角,R是圆周半径

  化为矩阵式

  可以看出θ如果拆成许多个小θ,即θ=θ1+θ2+θ3+…+θn,那么作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位余数。

  算法为笔算开方算法(快速平方根算法),流程如下:

  图片来自《基于FPGA快速平方根算法的实现》- 戢小亮,嵌入式技术,2007年14期

  该算法在硬件上实现很简单,只需要用到加法器和移位器即可,所以在本工程中实现出来的体积不大。最终实现了一个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个。

  下图为简易的CPU功能模块立体位置图。

下图为程序储存器侧面图,是立体8层叠加式结构,每一层128byte。

  储存器阵列是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产品。

  可以很明显的看出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个段都用到了,如下图,右边的“2”显然是“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码。

  上表字符的BIN码都是一个字节的低6位,另外还有一个字符Enter表示换行,使用01000000表示的。

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

  下图为字符显示器BIOS部分的输入端,有两个寄存器用轮发射方式发射字符信息,字符信息来自右边的只读储存器。

  下图为双线程字符译码器,整个字符显示器模块都是时序控制的。

  下图为字符显示器的输出部分,用总线连接一共两排24个单元,每个单元分显示器,锁存器和闪屏器。中间的后方是一个总的移位控制单元。全时序控制最快速的每3.4秒输出一个字符,可换行换页。

  下图就是双向移位触发器。

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

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

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

首先是计算器的功能:

  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万多字了,等最终成品做完了再发完整的技术文档。

  本文是2013年8月写的,不知为何2013年12月11日被大家顶上来。首先感谢大家的评论,分享和赞扬。需要看工程新进展可以到我的相册里找。工程最终大约在2015年完工,会再发一篇完整地视频和文档出来。

  最后再次感谢大家的支持!!!

后续更新

  最近仍有很多人关注我的工程,我非常感动。我没弃坑,只是进度缓慢。

  最新的进度图

  目前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/1  addr(9)

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

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

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

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

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

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

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

  之后还有约30种指令未完成,工程量很庞大,但我肯定会坚持完成的。实现所有指令后我会尝试做一个可视化的类似DOS界面的机器码处理界面。如果不做的话除了我就没人能看懂这个工程里CPU的作用了。字符显示器可以接收CPU传输过来的ASCII码并输出,不支持写入。

全力打造中国电子工程师微信第一品牌!
Copyright © 巴马腕表批发销售联盟@2017