《你是我的欧拉图》DCLily

11、第 10 章 （51～55）

　　------
　　以下为2022.1.3更新
　　51 算法（摆烂，后面重启剧情）
　　你敢信
　　来了来了，最近将暴更本文
　　------

　　“小说位面常见特征分析表。”小左拿着小本本饶有兴趣地看着，“啊这个就是随时随地获得机缘，将来称霸天下的主角团吗？你看这个灵石灵兽随便捡，各种宝剑都白菜价。”

　　白六啐了他一眼，没多说话。但戎一也一样不安分。

　　“某个班级的同学按学号站成一排，现在希望移走几位同学，让剩下的同学自动变成合唱队形。请问最少移走几个？”

　　“这个还有趣些。这班级，学号，合唱就是你们世界的东西？”

　　“emmm你可以这样理解，你前面排了一堆高电平草，所有草的甜度已知。现在让你吃掉一些，使得剩下的草的甜度先单调递增再单调递减。请问最少吃多少个。”

　　“顺序是不能变的吧。这其实是找哪一个草作为头头能保证两边能保持最多草的甜度下降。这个简单的贪心选最大的不一定行，因为1234321235就不满足。要存一下每一个的左边和右边都最多能保留几个。而x位置能保留几个取决于其临边的数。找到所有比他小的临边，选一个最大的加一即可。”

　　“求分法。随便一个数m，求这个数分成若干个数相加一共有多少种形式。3=1+2与3=2+1视为一种。”

　　“这个也是常见的题。做法是定义函数F（m，n），表示m拆分的数最大不超过n的方法个数。则其应当为F（m，n-1）与F（m-n，n）的和，即更小加数和当前加数。这样就可以递归计算了。”

　　“0-1背包问题。如果暴力搜索，我们可以首先按照性价比（v/w）对所有东西排序，然后剪枝函数定义为当前的价值+剩余空间*剩余物品的最高性价比与目前搜索到的最优解进行对比。”

　　“其实实际上你要运用这些东西，并不简单。更多的其实就是个度吧，现学现卖。”

　　所以.....绕了一大圈咱们究竟要去做什么呢？

　　戎一看着算法博物馆里的排序算法不断变化，整个世界的熵减逐渐剧烈起来。

　　他一直都不清楚自己来到这里经历的事情究竟代表了什么价值。

　　比如，刚到这个世界学习了各类逻辑和数电的知识。

　　之后莫名其妙地碰到了师弟，然后莫名其妙地捡回了一条命，然后莫名其妙地想帮他修理内核，做一个xv6。

　　然而很奇怪的是，自己又不受控制地想做数据库，之后又想做分布式和并行计算。还想着hadoop和spark是不是可以一起学一下。

　　之后莫名其妙地领着白六到了算法博物馆。

　　原本这个世界上如同宠物小精灵一般的存在，不论是哪一块FPGA板子，都似乎在开头的探险中弥散了。

　　所以，我们到底在做什么？

　　------
　　以下为2022.10.24-10.29更新
　　52—53 流水CPU设计A—B
　　你敢信
　　来了来了，最近将暴更本文
　　------

　　戎一思考了很久很久，以至于旁边的小左和白六都睁愣了一段时间。

　　“喂，你怎么了？”白六rua着自己脑袋上的呆毛，拍了拍戎一僵直的身子。

　　“不是，我突然感觉，我们是不是正在被什么东西控制，而做出一些我们其实并不想做的事情......”

　　“这不是必然的吗，你不是说有什么任务书的存在？”白六难得笑了笑，“你白爷我倒是觉得那个任务书就是个幌子。了，难道你不按照上面的做会死不成？”

　　“其实，我最近做的事情，感觉已经超脱了任务书的存在......”戎一咂嘴道，“比如我不受控制地让师弟戳我的手，然后还想帮他修操作系统......我这么利己主义的人，在那个时候像是被控制了一般，做出了违和的事。”

　　“那你说，你觉得你应该去做些什么？”白六问道。

　　“emmmm，应该去，治疗我的贯穿伤....吧。”戎一拉开了袖口，“之前那段时间，我也不知道有什么神秘力量的牵引或者说指使，吧，没什么感觉。”

　　“你这种情况是要去修复电路还是？”

　　“我康下，”小左拿起任务书，“戎一的体质是minisys1A-ifetch逻辑。现在，原身是修炼到逻辑电路，但是又有突破到微体系结构的潜力，特别是戎一受伤的位置，如果要修复的话，可能要强行提升戎一的修行等级？”

　　“啊？”白六莫名道，“你懂得挺多啊。”

　　“任务书上清清楚楚地写着的啊。”

　　白六歪着脑袋想了想，倏尔又抱头找了根之前从小五那边掰来的麦穗尝。

　　“你六爷我大概是知道了，总之现在戎一是必须强制升段微体系结构了，也就是学会minisys-1A的ifetch。”白六缓了缓说道，“话说你知道，流水CPU和单周期CPU的区别吗？”

　　“emmm难道不是流水CPU每个时钟每一个逻辑元件都有事做，而单周期CPU的IF、ID、EX、MEM和WB是一个一个指令要五个跑完后再进行下去的。”

　　“你这话说得又不是很对。你记得你课设时用vivado搞的CPU吗，当时时钟用了分频器，但这个只是因为板子上的频率太高。因此，我们在元件例化的时候，所有的模块都是接入分频后的时钟。然而你也知道的吧，ifetch的逻辑，就是每一个时钟都会把pc+4。那这样的话流水CPU是怎么提升速率的呢？”

　　“我知道的流水CPU需要段间寄存器......实际上需要clock使能的原件也就是存储器和pc了，其它的原件，获得pc后都是一根线连着的，即便是idecode中的寄存器，不过写寄存器都是在时钟下降沿。”

　　“所以说，原来的单周期CPU，指的就是在一个时钟片内顺序处理这五个模块，WB模块在时钟下降沿处理。另外24位IO分两次写入这个有那么一点不太懂，不过也无所谓。”

　　“其实，流水CPU的意思，就是提升时钟的频率，把这五个模块强行隔离开。你考虑一下，IF，ID要读，MEM，WB要写，这些都很慢的，而且要求的速度也不相同。”

　　“分开可以让我们提高分频器的频率。也就是说，流水CPU的时钟如果不进行任何处理的话，反而比单周期还慢5倍。”

　　“所以，六爷您觉得我能搞定这个？”戎一按着袖口问道。

　　“其实最麻烦的控制信号模块的改写。比如跳转。我们在单周期CPU中，在计算下一个pc值的时候，各种计算已经完成。直接按照上一个周期计算出的各种控制信号改变pc值。但是流水之后，我们要看的信号到底是上一个周期的，两个周期的，还是更多？例如beq指令，我们在if这个模块得到的指令，此时的control计算出的控制信号是针对这个指令的；但即使我算出来了又怎么样呢？我依然要等到ex模块算出来zero的值才知道要跳转；那应该怎么设计ifetch呢？一个想法是，ifetch传入的jmp等信号，是exe算出来的，并且多传入一个exe的ins。还有一种思路是，读的是当前指令，但是后续的指令清空流水线。”

　　“洒家这边给你个想法，按理来说jmp指令不需要等到exe执行完再跳转，方便起见我们直接全部等到执行完跳转，要注意MEM与WB指令，不要执行了错误的指令。一种可行的思路是，如果发生了跳转，jflag会置1，此时后面的两条指令是无效的，不用做，实现这个的方法是再ex_mem中读入这个jflag，如果为1，往后面输出全0。”

　　------
　　以下为2022.11.1更新
　　54—55 流水CPU设计C—D
　　你敢信
　　来了来了，最近将暴更本文
　　------

　　戎一了解了理论之后，发觉自己可能还没有能把它写成Verilog的毅力。

　　“所以接下来你打算怎么做？”小左问道。

　　“大概，商量好对策，然后去RAM林里找合适的编译器帮我疗伤。”戎一回应道，“唉，其实我越来越觉得高等级真没什么用。还不是要靠千千万万的低等级的能力。而且那些最基础的东西，才是最难的。这就不得不提到我六爷了。”

　　白六莫名觉得他没安好心，“你想说什么？”

　　“话说六爷您算是小时候是熊之后幻化成人型的吗？这边的人像您这样常见吗？”

　　“你六爷我是熊猫，白化的熊猫知道吗！”白六揉了揉不存在的黑眼圈，“虽然不该说这么多，但是也就是我这个变异的体质导致现在的情况。动物有什么贵贱之分，你不如说我从小是人，幻化成了熊猫。据传你那个三师弟原型是只虎。不过啊，我真的不理解这种崇尚人类是万物灵长的唯心主义说法，在动物也有智慧之后。”

　　“啊，恕我直言，”戎一回应，“在我们这个世界的白化熊猫会显得眼小单调，而六爷您看起来就很像是正常的白熊呀。”

　　“咳咳咳，”白六莫名心虚道，“小时候我是正常的熊猫样子，有照片的......这个白化是后天形成的。爷这话撂这了你爱信不信！真是的聊这个做甚。”

　　“唉行了行了，咱先往RAM那边走吧。”小左打圆场，“六爷跟着来吗？”

　　“走。”白六抖了抖披肩，翻出两个连线型变量，“我也不知道戎一的修为能承受多少组寄存器和电路啊...这个拿去，关键的时候能帮上忙。”

　　......

　　计算机内部的世界是丰富多彩的。而Verilog是对这些硬件的合理抽象。应该说是一个更大的集合，毕竟一些情况是可模拟不可综合的东西。

　　戎一一行人走到ram林附近，作为需要找合适IP核的人，他主动开始查起之前他碰都不愿意碰一下的东西。

　　“你看啊，这些RAM，要么是8位，要么是16位（半字读），要么是32位，就没有特别合适的斡旋的东西。”小左看着这些东西，“按照流水CPU要求，要加入的指令包括了半字和8位读，很少有这种IP核可以保证多种读写方式的......”

　　“交叉存储呗，你大学没看过mooc啊。”戎一莫名脾气变得坏了起来，但似乎又没什么道理，“不好意思啊，潜意识排斥这个东西。”

　　“这边还有适合uart的部件。”白六摘到一串reset信号，“一般的开发版，reset信号是低电平。但是过了看门狗就不一定了。”白六眼睛亮晶晶地，把一串uart塞到自己毛绒绒的脑袋上，趴到一边吸|毒去了。

　　“总之咱们去找四个八位的ram。”戎一和小左分析了一下目前的情况，“交叉存储的优势在于对于lb等指令的读写变得简单。此外还有一个问题，数据总线。”

　　“我觉得之前应该任务书里也说得清楚，把rom和ram单独分装出去，以后当接口会比较方便。然而吧，我只是个ifetch，我管交叉存储都已经是吃饱了撑的了，我用的是哈佛结构又不会有硬件的相关性问题。咱这个就等以后再说。虽然说我也莫名憧憬体系结构的大能都是什么东西，但是吧，某天发现自己能飞了还要露出一种范进中举的表情，很傻真的，固有的旧人类世界的法则其实在我们身上还是或多或少地留下了一些影响。”