这篇文档属于类型a，即报告了一项原创性研究。以下是针对该研究的学术报告：

共享内存多核架构上可扩展的非结构化网格计算研究

一、作者与发表信息

本研究由Haozhong Qiu（国防科技大学计算机科学与技术学院）、Chuanfu Xu（国防科技大学前沿装备数字化软件实验室）等多名作者合作完成，团队成员还包括来自中国空气动力研究与发展中心的Liang Deng、Jian Zhang等。该论文发表于PPoPP ‘24（ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming），会议时间为2024年3月2日至6日，地点为英国爱丁堡。

二、学术背景

研究领域：
本研究属于高性能计算（High Performance Computing, HPC）领域，聚焦于非结构化网格（unstructured mesh）计算在共享内存多核架构（shared memory many-cores）上的并行化优化。

研究动机：
非结构化网格计算（如计算流体力学CFD、结构力学、电磁学等）因数据冲突（data conflicts）和数据依赖性（data dependences）难以高效并行化。传统方法（如网格着色法mesh coloring、原子操作atomic operations）存在局限性：
1. 通用性不足：现有方法无法同时解决数据冲突和依赖性（如稀疏求解器中的Gauss-Seidel迭代）。
2. 扩展性差：随着多核处理器核心数增加，传统方法的同步开销和负载不均衡问题加剧。
3. 平台依赖性：多数方法仅适用于CPU或GPU单一架构。

研究目标：
提出一种通用、可扩展的共享内存并行化方法——任务依赖树（Task Dependency Tree, TDT），通过递归划分和重排序非结构化网格，显式暴露并行性并解决数据冲突与依赖性。

三、研究流程与方法

1. TDT构建算法

输入：非结构化网格（如CFD中的细胞、面、节点）、划分参数（partsize和numpart）。
步骤：
1. 递归划分网格：使用图划分工具（如METIS）将网格划分为numpart个子网格（sub-mesh）。
2. 构建隔离器（isolator）：标记共享面或节点的细胞，形成隔离子网格，确保子网格间无数据冲突。
3. 重排序网格元素：按子网格和隔离器重新编号细胞、面、节点，优化数据局部性。
4. 递归策略：
- 扁平递归（flat recursion）：所有子网格和隔离器继续划分，生成多级任务依赖树。
- 隔离器递归（isolator-only recursion）：仅递归划分隔离器，减少同步开销。

创新点：
- 动态任务粒度：通过partsize控制子网格大小，适配不同架构的缓存容量。
- 混合编程模型支持：支持OpenMP任务（CPU）和CUDA（GPU）等多种并行模型。

2. 并行化实现

• 树遍历策略：
  
  • 前向遍历（forward traversal）：并行执行子网格，同步后处理隔离器，解决数据冲突（如对流通量计算）。
    
  • 反向遍历（backward traversal）：先处理隔离器再并行子网格，满足稀疏求解器的反向依赖（如LU-SGS迭代）。
    
• API设计：提供tree_traversal接口，用户无需手动添加并行指令，仅需封装计算内核。
  

3. 实验验证

测试平台：
- CPU：Intel Xeon Gold 6258R、AMD EPYC 7742等4种多核处理器。
- GPU：NVIDIA Tesla V100。
测试用例：
- 工业级CFD软件：包含对流通量（convflux）、梯度重构（grad）和LU-SGS稀疏求解器（lusgs）三类核心。
- 网格数据：3种非结构化网格（如M6wing、CHN-T1），规模从370万至1700万细胞。

四、主要结果

1. 性能提升：

   • CPU：TDT-V1（扁平递归）最高提速8.1倍（vs. 传统Level-Scheduling），TDT-V2（隔离器递归）提速1.1–6.0倍。
     
   • GPU：TDT-V2在LU-SGS上提速3.4倍（vs. Level-Scheduling）。
     
   • 数据局部性优化：网格重排序使串行性能提升1.4–1.8倍。
     

2. 收敛性保持：

   • TDT严格保持LU-SGS的收敛性，而网格着色法导致收敛速度下降1.6倍（M6wing网格）。
     

3. 参数敏感性：

   • 最佳参数：partsize=256–512、numpart=4（CPU）或动态计算（GPU）。
     

五、结论与价值

科学价值：
1. 方法论创新：TDT首次通过递归划分和依赖树遍历统一解决数据冲突与依赖性，为非结构化计算提供通用并行框架。
2. 跨平台适配性：支持CPU/GPU混合编程模型，参数可调以适应不同架构。

应用价值：
- 工业CFD软件优化：已集成至中国空气动力研究与发展中心的NNW-FlowStar软件，显著提升仿真效率。
- 扩展潜力：可推广至图算法、稀疏计算等依赖冲突解决的领域。

六、研究亮点

1. 通用性与扩展性：TDT同时解决数据冲突和依赖性，且在28核CPU上仍保持线性加速。
   
2. 编程范式革新：用户无需手动并行化循环，通过API封装内核即可自动并行。
   
3. 收敛性保障：TDT严格保持稀疏求解器的数学特性，优于传统着色法。
   

七、其他价值

• 开源实现：TDT以独立库形式提供，支持参数调优和任务粒度动态调整。
  
• 预处理开销补偿：网格划分与重排序的预处理时间可通过大量CFD迭代分摊。
  

（全文约2000字）