融合优化与分段执行：提升程序性能的有效策略

### 融合优化与分段执行：提升程序性能的有效策略 #### 1. 融合优化 融合优化是一种重要的技术，其中“砍伐森林（Deforestation）”是用于融合聚合数据结构上顺序计算的知名技术。由于本地计算块形成顺序代码，这种技术也可在此应用。 主要优点包括： - 减少向量遍历次数。 - 减少（甚至消除）中间向量。 以函数 `SumSq` 为例，在库方法中，使用 `enumerate`、`vector...mult` 和 `sum` 三个函数实现程序。将这些函数转换为 `Cvr` 时，会形成三个代码块： - 第一部分：将参数拆分为局部值。 - 中间部分：实现三个向量操作内部的计算，可融合为单个 `Gen` 构造。 - 最后部分：对所有部分和进行全局归约。 融合将向量的生成和归约结合起来，实际上不会创建向量，使分段执行在此变得多余。 #### 2. 融合的局限性 `Loop` 和 `Gen` 构造不能跨全局操作进行融合，因为全局操作会破坏参数值的纯局部语义。以 `SumSqScan` 为例，`plus_scan` 被拆分为三部分，中间部分是全局操作，它会在处理器之间传播部分和。这种传播在代码块之间形成了障碍，导致并非所有本地代码块都能融合。只要在 `Loop` 或 `Gen` 构造对之间出现全局操作，就无法进行融合。 #### 3. 融合与分段执行的结合 为了结合分段执行和融合的优点，我们通过引入分段类型扩展了 `Cvr`，扩展后的语言称为 `Cpw`，它保留了 `Cvr` 的所有特性。 - **分段类型构造器**：使用 `<,'..?>` 表示分段类型的构造器。 - **高阶函数**：提供高阶函数 `<,'..?>`，将计算嵌入分段执行上下文。如果有函数 `f : a1 x ... x an -> β1 x ... x βm`，则 `<,'.f?>` 的类型为 `<,'.a1?> x ... x <,'.an?> -> <,'.β1?> x ... x <,'.βm?>`。 - **辅助函数**： - `pw_in: a -> <,'.a?>`：使值准备好进行分段执行。 - `pw_out : <,'.a?> -> a`：将分段类型的值转换为其原始类型。 以下是 `SumSqScan` 的融合版本和分段版本的代码示例： ```plaintext function SumSqScan'(sg, eg) = let n = spl-iLscalar(sg - eg) ace = spl-iLscalar( accg) (-v, b) = ((Gen (f, g, k)))( n, ace) c = propagate_+ (b) d = ((rr2 o Loop(/', g', k')))(v, c) in join-+ (d) functfon SumSqScan;.,(sg, eg) = let n = pw_·in(sg - eg) np = <,.spl·iLscalar ;> (n) ace = pw--in(accg) accp = <,.spl·iLscalar ;> (ace) (vp, bp) = <,.((Gen (f, g, k))) ;> (np, accp) cp = <,.propagate-+ »(bp) dp = <,.((rr2 o Loop (f', g', k'))) ;> (vp, cp) d = <,.jo·in_ + »( dp) in pw_o·ut(d) ``` 要以分段方式执行函数，需要将操作提升到分段类型，先将参数转换为分段值，最后再将分段输出转换为普通值。转换后的程序输入和输出类型与原始版本相同，不会影响调用者。 #### 4. 向量计算的规范表示 使用 `Loop` 和 `Gen` 对向量计算进行规范表示，非常适合对内存关键的程序模式进行自动分析。 - **生成器**：始终是 `Gen`，其过滤函数不是无条件为 `False`（`(Ax.Aa.False)`），并且后面不能仅跟对累积值的投