循环分块

切成短段本身不危险，提前进入下一行才会改变次序 ​

把一层 for i in range(0,n) 写成 for t ...; for i in 当前短段，若短段依次连接，原来的i次序没有改变。这个操作常叫strip mining。二维循环若先写成t0、i0、t1、i1，仍是先完成一行再做下一行。

常见分块模板却采用t0、t1、i0、i1。它把某一列块内的多行先做完，再进入右侧列块。正是把块循环t1提到i0外层的这一步改变了实例次序。因而分块可以由切短段加循环交换理路循环交换Loop interchange · Loop permutation · 循环置换置换矩形循环的嵌套顺序，生成实际For代码，再以实例一一覆盖与依赖边方向验证每次变换。理解，但不能仅凭“每个短段内部顺序不变”就放行。[1]

3×5的输出划成四块 ​

矩阵乘法的输出C有3行5列，选行块宽2、列块宽3。四块的输出槽数依次是6、4、3、2；若每个槽有两次k累加，更新数便是12、8、6、4，总和30。右边两块少一列，下面两块少一行，它们不是补零后的大矩阵。

实际生成六层循环 ​

取维度 $(3,5,2)$，块宽 $(2,3,2)$。参考程序输出的For结构对应

for ti in range(0,3,2):
  for tj in range(0,5,3):
    for tk in range(0,2,2):
      for i in range(ti,min(ti+2,3)):
        for j in range(tj,min(tj+3,5)):
          for k in range(tk,min(tk+2,2)):
            C[i,j] := C[i,j] + A[i,k]*B[k,j]

A取三行(1,2)、(3,4)、(5,6)，B取两行(1,2,3,4,5)、(6,7,8,9,10)，C初始为零。先处理输出行0、1与列0、1、2的12次累加；再处理同两行的列3、4，共8次；随后是最后一行的6次与4次。最终C为

图上的面积是输出槽数，执行器的计数是语句实例数，二者相差k长度2。正因为计数对象不同，不能把四块12+8+6+4误写成30个不同C元素。

覆盖六点，却破坏一条跨块边 ​

把源换成

for i in range(1,3):
  for j in range(1,4):
    A[i,j] := A[i-1,j+1] + 1

A为3×5零数组。按相对起点i=1、j=1作2×2分块，第一块执行 $(1,1),(1,2),(2,1),(2,2)$，第二块执行 $(1,3),(2,3)$。每个点各一次，块内也仍是i、j顺序。

但源有边 $(1,3)\to (2,2)$：后者读取前者的写入。目标把它们放在第4和第3位，方向倒置。源六格结果为 $[1,1,1,2,2,1]$，分块后为 $[1,1,1,2,1,1]$，差异位于A[2,2]。参考程序使用归一化坐标(u,v)=(i-1,j-1)，故报告 $(0,2)\to (1,1)$、RAW见证槽8、编号4→3。

若行块宽改成1，每块只含一行，原行顺序不会被越过；若列块宽至少3，整行位于同一列块，也不出现这次逆序。两者都可通过精确边检查。这说明“存在负距离分量”并不意味着所有块宽都非法，合法性属于具体调度。

尾块、超大块与空域 ​

当 $n_r$ 恰被 $b_r$ 整除时，最后一块仍通过同一个min表达式结束，无需另一套代码。若 $b_r>n_r>0$，该维只有一个裁边块。若 $n_r=0$，没有实际赋值，初始内存不变。

$b_r=0$不能产生向前移动的块序列，负块宽也不属于本模板；参考程序在生成IR前拒绝。索引加法在本模型中为数学整数。若落到固定宽度机器整数，需要另查t+b溢出，不能因最终取min就认为溢出无害。

一个对所有正块宽都成立的充分条件 ​

假设源每条冲突边从 $(\mathbf{i},s)$ 指向 $(\mathbf{j},t)$，其距离逐分量非负，即 $j_r-i_r\ge 0$。商函数单调，故每维都有

若某维块号严格增加，块号向量的第一个差异为正，目标键已保证前者在先。若全部块号相同，比较进入同一块内的原坐标及语句编号，而它们本来按源次序前后排列。两种情形都保持边，因此任何正块宽均合法。坐标相同而语句不同的边也由末尾编号保留。

独立A、B、C的矩阵累加恰满足此条件：冲突仅在同一C槽的两个k之间，距离为 $(0,0,k^{\prime }-k)$，且 $k^{\prime }>k$。因此不只是当前2×3×2块，任意正块宽都可用。此处没有交换一个C槽内的加法项次序；若采用另一个会改变项顺序的归约变换，尤其在浮点语义下，还要另作证明。

代码体积、检查成本和性能是三份账 ​

生成器从固定源体建立2d层For链，只复制循环控制结构，不复制每个动态实例的代码。输入语法检查后，生成控制链的工作和大小都是 $O(d)$；连同输入检查则为 $O(1+A+d)$。本页界表达式大小恒定，迭代器不会为整个range预先分配元素数组。

验证器仍从实际IR重新列出实例，核覆盖和全部依赖边；每批emit先受源实例数T的总上限检查，外来IR不能在拒绝之前物化任意多的重复记录。沿用依赖页A、F、T以及交换页Q、K、U，总检查时间为 $O(1+A+F+T^2+Q+K+U)$。对这里生成的固定大小界表达式，U可由K的常数倍覆盖；对外来任意嵌套界表达式则保留U。运行时块循环增加控制步骤，公共解释器还保存完整写轨迹，这些都不能隐藏在“算术次数仍是T”后面。

分块常为缩短数据复用的间隔服务，但合法并不等于快。缓存局部性与缺失分类理路局部性与缓存缺失分类Cache locality · Compulsory capacity and conflict misses · 3C model用明确的影子缓存区分首次、容量与冲突缺失，并通过改变对象布局而非算法验证局部性。需要具体容量、块大小、映射和替换规则；缓存无关模型理路缓存无关模型Cache-oblivious model算法代码不使用缓存参数，但在理想缓存中对所有块尺度分析 miss。另有代码不读取缓存参数的约定。本页只证明次序与内存值，既没有选择最佳块宽，也没有把解释器步骤数当硬件缓存缺失数。

共同终点任务要求提交六层IR、四块更新数与完整C，再把同一分块器作用于负距离反例。迁移时先将行块宽改成1，解释它为何恢复源次序；随后保持2×2但把负偏移依赖换成逐分量非负依赖，使用本节定理而不是有限几次试跑来说明任意块宽的合法性。