基于滑动窗口的多核程序数据竞争硬件检测算法

朱素霞; 陈德运; 季振洲; 孙广路

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

您当前的位置：

首页 >

文章列表页 >

基于滑动窗口的多核程序数据竞争硬件检测算法

学术论文 | 更新时间：2024-06-05

- 基于滑动窗口的多核程序数据竞争硬件检测算法
- Hardware data race detection algorithm based on sliding windows
- 通信学报 2016年37卷第9期页码：10-19
- 作者机构：
  
  1. 哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨 150080
  2. 哈尔滨理工大学计算机科学与技术学院博士后流动站，黑龙江哈尔滨 150080
  3. 哈尔滨工业大学计算机科学与技术学院，黑龙江哈尔滨 150001
- 作者简介：
  
  [ "朱素霞（1978-），女，山东寿光人，博士，哈尔滨理工大学副教授，主要研究方向为高性能体系结构、并行计算。" ]
  [ "陈德运（1962-），男，黑龙江哈尔滨人，哈尔滨理工大学教授、博士生导师，主要研究方向为图像处理、探测和成像技术。" ]
  [ "季振洲（1965-），男，黑龙江哈尔滨人，哈尔滨工业大学教授、博士生导师，主要研究方向为并行体系结构、并行计算和网络安全。" ]
  [ "孙广路（1979-），男，黑龙江哈尔滨人，哈尔滨理工大学教授，主要研究方向为网络安全、模式识别和机器学习。" ]
- 基金信息：
  
  国家自然科学青年基金资助项目(61502123);黑龙江省青年科学基金资助项目(QC2015084);中国博士后科学基金资助项目(2015M571429);国家重点基础研究发展计划（“973”计划）基金资助项目(2011CB302501)
- DOI：10.11959/j.issn.1000-436x.2016173
  中图分类号： TP303
- 网络出版日期：2016-09，
  
  纸质出版日期：2016-09-25
- 稿件说明：
移动端阅览
朱素霞, 陈德运, 季振洲, 等. 基于滑动窗口的多核程序数据竞争硬件检测算法[J]. 通信学报, 2016,37(9):10-19.

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.
朱素霞, 陈德运, 季振洲, 等. 基于滑动窗口的多核程序数据竞争硬件检测算法[J]. 通信学报, 2016,37(9):10-19. DOI： 10.11959/j.issn.1000-436x.2016173.

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 .

浏览量

1079

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于局部增强的中文医疗命名实体识别模型

支持差异化可协商的数据通信机制

基于云计算平台的物联网加密数据比较方案

云计算中的服务可用性保障机制

基于滑动窗口的移动自组网的自愈密钥发布机制