MLIR与CGRA编译优化技术解析

1. MLIR与CGRA编译优化技术概述

在异构计算架构快速发展的今天，粗粒度可重构阵列(Coarse-Grained Reconfigurable Arrays, CGRAs)因其独特的空间架构特性，成为加速计算密集型工作负载的理想选择。与FPGA相比，CGRA在操作级别可编程，具有更低的开销和更快的重配置时间。然而，其广泛应用面临一个关键挑战：如何实现高效的CGRA编译，特别是对控制数据流图(Control Data Flow Graph, CDFG)的有效管理。

传统CGRA编译器主要关注数据流图(Data Flow Graph, DFG)的映射，将控制流分歧的管理委托给专用硬件单元。这种方法存在两个主要局限：1) 每次内核部署到CGRA网格时都需要加载配置和数据，造成显著的重配置开销；2) 仅支持单循环映射，限制了应用范围。我们提出的基于MLIR的编译框架，通过编译器级别的控制流管理和优化，实现了硬件无关的高性能CDFG编译。

关键突破：我们的框架在PC控制模型下实现了零重配置开销的CDFG映射，同时通过CFG变换支持模调度(Modulo Scheduling)，相比现有方案最高可获得2.1倍的性能提升。

2. CGRA编译的核心挑战与解决方案

2.1 控制流管理的硬件复杂性

现有CGRA控制流管理方案主要分为两类：基于重配置的方法和基于程序计数器(PC)的方法。前者通过专用硬件模块处理基本块切换，但会引入指令和数据重配置开销；后者虽然减少了硬件复杂度，但无法有效利用循环级并行性。

我们的解决方案通过活性分析(Liveness Analysis)跟踪跨基本块传播的值，将CDFG映射分解为DFG级编译。如图1所示，每个DFG可以独立编译，只要通过活性分析解决块间依赖关系。这种方法无需专用硬件支持，仅通过简单的运行时PC操作即可处理分支。

2.2 运行时效率优化

为提高运行时效率，我们采用两种关键技术：

1. 基本块融合：通过水平合并、垂直合并和循环头体融合等变换，减少控制开销，增加指令级并行机会
2. CFG适配：通过调整循环长度L'使其等于启动间隔(II)，使模调度能够应用于PC控制模型，实现循环级并行

图3对比了不同方法的执行模型。传统PC控制模型(图3h)中基本块执行不能重叠，而我们的优化方案(图3j,n,q)通过编译器变换实现了高效的流水线执行。

3. 基于MLIR的编译框架设计

3.1 整体编译流程

我们的框架采用MLIR作为前端，支持从C/C++代码到CGRA汇编的完整编译流程(图5)：

1. 前端处理：MLIR解析高级代码并生成CDFG抽象
2. 中端优化：
   • 硬件无关的CFG简化
   • 硬件兼容性转换
   • 自定义cgra方言定义
3. 后端映射：
   • 模调度优化
   • CDFG映射
   • 寄存器分配

3.2 硬件无关的CFG变换

我们设计了三种原子级CFG变换，可灵活组合应对复杂控制流：

3.2.1 水平合并

将具有相同目的地的两个发散后继块合并(图6a)。前提是这些块是"写自由"的，即执行两条路径仅产生额外结果而不冲突。通过插入选择操作根据运行时条件确定最终输出。

3.2.2 垂直合并

合并两个顺序连接的无分支基本块(图6b)。这种无条件分支总是被执行，合并后允许两个块的操作并发执行。

3.2.3 循环头体融合

将循环条件检查集成到循环体中(图6c)。如果迭代次数在编译时已知大于零，可简化为无条件跳转，确保第一次迭代总是执行。

实践技巧：这些变换可以迭代应用。如图6d-e所示，先进行垂直合并，再进行水平合并，最后与前后驱块融合，能有效简化复杂CFG结构。

4. 硬件感知的优化与映射

4.1 内存操作转换

MLIR前端将数据访问表示为内存引用参数值。我们的框架将其转换为与物理地址对齐的访问。对于数组访问，分为两步：

1. 计算元素偏移量(索引×跨度)
2. 将偏移量加到数组基地址

// 原始C代码 int a0 = x[0]; // 前端IR %2 = memref.load %arg1[%1] : memref<20xf32> // 中端IR转换后 %2 = arith.muli %1, %c4_i32 : i32 // 计算偏移(假设4字节对齐) %3 = arith.addi %2, %c1000_i32 : i32 // 加基地址(假设1000) %4 = cgra.lwi %3 : i32 -> f32 // 生成CGRA加载指令

4.2 硬件特定的IR转换

针对不同CGRA的ISA特性，我们通过自定义cgra方言实现平台特定的指令转换。例如：

• 将MLIR的"compare"和"select"指令转换为利用零标志和符号标志的CGRA特定指令
• 使用CGRA的"branch"和"jump"指令连接基本块
• 检查立即数字段大小限制，必要时分解为多个操作

4.3 模调度与CDFG映射

我们采用整数线性规划(ILP)模型进行CDFG映射，关键创新点包括：

1. 活性分析约束：确保跨基本块的数据依赖得到满足
2. 无回溯映射：当遇到寄存器溢出或路由限制时，通过IR变换插入路由操作或分割DFG，无需回溯修改已有调度
3. 循环优化：通过调整循环长度L'=II，使模调度能应用于PC控制模型

图4展示了两个典型CDFG映射案例。在条件分支示例(图4a-b)中，活性分析确保变量x和y的正确传播；在嵌套循环示例(图4c-d)中，活性分析跟踪循环计数器i和k的跨块使用。

5. 实现效果与性能分析

5.1 实验设置

我们在OpenEdgeCGRA平台上评估框架效果，对比三种主流方案：

1. EffiMap：PC基础的CDFG映射
2. SAT-MapIt：DFG映射+CPU支持
3. Marionette：支持CGRA硬件重配置的CDFG映射

5.2 性能对比

我们的框架展现出显著优势：

• 相比EffiMap：2.12倍加速
• 相比SAT-MapIt：1.48倍加速
• 相比Marionette：1.20倍加速

关键优势来源于：

1. 零重配置开销：通过活性分析和PC控制消除基本块切换的配置加载
2. 高效资源利用：CFG变换和模调度提高硬件利用率
3. 广泛适用性：支持包含嵌套循环和发散分支的通用应用

5.3 编译效率

虽然采用ILP模型，但通过将CDFG分解为独立DFG映射和避免回溯的策略，我们的编译时间在可接受范围内。对于典型内核，编译时间在几秒到几分钟不等，具体取决于CGRA网格大小和应用复杂度。

6. 应用实践与经验分享

6.1 典型应用场景

该框架特别适合以下场景：

1. 数字信号处理：如FFT、FIR滤波等具有规则循环模式的应用
2. 图像处理：如卷积、边缘检测等计算密集型操作
3. 科学计算：矩阵运算、偏微分方程求解等

6.2 实际部署建议

1. CFG变换顺序：建议先应用循环头体融合，再进行垂直合并，最后考虑水平合并
2. 活性分析调试：使用可视化工具检查跨基本块的数据流，确保关键变量得到正确传播
3. 资源约束处理：当映射失败时，优先尝试插入路由操作而非分割DFG，以保持更高并行度

6.3 常见问题排查

1. 映射失败：检查是否所有基本块都满足资源约束，特别是活性变量所需的路由资源
2. 性能未达预期：检查循环是否成功应用模调度，II值是否合理
3. 结果不正确：验证跨基本块的活性变量映射是否一致，特别是phi函数处理

我在实际部署中发现，对复杂嵌套循环，采用逐步展开策略(先优化内层循环，再处理外层)往往能获得更好的效果。此外，合理设置CGRA网格中处理元素(PE)的功能单元分布，对提升映射成功率至关重要。