2022-D-杭州电子科技大学-论文精读

5.1.1 邻接矩阵

步骤 1：统计所有基本块编号，确定图的顶点总数,遍历整个 attachment3.csv，收集所有出现过的块号，去重排序，得到全部顶点集合。
步骤 2：构建 N 阶邻接矩阵（N = 顶点总数）
邻接矩阵 M 是 N×N 二维数组，初始化全部为 0；

5.1.2 数据依赖矩阵

设矩阵为 \(\boldsymbol{D}\)，维度 \(N \times N\)（\(N\) 为基本块总数），\(D_{i,j}\) 代表块 \(i\) 对块 \(j\) 的数据依赖关系：

\[D_{i,j}= \begin{cases} 1 \quad &i,j \text{ 存在写后读WAR / 写后写WAW依赖} \Rightarrow L(i) < L(j) \\ -1 \quad &i,j \text{ 存在读后写RAW依赖} \Rightarrow L(i) \leq L(j) \\ 0 \quad &i,j \text{ 无任何数据依赖} \end{cases} \]

5.1.3 控制依赖矩阵

1. 输入数据源：attachment3.csv 基本块跳转邻接表

2. 输出：\(N \times N\) 二值控制依赖矩阵 \(\boldsymbol{C}\)，\(N=\) 总基本块数量

\[C_{i,j}= \begin{cases} 1 \quad &\text{块}i\text{对块}j\text{存在控制依赖} \\ 0 \quad &\text{不存在控制依赖} \end{cases} \]

3. 控制依赖判定标准（赛题附录 A + 论文原文）
   从\(i\)出发的路径只有一部分路径能到达\(j\)，不是全部路径必经\(j\)，则\(C_{i,j} = 1\)，约束 \(L(i) \leq L(j)\)；

补充论文加速规则：仅 1 条出边 / 0 条出边的块\(i\)，对任意\(j\)都不存在控制依赖，直接\(C_{i,j} = 0\)。

模型建立

1. 决策变量

\[\begin{cases} X_{ij} = 1,\quad \text{基本块 }i\text{ 分配到第 }j\text{ 级流水线} \\ X_{ij} = 0,\quad \text{基本块 }i\text{ 不放在第 }j\text{ 级流水线} \end{cases} \]

下标含义拆解：

1. \(i\)：行下标 = 基本块编号（Block \(i\)，来自附件 1、2、3 的块序号 \(0,1,2,\dots\)）
2. \(j\)：列下标 = 流水线层级编号（流水线第 0 级、第 1 级、第 2 级……硬件串行层级）

本质：一个二维 0-1 矩阵，矩阵的行是所有代码块，列是流水线所有层级，单元格取值 0 或 1 标记是否放入。

2. 目标函数

目标函数：\(\min\ J\)
中文：最小化流水线总级数 \(J\)
也就是在满足所有约束条件下，让芯片流水线占用的层级数量尽可能少。

符号\(J\)到底代表什么
\(J\) = 所有基本块被分配到的最大流水线层级编号

举个例子：

• 所有块最高只放到第 2 级（层级 0、1、2）\(\rightarrow J = 3\) 级流水线深度；
• 最优方案只用到 2 层 \(\rightarrow J = 2\)，更优。

用之前的决策变量\(X_{ij}\)严格定义：

\[J = \max_{i}\left\{ \sum_{j} j \cdot X_{ij} \right\} \]

本质：遍历每一个基本块\(i\)算出它所在层级\(L(i)\)，取最大值就是整条流水线的总深度\(J\)。

3. 约束条件为

(1)

1. 公式 (5-3)

\[Z_i = \sum_{j=0}^{u} j \times X_{ij} \]

符号回顾

• \(i\)：第\(i\)个基本块；
• \(j\)：流水线层级编号 \((0,1,2,\dots)\)；
• \(X_{ij}\)：之前定义的 0-1 决策变量，块\(i\)放在层级\(j\)则为 1，否则为 0；
• \(u\)：预设流水线最大可能上限层数（给求解器一个上界，避免无限搜索）。

公式计算逻辑
根据约束一个块只能分配到唯一一层，对某一个块\(i\)，所有\(X_{ij}\)里有且仅有 1 个等于 1，其余全为 0。

举例：块 5 被分配到第 3 层 \(\Rightarrow X_{5,3}=1\)，其余\(X_{5,j}=0\)

\[Z_5 = 0\times0 + 1\times0 + 2\times0 + 3\times1 + \dots = 3 \]

直白结论：\(Z_i\)就是基本块\(i\)实际被分配到的流水线层级序号，等价于之前说的\(L(i)\)，只是论文换了符号\(Z_i\)。

---

2. 公式 (5-4)

\[J \ge Z_i,\quad \forall i \]

字面翻译
流水线总深度\(J\)，必须大于等于每一个基本块所在的层级编号\(Z_i\)。

本质数学定义

\[J = \max\big(Z_0,Z_1,Z_2,\dots,Z_{I-1}\big) \]

\(J\)是所有块层级的最大值，也就是整条流水线最终占用的总级数。

约束真实意义，核心作用：线性化目标函数

原始目标的痛点
我们要优化 \(\min\ J\)，而 \(J = \max(Z_i)\)。

\(\max\)（最大值）属于非线性运算，Gurobi/CPLEX 等整数规划求解器不能直接识别非线性表达式，无法求解。

论文这套约束的线性化巧妙处理
不用直接写 \(\max\)，改用两条规则等价替代：

1. 对每一个块，强制 \(J \ge Z_i\)（\(J\) 不小于任何一个块的层级）；
2. 目标函数是最小化 \(J\)。

在求解器最小化\(J\)的驱动下，\(J\)会被自动压缩到刚好等于最大的那个\(Z_i\)，完美等价于取最大值，全程都是线性不等式，求解器可以直接计算。

（2）

这是问题 1 最核心的单层硬件资源容量约束（公式 5-5），属于芯片物理硬件硬上限，任何排布方案都不能突破；本质是对每一级流水线 \(j\)，统计所有放在该层的基本块资源占用总和，强制不超过芯片单级最大承载量。

先统一所有符号含义

• \(i\)：基本块编号，一共\(I\)个块，遍历\(i = 0\)到\(I-1\)；
• \(j\)：流水线层级编号，遍历每一层\(j = 0,1,\dots,u\)；
• \(X_{ij}\)：0-1 决策变量，\(X_{ij}=1\)代表块\(i\)放在第\(j\)层，否则为 0；
• \(T_i\)：块\(i\)消耗的 TCAM 资源量；
• \(H_i\)：块\(i\)消耗的 HASH 资源量；
• \(A_i\)：块\(i\)消耗的 ALU 资源量；
• \(Q_i\)：块\(i\)消耗的 QUALIFY 资源量。

求和公式通用逻辑（四条式子完全同构）

\[\sum_{i=0}^{I-1} X_{ij} \cdot \text{资源}_i \le \text{单层上限} \]

对固定某一层\(j\)：
只有\(X_{ij}=1\)的块（真正放在这一层的块）才会把自身资源值计入累加和；\(X_{ij}=0\)相乘后为 0，不参与计算。

最终求和结果 = 第 \(j\) 层流水线所有并行执行基本块的该类资源总占用量。

（3）

折叠配对规则（芯片硬件物理架构）
流水线层级0~31共32级才有折叠机制，≥32级的层级无折叠约束：
成对折叠配对为：

\[0 \leftrightarrow 16、1 \leftrightarrow 17、2 \leftrightarrow 18 \dots\dots 15 \leftrightarrow 31 \]

也就是对于 \(j = 0,1,\dots,15\)，第\(j\)级 和 第\(j+16\)级为一对折叠绑定层级。

硬件资源绑定上限
每一对折叠两级整体共享一套资源池：

1. 一对两级合计 TCAM 总占用 \(\le 1\)
2. 一对两级合计 HASH 总占用 \(\le 3\)

ALU、QUALIFY不受折叠约束影响，只遵守上一条单层各自上限即可。

（4）

公式书写与符号含义

\[\sum_{j=0}^{u} X_{ij} = 1,\quad i = 0,1,\dots,I-1 \]

1. \(i\)：任意一个基本块编号，总共有\(I\)个基本块；
2. \(j\)：流水线层级编号，从 0 到预设最大层数\(u\)；
3. \(X_{ij}\)：0-1 二元决策变量，块\(i\)放在第\(j\)层则为 1，否则为 0。

数学直白翻译
对任意一个基本块\(i\)，遍历所有流水线层级\(j\)，所有\(X_{ij}\)加起来必须等于 1。

（5）

规则原文：占用了 TCAM 资源的偶数流水线层级，总个数不能超过 5 层。

通俗翻译：
只有层级编号 \(j=0,2,4,6\dots\) 偶数层，且该层放了 TCAM 资源（层内 TCAM 总和 \(>0\)），才算一个“有效计数层”；这类层的总数 \(\le 5\)。

公式分段拆解，逐个模块看懂
完整公式：

\[\frac12 \times \sum_{j=0}^{u} \big(1 + (-1)^j\big) \cdot \left( \sum_{i=0}^{I-1} X_{ij}T_i \right) \ \le\ 5 \]

模块 1：奇偶筛选因子 \(\boldsymbol{1 + (-1)^j}\)（最巧妙的数学设计）

• 当\(j\)为偶数：\((-1)^j = 1,\ 1+1=2\)
• 当\(j\)为奇数：\((-1)^j = -1,\ 1-1=0\)

作用：直接过滤掉所有奇数层级，奇数项整项乘 0，不参与求和；只保留偶数层级参与计算。

模块 2：内层求和 \(\boldsymbol{\sum_{i=0}^{I-1} X_{ij}T_i}\)
就是第\(j\)层流水线全部基本块 TCAM 资源占用总量，记为 \(SumT_j\)：

• \(SumT_j > 0\)：这一层放了占用 TCAM 的块，是要被统计的有效偶数层；
• \(SumT_j = 0\)：偶数层但没用到 TCAM，不计入数量。

模块 3：外层求和 + 乘以 \(\boldsymbol{\dfrac12}\)
偶数层带入因子 2，每一个有效偶数层贡献 \(2 \times 1 = 2\)，最后整体除以 2：

\[\frac12 \times 2 = 1 \]

等价于每一个使用了 TCAM 的偶数层，最终计数为 1，完全等价于统计有效层数。

(6) 数据依赖约束

若基本块 \(m\) 和基本块 \(n\) 之间具有写后读或写后写依赖，则基本块 \(m\) 的流水线级数 \(Z_m\) 应小于基本块 \(n\) 的流水线级数 \(Z_n\)；若具有读后写依赖，则基本块 \(m\) 的流水线级数 \(Z_m\) 应不大于基本块 \(n\) 的流水线级数 \(Z_n\)，由此可得公式 (5-9)：

\[\begin{cases} Z_m - Z_n < 0 \ , & s_{mn}=1,\ m=0,1,\dots,I-1,\ n=0,1,\dots,I-1 \\ Z_m - Z_n \le 0 \ , & s_{mn}=-1,\ m=0,1,\dots,I-1,\ n=0,1,\dots,I-1 \end{cases} \tag{5-9} \]

(7) 控制依赖约束

若基本块 \(m\) 和基本块 \(n\) 之间具有控制依赖，则基本块 \(m\) 的流水线级数 \(Z_m\) 应不大于基本块 \(n\) 的流水线级数 \(Z_n\)；由此可得公式 (5-10)：

\[Z_m - Z_n \le 0 \ ,\ c_{mn}=1,\ m=0,1,\dots,I-1,\ n=0,1,\dots,I-1 \tag{5-10} \]

灵敏度分析

控制其他所有条件不变，逐个微调芯片四类硬件单层资源上限、偶数层 TCAM 名额等硬性参数，观察最小流水线级数 J 的下降 / 上升幅度，判断各类资源的敏感程度，定位芯片硬件设计瓶颈，同时验证整数规划模型的稳定性。

第二小问新增约束

一、核心改动 1：单层 HASH、ALU 资源累加规则（最本质区别）

1. 问题 1：同一层级所有基本块资源直接全部求和

\[\sum X_{ij}H_i \le 2,\quad \sum X_{ij}A_i \le 56 \]

2. 问题 2：仅对同一条执行路径上的块累加 HASH、ALU；分支互斥、不会同时运行的块不计入占用

• 单层 HASH：层级内任意单条路径 HASH 总和 \(\le 2\)
• 单层 ALU：层级内任意单条路径 ALU 总和 \(\le 56\)

TCAM 单层\(\le1\)、QUALIFY 单层\(\le64\) 两式完全不动。