基于llvm的c程序的动态数据依赖分析工具的设计与实现

《基于llvm的c程序的动态数据依赖分析工具的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于LLVM的C程序的动态数据依赖分析工具的设计与实现第1章绪论1.1研究背景及意义现今的时代是计算机的时代，而多核处理器的到来则对计算机产业带来了巨大的挑战如何实行程序并行化，数以亿计的串行代码需要在多核处理器上高效运行，毋庸置疑是一项艰巨的任务，通过数十年的研究表明，实现串行代码并行化这一过程主要有两种形式：第一种是程序员手工改写串行代码成为并行版本，显然这也是消耗巨大工作两的代名词，其中最主要的手工改写并形化代码的方法是在并行化编程模型的基础上凭借改写或添加编译制导语句、语言扩展以及调用库函数，进行相应的串行代码的改写。该方法的优点是并行化的程序性能极高，但是相应的也有致命的缺点则是工

2、作量过于繁重，错误率高。由于过重的工作量导致程序员无法保证实现并行化后的程序其运行结果能否与串行程序一致，并且在实现并行化后会频繁出现死锁、数据竞争等错误。第二种则是利用编译器来实现自动并行化,这是程序自动并行化的一个很好的开端，并且现今也存在很多的静态分析方法，来实现串行程序的自动并行化，其主要优点是将忽略工作繁重这一问题，但是在实际应用中其效果可见一斑，主要原因在于程序中含有大量的指针引用、繁杂的控制流关系以及输入、输出相关依赖关系等因素，导致运用此种方法实现的并行化过于保守，从而丧失很多的并行性。近年来，国内外计算机领域，数据依赖分析技术得到越来越多的关注，同时它也成为自动检测并行化的

3、主要标志，它的应用不仅实现了对串行代码进行并行化，而且对程序后期的调试与检测也带来方便。依赖分析技术从实现角度进行分类可分为两种，即静态依赖分析技术和动态依赖分析技术。静态依赖分析技术与动态依赖分析技术分别是在编译时以及运行时两种时态下进行，各有春秋同时还可以相辅相成。就目前而言现存居多的都是静态数据依赖的相关分析算法，但是这些传统的依赖分析技术都存在不足或者局限，其在Fortran程序中颇有成就，但是对于类C语言的程序，则有一定的限制，对于一些不规则的程序静态分析无法准确进行分析并且也受限于当前的别名以及形状分析等技术，从而造成引入很多的伪依赖的可能并且在各个领域中都过多的程序都依赖指针，

4、因此只采用静态技术进行依赖分析效果明显不好。.........1.2依赖分析技术的国内外研究现状依赖分析技术成为当今研究程序并行化的主流技术，国内外许多学者都对此进行了相关学习及研究，并没有一个统一的标准来说明如何实现依赖分析，但是这些研究人员都通过运用静态依赖分析技术和动态依赖分析技术来实现对循环体的数据依赖的检测、实现类间依赖关系以及数据库间数据的依赖关系等等功能。高念书等人[1]提出并实现了一个实用、有效的数据依赖分析方案，此方案打破传统依赖测试算法中循环正规化的前提，采用对数组下标分类，并且根据不同类别的不同特点来决定合适的测试方法。并且此方法在PORT上得到验证和实现，PORT的并

5、行识别率以及加速比优于SGI上的PFA的并行编译。张艳梅等人[2]提出了一种基于动态依赖关系的类集成测试方法，并开发实现了基于测试集的类测试序列自动生成工具TLOG。在此方法的提出过程中，首先分析类间的静态依赖关系以及动态依赖关系，其次在力保测试桩数目较少前提下，设计算法消除由于静态依赖和动态依赖所形成的的环路。其中主要解决两个问题：静态以及动态依赖关系构成的环路中边删除的规则问题以及类测试顺序分配策略问题。曾扬[3]针对串行程序间的数据依赖关系，提出了两种新的数据依赖关系的分析方法系数判别法和实分析法。两种方法根据不同的场景分别提供相应的数据依赖分析，为串行程序并行化提供良好的理论基础。其

6、中系数判别法借助于GCD方法，不仅给出数组间准确的依赖关系，而且可以提供相应的依赖方向；实分析法则是巧妙的解决了CoupledSubscripts以及隐关系的分析问题。.......第2章相关技术介绍2.1依赖分析相关研究依赖关系是在一个程序中，若事件(或动作)B发生前，，若事件(或动作)A必须发生，则称B依赖与A[8]。依赖性是程序中语句间的偏序关系，它阐明了保持程序语义所需要的固有次序[9]，根据现今的研究情况，依赖关系主要分为数据依赖关系和控制依赖关系两类，其中数据依赖关系是在程序执行的中，同一地址被多次访问，其中至少存在一个写操作，其主要是由于对同一数据进行读/写操作而引起，这种数据

7、依赖关系是当下影响串行程序并行化尤为重要的因素。在依赖分析的过程中，主要关注数据依赖关系，这不仅是为程序并行化提供良好依据，更是计算机领域现今的研究热点。......2.2传统的依赖分析技术传统的数据依赖测试方法能够有效、快速的解决我们日常简单并且常见的数据依赖关系，通过对其进行相应的处理，则可高效准确地解决程序中的依赖关系，从而为程序并行化提供帮助。但是数据依赖问题是整数线性规划问题，故一般情况下，很难找到