Hardware data race detection algorithm based on sliding windows

Su-xia ZHU; De-yun CHEN; Zhen-zhou JI; Guang-lu SUN

doi:10.11959/j.issn.1000-436x.2016173

您当前的位置：

首页 >

文章列表页 >

Hardware data race detection algorithm based on sliding windows

Papers | 更新时间：2024-06-05

- Hardware data race detection algorithm based on sliding windows
- Journal on Communications Vol. 37, Issue 9, Pages: 10-19(2016)
- 作者机构：
  
  1. 哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨 150080
  2. 哈尔滨理工大学计算机科学与技术学院博士后流动站，黑龙江哈尔滨 150080
  3. 哈尔滨工业大学计算机科学与技术学院，黑龙江哈尔滨 150001
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China for Youths(61502123);Heilongjiang Province Science Foundation for Youths(QC2015084);The China Postdoctoral Science Foundation(2015M571429);The National Basic Research Program of China(2011CB302501)
- DOI：10.11959/j.issn.1000-436x.2016173
  CLC： TP303
- Online First：2016-09，
  
  Published：25 September 2016
- 稿件说明：
移动端阅览
Su-xia ZHU, De-yun CHEN, Zhen-zhou JI, et al. Hardware data race detection algorithm based on sliding windows[J]. Journal on Communications, 2016, 37(9): 10-19.
DOI：

Su-xia ZHU, De-yun CHEN, Zhen-zhou JI, et al. Hardware data race detection algorithm based on sliding windows[J]. Journal on Communications, 2016, 37(9): 10-19. DOI： 10.11959/j.issn.1000-436x.2016173.

摘要

数据竞争是引起多核程序发生并发错误的主要原因。针对现有基于硬件的 happens-before 数据竞争检测方法硬件开销大的问题，提出了一种轻量级的内存竞争硬件检测算法，该算法利用滑动窗口技术动态检测程序执行过程中发生的距离较近、更易引发并发错误的数据竞争。考虑竞争距离的大小，将并发线程片段细分为加锁并发竞争域和包含线程近期执行序列的未加锁并发竞争域，用一对交替移动的可重写滑动窗口保存未加锁并发竞争域内的内存操作指令，用一个大小可变的可重写滑动窗口保存加锁并发竞争域内的内存操作指令，当来自远程的共享访问与窗口内的内存访问发生冲突时，检测到数据竞争。在硬件实现结构中，仅为每个处理器核添加3对较小尺寸的硬件签名寄存器来保存并发竞争域内的数据地址，无需更改原有的cache一致性协议，带来的带宽开销低，能够快速地检测多核程序并发执行过程中发生的动态数据竞争，为多核程序开发和生产运行阶段的并发错误诊断提供有效的指导信息。

Abstract

Data race is a major factor which causes multi-core programs to produce concurrent bugs.To address the high hardware cost in happens-before detection proposals

a light-weight hardware data race detection approach based on sliding window technology was proposed.It used sliding windows to save recent memory instructions in thread execution and dynamically detected data races with small race distance which more easily lead to concurrent bugs.Considering the race distance

parallel thread segments were subdivided into concurrent race regions with lock and concurrent race regions without lock.A pair of alternate rewritable sliding windows was used to store the memory instructions in concurrent race region without lock

and a sliding window with variable size was used to store the memory instructions in concurrent race region with lock.When there was a conflict between a remote sharing access and memory accesses in sliding windows

a data race was detected.In the hardware implementation

the addresses of the data in sliding windows were automatically encoded into three hardware signatures with small size.Data races can be detected quickly without modifying the L1 cache and cache coherence protocol messages.This approach supplies efficient guidance to help users to diagnose concurrency bugs occurred in the development and production run of multi-core programs

achieving smaller hardware and bandwidth overhead.

关键词

Keywords

references

SAVAGE S , BURROWS M , NELSON G , et al . Eraser:a dynamic data race detector for multithreaded programs [J ] . ACM Transactions on Computer Systems (TOCS) , 1997 , 15 ( 4 ): 391 - 411 .

DI P , SUI Y . Accelerating dynamic data race detection using static thread interference analysis [C ] // The 7th International Workshop on Programming Models and Applications for Multicores and Manycores . ACM , 2016 : 30 - 39 .

WU Z , LU K , WANG X , et al . Collaborative technique for concurrency bug detection [J ] . International Journal of Parallel Programming , 2015 , 43 ( 2 ): 260 - 285 .

陈睿 , 杨孟飞 , 郭向英 . 基于变量访问序模式的中断数据竞争检测方法 [J ] . 软件学报 , 2016 , 27 ( 3 ): 547 - 561 .

CHEN R , YANG M F , GUO X Y . Interrupt data race detection based on shared variable access order pattern [J ] . Journal of Software , 2016 , 27 ( 3 ): 547 - 561 .

王文文 , 武成岗 . 动态容忍和检测非对称数据竞争 [J ] . 计算机研究与发展 , 2014 , 51 ( 8 ): 1748 - 1763 .

WANG W W , WU C G . Dynamically tolerating and detecting asymmetric race [J ] . Journal of Computer Research and Development , 2014 , 51 ( 8 ): 1748 - 1763 .

LU K , WU Z , WANG X , et al . RaceChecker:efficient identification of harmful data races [C ] // 2015 23rd Euromicro International Conference on Parallel,Distributed,and Network-Based Processing . IEEE , 2015 : 78 - 85 .

WESTER B , DEVECSERY D , CHEN P M , et al . Parallelizing data race detection [J ] . ACM Sigplan Notices , 2013 , 48 ( 4 ): 27 - 38 .

PRVULOVIC M , . CORD:cost-effective (and nearly overhead-free) order-recording and data race detection [C ] // The Twelfth International Symposium on High-Performance Computer Architecture . IEEE , 2006 : 232 - 243 .

ZHOU P , TEODORESCU R , ZHOU Y . HARD:hardware-assisted lockset-based race detection [C ] // 2007 IEEE 13th International Symposium on High Performance Computer Architecture . IEEE , 2007 : 121 - 132 .

MUZAHID A,SUÁREZ D , QI S , et al . SigRace:signature-based data race detection [J ] . ACM Sigarch Computer Architecture News , 2009 , 37 ( 3 ): 337 - 348 .

QI S , OTSUKI N , NOGUEIRA L O , et al . Pacman:tolerating asymmetric data races with unintrusive hardware [C ] // High Performance Computer Architecture (HPCA),2012 IEEE 18th International Symposium . IEEE , 2012 : 1 - 12 .

QI S , MUZAHID A A , AHN W , et al . Dynamically detecting and tolerating if-condition data races [C ] // The 20th IEEE International Symposium on High Performance Computer Architecture (HPCA) . IEEE Computer Society , 2014 : 120 - 131 .

OROSA L , . A hardware approach to detect,expose and tolerate high level data races [C ] // The 24th Euromicro International Conference on Parallel,Distributed,and Network-Based Processing (PDP) . IEEE , 2016 : 159 - 167 .

DEVIETTI J , WOOD B P , STRAUSS K , et al . RADISH:always-on sound and complete race detection in software and hardware [C ] // IEEE Computer Architecture (ISCA),2012 39th Annual International Symposium . IEEE , 2012 : 201 - 212 .

ARULRAJ J , CHANG P C , JIN G , et al . Production-run software failure diagnosis via hardware performance counters [J ] . ACM Sigarch Computer Architecture News , 2013 , 41 ( 1 ): 101 - 112 .

SHENG T , VACHHARAJANI N , ERANIAN S , et al . RACEZ:a lightweight and non-invasive race detection tool for production applications [C ] // The International Conference on Software Engineering . 2011 : 401 - 410 .

Intel Corporation Intel thread checker [EB/OL ] . http://www.intel.com http://www.intel.com . 2008 .

LUSK E , BOYLE J , BUTLER R , et al . Portable programs for parallel processors [M ] . Holt,Rinehart & Winston , 1988 .

MARTIN M M K , SORIN D J , BECKMANN B M , et al . Multifacet's general execution-driven multiprocessor simulator (GEMS) toolset [J ] . ACM SIGARCH Computer Architecture News , 2005 , 33 ( 4 ): 92 - 99 .

WOO S C , OHARA M , TORRIE E , et al . The SPLASH-2 programs:characterization and methodological considerations [J ] . ACM SIGARCH Computer Architecture News,ACM , 1995 , 23 ( 2 ): 24 - 36 .

Views

2228

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Chinese medical named entity recognition model based on local enhancement

Differentiated and negotiable mechanism for data communication

Data comparable encryption scheme based on cloud computing in Internet of things

Guaranteeing service availability in cloud computing

Self-healing key distribution scheme of MANET based on sliding window

Related Author

FENG Jianzhou

XING Kexuan

CHEN Jing

MENG Weilun

GUO Jingfeng

Wenlong KOU

Fenghua LI

Xiuze DONG

Related Institution

College of Mathematics and Computer Science, Guangdong Ocean University

The Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province

College of Information Science and Engineering, Yanshan University

School of Cyber Engineering, Xidian University

Institute of Information Engineering, Chinese Academy of Sciences

AI问答

⁰