基于LLVM中间表示的数据依赖并行计算方法

发布时间：2021-11-09 19:14

　　底层虚拟机（LLVM）是一个广泛使用的编译框架,其中间表示（IR）中包含有丰富的程序分析信息,众多以LLVM为平台的相关工作均以IR为基础开展。数据依赖关系在错误检测、定位及程序调试等领域有着重要应用,基于IR的数据依赖关系计算多采用串行迭代方式,但在应对较大规模IR文件时可扩展性不够理想。对此进行了数据依赖关系计算中指令读写的可并行性挖掘,结合图形处理器并行计算优势,提出一种基于LLVM IR的数据依赖关系并行计算方法 DRPC。以IR为输入,采用CPU-GPU双端协同方式实现程序数据依赖关系的高效计算。实验结果表明,针对基准程序集SPEC,DRPC分别在直接及传递数据依赖关系计算上最高获得了3. 48x和4. 91x的加速比。 

【文章来源】：计算机应用研究. 2020,37(02)北大核心CSCD

【文章页数】：6 页

【部分图文】：

加速比数据

图2给出了LLVM编译框架的构成，主要包含前端、优化器及后端三个部分。LLVM自定义的中间表示IR是该框架的重要组成部分。IR不仅是LLVM优化及后端相关工作的基础，也是基于LLVM程序分析的各种应用的主要输入。IR一般有可读汇编形式、二进制码形式及内存中间表示形式。LLVM IR内容文本通常以指令集形式提供包含函数声明、基本块、变量声明及函数调用等在内的各项程序分析信息。LLVM典型的指令集类别包括内存访问指令、终端指令、二进制指令、按位二进制指令以及其他指令等。在图1(b)中给出了图1(a)所示代码片段的IR文本内容示例。

本文主要围绕三个影响数据依赖并行计算的可扩展性问题，即非规则存取带来的带宽资源浪费问题、CPU-GPU双端的高效协同问题、线程不同步破坏传递数据依赖计算的动态性问题，提出基于LLVM IR的数据依赖关系并行计算框架(data dependence relation parallel computation framework,DRPC)。如图3所示，主要由IR特征指令匹配及信息提取(Pre＿Match＿Extract)、数据适配存储映射(Info＿Storage)、直接依赖关系计算(Direct＿DepCal)、传递依赖关系计算(Trans＿DepCal)和并行优化(Parallel＿Opt)及数据依赖关系应用输出(Dep Output＿for App)几个部分组成。其中，Pre＿Match＿Extract主要负责基于特征制导的关键指令匹配及相关程序分析信息的提取;Info＿Storage主要负责根据直接依赖关系及传递依赖关系计算需要，实现CPU端及GPU端的数据信息映射;Pre＿Match＿Extract和Info＿Storage是DRPC的基础性组成。在适应性数据映射完成后，由Direct＿DepCal和Trans＿DepCal共同负责完成各类数据依赖关系的并行计算。其中，Direct＿DepCal主要负责直接数据依赖关系的并行计算，Trans＿DepCal负责在直接数据依赖关系计算完成的基础上继续完成传递数据依赖关系的并行计算。在数据依赖关系的并行计算过程中，Parallel＿Opt会负责实施进一步的性能优化，最后由Dep Output＿forApp根据后续应用需求对数据依赖关系进行组织和输出。同时，本文使用CUDA作为DRPC的GPU并行计算环境。CUDA的线程模型被划分为线程格(grid)、线程块(block)以及线程(thread)三个层次。每个线程格内包含一定数量的线程块，每个线程块内包含一定数量的线程，并且每个线程、线程块和线程格都有编号。相同线程块中的线程可访问同一个共享内存区域，所有线程都可以访问全局内存。在进行数据依赖关系计算时，DRPC将待计算数据按线程数量划分，并利用线程编号进行数据索引，让多个线程同时进行数据依赖关系计算。

【参考文献】：
期刊论文
[1]软件漏洞静态检测模型及检测框架[J]. 王涛,韩兰胜,付才,邹德清,刘铭.  计算机科学. 2016(05)
[2]软件错误自动定位关键科学问题及研究进展[J]. 王克朝,王甜甜,苏小红,马培军.  计算机学报. 2015(11)
[3]一种基于异常传播分析的依赖性分析方法[J]. 姜淑娟,徐宝文,史亮,周晓宇.  软件学报. 2007(04)
[4]实用数据依赖分析方法[J]. 高念书,张兆庆,乔如良.  计算机学报. 1995(04)

硕士论文
[1]基于LLVM的C程序的动态数据依赖分析工具的设计与实现[D]. 吴忧.吉林大学 2016



本文编号：3485916