基于SDFG的控制流模型到数据流模型的程序转换方法

doi:10.19678/j.issn.1000-3428.0252315

计算机工程 ›› 2026, Vol. 52 ›› Issue (8): 193-202. doi: 10.19678/j.issn.1000-3428.0252315

基于SDFG的控制流模型到数据流模型的程序转换方法

付佳伟*(), 陈俊仕, 安虹

中国科学技术大学计算机科学与技术学院, 安徽合肥 230026

收稿日期:2025-04-11 修回日期:2025-06-05 出版日期:2026-08-15 发布日期:2025-07-22
通讯作者: 付佳伟
作者简介:
付佳伟(CCF学生会员), 男, 硕士研究生, 主研方向为并行编程模型、编译器设计
陈俊仕(CCF会员), 研究员、博士
安虹(CCF会员), 教授、博士
基金资助:
中国科学院战略性先导科技专项(XDB0500102)

Program Transpilation Method from Control Flow Model to Dataflow Model Based on SDFG

FU Jiawei*(), CHEN Junshi, AN Hong

School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, Anhui, China

Received:2025-04-11 Revised:2025-06-05 Online:2026-08-15 Published:2025-07-22
Contact: FU Jiawei

摘要/Abstract

摘要：

数据流编程是一种新型的并行编程范式, 其通过细粒度的任务拆分实现高性能的并行计算, 但也带来了额外的编程复杂性。本文提出一种新型的程序转换方法与编译流程, 借助两层程序中间表示实现了将控制流结构的计算程序全自动无缝转换为数据流结构。由于两种编程模型在程序的表达方式上具有诸多差异, 自动化转换过程中面临许多挑战, 本文将其细化为4个具体的类别, 并逐一提出应对方案。在PolyBench/C数据集上的实验结果表明, 通过本文设计的转换方案产生的数据流程序, 其整体并行计算性能接近基于有状态数据流多重图(SDFG)的OpenMP并行化方案, 并在近一半的样例中超越OpenMP方案。本文还选择了多个具体的程序进行深入分析, 讨论了不同编译方案产生的结果存在性能差异的原因, 展现了Codelet模型在大量线程下面对不规则并行模式的优越性。

关键词: 数据流编程, Codelet模型, 有状态数据流多重图, 程序转换, 源到源翻译器

Abstract:

Dataflow programming is an emerging parallel-programming paradigm. By splitting tasks into fine granularities, high-performance parallel computing can be achieved at the expense of increased programming complexity. This study proposes a new program transpilation method and compilation procedure that leverages two levels of intermediate representation and converts control flow computational programs into a dataflow architecture in a fully automatic manner. Owing to the substantial disparities between these programming models, many challenges exist in automatic conversion schemes, which are split into four categories and addressed separately. Experimental results on the PolyBench/C dataset indicate that the proposed conversion scheme can produce dataflow parallel programs on par with those produced by the Stateful DataFlow multiGraph (SDFG)-based OpenMP parallelizing compiler while surpassing it in approximately half of the cases. This study also conducts case studies on multiple program samples and discusses the causes of performance distinctions in different compilation schemes, revealing the superiority of the Codelet model with a massive number of threads on irregular parallelism.

Key words: dataflow programming, Codelet model, Stateful DataFlow multiGraph (SDFG), program transpilation, source-to-source compiler

付佳伟, 陈俊仕, 安虹. 基于SDFG的控制流模型到数据流模型的程序转换方法[J]. 计算机工程, 2026, 52(8): 193-202.

FU Jiawei, CHEN Junshi, AN Hong. Program Transpilation Method from Control Flow Model to Dataflow Model Based on SDFG[J]. Computer Engineering, 2026, 52(8): 193-202.

https://www.ecice06.com/CN/Y2026/V52/I8/193

图/表 8

图1 Codelet执行模型

Fig.1 The Codelet execution model

图2 SDFG模型中的Laplace迭代算法

Fig.2 Iterative Laplace algorithm in SDFG model

图3 完整的编译与转换流程

Fig.3 Complete compilation and transpilation procedure

图4 参与评测的编译方案

Fig.4 Compilation schemes compared

图5 DARTS方案相对于SDFG方案在21个程序中的加速比

Fig.5 Acceleration ratio of DARTS over SDFG in 21 programs

参考文献 25

1	LUNDSTROM M S , ALAM M A . Moore's law: the journey ahead. Science, 2022, 378 (6621): 722- 723. doi: 10.1126/science.ade2191
2	LEE E A . The problem with threads. Computer, 2006, 39 (5): 33- 42.
3	GROPP W , LUSK E , DOSS N , et al. A high-performance, portable implementation of the MPI message passing interface standard. Parallel Computing, 1996, 22 (6): 789- 828. doi: 10.1016/0167-8191(96)00024-5
4	DAGUM L , MENON R . OpenMP: an industry standard API for shared-memory programming. IEEE Computational Science and Engineering, 1998, 5 (1): 46- 55. doi: 10.1109/99.660313
5	SANDERS J , KANDROT E , SANDERS J , et al. CUDA by example: an introduction to general purpose GPU programming. Boston, USA: Addison-Wesley Professional, 2010.
6	STONE J E , GOHARA D , SHI G C . OpenCL: a parallel programming standard for heterogeneous computing systems. Computing in Science & Engineering, 2010, 12 (3): 66- 73.
7	DENNIS J B . Data flow supercomputers. Computer, 1980, 13 (11): 48- 56.
8	FLYNN M J . Some computer organizations and their effectiveness. IEEE Transactions on Computers, 1972, 100 (9): 948- 960.
9	JOHNSTON W M , PAUL H J R , MILLAR R J . Advances in dataflow programming languages. ACM Computing Surveys, 2004, 36 (1): 1- 34. doi: 10.1145/1013208.1013209
10	OVIEDO E I. Control flow, data flow and program complexity[D]. Buffalo, USA: State University of New York at Buffalo, 1984.
11	BAUER M, TREICHLER S, SLAUGHTER E, et al. Legion: expressing locality and independence with logical regions[C]//Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. New York, USA: ACM Press, 2012: 1-11.
12	PHEATT C . Intel threading building blocks. Journal of Computing Sciences in Colleges, 2008, 23 (4): 298.
13	GRAY A L. CUDA graphs: flexible dependency representation for efficient GPU work submission[EB/OL]. [2025-01-10]. https://developer.nvidia.com/blog/cuda-graphs.
14	BEN-NUN T, FINE L J, ZIOGAS A N, et al. Stateful dataflow multigraphs: a data-centric model for performance portability on heterogeneous architectures[C]//Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. New York, USA: ACM Press, 2019: 1-14.
15	LATTNER C, AMINI M, BONDHUGULA U, et al. MLIR: scaling compiler infrastructure for domain specific computation[C]// Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization (CGO). Seoul, Korea: IEEE Press, 2021: 2-14.
16	BEN-NUN T, ATES B, CALOTOIU A, et al. Bridging control-centric and data-centric optimization[C]//Proceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization. New York, USA: ACM Press, 2023: 173-185.
17	SUETTLERLEIN J, ZUCKERMAN S, GAO G R. An implementation of the Codelet model[C]//Proceedings of Euro-Par 2013. Berlin, Germany: Springer, 2013: 633-644.
18	SUETTERLEIN J. DARTS: a runtime based on the Codelet execution model[D]. Newark, USA: University of Delaware, 2014.
19	YUKI T, POUCHET L N. PolyBench 4.2.1 (pre-release)[EB/OL]. [2025-01-10]. https://github.com/MatthiasJReisinger/PolyBenchC-4.2.1/blob/master/polybench.pdf.
20	MOSES W S, CHELINI L, ZHAO R Z, et al. Polygeist: raising C to polyhedral MLIR[C]//Proceedings of the 30th International Conference on Parallel Architectures and Compilation Techniques (PACT). Atlanta, USA: IEEE Press, 2021: 45-59.
21	flamegraphs for Rust[EB/OL]. [2025-01-10]. https://github.com/flamegraph-rs/flamegraph.
22	CHEN L , TANG S L , FU Y , et al. AceMesh: a structured data driven programming language for high performance computing. CCF Transactions on High Performance Computing, 2020, 2 (4): 309- 322. doi: 10.1007/s42514-020-00047-4
23	BOSILCA G , BOUTEILLER A , DANALIS A , et al. PaRSEC: exploiting heterogeneity to enhance scalability. Computing in Science & Engineering, 2013, 15 (6): 36- 45.
24	KABRICK R, PERDOMO D A R, RASKAR S, et al. CODIR: towards an MLIR codelet model dialect[C]// Proceedings of the 4th Annual Workshop on Emerging Parallel and Distributed Runtime Systems and Middleware (IPDRM). Washington D. C., USA: IEEE Press, 2020: 33-40.
25	李金熹, 尹首一, 魏少军, 等. 基于MLIR的数据流模型. 计算机工程与科学, 2024, 46 (7): 1151- 1157.
	LI J X , YIN S Y , WEI S J , et al. A codelet model based on MLIR. Computer Engineering and Science, 2024, 46 (7): 1151- 1157.

[1]	熊军军. Informix向Oracle迁移的关键技术研究[J]. 计算机工程, 2012, 38(14): 52-55.
[2]	秦青文;王戟;孙旭光;梅文华. 基于IDA-Pro的软件逆向分析方法[J]. 计算机工程, 2008, 34(22): 86-88.

选择文件类型/文献管理软件名称

选择包含的内容

基于SDFG的控制流模型到数据流模型的程序转换方法

Program Transpilation Method from Control Flow Model to Dataflow Model Based on SDFG

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 25

相关文章 2

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于SDFG的控制流模型到数据流模型的程序转换方法

Program Transpilation Method from Control Flow Model to Dataflow Model Based on SDFG

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 25

相关文章 2

编辑推荐

Metrics

本文评价