Effective architectural support for detecting concurrency bugs

Debugging;Concurrency Bugs;Multithreaded Programs;Multicore

Muzahid, Abdullah

关键词: Debugging;    Concurrency Bugs;    Multithreaded Programs;    Multicore;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/34513/Muzahid_Abdullah.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Multicore machines have become pervasive and, as a result, parallelprogramming has received renewed interest. Unfortunately, writingcorrect parallel programs is notoriously hard. Therefore, it isimportant to innovate with techniques and approaches to tacklevarious types of concurrency bugs.This thesis aims at making parallel programming easier by detectingsome of the most common and difficultconcurrency bugsin shared memory parallel programs,namely data races, atomicity violations, and sequential consistencyviolations. Specifically,we propose novel, effective and efficient hardware-based techniquesthat help detect and isolate these bugs. We use hardware-basedsolutions because they lead to low overhead solutions. Thereforewe can use these techniques to detect the bugs both during developmenttime and during production run.The proposal to detect data races is called SigRace. It uses hardwareaddress signatures to detect data races dynamically at run time. Asa processor runs, the addresses of the data that it accesses are automaticallyencoded in signatures. At certain times, the signatures are automaticallypassed to a hardware module that intersects them with those of other processors.If the intersection is not null, a data race may have occurred, in whichcase we run a more detailed analysis to pinpoint the race.SigRace can detect data races successfully. But even if a multithreaded program does nothave any data races, it can still show incorrect behavior because of a bugnamed atomicity violation. The proposal to detect atomicity violations is called AtomTracker. It is based on first trying to learn atomicity constraints automatically fromthe program, by analyzing many correct executions. After it finds theset of possible atomic regions, the hardware monitors the executionto detect any violations of these atomic regions. AtomTracker usesa hardware very similar to SigRace to accomplish this.The above approaches tackle data races in a classical sense or in a more higher levelsense (namely atomicity violations). The last work of this thesis is to find out a special patternof data races that are particularly hard to detect and analyze. This complicatedpattern of data races leads to violation of sequential consistency which is theunderlying behavior of the memory model that programmers usually assume.Sequential consistency violations (SCV)lead to some of the most notorious bugs in parallel programs. Inorder to detect SCV in a machine with a relaxed memory model, weleverage cache coherence protocol transactions and dynamically detectcycles in memory-access orderings across threads. When one such cycleis about to occur, an exception is triggered, providing the exactarchitectural state.We performed detailed experimentation with each of these techniques and showedthat they are effective in detecting various types of concurrency bugs. More importantly,we uncovered several new and previously unreported bugs in various popular open source codes using these solutions.