这篇论文是发表在ASPLOS2020的《Classifying Memory Access Patterns for Prefetching》，作者来自Google的Parthasarathy Ranganathan和来自Stanford的Christos Kozyrakis，第一作者是Grant Ayers和Heiner Litz。
这篇文章通过分析内存访问的行为来判断是否一个Prefetcher是否有效。作者结合二进制代码分析和动态的Trace分析制作了了一个分析工具，揭示了访问的特性，同时利用特性提出了software prefetch injection的方法。
方法
内存访问的分类
- 只关注load instruction：带来最多cache miss
- 同一个PC两次load的address分类
- Constant: $A_n=A_{n-1}$，例如*ptr访问
- Delta: $A_n=A_{n-1}+d$，例如streaming,array traversal
- Pointer Chase: $A_n=Ld(A_{n-1})$，例如next=current->next
- 地址是从之前的地址得到的
- Indirect Delta: $A_n=Ld(B_{n-1}+d)$，例如*(M[i])
- Indirect Index: $A_n=Ld(B_{n-1+c}+d)$，例如M[N[i]]
- Constant plus offset reference: $A_n=Ld(B_{n-1}+c_2)+c_1$例如Linked list(链表)遍历
预取器内核(Prefetch Kernel)抽取
- dataflow analysis
- 找到并分类instructions causing miss
- 因为可能的path极多，dynamic profile能剪枝到prefetch最重要的部分
- prefetch kernel
- miss address=data+computations
- 用图表示关系，vetex是data，edge是computation
- 根节点是miss PC的地址
- 找生成根节点的子节点的依赖
- 找到一个PC所有出现的地方
- 细节
- Load-to store依赖：找load instruction的address的prior store（必须要动态分析，最大的不同点）
- 直到所有节点是terminal节点：constant、random number、trace边界等
- 不考虑控制逻辑，因为trace本身就考虑了控制逻辑，同一个PC使用那些出现频繁的flow
- Compaction（压缩）
- dataflow kernel包括不需要的操作
- 例如memory loads/stores caused by register spilling/function calls
- Store-Load Bypassing
- 通过dynamic直接把store-load连接起来
- Arithmetic Distribution and Compaction
- flatten the dataflow graphs by distributing and reducing nested arithmetic operations
- 例如(3 + 4) − (6 + 1)
- 减少了1000x的graphs
- Assignment and Zero pruning
- Assignment between registers对图没用，去掉
- 0计算，去掉
- dataflow kernel包括不需要的操作
- 例子
- An = 0x28 + load(0x38 + load(−0x8 + load(rsp)))
- An =0x28+load(0x38+rax)
分析