P5 踩坑總結…

kevlps 2022-01-08 02:05:39 阅读数:547

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,或者 Hit ‾ \overline{\text{Hit}} 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,0xabcd
sw $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和LRU
sw $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=0
for l in _output_format:
res.append(int(''.join(line[s:s+l]),2))
s=s+l
return res
def instr_handler(_instr):
global outstr
op=_instr>>26
funct=_instr&0b111111
rs=(_instr>>21)&0b11111
rt=(_instr>>16)&0b11111
rd=(_instr>>11)&0b11111
imm26=_instr&0x03ffffff
imm16=_instr&0xffff
s_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: break
outstr = outstr+' '
af=open(ac_file,'r')
jf=open(judge_file,'r')
try:
while judge_output>=0:
while True:
al=af.readline()
if not al:break
ah=line_handler(al)
if ah[1]==1 or ah[4]==1:break
while True:
jl=jf.readline()
if not jl:break
jh=line_handler(jl)
instr_handler(jh[0])
if jh[1]==1 or jh[4]==1:break
print(outstr+'\t')
if not al or not jl:break
if 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-1
print(outstr)
finally:
af.close()
jf.close()

寫在最後

以上可以看作是關於P5實驗書的一點點小擴充,結合了我在做P5的時候踩的坑,希望有點小幫助。

因為語言錶達比較匱乏,加上比較忙沒有時間寫太多,原理也沒有多講,和P4大佬的博還是沒法比,只是簡單分享。

雖然能A,但是P4A了之後我又發現了好多BUG,如果上面有什麼BUG請多多指正…

版权声明:本文为[kevlps]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080205388000.html