数据并行程序正确性分析与网络流量优化
发布时间：2018-11-20 07:46
【摘要】：数据并行编程模型以其简单的特点在大数据计算领域获得了广泛的应用。但是，编写用户自定义函数的串行思维与实际的并行执行之间存在显著的差异，使得程序员容易忽略并行执行中的不确定性和通讯开销，并引入正确性与性能方面的问题。本文分别从这两方面问题入手，发现并改进了现有工作的不足。本文的主要工作包括： （1）针对并行执行不确定性引起的正确性问题，本文从上万个真实数据并行程序中提取了507个不同的Reduce函数并进行了人工分析，发现了大量并无正确性问题的不可交换Reduce函数，否定了现有工作关于不可交换Reduce函数必为程序缺陷的假设。此外，本文进一步发现了5种不可交换模式，以及部分模式依赖特定隐含数据性质保证确定性的特点。通过检查实际数据上的性质，本文成功发现了5个长期隐藏在产品环境中的真实程序缺陷，并讨论了改进现有测试方法的思路。 （2）本文提出了Cybertron，一种动静态结合的数据并行程序网络流量优化技术。通过结合静态程序分析结果和运行时动态信息，Cybertron克服了现有静态技术在处理实际程序中面临的限制，，通过在运行时精确跟踪给定运算对数据的使用情况，更细粒度地过滤无用数据，并使用数据约束编码的技术对数据进行更高效的编码。它在合理的运行时开销下显著提高了现有方法对数据并行程序网络流量的优化效果，并在各种网络环境下有效提高了程序性能。
[Abstract]:Data parallel programming model has been widely used in big data computing field because of its simple characteristics. However, there is a significant difference between the serial thinking of writing user-defined functions and the actual parallel execution, which makes it easy for programmers to ignore the uncertainty and communication overhead in parallel execution, and introduce the problems of correctness and performance. Starting with these two problems, this paper finds out and improves the shortcomings of the existing work. The main work of this paper includes: (1) aiming at the correctness problem caused by the uncertainty of parallel execution, we extract 507 different Reduce functions from tens of thousands of real data parallel programs and carry out manual analysis. A large number of non-commutative Reduce functions with no correctness problems are found, which negates the existing hypothesis that non-commutative Reduce functions must be program defects. In addition, five kinds of non-commutative patterns are further found, and some patterns depend on the nature of the specific implicit data to ensure certainty. By checking the properties of the actual data, this paper successfully finds five real program defects hidden in the product environment for a long time, and discusses the ideas of improving the existing testing methods. (2) in this paper, a dynamic and static data parallel program network traffic optimization technique based on Cybertron, is proposed. By combining the results of static program analysis and runtime dynamic information, Cybertron overcomes the limitations of existing static techniques in dealing with practical programs and accurately tracks the usage of data in given operations at run time. Filter useless data with finer granularity and use data constraint coding technology to encode data more efficiently. With reasonable runtime overhead, it can significantly improve the efficiency of the existing methods in optimizing the network traffic of data parallel programs, and improve the program performance in various network environments.
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TP311.1;TP393.06
[Abstract]:Data parallel programming model has been widely used in big data computing field because of its simple characteristics. However, there is a significant difference between the serial thinking of writing user-defined functions and the actual parallel execution, which makes it easy for programmers to ignore the uncertainty and communication overhead in parallel execution, and introduce the problems of correctness and performance. Starting with these two problems, this paper finds out and improves the shortcomings of the existing work. The main work of this paper includes: (1) aiming at the correctness problem caused by the uncertainty of parallel execution, we extract 507 different Reduce functions from tens of thousands of real data parallel programs and carry out manual analysis. A large number of non-commutative Reduce functions with no correctness problems are found, which negates the existing hypothesis that non-commutative Reduce functions must be program defects. In addition, five kinds of non-commutative patterns are further found, and some patterns depend on the nature of the specific implicit data to ensure certainty. By checking the properties of the actual data, this paper successfully finds five real program defects hidden in the product environment for a long time, and discusses the ideas of improving the existing testing methods. (2) in this paper, a dynamic and static data parallel program network traffic optimization technique based on Cybertron, is proposed. By combining the results of static program analysis and runtime dynamic information, Cybertron overcomes the limitations of existing static techniques in dealing with practical programs and accurately tracks the usage of data in given operations at run time. Filter useless data with finer granularity and use data constraint coding technology to encode data more efficiently. With reasonable runtime overhead, it can significantly improve the efficiency of the existing methods in optimizing the network traffic of data parallel programs, and improve the program performance in various network environments.
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TP311.1;TP393.06
【共引文献】
相关期刊论文 前10条
1 李冰雨;吕帅;何丽莉;;改进的基于逆向流分析的C程序切片算法[J];吉林大学学报(信息科学版);2014年01期
2 陈刚;;新能源发电并网控制策略研究[J];装备制造技术;2014年11期
3 龙庆;王t
本文编号：2344299
本文链接：https://www.wllwen.com/guanlilunwen/ydhl/2344299.html
