News

CS researchers develop first hardware scheme to precisely detect Sequential Consistency Violations at runtime

9/18/2012 4:59:00 PM

The research group of computer science professor Josep Torrellas has developed a novel hardware scheme that can dynamically detect the programming errors called Sequential Consistency Violations at runtime.

Josep Torrellas
Josep Torrellas
Torrellas’ group will present the paper that details this method, “Hardware Support for Detecting Sequential Consistency Violations Dynamically,” at the 45th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), on December 1-5, 2012 in Vancouver, BC, Canada. MICRO is one of the top conferences in computer architecture, with an 18% acceptance rate.

The paper, authored by Abdullah Muzahid, Shanxiang Qi, and Josep Torrellas, describes novel hardware extensions to the cache coherence protocol of a multicore that automatically detect when the threads of a multithreaded program are about to interleave in way that violates Sequential Consistency. A Sequential Consistency Violation occurs due to a synchronization bug in the program, which causes threads to interleave in a way that cannot be reproduced by multiplexing the threads of the program on a uniprocessor. Such interleaving is, therefore, highly non-intuitive, and comes about because the instructions from different threads have overlapped in a convoluted manner. A Sequential Consistency Violation is impossible to reproduce with a program debugger, which single-steps on the instructions.

The hardware scheme proposed, called Vulcan, is the first to precisely detect Sequential Consistency Violations at runtime. The scheme uses the cache coherence protocol transactions to dynamically detect these violations.  When one is about to occur, an exception is triggered.  For the conditions considered in the paper and with enough hardware, Vulcan neither suffers false alarms nor misses any violation.

With Vulcan, the authors show that they detect three new bugs in popular codes. Moreover, Vulcan has a negligible execution overhead, which makes it suitable for on-the-fly use on real programs. Overall, Vulcan is a novel technique that can help to improve the debuggability and programmability of parallel codes significantly.

This work is part of the Illinois-Intel Parallelism Center (I2PC), which focuses on novel technologies to improve the programmability of parallel client systems. The paper can be obtained from http://iacoma.cs.uiuc.edu/iacoma-papers/micro12.pdf.
__________________________

Contact: Josep Torrellas, Department of Computer Science, 217/244-4148.

Writer: Megan Osfar, I2PC Project coordinator, Department of Computer Science, 217/265 6738.

If you have any questions about the College of Engineering, or other story ideas, contact Rick Kubetz, editor, Engineering Communications Office, 217/244-7716, University of Illinois at Urbana-Champaign.