par2serial-cc

par2serial-cc: Parallel-to-Serial Optimizing C Compiler

<p align="center"> <b>将高度并行化的C程序编译为优化的串行CPU代码</b><br> <i>一定程度解决无GPU只能用CPU跑的问题</i> </p>

---

🎯 项目目标

par2serial-cc 是一个源到源的C编译器(transpiler)，专注于：

1. 识别并行模式：检测 parallel_for、parallel_reduce、parallel_scan、parallel_map、barrier同步、共享内存访问等并行原语
2. 转换为高效串行代码：通过一系列精心设计的优化Pass，将并行代码转换为在CPU上高效执行的串行代码
3. 自动SIMD向量化：利用SSE/AVX指令集实现数据级并行
4. 深度循环优化：循环分块(tiling)、融合(fusion)、展开(unrolling)、交换(interchange)
5. 内存布局优化：AoS↔SoA转换、数据对齐、预取提示

🏗 编译器架构

源代码(.pc文件)
    │
    ▼
┌──────────────┐
│  词法分析器   │  Lexer: 识别parallel关键字、标准C tokens
│  (lexer.c)   │
└──────┬───────┘
       │ Token流
       ▼
┌──────────────┐
│  语法分析器   │  Parser: 递归下降，构建AST
│  (parser.c)  │
└──────┬───────┘
       │ AST
       ▼
┌──────────────┐
│  语义分析器   │  Semantic: 类型检查、作用域、依赖分析
│  (semantic.c)│
└──────┬───────┘
       │ 标注AST
       ▼
┌──────────────┐
│  IR生成器     │  IR Builder: AST → 三地址码IR
│  (ir.c)      │
└──────┬───────┘
       │ IR
       ▼
┌──────────────────────────────────────────┐
│           优 化 流 水 线                   │
│                                          │
│  ┌────────────────────────────────────┐  │
│  │  Pass 1: 并行模式检测与分析         │  │
│  │  (parallel_detect.c)              │  │
│  │  - 识别parallel_for/reduce/scan   │  │
│  │  - 依赖距离向量分析               │  │
│  │  - 归约变量检测                   │  │
│  └──────────┬─────────────────────────┘  │
│             ▼                            │
│  ┌────────────────────────────────────┐  │
│  │  Pass 2: 循环优化                  │  │
│  │  (loop_opt.c)                     │  │
│  │  - 循环分块 (Tiling)              │  │
│  │  - 循环融合 (Fusion)              │  │
│  │  - 循环展开 (Unrolling)           │  │
│  │  - 循环交换 (Interchange)         │  │
│  │  - 循环分裂 (Fission)             │  │
│  └──────────┬─────────────────────────┘  │
│             ▼                            │
│  ┌────────────────────────────────────┐  │
│  │  Pass 3: 自动SIMD向量化            │  │
│  │  (vectorize.c)                    │  │
│  │  - 向量化可行性分析               │  │
│  │  - 标量→SIMD提升                  │  │
│  │  - 归约向量化                     │  │
│  │  - 残余循环处理                   │  │
│  └──────────┬─────────────────────────┘  │
│             ▼                            │
│  ┌────────────────────────────────────┐  │
│  │  Pass 4: 内存优化                  │  │
│  │  (memory_opt.c)                   │  │
│  │  - AoS→SoA转换                    │  │
│  │  - 数据对齐 (alignas)             │  │
│  │  - 预取指令插入                   │  │
│  │  - 缓存分块                       │  │
│  └──────────┬─────────────────────────┘  │
│             ▼                            │
│  ┌────────────────────────────────────┐  │
│  │  Pass 5: 标量优化                  │  │
│  │  (scalar_opt.c)                   │  │
│  │  - 常量折叠/传播                  │  │
│  │  - 死代码消除                     │  │
│  │  - 强度削减                       │  │
│  │  - 公共子表达式消除               │  │
│  └──────────┬─────────────────────────┘  │
└─────────────┼────────────────────────────┘
              │ 优化后IR
              ▼
┌──────────────┐
│  代码生成器   │  CodeGen: IR → 优化的C代码
│  (codegen.c) │  - SIMD intrinsics
└──────┬───────┘  - OpenMP hints (可选)
       │          - restrict/aligned指针
       ▼
  输出: 优化的C源文件(.c)
    → 可直接用gcc/clang编译

📝 输入语言 (.pc)

扩展C语言，增加并行原语：

#include <par2serial.h>

// parallel_for: 并行循环
parallel_for(i, 0, N) {
    C[i] = A[i] + B[i];
}

// parallel_reduce: 并行归约
float sum = 0;
parallel_reduce(sum, +, i, 0, N) {
    sum += A[i];
}

// parallel_scan: 并行前缀扫描
parallel_scan(prefix_sum, +, i, 0, N) {
    prefix_sum[i] = A[i];
}

// parallel_map: 对每个元素应用函数
parallel_map(B, A, N, func) {
    B[i] = func(A[i]);
}

// tile_hint: 分块提示
tile_hint(TILE_SIZE, 32);

// simd_hint: 向量化提示
simd_hint(AVX2);

// memory_layout: 内存布局提示
memory_layout(particles, SOA);  // AoS → SoA

⚡ 优化示例

输入: 并行矩阵乘法

parallel_for(i, 0, M) {
    parallel_for(j, 0, N) {
        float sum = 0;
        parallel_reduce(sum, +, k, 0, K) {
            sum += A[i*K+k] * B[k*N+j];
        }
        C[i*N+j] = sum;
    }
}

输出: 优化的串行代码 (带SIMD + 分块)

#include <immintrin.h>

// 分块矩阵乘法 + AVX向量化
for (int ii = 0; ii < M; ii += TILE_I) {
  for (int jj = 0; jj < N; jj += TILE_J) {
    for (int kk = 0; kk < K; kk += TILE_K) {
      for (int i = ii; i < ii+TILE_I && i < M; i++) {
        for (int j = jj; j < jj+TILE_J && j < N; j += 8) {
          __m256 vsum = _mm256_loadu_ps(&C[i*N+j]);
          for (int k = kk; k < kk+TILE_K && k < K; k++) {
            __m256 va = _mm256_broadcast_ss(&A[i*K+k]);
            __m256 vb = _mm256_loadu_ps(&B[k*N+j]);
            vsum = _mm256_fmadd_ps(va, vb, vsum);
          }
          _mm256_storeu_ps(&C[i*N+j], vsum);
        }
      }
    }
  }
}

🔧 构建与使用

# 构建编译器
make

# 编译并行程序为优化串行代码
./par2serial input.pc -o output.c

# 指定优化级别
./par2serial input.pc -o output.c -O2

# 指定目标SIMD指令集
./par2serial input.pc -o output.c --simd=avx2

# 查看优化报告
./par2serial input.pc -o output.c --report

# 编译生成的代码
gcc -O3 -mavx2 -mfma output.c -o program

优化级别

SIMD目标

📊 Benchmark结果

在典型并行算法上的性能对比（相对于朴素串行化的加速比）：

📁 项目结构

par2serial-cc/
├── src/
│   ├── main.c              # 编译器入口、命令行解析
│   ├── lexer.h / lexer.c   # 词法分析器
│   ├── parser.h / parser.c # 语法分析器(递归下降)
│   ├── ast.h / ast.c       # 抽象语法树定义
│   ├── semantic.h/.c       # 语义分析
│   ├── ir.h / ir.c         # 中间表示(三地址码)
│   ├── parallel_detect.h/.c # 并行模式检测
│   ├── loop_opt.h/.c       # 循环优化
│   ├── vectorize.h/.c      # SIMD自动向量化
│   ├── memory_opt.h/.c     # 内存布局优化
│   ├── scalar_opt.h/.c     # 标量优化
│   ├── codegen.h/.c        # C代码生成
│   └── utils.h / utils.c   # 工具函数
├── include/
│   └── par2serial.h        # 用户头文件(并行原语定义)
├── tests/
│   ├── test_matmul.pc      # 矩阵乘法测试
│   ├── test_reduce.pc      # 归约测试
│   ├── test_stencil.pc     # Stencil计算测试
│   ├── test_scan.pc        # 前缀扫描测试
│   └── benchmark.sh        # 性能测试脚本
├── examples/
│   ├── matmul.pc           # 矩阵乘法示例
│   ├── nbody.pc            # N-body模拟示例
│   └── convolution.pc      # 卷积示例
├── Makefile
└── README.md

🧠 技术原理

并行→串行核心转换策略

1. parallel_for → 串行循环 + SIMD

   • 去除线程分配开销
   • 检测数据依赖，决定向量化策略
   • 无依赖循环直接SIMD化

2. parallel_reduce → 向量化归约

   • 展开为SIMD宽度的部分和
   • 最后做水平归约
   • 比朴素串行循环快4-8倍(AVX2)

3. parallel_scan → Blelloch串行实现

   • 利用缓存局部性的串行前缀和
   • 结合SIMD加速

4. barrier/同步 → 消除

   • 串行执行天然有序
   • 安全消除所有同步原语

5. 共享内存 → 寄存器/栈提升

   • 小数组提升到栈
   • 频繁访问标量提升到寄存器

License

MIT License