基于分布式图计算的大规模程序静态分析算法与系统
发布时间：2021-01-06 05:36
程序静态分析技术被广泛应用于计算机程序设计与开发的诸多环节,包括错误检测、代码优化、测试等。基于CFL（Context-Free Language）可达的过程间程序静态分析是一种具有较高通用意义的过程间静态分析方法,该方法本质上是一种图的可达性计算问题。尽管程序静态分析方面的研究取得了很多进展,但是由于硬件资源和传统方法的限制,单机计算已难以支撑日益增长大规模图数据的高效处理,从而导致了静态分析方法的性能低效且可扩展性较低。因此对大规模现代软件进行复杂的过程间分析仍然具有挑战性。针对大规模程序静态分析性能低效和可扩展性低的问题,本文提出了一种基于分布式图计算模型的高效可扩展的并行化大规模程序静态分析方法,并设计实现了高效可扩展的分布式大规模程序静态分析系统。本文的主要研究工作和贡献点如下:（1）将基于CFL可达的程序静态分析问题抽象为大规模图计算问题,基于数据并行框架研究设计了一种新型的并行化传递闭包算法和Join-Process-Filter计算模型,基于该算法和计算模型,设计实现了一个分布式离线全量程序静态分析系统,分别提出了算法级和系统级优化,并设计了具有压缩效果的数据结构。（2...
【文章来源】：南京大学江苏省 211工程院校 985工程院校 教育部直属院校
【文章页数】：87 页
【学位级别】：硕士
【部分图文】：
图２－３?Ｓｐａｒｋ生态系统组件??
第三章离线全量程序静态分析方法与并行化算法??用图的形式表达可达关系传递规则，则图中的边即为可达关系的体现。传递??闭包公式３－１分别对应图３－１中可达关系的三种传递方式，其中ｘ?＝?ｙ上ｚ即为一??组边对。??匚?ｃ／ｌ?＜Ａ?３??＾?ｃ??ａ）?ｅ?ｓ?ｂ）?Ｃ?ｃ／Ｚ?ｃ）?Ｃ?ｃ／Ｚ?乃??图３－１可达关系传递规则的图表现形式??边对模型的提出，为数据并行化算法设计提供了有利条件：将边对以中间节??点（节点ｙ即是边对ｘ＾ｙ三ｚ的中间节点）为核心进行存储，由于产生式的右部??不超过两个符号，中间节点通过对入边（ｉｎｃｏｍｉｎｇｅｄｇｅ）和出边（ｏｕｔｇｏｉｎｇｅｄｇｅ）??的收集，可以独立完成可达关系的传递，不必依赖别的节点的计算结果，因此可??以并行化执行每个中间节点的标签匹配任务，即多个中间节点同时对自己的“左??邻右舍”进行符合产生式的可达关系传递。??３．１．２?串行?Ｗｏｒｋｌｉｓｔ?算法??从３．１．１节可达关系的传递方式可以看出，传递闭包是动态更新的，每次向??传递闭包中添加可达关系，都有可能触发新的可达关系的生成，这是一个迭代更??新的过程。??Ｗｏｒｋｌｉｓｔ算法是一种基于搜索的可达性计算的算法［２２］［３６］。它的主要工作流??程如下：使用ｗｏｒｋｌｉｓｔ存储计算中的顶点和以它为终点的路径信息
顶点和目标顶点进行分区，即通过对边的复制，解除中间节点的边集共享问题。??这样做可以使边同时完成双向的路径传递，实现标签匹配操作的并行化。复制操??作如图３－２所示：??ＡＢＣ??？?，?＾??ｘ?ｙ?ｚ?ｗ??复制ｙ－＞ｚ??ａ?Ｂ?２?￣?ｅ?▲??？?＾＾??Ｘ?ｙ?ｚ?ｙ?Ｚ?Ｗ??图３－２通过复制解除中间节点的依赖关系??具有相同源或目标顶点（键）的边被放在与图３－４框中矩形相对应的相同分??区中。分区内部计算是并行执行的，提高了并行效率和资源利用率。??ｊｏｉｎ和ｆｉｌｔｅｒ操作的并行化基于上述分区完成。??３．２．２数据结构设计??分区中边集（包括待计算边集ＩＶ和原传递闭包ＴＣ的边）被处理为以顶点为??键，与顶点相连的边集为值的ｋｅｙ－ｖａｌｕｅ形式，这是离线系统实现中的基本数据??结构。需要注意的是，为了算法能及时收敛和避免冗余计算，每个键值对中，只??１９??
本文编号：2960022
【文章来源】：南京大学江苏省 211工程院校 985工程院校 教育部直属院校
【文章页数】：87 页
【学位级别】：硕士
【部分图文】：
图２－３?Ｓｐａｒｋ生态系统组件??
第三章离线全量程序静态分析方法与并行化算法??用图的形式表达可达关系传递规则，则图中的边即为可达关系的体现。传递??闭包公式３－１分别对应图３－１中可达关系的三种传递方式，其中ｘ?＝?ｙ上ｚ即为一??组边对。??匚?ｃ／ｌ?＜Ａ?３??＾?ｃ??ａ）?ｅ?ｓ?ｂ）?Ｃ?ｃ／Ｚ?ｃ）?Ｃ?ｃ／Ｚ?乃??图３－１可达关系传递规则的图表现形式??边对模型的提出，为数据并行化算法设计提供了有利条件：将边对以中间节??点（节点ｙ即是边对ｘ＾ｙ三ｚ的中间节点）为核心进行存储，由于产生式的右部??不超过两个符号，中间节点通过对入边（ｉｎｃｏｍｉｎｇｅｄｇｅ）和出边（ｏｕｔｇｏｉｎｇｅｄｇｅ）??的收集，可以独立完成可达关系的传递，不必依赖别的节点的计算结果，因此可??以并行化执行每个中间节点的标签匹配任务，即多个中间节点同时对自己的“左??邻右舍”进行符合产生式的可达关系传递。??３．１．２?串行?Ｗｏｒｋｌｉｓｔ?算法??从３．１．１节可达关系的传递方式可以看出，传递闭包是动态更新的，每次向??传递闭包中添加可达关系，都有可能触发新的可达关系的生成，这是一个迭代更??新的过程。??Ｗｏｒｋｌｉｓｔ算法是一种基于搜索的可达性计算的算法［２２］［３６］。它的主要工作流??程如下：使用ｗｏｒｋｌｉｓｔ存储计算中的顶点和以它为终点的路径信息
顶点和目标顶点进行分区，即通过对边的复制，解除中间节点的边集共享问题。??这样做可以使边同时完成双向的路径传递，实现标签匹配操作的并行化。复制操??作如图３－２所示：??ＡＢＣ??？?，?＾??ｘ?ｙ?ｚ?ｗ??复制ｙ－＞ｚ??ａ?Ｂ?２?￣?ｅ?▲??？?＾＾??Ｘ?ｙ?ｚ?ｙ?Ｚ?Ｗ??图３－２通过复制解除中间节点的依赖关系??具有相同源或目标顶点（键）的边被放在与图３－４框中矩形相对应的相同分??区中。分区内部计算是并行执行的，提高了并行效率和资源利用率。??ｊｏｉｎ和ｆｉｌｔｅｒ操作的并行化基于上述分区完成。??３．２．２数据结构设计??分区中边集（包括待计算边集ＩＶ和原传递闭包ＴＣ的边）被处理为以顶点为??键，与顶点相连的边集为值的ｋｅｙ－ｖａｌｕｅ形式，这是离线系统实现中的基本数据??结构。需要注意的是，为了算法能及时收敛和避免冗余计算，每个键值对中，只??１９??
本文编号：2960022
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2960022.html
