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

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

摘要/Abstract

摘要：

数据竞争是引起多核程序发生并发错误的主要原因。针对现有基于硬件的 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.

Key words: data race, sliding window, hardware signature, concurrency bug, multi-core program

朱素霞,陈德运,季振洲,孙广路. 基于滑动窗口的多核程序数据竞争硬件检测算法[J]. 通信学报, 2016, 37(9): 10-19.

Su-xia ZHU,De-yun CHEN,Zhen-zhou JI,Guang-lu SUN. Hardware data race detection algorithm based on sliding windows[J]. Journal on Communications, 2016, 37(9): 10-19.

图/表 16

图1

图2

图3

图4

图5

图6

图7

图8

表1

图9

表2

表3

图10

图11

图12

图13

参考文献 20

[1]	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.
[2]	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.
[3]	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.
[4]	陈睿, 杨孟飞, 郭向英 . 基于变量访问序模式的中断数据竞争检测方法[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.
[5]	王文文, 武成岗 . 动态容忍和检测非对称数据竞争[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.
[6]	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.
[7]	WESTER B , DEVECSERY D , CHEN P M ,et al. Parallelizing data race detection[J]. ACM Sigplan Notices, 2013,48(4): 27-38.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[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.
[13]	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.
[14]	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.
[15]	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.
[16]	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.
[17]	Intel Corporation Intel thread checker[EB/OL]. . 2008.
[18]	LUSK E , BOYLE J , BUTLER R ,et al. Portable programs for parallel processors[M]. Holt,Rinehart & Winston, 1988.
[19]	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.
[20]	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.

指令	描述
Lock_on	开启加锁并发竞争域和地址过滤功能
Lock_off	开启未加锁并发竞争域和地址过滤功能
Filter_off	结束地址过滤功能

操作	方法	代码
	原函数	define(LOCK,`{lock($1);
		}')
lock		define(LOCK,`{Lock_on;
	RaceSW	lock($1);
		Filter_off;
		}')
		define(UNLOCK,`{
	原函数	lock($1);
		}')
unlock		define(UNLOCK,`{Lock_off;
	RaceSW	lock($1);
		Filter_off;
		}')
		define(BARRIER,`{
	原函数	barrier(($1),($2));
		}')
barrier		define(BARRIER,`{Lock_off;
		barrier(($1),($2));
	RaceSW	Filter_off;
		}')

参数	说明
Cores	8核，in-order，3 GHz
Private L1 Cache	分离的指令cache和数据cache，大小为64 KB、4路组相关、采用写回策略、每个cache块为64 byte，LRU替换策略
Shared L2 Cache	2 MB，4路组相关，LRU替换策略
Memory	4 GB DRAM
Coherence	MESI
Consistency Model	sequential consistency（SC）