操纵 mips 汇编代码以降低缓存未命中率（火星模拟器）
manipulating mips assembly code to decrease cache miss rate (mars simulator)
如何优化汇编代码以降低缓存的未命中率？我知道更改放置 policy/block size/block 替换策略会影响缓存未命中率，但我特别要求修复 mars 上的设置。
我们目前被要求使用直接映射、块大小字 2 和缓存大小 128 字节，而不是专注于代码以提高未命中率。
我的数据段目前是这样的：
.data #data segment
X: .word 1,1,1,2,2,3,4,2,1,1,2,3,2,4,8,1,1,1,1,2,2,3,4,2,1,1,2,3,2,4,8,1 #X[]
H: .word 1,5,1,4,2,1,1,1,1,5,1,4,2,1,1,1,1,5,1,4,2,1,1,1 #H[]
Y: .word 0:8 #Y[]
m: .word 8 #m = 8
n: .word 24 #n = 24
我注意到将 X[] 数组移动到 n 下可将未命中率从 53% 降低到 44%。我可以进一步操纵我的代码以降低失误率吗？难道只能通过操作数据段来实现吗？为什么我将 X 数组向下移动几行时，命中率会提高？
如果能得到更多“为什么会发生这种情况以及如何利用它”的解释，我将不胜感激，但为了示例起见，我将保留我的全部代码。
.data #data segment
H: .word 1,5,1,4,2,1,1,1,1,5,1,4,2,1,1,1,1,5,1,4,2,1,1,1 #H[]
n: .word 24 #n = 24
Y: .word 0:8 #Y[]
m: .word 8 #m = 8
X: .word 1,1,1,2,2,3,4,2,1,1,2,3,2,4,8,1,1,1,1,2,2,3,4,2,1,1,2,3,2,4,8,1 #X[]
.text
fir: #void fir
la $t0, X #address of X[]
la $t1, H #address of H[]
la $t2, Y #address of Y[]
lw $t3, n
lw $t4, m
add $t5,$zero,$zero #set j counter to 0
addi $s4,$zero,4
j for1 #go to for1 loop
for1:
beq $t5,$t4,exit #when j is equal to m loop stops and goes to the exit function
add $t6,$zero,$zero #y0 = r6 = 0
add $t7,$zero,$zero #set i counter to 0 for every loop
bne $t5,$t4,for2 #go to the nested loop for2
for2:
beq $t7,$t3, afterfor2 # for(i=0, i<n, i++)
#making X[i+j]
add $t8,$t5,$t7 #i+j stored in r8
mul $t9,$t8,$s4 #(i+j)*8 to find address stored in r9
addu $t9,$t9,$t0
lw $s0,($t9) #load x[i+j] to $s0
#making H[i]
mul $s1,$s4,$t7 #8*i
addu $s1,$s1,$t1 #adding 8*i to the base address
lw $s2,($s1) #load h[i] to $s2
mul $s3,$s0,$s2 #x[i+j] * h[i]
add $t6,$t6,$s3 #y0 = y0 + x[i+j]*h[i]
addi $t7,$t7,1 # i++
j for2 # repeat loop
afterfor2:
mul $s5,$t5,$s4 #8*j stored to $s5
addu $s5,$s5,$t2
sw $t6,($s5) #Y[j] = y0
addi $t5,$t5,1 #j++
j for1 #go back to start of loop for1
exit:
li $v0, 10
syscall #exit program
是否有任何命令（例如 sw 或 la）可以更改以提高命中率，还是仅取决于数据段？
命中率取决于代码的数据放置和访问模式。
在直接映射缓存中，只有一个地方可以缓存每个字节的内存，并且该位置由字节的内存地址决定。
具体来说，地址分为以下字段：
+--------+-------+--------+
| tag | index | offset | field name
+--------+-------+--------+
25 3 4 field size
有8个blocks/lines，所以索引大小是3位（8个值）。每个 block/line 有 4 个字，即 16 个字节，因此偏移量为 4 位（16 个值）。
当两个相近的内存变量，按它们的地址，具有相同的index & tag那么，当它们被交替访问时，缓存表现良好。
当两个distant memory variables，按他们的地址，有相同的index（但有不同的tag），那么当他们交替访问时，直接映射缓存必须逐出一个顺序缓存另一个。
如果程序的访问模式在两个远距离内存变量之间交替，那么它会破坏缓存。
例如，让我们关注单个缓存块，索引 0 处的第一个缓存块：
假设我们访问位置 0x10010000。它将缓存在 block/line 0 中，因为该地址的索引字段是 0002。接下来我们访问位置 0x10010080。这是一个不同的地址，但也解析为索引 0。直接映射缓存别无选择，只能从块 0 中逐出地址 0x10010000，以便它可以在那里缓存地址 0x10010080。如果程序接下来再次访问 0x10010000，因为它不再被缓存，那么这是一个未命中，其副作用是从块 0 中逐出 0x10010080。每次程序在这两个地址之间移动时，都会有一个未命中。
相对于另一个数组移动一个数组会改变两个数组的哪些元素共享相同的索引，从而在缓存中发生冲突。
更改数组的大小也会产生影响：一个 24 字的数组有 96 个字节，这是该缓存的一个很好的块。
更改算法会更改访问模式，因此也会产生影响。有时我们可以更改算法以一次处理数组的较小部分，这样可以减少冲突。
更改高速缓存设计可以以更多硬件为代价显着改善抖动。
如何优化汇编代码以降低缓存的未命中率？我知道更改放置 policy/block size/block 替换策略会影响缓存未命中率，但我特别要求修复 mars 上的设置。
我们目前被要求使用直接映射、块大小字 2 和缓存大小 128 字节，而不是专注于代码以提高未命中率。
我的数据段目前是这样的：
.data #data segment
X: .word 1,1,1,2,2,3,4,2,1,1,2,3,2,4,8,1,1,1,1,2,2,3,4,2,1,1,2,3,2,4,8,1 #X[]
H: .word 1,5,1,4,2,1,1,1,1,5,1,4,2,1,1,1,1,5,1,4,2,1,1,1 #H[]
Y: .word 0:8 #Y[]
m: .word 8 #m = 8
n: .word 24 #n = 24
我注意到将 X[] 数组移动到 n 下可将未命中率从 53% 降低到 44%。我可以进一步操纵我的代码以降低失误率吗？难道只能通过操作数据段来实现吗？为什么我将 X 数组向下移动几行时，命中率会提高？
如果能得到更多“为什么会发生这种情况以及如何利用它”的解释，我将不胜感激，但为了示例起见，我将保留我的全部代码。
.data #data segment
H: .word 1,5,1,4,2,1,1,1,1,5,1,4,2,1,1,1,1,5,1,4,2,1,1,1 #H[]
n: .word 24 #n = 24
Y: .word 0:8 #Y[]
m: .word 8 #m = 8
X: .word 1,1,1,2,2,3,4,2,1,1,2,3,2,4,8,1,1,1,1,2,2,3,4,2,1,1,2,3,2,4,8,1 #X[]
.text
fir: #void fir
la $t0, X #address of X[]
la $t1, H #address of H[]
la $t2, Y #address of Y[]
lw $t3, n
lw $t4, m
add $t5,$zero,$zero #set j counter to 0
addi $s4,$zero,4
j for1 #go to for1 loop
for1:
beq $t5,$t4,exit #when j is equal to m loop stops and goes to the exit function
add $t6,$zero,$zero #y0 = r6 = 0
add $t7,$zero,$zero #set i counter to 0 for every loop
bne $t5,$t4,for2 #go to the nested loop for2
for2:
beq $t7,$t3, afterfor2 # for(i=0, i<n, i++)
#making X[i+j]
add $t8,$t5,$t7 #i+j stored in r8
mul $t9,$t8,$s4 #(i+j)*8 to find address stored in r9
addu $t9,$t9,$t0
lw $s0,($t9) #load x[i+j] to $s0
#making H[i]
mul $s1,$s4,$t7 #8*i
addu $s1,$s1,$t1 #adding 8*i to the base address
lw $s2,($s1) #load h[i] to $s2
mul $s3,$s0,$s2 #x[i+j] * h[i]
add $t6,$t6,$s3 #y0 = y0 + x[i+j]*h[i]
addi $t7,$t7,1 # i++
j for2 # repeat loop
afterfor2:
mul $s5,$t5,$s4 #8*j stored to $s5
addu $s5,$s5,$t2
sw $t6,($s5) #Y[j] = y0
addi $t5,$t5,1 #j++
j for1 #go back to start of loop for1
exit:
li $v0, 10
syscall #exit program
是否有任何命令（例如 sw 或 la）可以更改以提高命中率，还是仅取决于数据段？
命中率取决于代码的数据放置和访问模式。
在直接映射缓存中，只有一个地方可以缓存每个字节的内存，并且该位置由字节的内存地址决定。
具体来说，地址分为以下字段：
+--------+-------+--------+
| tag | index | offset | field name
+--------+-------+--------+
25 3 4 field size
有8个blocks/lines，所以索引大小是3位（8个值）。每个 block/line 有 4 个字，即 16 个字节，因此偏移量为 4 位（16 个值）。
当两个相近的内存变量，按它们的地址，具有相同的index & tag那么，当它们被交替访问时，缓存表现良好。
当两个distant memory variables，按他们的地址，有相同的index（但有不同的tag），那么当他们交替访问时，直接映射缓存必须逐出一个顺序缓存另一个。
如果程序的访问模式在两个远距离内存变量之间交替，那么它会破坏缓存。
例如，让我们关注单个缓存块，索引 0 处的第一个缓存块：
假设我们访问位置 0x10010000。它将缓存在 block/line 0 中，因为该地址的索引字段是 0002。接下来我们访问位置 0x10010080。这是一个不同的地址，但也解析为索引 0。直接映射缓存别无选择，只能从块 0 中逐出地址 0x10010000，以便它可以在那里缓存地址 0x10010080。如果程序接下来再次访问 0x10010000，因为它不再被缓存，那么这是一个未命中，其副作用是从块 0 中逐出 0x10010080。每次程序在这两个地址之间移动时，都会有一个未命中。
相对于另一个数组移动一个数组会改变两个数组的哪些元素共享相同的索引，从而在缓存中发生冲突。
更改数组的大小也会产生影响：一个 24 字的数组有 96 个字节，这是该缓存的一个很好的块。
更改算法会更改访问模式，因此也会产生影响。有时我们可以更改算法以一次处理数组的较小部分，这样可以减少冲突。
更改高速缓存设计可以以更多硬件为代价显着改善抖动。