CPU访存行为优化

常见优化

• 分块:形式上，把一个循环切分成两层循环。目的是为了改变访存的顺序，把访问数据的模式限定在某个局部区域，使得cache不至于频繁替换，需要结合循环交换技术才能达到此目的。分块之后能更好地使用循环合并的技术，通常分块之后我们可以把块内的数据一次性load到cache。一般意义上的分块指的是分块之后且数据重用

• 循环合并:数据重用,

  for(i in range(n)):
    b(i) = a(i) * c(i)
  for i in range(n):
    d(i) = a(i) * f(i)
    
  #可以合并成一个循环
  for(i in range(n)):
    b(i) = a(i) * c(i)
    d(i) = a(i) * f(i)
  #这样还看不出有什么但是写成下面形式
  for(i in range(n)):
    t_a = a(i)
    b(i) = t_a * c(i)
    d(i) = t_a * f(i)
  # 于是我们减少了对a[]向量load数据量。
  

  对于嵌套循环可能内部循环只有一个，此时我们可以对外层循环展开，生成两个内部循环，两个内部循环之间可以有数据重用

  for i in range(m):
    for j in range(n):
      c(i) = c(i) + A(i,j) * b(j)
      
  # 上述的例子是一个dgemv，对外层循环展开一次
  for i in range(m,2):
    for j in range(n):
      c(i) = c(i) + A(i,j) * b(j)
    for j in range(n):
      c(i+1) = c(i+1) + A(i+1,j) * b(j)
  # 没合并之前还没看出来什么
  for i in range(m,2):
    for j in range(n):
      t_b= b(j)
      c(i) = c(i) + A(i,j) * t_b
      c(i+1) = c(i+1) + A(i+1,j) * t_b
  # 于是我们对b()重用了一次！！节约了一次load
  

  除了可以重用数据，或许还能解决真相关依赖的流水线气泡填充

• 循环交换

  可以改变数据重用的对象，同样以上述的gemv为例

  for i in range(m):
    for j in range(n):
      c(i) = c(i) + A(i,j) * b(j)
  #上述的计算过程对b访问了m次，对c访问了1次(重用了c)
  for j in range(n):
  	for i in range(m):
      c(i) = c(i) + A(i,j) * b(j)
  # 上述过程对b访问了1次，但是对c访问了n次(重用了b)
  
  # 对于spmv, 如果每一行的非零元很少，而每一行的非零元个数都不为0，这意味着对b的读很少，但是需要写全部的c
  # 这时候应当采用重用c的策略(用谁多就重用谁)
  

• 最内层循环展开:填充流水线

  #一般是为了充分利用发射宽度,或者SIMD宽度