Files in this item



application/pdfMuzahid_Abdullah.pdf (497kB)
(no description provided)PDF


Title:Effective architectural support for detecting concurrency bugs
Author(s):Muzahid, Abdullah
Director of Research:Torrellas, Josep
Doctoral Committee Chair(s):Torrellas, Josep
Doctoral Committee Member(s):Snir, Marc; Marinov, Darko; King, Samuel T.; Frank, Matthew I.; Peterson, Paul E.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Concurrency Bugs
Multithreaded Programs
Abstract:Multicore machines have become pervasive and, as a result, parallel programming has received renewed interest. Unfortunately, writing correct parallel programs is notoriously hard. Therefore, it is important to innovate with techniques and approaches to tackle various types of concurrency bugs. This thesis aims at making parallel programming easier by detecting some of the most common and difficult concurrency bugs in shared memory parallel programs, namely data races, atomicity violations, and sequential consistency violations. Specifically, we propose novel, effective and efficient hardware-based techniques that help detect and isolate these bugs. We use hardware-based solutions because they lead to low overhead solutions. Therefore we can use these techniques to detect the bugs both during development time and during production run. The proposal to detect data races is called SigRace. It uses hardware address signatures to detect data races dynamically at run time. As a processor runs, the addresses of the data that it accesses are automatically encoded in signatures. At certain times, the signatures are automatically passed 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 which case we run a more detailed analysis to pinpoint the race. SigRace can detect data races successfully. But even if a multithreaded program does not have any data races, it can still show incorrect behavior because of a bug named atomicity violation. The proposal to detect atomicity violations is called AtomTracker. It is based on first trying to learn atomicity constraints automatically from the program, by analyzing many correct executions. After it finds the set of possible atomic regions, the hardware monitors the execution to detect any violations of these atomic regions. AtomTracker uses a hardware very similar to SigRace to accomplish this. The above approaches tackle data races in a classical sense or in a more higher level sense (namely atomicity violations). The last work of this thesis is to find out a special pattern of data races that are particularly hard to detect and analyze. This complicated pattern of data races leads to violation of sequential consistency which is the underlying behavior of the memory model that programmers usually assume. Sequential consistency violations (SCV) lead to some of the most notorious bugs in parallel programs. In order to detect SCV in a machine with a relaxed memory model, we leverage cache coherence protocol transactions and dynamically detect cycles in memory-access orderings across threads. When one such cycle is about to occur, an exception is triggered, providing the exact architectural state. We performed detailed experimentation with each of these techniques and showed that 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.
Issue Date:2012-09-18
Rights Information:Copyright 2012 Abdullah Al Muzahid
Date Available in IDEALS:2012-09-18
Date Deposited:2012-08

This item appears in the following Collection(s)

Item Statistics