P5 踩坑总结…

本文主要是介绍P5 踩坑总结…，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本篇文章初衷是帮助已经画好Cache的同学或者画到一半遇到问题的同学Debug的，列举了一些再各个模块中容易出错的点和常规的实现思路，请认真阅读实验指导书后结合食用。
这里不涉及与Cache原理之类的理论知识，如果指导书看不懂的话，建议先去过一下ppt，否则下面的内容应该也看不懂。

—12.5更—

这里发现一篇讲Cache理论的文章，感觉写的不错：Cache的基本原理-知乎
对以下名词进行一个解释，上面文章比我写的更详细，而且图不错，推荐学习：

Block：块，常指主存块，也就是主存与Cache交换数据的最小单位，实验指导书上用到了Cache块这个词，同时也有Cache Line也就是Cache行这个概念，这两个词经常混用，但是严格来说我们画的这个Block应该是Line，也就是存储块、Tag、有效位、脏位等一些信息的容器，块的长度又称为Cache行长，实验中块大小为4个字（128bit），实际应用中块大小可能会大得多
LRU：Least Recently Used，最近最少使用，一种页置换算法，Cache置换算法，名字很明显就是选最久没用过的那条换出去，实现方式是给每个单元加个计数器，记录距离上次访问经过的周期数，其他替换算法常用有RAND、FIFO、LFU（最不经常使用），课上考察可能会考LFU？因为前面两个太简单了。当然也有可能考自创
Cache：通常由SRAM构成，为了解决通用寄存器数量不足，但主存与CPU速度差异过大而出现的高速缓冲存储器，利用程序的局部性原理存储主存的部分内容
Tag：根据映射方式，表示Cache行对应的主存地址，全相联映射中存储主存块号，直接映射中存储地址Cache行号以上的最高t位，组相联映射里存储组号以上的高t位。实验中主存地址共12位，字节编址，32位机，字内地址2位（4Byte），主存块大小4个字，块内地址两位，Cache共16行，采用四路组相联映射，四组每组4行，块内地址2位，剩余位为CacheTag=12-2-2-2=6位
四路组相联映射：Cache行和主存块的映射关系分3种：直接映射类似于hash表，冲突概率高，全相联映射所有地址都能映射到所有Cache行中，冲突概率低、空间利用率高但是Tag比较电路成本高、速度慢，组相联则是将Cache分成大小相同的组，主存的某一个地址只能装在某一个Cache组内，组内全相联，组相联映射降低了Tag比较电路的规模。n路组相联映射，意味这每个Cache组内有n行Cache行，实验中Cache大小为256B，每一个Block为16B，意味着有16个Cache行，题目要求四路组相连每一组有4个line，也就是有16/4=4个Cache组
Cache更新策略：对于Cache写命中，有写直通法（同时写Cache和主存，主存设置写缓冲）和写回法（只写Cache，行换出时写回主存，Cache行需要脏位标记该块有没有被修改过），对应两种写命中策略有两种写不命中策略写分配法（加载这个块到Cache中然后再写）和非写分配法（直接写主存，不更新Cache）。通常非写分配法配合写直通法（也就是我们实验中实现的Cache），写分配法配合写回法。

—以下原文–

Block

Block基本没什么坑点，V、Tag、Data1-4总共6个寄存器连好就行

V按照指导书Block启动后衡置1，可以这么画

在这里插入图片描述

LRU

按照指导书中的表格画逻辑就可以了，只有命中&写入和未命中&不写入两种情况有输出

注意表格中的输出条件只涉及MemWrite，这个模块可以不使用MemRead输入
注意使能信号，因为LRU的输出就是Block的使能信号，在LRU不使能（也就是Group不使能的时候不能使能Block
选择最大计数器，我这里用的是六个比较器（好像有点蠢？或许有更好的方法）

Counter

最开始指导书给出的逻辑比较复杂，现在好像改了，按简单地写

Counter记录的是距离上次访问这个块经过的周期数

不需要考虑Counter溢出（16位），使用自带计数器实现

计数器count有效的条件仅有一种：MemRead有效，Group使能且这个计数器不满足清零条件（第四条写为什么要不满足清零条件），简单来说就是读时计数（加上Group使能计数更慢一点，计数器更不容易爆了，不加应该也行）
计数器清零的条件有两种：Hit&MemRead，或者 $\overline{\text{Hit}}$ &MemRead&BlockEnable，分别对应着Cache命中当前块时清零和Cache未命中，但是LRU选择块替换时清零
计数器归零方式是load一个0进去
注意计数器load和count同时有效的时候行为是计数减一，所以需要load零的时候要ban掉count，对应着第一条为啥要有不满足清零条件

Group

注意四个Hit信号的生成，一是要比较BlockTag与输入Tag是否一致，二是要看V
Group内的模块的EN信号需要满足条件：Group的EN有效，Stop无效，也就是Stop的时候不要更新
Group输出的Hit信号产生的条件是：Group的EN有效，与Stop无关，因为Hit涉及到RAM内部暂停五个周期之后恢复运行的逻辑（助教画的），如果把这个EN信号和上面那条合并的话…就g了
Mux就是根据Hit四选一，注意你定义的模块的高低地址接线，别接反了（助教的RAM是左高右低，我用的是左高右低上高下低）

Cache

关于ReadTime和HitTime，简单计数器即可，ReadTime会在Stop之后再更新，评测可以过不用担心

在这里插入图片描述

各个Group的使能信号，我是Decode了组地址之后与了MemRead和MemWrite，也就是非存取数指令不开Cache，内部LRU只需要考虑MemWrite信号就是因为这里已经把MemRead筛在使能信号了（没写就是读？大概就是这样）
RAM的Hit是四个组的Hit取或，注意Group没给使能的时候不要输出Hit，组地址不同Tag碰撞了也没用（上面已经提了一边了，再说一遍是因为这个Bug我De了半天）
Mux要注意的坑有两个，一是MemWrite和Stop的时候要输出0，这个是题面要求，二是在Stop五个周期结束的时候输出正确的数的时候要从RAM里拿（因为Cache也是在这个周期才更新，不能拿Cache的数），我是用Hit解决的，只有没Hit才会Stop，当前周期Cache还没更新，但是RAM的Stop已经归0了，所以Hit=0的时候从RAM取数

测试

这个Cache测试看起来就头大，其实还凑合。个人推荐放到单周期里，然后把Stop信号取反接到PC寄存器的使能上就好了，然后跑一堆存取数指令，观察Cache里的读计数、碰撞计数还有LRU四个计数器的计数是否符合预期，GRF的各个寄存器值对不对就行了

我用下面这几行（和我自己用的不完全一样，我又魔改了一下）测出了几个BUG之后能A了，但不保证测试数据覆盖全面，也不保证我的电路里还没有BUG，这次课下测试数据量惊人…

ori $t1,$0,0x1234
ori $s1,$0,0x5678
ori $s2,$0,0xabcdsw $t1,0x000($0)
sw $s1,0x040($0)
sw $s2,0x080($0)
sw $t1,0x0C0($0)
lw $t1,0x080($0)
lw $t1,0x000($0)
lw $t1,0x0C0($0)
lw $t1,0x040($0)
lw $t1,0x080($0) #这段是看组内的Counter和LRUsw $t1,0x000($0)
sw $t1,0x010($0)
sw $t1,0x020($0)
sw $t1,0x030($0)
lw $t2,0x030($0)
lw $t3,0x020($0)
lw $t4,0x010($0)
lw $t5,0x000($0) #这段是看组间选择有没有问题sw $s1,0x004($0)
sw $s2,0x008($0)
lw $t7,0x004($0) #这段是看块内地址有没有弄错

最后再贴一个p3、p4用的测试脚本，p5测试也凑合能用（但是推荐用上面的在线调试），原理和logging一样，用python简化了一点diff的流程（有bug，不想de，没有文档）

#coding=utf-8#生成log用java -jar logisim-generic-2.7.1.jar yours.circ -tty table -load ram-data> j.log
#需要先把指令加载到ROM里保存，不想写xml解析了，不想写jar解析了...
ac_file="ac.log" 
judge_file="j.log"
judge_output=20
output_format=[32,1,5,32,1,5,32]op_dict={0b100011:'lw',0b101011:'sw',0b000000:'R',0b001101:'ori',0b000010:'j',0b000100:'beq',0b001111:'lui',0b000011:'jal'}
funct_dict={0b100001:'addu',0b100011:'subu',0b000000:'nop',0b001000:'jr'}
r_str={'addu','subu'}
i_str={'ori','lui','lw','sw','beq'}
j_str={'j','jal','jr','nop'}outstr=str()def line_handler(_line, _output_format=output_format):line = list(filter(str.isdigit, _line))res=[]s=0for l in _output_format:res.append(int(''.join(line[s:s+l]),2))s=s+lreturn resdef instr_handler(_instr):global outstrop=_instr>>26funct=_instr&0b111111rs=(_instr>>21)&0b11111rt=(_instr>>16)&0b11111rd=(_instr>>11)&0b11111imm26=_instr&0x03ffffffimm16=_instr&0xffffs_op=op_dict[op]if s_op=='R':s_op=funct_dict[funct]if s_op in r_str:outstr="{} ${}, ${}, ${}".format(s_op,rd,rs,rt)if s_op in i_str:if s_op=='sw' or s_op=='lw':outstr="{} ${}, ${}({:#x})".format(s_op,rt,rs,imm16)elif s_op=='lui':outstr="{} ${}, {:#x}".format(s_op,rt,imm16)else:outstr="{} ${}, ${}, {:#x}".format(s_op,rs,rt,imm16)if s_op in j_str:if s_op == 'jr':outstr="{} ${}".format(s_op,rs)elif s_op == 'nop':outstr="{}".format(s_op)else:outstr="{} {:#x}".format(s_op,imm26)while True:if len(outstr)>25: breakoutstr = outstr+' 'af=open(ac_file,'r')
jf=open(judge_file,'r')
try:while judge_output>=0:while True:al=af.readline()if not al:breakah=line_handler(al)if ah[1]==1 or ah[4]==1:breakwhile True:jl=jf.readline()if not jl:breakjh=line_handler(jl)instr_handler(jh[0])if jh[1]==1 or jh[4]==1:breakprint(outstr+'\t')if not al or not jl:breakif ah[1]==jh[1]==1:aadd=ah[2]jadd=jh[2]adata=ah[3]jdata=jh[3]if aadd==jadd and adata==jdata:outstr = outstr+'\tREG    ${}    {:#x}'.format(aadd,adata)else:outstr = outstr+'\tREG    ${}(AC:${})     {:#x}:(AC:{:#x})     WA'.format(jadd,aadd,jdata,adata)elif ah[4]==jh[4]==1:aadd=ah[5]jadd=jh[5]adata=ah[6]jdata=jh[6]if aadd==jadd and adata==jdata:outstr = outstr+'\tMEM    ${}    {:#x}'.format(aadd,adata)else:outstr = outstr+'\tMEM    ${}(AC:${})     {:#x}:(AC:{:#x})     WA'.format(jadd,aadd,jdata,adata)else:outstr = outstr+'\tERROR'judge_output=judge_output-1print(outstr)
finally:af.close()jf.close()