论文基本信息

• 题目: 通过代数分解和公共子表达式消除优化多项式表达式
• 作者: Anup Hosangadi, Farzan Fallah, Ryan Kastner
• 机构: University of California, Santa Barbara; Fujitsu Labs of America, Inc.
• 核心贡献: 提出了一种借鉴多级逻辑综合领域的代数技术，通过因式分解和公共子表达式消除来优化多项式表达式的方法，旨在减少计算中的操作次数（特别是乘法），从而降低延迟和能耗。

方法与核心思路

论文的核心思想是将多项式表达式的优化问题，转化为一个类似于多级布尔逻辑综合的问题。它通过以下步骤实现：

1. 表达式的矩阵表示: 将多项式表示为一个整数矩阵，便于进行代数运算。
2. 提取核心 (Kernels): 通过代数除法，系统性地找出所有可能的因式分解项（即 kernels 和 co-kernels）。
3. 构建矩阵寻找公共子表达式:
   • Kernel Cube Matrix (KCM): 用于寻找多项式级别的公共子表达式（例如，a+b）。
   • Cube Literal Incidence Matrix (CIM): 用于寻找单项式级别的公共子表达式（例如，x*y）。
4. 贪心算法选择最优子表达式: 通过定义一个价值函数 (Value function)，以贪心的方式迭代地选择并提取能带来最大收益（操作节省最多）的公共子表达式，并重写原多项式。

下面，我们将重点解析其中涉及的关键公式。

---

公式一：多项式级别公共子表达式的价值函数 (Value Function for KCM)

这是论文中最核心的公式之一，用于评估在Kernel Cube Matrix (KCM) 中选择一个“矩形”所带来的收益。这个矩形代表着一个可以被提取的公共子表达式。

$${\text{Value}}_1=m\cdot \{(C-1)\cdot (R+\sum _{R}M(R_i))+(R-1)\cdot (\sum _{C}M(C_j))\}+(R-1)\cdot (C-1)$$

1. 逐步推导与符号解释

• $R$: 矩形中的行数。每一行对应一个co-kernel（即提取公共因子后，剩下的乘子）。
• $C$: 矩形中的列数。每一列对应公共子表达式（即kernel）中的一个单项式（cube）。
• $M(R_i)$: 第 $i$ 个 co-kernel（第 $i$ 行）本身所需的乘法次数。
• $M(C_j)$: 公共子表达式中第 $j$ 个单项式（第 $j$ 列）所需的乘法次数。
• $m$: 一个权重因子，表示一次乘法相对于一次加法的成本。例如，在ARM处理器上，$m$ 约等于5，因为乘法指令的周期数大约是加法的5倍。

推导逻辑分解:

这个价值函数计算的是提取公共子表达式前后，计算操作数量的变化（即节省的操作数）。我们分步来看：

1. 原始计算成本:

   • 不提取公共因子时，矩形覆盖的 $R\times C$ 个最终项，每一个项都是由一个 co-kernel 和一个 kernel-cube 相乘得到。
   • 计算第 $i$ 行的 co-kernel 需要 $M(R_i)$ 次乘法。
   • 计算第 $j$ 列的 kernel-cube 需要 $M(C_j)$ 次乘法。
   • 将它们相乘得到最终项，还需要1次乘法。
   • 因此，计算一个 (i, j) 位置的项需要 $M(R_i)+M(C_j)+1$ 次乘法。
   • 整个矩形覆盖的所有项的总乘法次数为：
     $$\sum _{i=1}^R\sum _{j=1}^C(M(R_i)+M(C_j)+1)=R\cdot \sum _{C}M(C_j)+C\cdot \sum _{R}M(R_i)+R\cdot C$$
   • 此外，每个 co-kernel 对应的表达式内部，需要将 $C$ 个项相加，需要 $C-1$ 次加法。总共有 $R$ 行，所以总加法次数为 $R\cdot (C-1)$。

2. 提取公共子表达式后的计算成本:

   • 首先，计算一次公共子表达式 (Kernel)。这个子表达式包含 $C$ 个单项式。
     • 计算这 $C$ 个单项式，总共需要 ${\sum }_{C}M(C_j)$ 次乘法。
     • 将这 $C$ 个单项式相加，需要 $C-1$ 次加法。
   • 然后，将这个公共子表达式的结果，分别与 $R$ 个 co-kernels 相乘。
     • 计算 $R$ 个 co-kernels，总共需要 ${\sum }_{R}M(R_i)$ 次乘法。
     • 将公共子表达式的结果与每个 co-kernel 相乘，需要 $R$ 次乘法。
   • 总乘法次数为: ${\sum }_{C}M(C_j)+{\sum }_{R}M(R_i)+R$。
   • 总加法次数为: $(C-1)$（在kernel内部）加上每个最终表达式内部的加法（如果还有其他项）。这里我们只关注矩形内部，所以是 $C-1$。

3. 计算节省量:

   • 节省的乘法次数:
     $${\text{Savings}}_{\text{mul}}=(\text{原始乘法})-(\text{新乘法})$$
     $$=(R\cdot \sum _{C}M(C_j)+C\cdot \sum _{R}M(R_i)+R\cdot C)-(\sum _{C}M(C_j)+\sum _{R}M(R_i)+R)$$
     $$=(R-1)\cdot \sum _{C}M(C_j)+(C-1)\cdot \sum _{R}M(R_i)+R\cdot C-R$$
     $$=(R-1)\cdot \sum _{C}M(C_j)+(C-1)\cdot \sum _{R}M(R_i)+R\cdot (C-1)$$
     通过重新组合，可以得到论文中公式的形式（稍有出入，但核心思想一致）：
     • ${\sum }_{C}M(C_j)$ 这个公共部分，原来要计算 $R$ 次，现在只计算1次，节省了 $(R-1)\cdot {\sum }_{C}M(C_j)$。
     • 每个 co-kernel $M(R_i)$ 乘以 $C$ 个项，现在只乘以1个公共因子，节省了 $(C-1)$ 次乘法。总节省 $(C-1)\cdot {\sum }_{R}M(R_i)$。（这里论文的推导似乎更精炼）
     • 论文中的 $(C-1)\cdot (R+{\sum }_{R}M(R_i))$ 项可以理解为：对于公共因子（有 $C-1$ 次加法和 $\sum M(C_j)$ 次乘法），我们节省了 $R-1$ 次计算。而对于 $R$ 个 co-kernels，它们每个原来要跟 $C$ 个项作用，现在只跟1个结果作用。
   • 节省的加法次数:
     $${\text{Savings}}_{\text{add}}=(\text{原始加法})-(\text{新加法})$$
     $$=(R\cdot (C-1))-(C-1)=(R-1)\cdot (C-1)$$
   • 总价值: 将节省的乘法和加法次数用权重 $m$ 结合起来，就得到了 ${\text{Value}}_1$。

2. 核心思想与直观解释

• 核心思想: 该公式的核心是量化“提取公因式”这一操作所带来的计算收益。它不仅考虑了节省的乘法和加法数量，还通过权重 $m$ 将它们统一到一个度量标准下，从而可以比较不同公因式提取方案的优劣。
• 直观解释: 想象一下计算 ax + ay 和 bx + by。
  • 不优化：需要4次乘法 (ax, ay, bx, by) 和2次加法。
  • 优化后：先计算公共部分 d = x + y (1次加法)，再计算 a*d 和 b*d (2次乘法)。总共2次乘法和1次加法。
  • 节省了2次乘法和1次加法。
  • 在这个例子中，$R=2$ (co-kernels 是 a 和 b), $C=2$ (kernel 是 x+y)。$M(R_i)=0,M(C_j)=0$。代入公式：
    $${\text{Value}}_1=m\cdot \{(2-1)(2+0+0)+(2-1)(0+0)\}+(2-1)(2-1)=2m+1$$。这正好对应节省的2次乘法和1次加法。

3. 应用场景

此公式是贪心算法的核心驱动力。在KCM矩阵中，算法会寻找所有可能的“矩形”（代表潜在的公共子表达式），并用 ${\text{Value}}_1$ 计算每一个矩形的价值。然后，选择价值最高的那个矩形，执行相应的表达式重写，然后更新KCM矩阵，进入下一次迭代，直到找不到有正收益的矩形为止。

---

公式二：单项式级别公共子表达式的价值函数 (Value Function for CIM)

这个公式用于评估在Cube Literal Incidence Matrix (CIM) 中提取一个单项式公共子表达式（例如从 a²b³c 和 a³b² 中提取 a²b²）的收益。

$${\text{Value}}_2=(R-1)\cdot (\sum _{C}C[i]-1)$$

1. 逐步推导与符号解释

• $R$: 矩形中的行数，即共享这个公共单项式的原始单项式（cube）的数量。
• $C$: 代表提取出的公共单项式。
• ${\sum }_{C}C[i]$: 公共单项式 $C$ 中所有变量的指数之和。这代表计算这个公共单项式本身所需的乘法次数。例如，对于 $C=a^2{b}^3$，${\sum }_{C}C[i]=2+3=5$，需要5次乘法（a*a*b*b*b）。注意，论文中提到 saves ΣC[i] - 1 次乘法，这意味着计算一个幂次为 $k$ 的变量 $x^k$ 需要 $k-1$ 次乘法，所以 $\sum (C[i]-1)$ 更准确，但这里我们遵循原文的表达 $\sum C[i]-1$ 作为计算成本。

推导逻辑:

1. 计算公共单项式 $C$ 的成本: 需要 $({\sum }_{C}C[i]-1)$ 次乘法。
2. 提取前后的变化:
   • 提取前: $R$ 个原始单项式各自独立计算。
   • 提取后:
     • 先计算一次公共单项式 $C$。
     • 然后 $R$ 个原始单项式都利用 $C$ 的计算结果，只需要再乘以剩下的部分。
   • 节省量: 公共单项式 $C$ 的计算，原本需要执行 $R$ 次，现在只需要执行1次。因此，节省了 $R-1$ 次对 $C$ 的计算。
   • 每次计算 $C$ 的成本是 $({\sum }_{C}C[i]-1)$ 次乘法。
   • 所以，总共节省的乘法次数就是 $(R-1)\cdot ({\sum }_{C}C[i]-1)$。

2. 核心思想与直观解释

• 核心思想: 量化提取公共乘法因子的收益。与 ${\text{Value}}_1$ 不同，这里不涉及加法，只关注乘法的节省。
• 直观解释: 考虑 F₁ = a²b³c 和 F₂ = a³b²。
  • 它们的公共子表达式是 d = a²b²。
  • 计算 d 需要 $2+2-1=3$ 次乘法 (假设 a*a*b*b)。
  • 优化前: 计算 F₁ 和 F₂ 需要大量独立的乘法。
  • 优化后:
    • F₁ 变为 d * b * c
    • F₂ 变为 d * a
    • 公共部分 d 只计算了一次。
  • 在这个例子中，$R=2$ (F₁ 和 F₂)，公共部分 $C=a^2{b}^2$，$\sum C[i]=4$。
  • 代入公式：${\text{Value}}_2=(2-1)\cdot (4-1)=3$。即节省了3次乘法。

3. 应用场景

与 ${\text{Value}}_1$ 类似，${\text{Value}}_2$ 是在单项式级别进行优化的贪心算法的驱动力。该算法在CIM矩阵中寻找价值最高的矩形，提取对应的公共单项式，重写表达式，然后迭代，直到没有更多收益。这个过程通常在多项式级别的优化（基于KCM）之后进行。

复杂度分析

论文在4.3节中对算法的复杂度进行了讨论，这是一个重要的补充：

• Kernel生成: 最坏情况下，kernel的数量是指数级的，具体为 $(n+1{)}^m$，其中 $m$ 是变量数，$n$ 是最高指数。例如，对于2个变量 $a,b$，最高2次，co-kernels就有 $(2+1{)}^2=9$ 种可能（$1,b,b^2,a,ab,a{b}^2,\dots$）。
• 矩形覆盖问题: 在KCM或CIM中寻找最优矩形覆盖是NP-hard问题。
• 结论: 论文提出的算法是贪心启发式算法 (greedy heuristic algorithms)，它不保证找到全局最优解，但能在可接受的时间内（实验中平均0.45s）找到高质量的解。暴力搜索所有可能的子表达式和提取顺序对于中等规模的问题都是不现实的。

总结

这篇论文巧妙地将数字电路设计中的逻辑综合思想迁移到了多项式优化这一经典计算问题上。通过矩阵化表示、系统性地生成候选因子(kernels)，并利用带权重的价值函数驱动贪心算法，它构建了一套完整的、自动化的优化流程。其核心公式 ${\text{Value}}_1$ 和 ${\text{Value}}_2$ 是整个算法的灵魂，它们精确地量化了不同优化选择的收益，使得在巨大的搜索空间中进行有效决策成为可能。尽管是启发式的，但实验结果表明，该方法在降低延迟和能耗方面远优于传统的编译器优化技术（如CSE和Horner法则）。