循环分块对减少off-chip memory access的具体分析

如图，我们要计算 N a N_a Na​个 t ( i ) t(i) t(i)和 N b N_b Nb​个 r ( j ) r(j) r(j)两两之间的距离，这是未进行分块的原始代码，假设cache（或者片上缓存）的容量为M个向量，并假设 N a N_a Na​和 N b N_b Nb​远大于 M M M，则对每个i，我们从片外存储器load一个 t t t，并且从片外存储器load M-1个 r r r，进行M-1次的距离计算后，这M-1个r便被替换出cache，转而加载下一组M-1个的r，因此，对每个确定的i，需要进行约 [ N b M − 1 ] [\dfrac{N_b}{M-1}] [M−1Nb​​]次cache与DDR之间的数据交换，而i共循环 N a N_a Na​次，因此总的交换次数为 N a ∗ [ N b M − 1 ] N_a*[\dfrac{N_b}{M-1}] Na​∗[M−1Nb​​]，近似为 N a N b / M ∗ c a c h e _ s i z e N_aN_b/M*cache\_size Na​Nb​/M∗cache_size字节的数据传输量。下面对 N a 循 环 和 N b 循 环 进 行 l o o p    t i l i n g N_a循环和N_b循环进行loop \,\,tiling Na​循环和Nb​循环进行looptiling,分块系数分别为 T i 和 T j T_i和T_j Ti​和Tj​，如下图所示： 并假设 T i 和 T j T_i和T_j Ti​和Tj​的和小于cache容量 M M M，那么，对每个i，事实上，我们可以从DRAM加载 M T i + T j \dfrac{M}{T_i+T_j} Ti​+Tj​M​个 T i + T j T_i+T_j Ti​+Tj​的block,这里 M T i + T j 是 指 一 次 性 l o a d 的 j 的 次 数 \dfrac{M}{T_i+T_j}是指一次性load的j的次数 Ti​+Tj​M​是指一次性load的j的次数，那么总的内存交换次数应该为 N a / T i ∗ N b / T j M / ( T i + T j ) \dfrac{N_a/T_i*N_b/Tj}{M/(T_i+T_j)} M/(Ti​+Tj​)Na​/Ti​∗Nb​/Tj​ 和未分块的 N a N b / M N_aN_b/M Na​Nb​/M相比，减少为 T i + T j T i T j \dfrac{T_i+T_j}{T_iT_j} Ti​Tj​Ti​+Tj​​ 这个收益是相当可观的！