Effective architectural support for detecting concurrency bugs

Muzahid, Abdullah

Permalink

https://hdl.handle.net/2142/34513 Copy

Description

Title

Effective architectural support for detecting concurrency bugs

Author(s)

Muzahid, Abdullah

Issue Date

2012-09-18T21:20:52Z

Director of Research (if dissertation) or Advisor (if thesis)

Torrellas, Josep

Doctoral Committee Chair(s)

Torrellas, Josep

Committee Member(s)

• Snir, Marc
• Marinov, Darko
• King, Samuel T.
• Frank, Matthew I.
• Peterson, Paul E.

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Debugging
• Concurrency Bugs
• Multithreaded Programs
• Multicore

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.

Graduation Semester

2012-08

Permalink

http://hdl.handle.net/2142/34513

Copyright and License Information

Copyright 2012 Abdullah Al Muzahid

Owning Collections