适用于商用系统环境的低开销确定性重放技术

doi:10.13229/j.cnki.jdxbgxb201701031

吉林大学学报(工学版) ›› 2017, Vol. 47 ›› Issue (1): 208-217.doi: 10.13229/j.cnki.jdxbgxb201701031

适用于商用系统环境的低开销确定性重放技术

应欢^{1, 2}, 王东辉¹, 武成岗³, 王喆^{2, 3}, 唐博文⁴, 李建军³

1.中国科学院声学研究所,北京 100190;
2.中国科学院大学,北京 100049;
3.中国科学院计算技术研究所,北京 100190;
4.首都师范大学信息工程学院,北京 100048

收稿日期:2015-09-12 出版日期:2017-01-20 发布日期:2017-01-20
通讯作者: 王东辉(1973-),男,教授,博士生导师.研究方向:VLSI信号处理.E-mail:wangdh@mail.ioa.ac.cn
作者简介:应欢 (1988-),女,博士研究生.研究方向:并行程序,动态优化.E-mail:yinghuan1022@126.com
基金资助:
“863”国家高技术研究发展计划项目 (2012AA010901).

Efficient deterministic replay technique on commodity system environment

YING Huan^{1, 2}, WANG Dong-hui¹, WU Cheng-gang³, WANG Zhe^{2, 3}, TANG Bo-wen⁴, LI Jian-jun³

1.Institute of Acoustics, Chinese Academy of Sciences, Beijing 100190, China;
2.University of Chinese Academy of Sciences, Beijing 100049, China;
3.Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China;
4. College of Information Engineering,Capital Normal University, Beijing 100048, China

Received:2015-09-12 Online:2017-01-20 Published:2017-01-20

摘要/Abstract

摘要： 针对现有确定性重放技术中存在运行时开销大和安全隐患等问题,提出了一种低开销的确定性重放技术。该技术在已有的硬件平台和系统环境下,利用页保护捕获并记录并行程序对共享内存的访问顺序。深入研究了该技术引入的性能开销,针对性地提出了私有锁、私有堆、主动抢占等优化策略。采用PARSEC测试集进行性能评估,实验结果显示该系统引入的开销较小。

关键词: 计算机软件, 并行程序, 确定性重放, 页保护

Abstract: Deterministic replay plays an important role in debugging parallel programs. In parallel program design, recording share memory access has become a light spot, according to great non-determinism brought by multithreading memory interleaving. Previous research focused on fine grained instrumentation of memory access instruction, or kernel modification, or special hardware extension to record shared memory communication. However, these methods have the problems of runtime overhead cost and awful potential safety hazard. This paper proposes an efficient deterministic replay technique employing page-protection mechanism on commodity hardware platforms and operating system. Furthermore, this work deeply analyzes the runtime overhead incurred by the proposed technique, and puts forward several optimization strategies of private-lock mechanism, private heap memory pool and initiative page-preemption algorithm to promote the performance. Our prototype UPLAY is implemented on Linux. Performance evaluation shows that the record slowdown is only 9.26X and is much smaller than prior user-level replay system.

Key words: computer software, parallel program, deterministic replay, page protection

中图分类号:

TP311

应欢, 王东辉, 武成岗, 王喆, 唐博文, 李建军. 适用于商用系统环境的低开销确定性重放技术[J]. 吉林大学学报(工学版), 2017, 47(1): 208-217.

YING Huan, WANG Dong-hui, WU Cheng-gang, WANG Zhe, TANG Bo-wen, LI Jian-jun. Efficient deterministic replay technique on commodity system environment[J]. 吉林大学学报(工学版), 2017, 47(1): 208-217.

参考文献

[1] Yuan Xiang, Wu Cheng-gang, Wang Zhen-jiang, et al. Reproducing concurrency bugs using local clocks[C]∥Proceedings of the 37th International Conference on Software Engineering, Florence, 2015:824-834.
[2] Lu Shan, Park S, Seo E, et al. Learning from mistakes-a comprehensive study on real world concurrency bug characteristics[C]∥Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems, Washington, 2008: 329-339.
[3] LeBlanc T J, Mellor-Crummey J M. Debugging parallel programs with instant replay[J]. IEEE Transactions on Computers, 1987,36(4): 471-482.
[4] Patil H, Pereira C, Stallcup M, et al. PinPlay: A framework for deterministic replay and reproducible analysis of parallel programs[C]∥Proceedings of the 8th annual IEEE/ACM International Symposium on Code Generation and Optimization, Toronto, 2010:2-11.
[5] Bhansali S, Chen Wen-Ke, Edwards A, et al. Framework for instruction-level tracing and analysis of program executions[C]∥Proceedings of the 2nd International Conference on Virtual Execution Environments, Ottawa, 2006:154-163.
[6] Laadan O, Viennot N, Nieh J. Transparent, lightweight application execution replay on commodity multiprocessor operating systems[C]∥Proceedings of the ACM Sigmetrics International Conference on Measurement and Modeling of Computer Systems, New York, 2010:155-166.
[7] Dunlap G W, Lucchetti D G, Fetterman M A, et al. Execution replay for multiprocessor virtual machines[C]∥Proceedings of the 4th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, Seattle, 2008:121-130.
[8] Wang Zhe, Li Jian-jun, Wu Cheng-gang, et al. HSPT: practical implementation and efficient management of embedded shadow page tables for cross-ISA system virtual machines[C]∥Proceedings of the 11th ACM Sigplan/Sigops International Conference on Virtual Execution Environments, Istanbul, 2015:53-64.
[9] CVE. URL http://www.cvedetails.com,2014-11-27.
[10] Liu Peng, Zhang Xiang-yu, Tripp O, et al. Light: replay via tightly bounded recording[C]∥Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, Portland, 2015:55-64.
[11] Park S, Zhou Yuan-yuan, Xiong Wei-wei, et al. PRES: Probabilistic replay with execution sketching on multiprocessors[C]∥Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles, BigSky, 2009:177-192.
[12] Jiang Yan-yan, Gu Tian-xiao, Xu Chang, et al. CARE: cache guided deterministic replay for concurrent Java programs[C]∥Proceedings of the 36th International Conference on Software Engineering, Hyderabad, 2014:457-467.
[13] Qian Xue-hai, Sahelices B, Qian De-pei. Pacifier: record and replay for relaxed-consistency multiprocessors with distributed directory protocol[C]∥Proceeding of the 41st Annual International Symposium on Computer Architecture, Minneapolis, 2014:433-444.
[14] Pokam G, Danne K, Pereira C, et al. QuickRec: prototyping an intel architecture extension for record and replay of multithreaded programs[C]∥Proceedings of the 40th Annual International Symposium on Computer Architecture, Tel Aviv, 2013:643-654.
[15] Honarmand N, Torrellas J. RelaxReplay: record and replay for relaxed-consistency multiprocessors[C]∥Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems, Salt Lake City, 2014:223-238.
[16] Honarmand N, Torrellas J. Replay debugging: Leveraging record and replay for program debugging[C]∥Proceeding of the 41st Annual International Symposium on Computer Architecture, Minneapolis, 2014:445-456.
[17] Ding Chen, Shen Xi-peng, Kelsey K, et al. Software behavior oriented parallelization[C]∥Proceedings of the 28th ACM Sigplan Conference on Programming Language Design and Implementation, San Diego, 2007:223-234.
[18] Bienia C, Kumar S, Singh J P, et al. The PARSEC benchmark suite: Characterization and architectural implications[C]∥Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques, Toronto, 2008:72-81.
[19] Chen Yu-fei, Chen Hai-bo. Scalable deterministic replay in a parallel full-system emulator[C]∥Proceedings of the 18th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming, Shenzhen, 2013:207-218.
[20] Kedia P. Efficient deterministic replay through dynamic binary translation[D].Delhi:Indian Institute of Technology Delhi, 2015.
[21] Liu Tongping,Curtsinger C,Berger E D.Dthreads:efficient deterministic multithreading[C]∥Proceedings of the 23rd ACM Symposium on Operating Systems Principles, Cascais, 2011:327-336.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

适用于商用系统环境的低开销确定性重放技术

Efficient deterministic replay technique on commodity system environment

RICH HTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10

[1]	应欢,刘松华,唐博文,韩丽芳,周亮. 基于自适应释放策略的低开销确定性重放方法[J]. 吉林大学学报(工学版), 2018, 48(6): 1917-1924.
[2]	马健, 樊建平, 刘峰, 李红辉. 面向对象软件系统演化模型[J]. 吉林大学学报(工学版), 2018, 48(2): 545-550.
[3]	罗养霞, 郭晔. 基于数据依赖特征的软件识别[J]. 吉林大学学报(工学版), 2017, 47(6): 1894-1902.
[4]	李勇, 黄志球, 王勇, 房丙午. 基于多源数据的跨项目软件缺陷预测[J]. 吉林大学学报(工学版), 2016, 46(6): 2034-2041.
[5]	王念滨, 祝官文, 周连科, 王红卫. 支持高效路径查询的数据空间索引方法[J]. 吉林大学学报(工学版), 2016, 46(3): 911-916.
[6]	特日跟, 江晟, 李雄飞, 李军. 基于整数数据的文档压缩编码方案[J]. 吉林大学学报(工学版), 2016, 46(1): 228-234.
[7]	康辉, 王家琦, 梅芳. 基于Pi演算的并行编程语言[J]. 吉林大学学报(工学版), 2016, 46(1): 235-241.
[8]	陈鹏飞, 田地, 杨光. 基于MVC架构的LIBS软件设计与实现[J]. 吉林大学学报(工学版), 2016, 46(1): 242-245.
[9]	刘磊, 王燕燕, 申春, 李玉祥, 刘雷. Bellman-Ford算法性能可移植的GPU并行优化[J]. 吉林大学学报(工学版), 2015, 45(5): 1559-1564.
[10]	冯晓宁, 王卓, 张旭. 基于L-π演算的WSN路由协议形式化方法[J]. 吉林大学学报(工学版), 2015, 45(5): 1565-1571.
[11]	李明哲, 王劲林, 陈晓, 陈君. 基于网络处理器的流媒体应用架构模型(VPL)[J]. 吉林大学学报(工学版), 2015, 45(5): 1572-1580.
[12]	王克朝, 王甜甜, 苏小红, 马培军. 基于频繁闭合序列模式挖掘的学生程序雷同检测[J]. 吉林大学学报(工学版), 2015, 45(4): 1260-1265.
[13]	黄宏涛，王静，叶海智，黄少滨. 基于惰性切片的线性时态逻辑性质验证[J]. 吉林大学学报(工学版), 2015, 45(1): 245-251.
[14]	范大娟^{1, 2}, 黄志球¹, 肖芳雄¹, 祝义¹, 王进¹. 面向多服务交互的相容性分析与适配器生成[J]. 吉林大学学报(工学版), 2014, 44(4): 1094-1103.
[15]	贺秦禄¹, 李战怀¹, 王乐晓¹, 王瑞². 云存储系统聚合带宽测试技术[J]. 吉林大学学报(工学版), 2014, 44(4): 1104-1111.