PolyBench基准程序详解：编译器优化评测指标

PolyBench基本概念

PolyBench（Polyhedral Benchmark）是由UCLA（加州大学洛杉矶分校）的Louis-Noël Pouchet及其研究团队开发的基准测试套件，专门用于评估多面体编译技术和循环优化效果。该套件位于 ucla.edu/pouchet/software/polybench，提供了一组标准化的计算密集型内核，这些内核包含嵌套循环和规则的数组访问模式，非常适合应用多面体编译技术进行优化。

PolyBench的核心价值在于提供小而精的基准程序，这些程序能够代表科学计算、线性代数和数据处理领域中常见的计算模式。通过这些基准程序，研究人员可以评估编译器优化技术、硬件性能和并行化策略的效果。

引言

看论文傻傻不懂指标，2nm？3nm?什么鬼？本文详解
在这里插入图片描述

GPU测试速度参考，A100 ,400w，数据来源

重点基准程序详解

本文将重点介绍几个关键的PolyBench基准程序：2MM、3MM、ATAX、BICG、GEMM、GESUMMV、MVT、SPAM-FILTER和DOITGEN。这些程序代表了线性代数和数据挖掘领域中的典型计算模式，是评估编译器优化和硬件性能的重要指标。

基准程序	计算模式	关键优化点	应用领域
2MM	$\alpha \cdot A \times B \times C + \beta \cdot D$	循环平铺、循环交换、向量化、并行化	数值模拟、物理模拟、图像处理、机器学习
3MM	$\times B) \times (C \times D)$	多级循环平铺、中间结果缓存、多级并行化	气象模拟、流体动力学、复杂物理系统模拟、高级图形渲染
ATAX	$A^T \times (A \times x)$	循环融合、向量化、缓存阻塞、数据布局优化	数字信号处理、图像处理、特征转换、线性变换
BICG	$\times p$ , $A^T \times r$	循环交换、向量化、并行化、缓存阻塞	稀疏矩阵求解、计算机图形学、有限元分析、线性系统求解
GEMM	$\alpha \cdot A \times B + \beta \cdot C$	循环平铺、循环展开、向量化、并行化、BLAS库	机器学习、图像处理、数值模拟、科学计算
GESUMMV	$\alpha \cdot A \times x + \beta \cdot B \times x$	循环融合、向量化、预取、数据布局优化	数据压缩、图像滤波、数字信号处理、线性变换组合
MVT	$\times y1$ , $A^T \times y2$	循环融合、向量化、缓存阻塞、数据布局优化	数据分析、科学模拟、线性系统求解、特征提取
DOITGEN	$\sum_{p=0}^{NP-1} A[r][q][p] \times C4[p][s]$	多维循环平铺、多级缓存优化、向量化、数据布局转换	信号处理、图像压缩、多分辨率分析、张量操作

1. 2MM（Two Matrix Multiplications）

计算模式：
2MM实现了两次矩阵乘法运算的序列，表示为：
$\alpha \cdot A \times B \times C + \beta \cdot D$

这可以分解为两步：

计算临时矩阵： $\times B$
计算最终结果： $\alpha \cdot E \times C + \beta \cdot D$

核心代码结构：

/* 第一次矩阵乘法：E = A*B */
for (i = 0; i < ni; i++) {for (j = 0; j < nj; j++) {E[i][j] = 0;for (k = 0; k < nk; k++) {E[i][j] += A[i][k] * B[k][j];}}
}/* 第二次矩阵乘法：D = alpha*E*C + beta*D */
for (i = 0; i < ni; i++) {for (j = 0; j < nl; j++) {D[i][j] *= beta;for (k = 0; k < nj; k++) {D[i][j] += alpha * E[i][k] * C[k][j];}}
}

优化空间：

循环平铺以提高缓存利用率
循环交换以优化内存访问模式
向量化内部循环以利用SIMD指令
并行化外部循环以利用多核处理器

应用领域：

数值模拟
物理模拟
图像处理
机器学习中的复合矩阵运算

2. 3MM（Three Matrix Multiplications）

计算模式：
3MM实现了三次矩阵乘法运算的序列，计算：
$\times B) \times (C \times D)$

这可以分解为三步：

计算 $\times B$
计算 $\times D$
计算 $\times F$

核心代码结构：

/* 第一次矩阵乘法：E = A*B */
for (i = 0; i < ni; i++) {for (j = 0; j < nj; j++) {E[i][j] = 0;for (k = 0; k < nk; k++) {E[i][j] += A[i][k] * B[k][j];}}
}/* 第二次矩阵乘法：F = C*D */
for (i = 0; i < nj; i++) {for (j = 0; j < nl; j++) {F[i][j] = 0;for (k = 0; k < nm; k++) {F[i][j] += C[i][k] * D[k][j];}}
}/* 第三次矩阵乘法：G = E*F */
for (i = 0; i < ni; i++) {for (j = 0; j < nl; j++) {G[i][j] = 0;for (k = 0; k < nj; k++) {G[i][j] += E[i][k] * F[k][j];}}
}

优化空间：

多级循环平铺
中间结果的缓存优化
多级并行化（任务级和数据级）
矩阵乘法算法的选择（如Strassen算法）

应用领域：

气象模拟
流体动力学
复杂物理系统模拟
高级图形渲染

3. ATAX（Matrix Transpose and Vector Multiplication）

计算模式：
ATAX计算矩阵转置与向量乘积：
$A^T \times (A \times x)$

这可以分解为两步：

计算 $\times x$
计算 $A^T \times tmp$

核心代码结构：

/* 初始化输出向量 */
for (i = 0; i < ny; i++)y[i] = 0;/* 计算 y = A^T * (A * x) */
for (i = 0; i < nx; i++) {tmp[i] = 0;for (j = 0; j < ny; j++)tmp[i] += A[i][j] * x[j];for (j = 0; j < ny; j++)y[j] += A[i][j] * tmp[i];
}

优化空间：

循环融合以减少临时存储和提高数据局部性
向量化内部循环
缓存阻塞以优化大矩阵的处理
数据布局优化以提高空间局部性

应用领域：

数字信号处理
图像处理
机器学习中的特征转换
科学计算中的线性变换

4. BICG（BiConjugate Gradient Method Kernel）

计算模式：
BICG实现了双共轭梯度法的子内核，计算：
$\times p$
$A^T \times r$

核心代码结构：

/* 初始化输出向量 */
for (i = 0; i < m; i++)s[i] = 0;
for (i = 0; i < n; i++)q[i] = 0;/* 计算 q = A*p 和 s = A^T*r */
for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {s[i] += A[i][j] * r[j];q[j] += A[i][j] * p[i];}
}

优化空间：

循环交换以优化内存访问模式
向量化和并行化
缓存阻塞以处理大矩阵
数据布局优化以减少缓存未命中

应用领域：

稀疏矩阵求解
计算机图形学
有限元分析
大规模线性系统求解

5. GEMM（General Matrix Multiplication）

计算模式：
GEMM实现了通用矩阵乘法：
$\alpha \cdot A \times B + \beta \cdot C$

核心代码结构：

/* 计算 C = alpha*A*B + beta*C */
for (i = 0; i < ni; i++) {for (j = 0; j < nj; j++) {C[i][j] *= beta;for (k = 0; k < nk; k++) {C[i][j] += alpha * A[i][k] * B[k][j];}}
}

优化空间：

循环平铺和缓存阻塞
循环展开以减少循环开销
向量化和并行化
专用矩阵乘法算法（如BLAS库）

应用领域：

机器学习（尤其是深度神经网络）
图像处理
数值模拟
几乎所有科学计算领域

GEMM是线性代数中最基础也是最重要的操作之一，是评估编译器性能的关键指标。它直接影响到许多科学计算和机器学习应用的性能。GEMM也是BLAS（基础线性代数子程序）库的核心，是优化库和硬件加速器的主要目标。

6. GESUMMV（Scalar, Vector and Matrix Multiplication）

计算模式：
GESUMMV计算两个矩阵-向量乘积的加权和：
$\alpha \cdot A \times x + \beta \cdot B \times x$

核心代码结构：

/* 计算 y = alpha*A*x + beta*B*x */
for (i = 0; i < n; i++) {tmp[i] = 0;y[i] = 0;for (j = 0; j < n; j++) {tmp[i] += A[i][j] * x[j];y[i] += B[i][j] * x[j];}y[i] = alpha * tmp[i] + beta * y[i];
}

优化空间：

循环融合以提高数据局部性
向量化内部循环
预取以减少内存延迟
数据布局优化以提高缓存命中率

应用领域：

数据压缩
图像滤波
数字信号处理
线性变换组合

7. MVT（Matrix Vector Product and Transpose）

计算模式：
MVT计算两个矩阵-向量乘积：
$\times y1$
$A^T \times y2$

核心代码结构：

/* 计算 x1 = A*y1 */
for (i = 0; i < n; i++) {for (j = 0; j < n; j++) {x1[i] += A[i][j] * y1[j];}
}/* 计算 x2 = A^T*y2 */
for (i = 0; i < n; i++) {for (j = 0; j < n; j++) {x2[i] += A[j][i] * y2[j];}
}

优化空间：

循环融合以提高数据重用
向量化内部循环
缓存阻塞以处理大矩阵
数据布局优化以提高转置操作的效率

应用领域：

数据分析
科学模拟
线性系统求解
特征提取

9. DOITGEN（Multi-resolution Analysis Kernel）

计算模式：
DOITGEN实现了多分辨率分析内核，涉及多维数组操作：
$\sum_{p=0}^{NP-1} A[r][q][p] \times C4[p][s]$

核心代码结构：

/* 多维数组操作 */
for (r = 0; r < nr; r++) {for (q = 0; q < nq; q++) {for (p = 0; p < np; p++) {sum[p] = 0;for (s = 0; s < np; s++) {sum[p] += A[r][q][s] * C4[s][p];}}for (p = 0; p < np; p++) {A[r][q][p] = sum[p];}}
}

优化空间：

多维循环平铺
多级缓存优化
向量化内部循环
数据布局转换以提高多维数组访问效率

应用领域：

信号处理
图像压缩
多分辨率分析
科学计算中的张量操作

MLIR中的表示与优化

MLIR（Multi-Level Intermediate Representation）提供了强大的框架来表示和优化上述PolyBench基准程序。以下是如何在MLIR中表示和优化这些基准程序的示例：

1. 高级表示（Linalg Dialect）

以GEMM为例，在Linalg Dialect中的表示：

// C = alpha*A*B + beta*C
%result = linalg.generic {indexing_maps = [affine_map<(i, j, k) -> (i, k)>,  // Aaffine_map<(i, j, k) -> (k, j)>,  // Baffine_map<(i, j, k) -> (i, j)>   // C],iterator_types = ["parallel", "parallel", "reduction"]
} ins(%A, %B, %alpha, %beta : tensor<ni x nk x f32>, tensor<nk x nj x f32>, f32, f32) outs(%C : tensor<ni x nj x f32>) {^bb0(%a: f32, %b: f32, %alpha: f32, %beta: f32, %c: f32):%scaled_c = arith.mulf %c, %beta : f32%a_scaled = arith.mulf %a, %alpha : f32%ab = arith.mulf %a_scaled, %b : f32%result = arith.addf %scaled_c, %ab : f32linalg.yield %result : f32
}

Linalg Dialect对结构化数据进行结构化处理的通用表示，具有以下特点：

既可以将tensor作为操作数，也可以将buffer作为操作数
包含payload操作（执行具体运算）和struct操作（表示如何进行运算）
在实际应用中，外部Dialect很多情况下会先转换到Linalg Dialect再执行后续优化

2. 仿射表示（Affine Dialect）

对于2MM，在Affine Dialect中的表示：

// 第一次矩阵乘法：E = A*B
affine.for %i = 0 to %ni {affine.for %j = 0 to %nj {%init = constant 0.0 : f32%sum = affine.for %k = 0 to %nk iter_args(%sum_iter = %init) -> f32 {%a = affine.load %A[%i, %k] : memref<ni x nk x f32>%b = affine.load %B[%k, %j] : memref<nk x nj x f32>%prod = arith.mulf %a, %b : f32%next = arith.addf %sum_iter, %prod : f32affine.yield %next : f32}affine.store %sum, %E[%i, %j] : memref<ni x nj x f32>}
}

Affine Dialect对多面体编译（polyhedral compilation）的实现，其主要特点：

包含多维数据结构的控制流操作
支持多维数据的循环和条件控制，存储映射操作等
目标是实现多面体变换，如自动并行化、循环融合和平铺等
使用仿射表达式描述循环边界和内存访问模式

3. 向量化表示（Vector Dialect）

Vector Dialect提供了对SIMD（单指令多数据）或SIMT（单指令多线程）模型的抽象：

// 对ATAX内部循环向量化
affine.for %i = 0 to %nx {%tmp_init = constant 0.0 : f32affine.store %tmp_init, %tmp[%i] : memref<nx x f32>// 向量化内部循环%tmp_val = affine.vector.load %tmp[%i] : memref<nx x f32>, vector<4xf32>%vec_sum = affine.for %j_unroll = 0 to %ny step 4 iter_args(%vec_acc = %tmp_val) -> vector<4xf32> {%x_vec = vector.load %x[%j_unroll] : memref<ny x f32>, vector<4xf32>%a_vec = affine.vector.load %A[%i, %j_unroll] : memref<nx x ny x f32>, vector<4xf32>%prod = arith.mulf %a_vec, %x_vec : vector<4xf32>%sum_vec = arith.addf %vec_acc, %prod : vector<4xf32>affine.yield %sum_vec : vector<4xf32>}// 存储结果affine.vector.store %vec_sum, %tmp[%i] : memref<nx x f32>, vector<4xf32>
}

Vector Dialect的特点：

作为向量的中间表示，可以被转换到不同目标平台的底层表示
实现Tensor在不同平台的支持
包含向量化操作，如向量加载/存储、向量计算等

4. 结构化控制流（SCF Dialect）

SCF（Structured Control Flow）Dialect提供了比控制流图CFG更高层的抽象：

// 使用SCF表示GEMM
scf.for %i = %c0 to %ni step %c1 {scf.for %j = %c0 to %nj step %c1 {// 加载并缩放C%c_val = memref.load %C[%i, %j] : memref<ni x nj x f32>%c_scaled = arith.mulf %c_val, %beta : f32memref.store %c_scaled, %C[%i, %j] : memref<ni x nj x f32>// 计算矩阵乘法scf.for %k = %c0 to %nk step %c1 {%a_val = memref.load %A[%i, %k] : memref<ni x nk x f32>%b_val = memref.load %B[%k, %j] : memref<nk x nj x f32>%ab = arith.mulf %a_val, %b_val : f32%ab_scaled = arith.mulf %ab, %alpha : f32%c_current = memref.load %C[%i, %j] : memref<ni x nj x f32>%c_new = arith.addf %c_current, %ab_scaled : f32memref.store %c_new, %C[%i, %j] : memref<ni x nj x f32>}}
}

SCF Dialect的特点：