1. Three Types of Nested Loop

以第一种 Perfect loop nest 作为基础类型，根据循环边界是否为变量和循环体位置扩展出其他类型的 Nested Loop

  • 循环变量是否为常数
    • Semi-Perfect loop nest : 最外层循环体为变量
    • Imperfect loop nest 2 : 最内层循环体为变量
  • 循环体位置
    • Imperfect loop nest 1 : 循环体位于内层和外层中间

2. Case 1 - Perfect Loop

以下面代码为例，是一个 Perfect Loop，这里 M = 2, N = 4。然后对比了三种 solution，分别是不做任何设置，只对内部 loop 做 pipeline 和只对外部 loop 做 pipeline。从 latency 上看对外部做 pipeline 是最小的，但 utilization 确实最大的，这是因为在外部 loop 做 pipeline 的话其下的所有 loop 都会被打开，可以看到这里 DPS48E 使用了 4 个。

对 inner loop 做 pipeline，可以理解成将两个 loop 展开（计算一共执行了多少次），得到的次数是 8。

使用 LOOP_FLATTEN 实现上面的结果，来将两个 loop collapsed into 一个，以提升 latency。这种方式只适用于 perfect 和 semi-perfect 。

3. Case 2 - Imperfect Loop

a. Innermost Loop

因为最内层 for 循环外面有循环体，所以这里不能使用上面的 LOOP_FLATTEN。因此可以看到这里的 Trip Count 是 9，然后 product 是 3 即执行最内部的 for 循环。

b. Sub-inner Loop

接下来看下如何对第二层 for 循环做流水，即 Col 对应的 for 循环。

注意 Unroll 和 LOOP_FLATTEN 是不一样的概念

c. Outer-most Loop

d. Comparison

4. Optimization

5. Summary