Skip to content

Latest commit

 

History

History
executable file
·
75 lines (63 loc) · 7.03 KB

【CSAPP】实验cache-lab.md

File metadata and controls

executable file
·
75 lines (63 loc) · 7.03 KB
title date tags categories
实验cache_lab
2018-03-24 04:12:52 -0700
CSAPP
CSAPP系列

实验内容

两个实验：

  1. Part A: implementing a cache simulator
  2. Part B: writing a matrix transpose function that is optimized for cache performance

Part A: implementing a cache simulator

思路

首先有通过valgrind生成内存的访问情况记录（放在trace文件目录下），然后通过我们的程序去解析，统计它的命中与换出。要注意：

  1. 这里并不是要你真的去实现一个缓存，不需要把具体内容放到你申请的内存里。你只是需要统计内存的使用。
  2. 我们的前提是假设读取一个trace文件的时候，缓存里没有任何东西。也就是第一个内存访问是不命中的。然后我们自己要维护一个表，来记录缓存里的情况（再次强调，这里是记录情况，而不是把数据写在缓存里，因此我们并不需要blcok的部分）。
  3. algrind的输出文件的一些规则：
    • L：读，从内存中读取
    • S：写，向内存中写
    • M：修改，这涉及一次读，一次写。这个写由于已经读了，所以写一定是命中的
  4. 还有一个要注意的是set的位数s就决定了缓存里一定有2s。但是我们在设置line的个数时却不是根据一个地址里有几个bit作为line的标记来计算的。所以我们在计算需要多少个cache line的时候，要注意这一点。并且，对于任何一个组索引，缓存表里总能找到这样一个组来对应。只是tag不相同。
  5. 还有就是要熟悉取一个二进制任何哪几位的方法。

于是我们的代码的步骤就是：

  1. 首先解析命令行
  2. 根据命令行的设定维护一个cache的表。
  3. 读取trace下的文件，解析每一行
  4. 根据缓存命中规则和最近最少使用换出算法统计命中与换出。

对于1，可以通过getopt 对于2，通过malloc申请内存，并且设置一个结构体cache line的数组。 对于3，可以用fscanf() 对于4，缓存命中就是判断tage和组号等，但是我们的cache_line可以只有tag成员变量，而不需要组序号这个变量。我们可以直接通过组序号算出来是哪一个位置。另外就是在置换的时候虽然是要比较最近最少使用的，但是如果我们用一个数组来表示的话，我们就可以直接用数组的下表来暗含这种先后关系。下标大的比下标小的使用时间更短更新。我们每次置换就置换每一组的第一个line。

debug的一些笔记

  1. 如果一个指针变量用引用传递参数会怎样？
  2. C语言里常数指针与指向常数的指针
  3. return和exit的区别
  4. 结构体作为参数传递是值传递，而不是像数组一样是指针传递。
  5. memcpy(&(cur+1), &cur, sizeof(cache_line));&(cur+1)错误，因为cur+1是一个临时的变量，不能用&求地址。
  6. while(fscanf(fp, " %c %u,%d",&operation, &addr, &dataSize)>0),这里如果没有>0,则会一直读取最后一行。估计是因为fscanf会返回-1,而这个会当作true
  7. gdb设置参数可以直接set args把后面的参数行写进去。
  8. fscanf(fp, " %c %x,%d",&operation, &addr, &dataSize)>0这里一开始%x我用的是%u,于是这样就是十进制的数，对地址转换就有问题。
  9. 还有就是除了在命中的时候要更新位置，在写入一个新的，或者置换了一个新的cache_line以后也要更新位置。

改进空间

  1. LRU的算法，cache可以用一个链表表示，而不是用数组。

Part B: writing a matrix transpose function that is optimized for cache performance

前提是评分里规定

  1. 缓存器是25个set，每个set一个line，然后每个line存25bytes数据。也就是8个int。
  2. 局部变量不能超过12个。
  3. 这个部分大都是硬编码，拿到大部分的分就ok，这个优化可能是无止尽的，性价比不高。重点是理解这种优化的逻辑，就是利用局部性，一次尽量处理内存上连续的数据，或者已经放在缓存里的数据。

思路：

  1. 32*32 这个很多博客里都有些，就是普通的分块，8*8。但是要考虑到A和B中对应的元素都是映射到同一行1，对于对角线的操作B[i][i]=A[i][i]，这样就会引发缓存不命中，并且会把A数组的缓存替换成。后面再继续B[i][j]=A[j][i]时，又会把A数组替换回去。解决方法是用8个局部变量一次把A的8个数都保存好，然后去修改B数组时就直接替换一次就好了。 于是最低是4*4*16 = 256次。再加上每转置一行A中的8个数，就要替换一行给对应的B。因此287也算是合理。 为什么不能是8*16呢？缓存16行A，16行B，简直完美啊？ 你可以推导一下就知道A的第8行和第0行是在一个缓存行里的，不可能同时缓存。
  2. 64*64 如果按照32*32的来，那么理论上完美的miss数是8*8*(8*2)=1024次。但是又别忘了，此时A的第0行和第4行就开始重叠缓存行了，因此我们分块也定多是分成4*8一块。用这个分法试一下结果是miss 4611次。
  • 为什么呢？思路不都一样吗？因为每次缓存A的4*8这么4个缓存行，转置过去以后B依旧要缓存8行而却只能修改每一行的4个数。所以B的缓存我们只利用了一半。而且局部变量也只需要4个。
  • 64*64的这个矩阵结构注定了无论是A还是B，我们每次都最多能缓存4行数据（是数组里的数据，而不是缓存行）。因此瓶颈就在于我们每一次缓存了整个4*8的数却只能完成4*4的转置。如果我们把A中缓存了的数据在转置中无法用到的部分暂时存在B中转置无法用到的部分，然后等到B缓存到某个块时，我们可以直接从B的某个位置独到这个块的信息。思路就是这个思路，可以自己去推导一下。
  1. 61*67 因为这个的要求放的比较低，不超过2000。并且由于67行，数据行之间无法想上面一样有非常规整的关系。比如第0行的数据就是会和第3行的数据在缓存上的地址一一对应。可以试几个分法，比如8*8，16*16。

debug的一些注意点

  1. 关于中间变量，直接用B[j][i]=A[i][j]也可以，为什么要引入一个temp？这里引入temp没有什么意义，最后的hits是一样的，但是后面transpose_submit则需要中间变量，原因是这个矩阵恰好是8*32int的倍数，也就是说A[i][j]的缓存一定会被B[i][j]替换，因为A和B是相邻的数组。因此我们用中间变量一次性读完。参考

Footnotes

  1. <深入理解计算机系统》配套实验：Cache Lab里的评论里说了两个数组是一个静态链接，也就是地址是固定的。所以我们的这些分析都是非常具有针对性的。下次遇到同样的数组转置还是要具体问题具体分析，再次强调大家不要太去追求极致。 ↩