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

• Orginal Article • Previous Articles     Next Articles

Efficient deterministic replay technique on commodity system environment

YING Huan1, 2, WANG Dong-hui1, WU Cheng-gang3, WANG Zhe2, 3, TANG Bo-wen4, LI Jian-jun3   

  1. 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: 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

CLC Number: 

  • TP311
[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.
[1] YING Huan,LIU Song-hua,TANG Bo-wen,HAN Li-fang,ZHOU Liang. Efficient deterministic replay technique based on adaptive release strategy [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1917-1924.
[2] MA Jian, FAN Jian-ping, LIU Feng, LI Hong-hui. The evolution model of objective-oriented software system [J]. 吉林大学学报(工学版), 2018, 48(2): 545-550.
[3] LUO Yang-xia, GUO Ye. Software recognition based on features of data dependency [J]. 吉林大学学报(工学版), 2017, 47(6): 1894-1902.
[4] LI Yong, HUANG Zhi-qiu, WANG Yong, FANG Bing-wu. New approach of cross-project defect prediction based on multi-source data [J]. 吉林大学学报(工学版), 2016, 46(6): 2034-2041.
[5] WANG Nian-bin, ZHU Guan-wen, ZHOU Lian-ke, WANG Hong-wei. Novel dataspace index for efficient processing of path query [J]. 吉林大学学报(工学版), 2016, 46(3): 911-916.
[6] TE Ri-gen, JIANG Sheng, LI Xiong-fei, LI Jun. Document compression scheme based on integer data [J]. 吉林大学学报(工学版), 2016, 46(1): 228-234.
[7] KANG Hui, WANG Jia-qi, MEI Fang. A parallel programming language based on Pi-calculus [J]. 吉林大学学报(工学版), 2016, 46(1): 235-241.
[8] CHEN Peng-fei, TIAN Di, YANG Guang. Design and implementation of LIBS software based on MVC architecture [J]. 吉林大学学报(工学版), 2016, 46(1): 242-245.
[9] LIU Lei, WANG Yan-yan, SHEN Chun, LI Yu-xiang, LIU Lei. Performance portable GPU parallel optimization technique on Bellman-Ford algorithm [J]. 吉林大学学报(工学版), 2015, 45(5): 1559-1564.
[10] FENG Xiao-ning, WANG Zhuo, ZHANG Xu. Formal method for routing protocol of WSN based on L-π calculus [J]. 吉林大学学报(工学版), 2015, 45(5): 1565-1571.
[11] LI Ming-zhe, WANG Jin-lin, CHEN Xiao, CHEN Jun. Architecture model of streaming media applications on network processors(VPL) [J]. 吉林大学学报(工学版), 2015, 45(5): 1572-1580.
[12] WANG Ke-chao, WANG Tian-tian, SU Xiao-hong, MA Pei-jun. Plagiarism detection in student programs based on frequent closed sequence mining [J]. 吉林大学学报(工学版), 2015, 45(4): 1260-1265.
[13] HUANG Hong-tao,WANG Jing,YE Hai-zhi,HUANG Shao-bin. Lazy slicing based method for verifying linear temporal logic property [J]. 吉林大学学报(工学版), 2015, 45(1): 245-251.
[14] FAN Da-juan, HUANG Zhi-qiu, XIAO Fang-xiong, ZHU Yi, WANG Jin. Compatibility analysis and adaptor generation for multi-service interaction [J]. 吉林大学学报(工学版), 2014, 44(4): 1094-1103.
[15] HE Qin-lu, LI Zhan-huai, WANG Le-xiao, WANG Rui. Testing technology for aggregate bandwidth of cloud storage system [J]. 吉林大学学报(工学版), 2014, 44(4): 1104-1111.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LIU Song-shan, WANG Qing-nian, WANG Wei-hua, LIN Xin. Influence of inertial mass on damping and amplitude-frequency characteristic of regenerative suspension[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[2] WANG Tong-jian, CHEN Jin-shi, ZHAO Feng, ZHAO Qing-bo, LIU Xin-hui, YUAN Hua-shan. Mechanical-hydraulic co-simulation and experiment of full hydraulic steering systems[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[3] ZHANG Chun-qin, JIANG Gui-yan, WU Zheng-yan. Factors influencing motor vehicle travel departure time choice behavior[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[4] XIAO Rui, DENG Zong-cai, LAN Ming-zhang, SHEN Chen-liang. Experiment research on proportions of reactive powder concrete without silica fume[J]. 吉林大学学报(工学版), 2013, 43(03): 671 -676 .
[5] CHEN Si-guo, JIANG Xu, WANG Jian, LIU Yan-heng, DENG Wei-wen, DENG Jun-yi. Mashup of vehicular ad-hoc network and universal mobile telecommunications system[J]. 吉林大学学报(工学版), 2013, 43(03): 706 -710 .
[6] MENG Chao, SUN Zhi-xin, LIU San-min. Multiple execution paths for virus based on cloud computing[J]. 吉林大学学报(工学版), 2013, 43(03): 718 -726 .
[7] XIAN Shu, ZHENG Jin, LU Xing, ZHANG Shi-peng. Identification approach of P2P flow based on the content redistribution model[J]. 吉林大学学报(工学版), 2013, 43(03): 727 -733 .
[8] LYU Yuan-zhi, WANG Shi-gang, YU Jue-qiong, WANG Xiao-yu, LI Xue-song. Display characteristics of one-dimensional integral imaging in virtual mode based on lenticular lens array[J]. 吉林大学学报(工学版), 2013, 43(03): 753 -757 .
[9] WANG Dan, LI Yang, NIAN Gui-jun, WANG Ke. An inhomogeneity mask for spatial watermarking[J]. 吉林大学学报(工学版), 2013, 43(03): 771 -775 .
[10] FENG Lin-han, QIAN Zhi-hong, SHANG Ke-cheng, ZHU Shuang. Improved hidden node collision avoidance strategy based on IEEE802.15.4[J]. 吉林大学学报(工学版), 2013, 43(03): 776 -780 .