Journal of Jilin University(Engineering and Technology Edition) ›› 2018, Vol. 48 ›› Issue (6): 1917-1924.doi: 10.13229/j.cnki.jdxbgxb20171161

Previous Articles     Next Articles

Efficient deterministic replay technique based on adaptive release strategy

YING Huan1(),LIU Song-hua2,TANG Bo-wen3,4,HAN Li-fang1,ZHOU Liang1   

  1. 1. China Electric Power Research Institute,Beijing 100192,China
    2. State Grid Electric Power Company of ShanDong Province DongMing County Power Supply Company,Heze 274500,China
    3. Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190, China
    4. University of Chinese Academy of Sciences,Beijing 100049,China
  • Received:2017-11-29 Online:2018-11-20 Published:2018-12-11

RICH HTML

 2   

PDF (PC)

102

Abstract:

Inherent non-determinism in parallel program brings huge difficulty and challenge to programmers to test and debug. The major source of non-determinism is the undetermined order of shared memory accesses. Deterministic replay provides the possibility of reproducing parallel program execution, and deterministic replay method based on page protection mechanism can reduce the recording overhead effectively. However, the exception of page protection is the main performance cost. This paper deeply analyzes runtime overhead incurred by release synchronization points in record-runs, and proposes a deterministic replay method based on adaptive release strategy. Performance evaluation shows that the record slowdown is much smaller than prior user-level replay system.

Key words: information processing technology, parallel program, shared memory, debugging, deterministic replay, page protection

CLC Number: 

  • TP368

Table 1

Performance analysis for releasing synchronization points %"

benchmarks (trecord_2-trecord_1)/
trecord_1		 tsegv/trecord tinit/tsegv tlibc/tsegv trequest/tsegv tpthreads/tseg thandler/tsegv tpreempted/tsegv
1 2 1 2 1 2 1 2 1 2 1 2 1 2
ferret 17.4 2.0 21.6 35.7 1.9 2.5 0.0 0.0 4.3 15.5 0.0 46.3 0.0 0.0 93.9
facesim -28.5 24.1 10.3 4.8 9.8 20.8 0.0 5.3 43.2 0.4 0.0 6.6 0.0 7.5 34.1
raytrace -22.6 39.2 23.5 5.3 16.6 0.0 0.0 40.0 74.1 0.0 0.0 54.7 0.0 0.0 0.0
bodytrack -5.3 -4.1 9.0 79.0 70.5 0.5 0.0 2.2 6.9 1.5 0.0 8.9 0.0 1.3 0.7
vips 3.6 5.5 4.9 63.1 58.0 0.0 0.0 0.4 12.2 0.2 0.0 16.2 0.0 20.1 29.8
x264 4.4 0.0 0.0 65.5 10.0 0.0 0.0 0.3 0.0 31.8 0.0 2.5 0.0 0.0 0.0
blackscholes 20.1 0.0 9.6 76.8 6.9 20.1 0.0 0.0 0.0 0.0 0.0 13.1 0.0 0.0 0.0
swaptions 42.6 5.2 36.8 59.2 33.4 2.7 0.0 0.0 35.1 0.0 0.0 0.5 0.0 0.0 0.0
canneal 2.3 80.0 81.0 3.6 2.3 5.9 0.0 42.1 96.6 0.0 0.0 47.2 0.0 0.4 0.3
dedup 3.9 21.5 27.4 51.3 46.8 0.0 0.0 9.0 42.8 9.5 0.0 21.3 0.0 8.1 9.4
streamcluster -14.5 32.7 31.6 1.5 1.3 0.0 0.0 4.4 50.8 18.2 0.0 67.6 0.0 6.6 12.8

Fig.1

A fragment of parallel program"

Fig.2

Performance impact for releasing synchronization points"

Fig.3

Program parallelism"

Fig.4

Algorithm of adaptive giving up"

Fig.5

Usage of conditional variable"

Fig.6

Performance comparison of Scribe, UPLAY & APLAY"

[1] 蒋炎岩, 许畅, 马晓星 , 等. 获取访存依赖:并发程序动态分析基础技术综述[J]. 软件学报, 2017,28(4):747-763.
Jiang Yan-yan, Xu Chang, Ma Xiao-xing , et al. Approaches to obtaining shared memory dependences for dynamic analysis of concurrent programs: a survey[J]. Journal of Software, 2017,28(4):747-763.
[2] Patil H, Pereira C, Stallcup M, et al. PinPlay:a framework for deterministic replay and reproducible analysis of parallel programs [C]//The 8th International Symposium on Code Generation and Optimization, Toronto, Ontario, Canada, 2010: 2-11.
[3] Huang J, Liu P, Zhang C. LEAP: lightweight deterministic multi-processor replay of concurrent Java programs [C]//Proceedings of the 8th ACM Sigsoft International Symposium on Foundations of Software Engineering,Santa Fe, NM, USA, 2010: 207-216.
[4] Lee D, Chen P M, Flinn J, et al. Chimera: hybrid program analysis for determinism [C]//Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, New York, NY, USA, 2012: 463-474.
[5] Bond M D, Kulkarni M, Cao M, et al. Efficient deterministic replay of multithreaded executions in a managed language virtual machine [C]//Proceedings of the Principles and Practices of Programming on the Java Platform, New York, NY, USA, 2015: 90-101.
[6] Honarmand N, Torrellas J. Replay debugging: leveraging record and replay for program debugging [C]//Proceeding of the 41st Annual International Symposium on Computer Architecuture, Minneapolis, MN, USA, 2014: 445-456.
[7] Pokam G, Danne K, Pereira C. 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,Israel, 2013: 643-654.
[8] Honarmand N, Dautenhahn N, Torrellas J, et al. Cyrus: unintrusive application-level record-replay for replay parallelism [C]//Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems, Houston, TX, USA, 2013: 193-206.
[9] Honarmand N, Torrellas J. Replay debugging: leveraging record and replay for program debugging [C]//Proceeding of the 41st Annual International Symposium on Computer Architecuture, Minneapolis, MN, USA, 2014: 445-456.
[10] Pokam G, Pereira C, Hu S L, et al. CoreRacer: a practical memory race recorder for multicore x86 TSO processors [C]//Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture, Porto Alegre, Brazil, 2011: 216-225.
[11] 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,USA, 2010: 155-166.
[12] 应欢, 王东辉, 武成岗 , 等. 适用于商用系统环境的低开销确定性重放技术[J]. 吉林大学学报:工学版, 2017,47(1):208-217.
Ying Huan, Wang Dong-hui, Wu Cheng-gang , et al. Efficient deterministic replay technique on commodity system environment[J]. Journal of Jilin University(Engineering and Technology Edition), 2017,47(1):208-217.
[13] Wang Z, Li J, Wu C, 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.
[14] Kedia P . Efficient deterministic replay through dynamic binary translation[D]. Delhi:Indian Institute of Technology, 2015.
[15] Lee D . Holistic system design for deterministic replay[D]. Ann Arbor:University of Michigan, 2013.
[16] Honarmand N . record and deterministic replay of parallel programs on multiprocessors[D]. Urbana:University of Illinois, 2014.
[17] 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, Ontario, Canada, 2008: 72-81.
[18] Yuan X, Wu C, Wang Z, et al. ReCBuLC: reproducing concurrency bugs using local clocks [C]//Proceedings of the 37th International Conference on Software Engineering,Florence, 2015: 824-834.
[19] 唐士斌 . 多线程程序的确定性调试方法[D]. 北京:中国科学院计算技术研究所, 2014.
Tang Shi-bin . Debugging muiltithreaded programs with determinism[D]. Beijing:The Institute of Computing Technology ,Chinese Academy of Sciences, 2014.
[20] 陈宇飞 . 可伸缩的确定性重放技术研究[D]. 上海:复旦大学计算机科学技术学院, 2014.
Chen Yu-fei . Improving the scalability of deterministic replay[D]. Shanghai:School of Computer Science, Fudan University, 2014.
[1] Tohtonur,Hai⁃long ZHANG,Jie WANG,Na WANG,Xin⁃chen YE,Wan⁃qiong WANG. High speed median filtering algorithm based on graphics processing unit [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 979-985.
[2] Lu⁃tao LIU,Na LI. Source detection based on coprime array [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 986-993.
[3] Yin⁃juan FU,Yong LI,Li⁃qin XU,Kun⁃hui ZHANG. Design and analysis of NLFM⁃Costas RF stealth radar signal [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 994-999.
[4] LIU Zhong-min,WANG Yang,LI Zhan-ming,HU Wen-jin. Image segmentation algorithm based on SLIC and fast nearest neighbor region merging [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1931-1937.
[5] SHAN Ze-biao,LIU Xiao-song,SHI Hong-wei,WANG Chun-yang,SHI Yao-wu. DOA tracking algorithm using dynamic compressed sensing [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1938-1944.
[6] YAO Hai-yang, WANG Hai-yan, ZHANG Zhi-chen, SHEN Xiao-hong. Reverse-joint signal detection model with double Duffing oscillator [J]. 吉林大学学报(工学版), 2018, 48(4): 1282-1290.
[7] QUAN Wei, HAO Xiao-ming, SUN Ya-dong, BAI Bao-hua, WANG Yu-ting. Development of individual objective lens for head-mounted projective display based on optical system of actual human eye [J]. 吉林大学学报(工学版), 2018, 48(4): 1291-1297.
[8] CHEN Tao, CUI Yue-han, GUO Li-min. Improved algorithm of multiple signal classification for single snapshot [J]. 吉林大学学报(工学版), 2018, 48(3): 952-956.
[9] CHEN Mian-shu, SU Yue, SANG Ai-jun, LI Pei-peng. Image classification methods based on space vector model [J]. 吉林大学学报(工学版), 2018, 48(3): 943-951.
[10] MENG Guang-wei, LI Rong-jia, WANG Xin, ZHOU Li-ming, GU Shuai. Analysis of intensity factors of interface crack in piezoelectric bimaterials [J]. 吉林大学学报(工学版), 2018, 48(2): 500-506.
[11] LIN Jin-hua, WANG Yan-jie, SUN Hong-hai. Improved feature-adaptive subdivision for Catmull-Clark surface model [J]. 吉林大学学报(工学版), 2018, 48(2): 625-632.
[12] WANG Ke, LIU Fu, KANG Bing, HUO Tong-tong, ZHOU Qiu-zhan. Bionic hypocenter localization method inspired by sand scorpion in locating preys [J]. 吉林大学学报(工学版), 2018, 48(2): 633-639.
[13] YU Hua-nan, DU Yao, GUO Shu-xu. High-precision synchronous phasor measurement based on compressed sensing [J]. 吉林大学学报(工学版), 2018, 48(1): 312-318.
[14] LIU Dong-liang, WANG Qiu-shuang. Instantaneous velocity extraction method on NGSLM data [J]. 吉林大学学报(工学版), 2018, 48(1): 330-335.
[15] WANG Fang-shi, WANG Jian, LI Bing, WANG Bo. Deep attribute learning based traffic sign detection [J]. 吉林大学学报(工学版), 2018, 48(1): 319-329.
Viewed
Full text
104
HTML PDF
Just accepted Online first Issue Just accepted Online first Issue
0 0 2 0 0 102

  From Others local
  Times 3 101
  Rate 3% 97%

Abstract
616
Just accepted Online first Issue
0 0 616
  From Others
  Times 616
  Rate 100%

Cited
Web of Science  Crossref   ScienceDirect  Search for Citations in Google Scholar >>
 
This page requires you have already subscribed to WoS.
  Shared   
  Discussed   
[1] Li Yue-ying，Liu Yong-bing，Chen Hua . Surface hardening and tribological properties of a cam materials[J]. 吉林大学学报(工学版), 2007, 37(05): 1064 -1068 .
[2] Nie Jian-jun，Du Fa-rong，Gao Feng . Finite time thermodynamics of real combined power cycle operating
between internal combustion engine and Stirling engine with heat leak[J]. 吉林大学学报(工学版), 2007, 37(03): 518 -0523 .
[3] Wang Chao,Song Ke-zhu,Tang Jin . High performance data acquisition system for marine seismic survey[J]. 吉林大学学报(工学版), 2007, 37(01): 168 -172 .
[4] Bao Tie，Liu Shu-fen . Network fault management formal description based on Communication Sequential Processes （CSP）[J]. 吉林大学学报(工学版), 2007, 37(01): 117 -120 .
[5] Xu Si-chuan,Li Rong-qing,Cheng Qin,Guo Ying-nan,Zhang Ji-peng,Sun Ji-mei,Wang Yong-fu . Influence of boundary condition on combustion of ethanol HCCI engine[J]. 吉林大学学报(工学版), 2007, 37(01): 74 -78 .
[6] Shao Bao-dong Sun Zhao-wei,Wang Li-feng . Optimization design of structural size of microchannel cooling heat sink[J]. 吉林大学学报(工学版), 2007, 37(02): 313 -0318 .
[7] Yang Wen, Shi Yong-jiu, Wang Yuan-qing, Shi Gang . Threedimensional finite element analysis on welding residual
stresses of construction steel[J]. 吉林大学学报(工学版), 2007, 37(02): 347 -0352 .
[8] Cheng Ping，Zhang Hai-tao，Gao Yan，Li Jun-feng，Wang Hong-yan . Application of ANN in property prediction of polyacrylate emulsion
[J]. 吉林大学学报(工学版), 2007, 37(02): 362 -0366 .
[9] Xiao Xian-qiang,Li Xin-xin,Yang Zhi-gang,Cheng Guang-ming . Vision control algorithm based on motion estimation and image match[J]. 吉林大学学报(工学版), 2007, 37(03): 655 -0659 .
[10] Li Hong-ping，Pei Yu-long，Yang Zhong-liang . Factors influencing free flow speed on expressway[J]. 吉林大学学报(工学版), 2007, 37(04): 772 -776 .
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd