论文笔记 《Classifying Memory Access Patterns for Prefetching》

这篇论文是发表在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计算,去掉
  • 例子
    • An = 0x28 + load(0x38 + load(−0x8 + load(rsp)))
    • An =0x28+load(0x38+rax)

分析

  • top 200 miss PCs
  • classification
    • 多数的miss address都包括loading from memory
  • complexity(kernel computations)
    • 小workload大部分<10
    • 大workload大部分<100
  • prefetch kernel timeliness

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×