SigRace: signature-based data race detection

ABSTRACT

Detecting data races in parallel programs is important for both software development and production-run diagnosis. Recently, there have been several proposals for hardware-assisted data race detection. Such proposals typically modify the L1 cache and cache coherence protocol messages, and largely lose their capability when lines get displaced or invalidated from the cache. To eliminate these shortcomings, this paper proposes a novel, different approach to hardware-assisted data race detection. The approach, called SigRace, relies on hardware address signatures. 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.

This paper presents the architecture of SigRace, an implementation, and its software interface. With SigRace, caches and coherence protocol messages are unmodified. Moreover, cache lines can be displaced and invalidated with no effect. Our experiments show that SigRace is significantly more effective than a state-of-the-art conventional hardware-assisted race detector. SigRace finds on average 29% more static races and 107% more dynamic races. Moreover, if we inject data races, SigRace finds 150% more static races than the conventional scheme.

REFERENCES

• 1: Christian Bienia , Sanjeev Kumar , Jaswinder Pal Singh , Kai Li, The PARSEC benchmark suite: characterization and architectural implications, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454128]
• 2: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 3: Luis Ceze , James Tuck , Pablo Montesinos , Josep Torrellas, BulkSC: bulk enforcement of sequential consistency, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 4: Luis Ceze , James Tuck , Josep Torrellas , Calin Cascaval, Bulk Disambiguation of Speculative Threads in Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.227-238, June 17-21, 2006
• 5: Jong-Deok Choi , Keunwoo Lee , Alexey Loginov , Robert O'Callahan , Vivek Sarkar , Manu Sridharan, Efficient and precise datarace detection for multithreaded object-oriented programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 6: Leonardo Dagum , Ramesh Menon, OpenMP: An Industry-Standard API for Shared-Memory Programming, IEEE Computational Science & Engineering, v.5 n.1, p.46-55, January 1998 [doi>10.1109/99.660313]
• 7: Colin Fidge, Logical Time in Distributed Computing Systems, Computer, v.24 n.8, p.28-33, August 1991 [doi>10.1109/2.84874]
• 8: Intel Corporation. Intel Thread Checker. http://www.intel.com, 2008.
• 9: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 10: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 11: Ewing Lusk , James Boyle , Ralph Butler , Terrence Disz , Barnett Glickfeld , Ross Overbeek , James Patterson , Rick Stevens, Portable programs for parallel processors, Holt, Rinehart & Winston, Austin, TX, 1988
• 12: Sang L. Min , Jong-Deok Choi, An efficient cache-based access anomaly detection scheme, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.235-244, April 08-11, 1991, Santa Clara, California, United States
• 13: Chi Cao Minh , Martin Trautmann , JaeWoong Chung , Austen McDonald , Nathan Bronson , Jared Casper , Christos Kozyrakis , Kunle Olukotun, An effective hybrid transactional memory system with strong isolation guarantees, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 14: Satish Narayanasamy , Zhenghao Wang , Jordan Tigani , Andrew Edwards , Brad Calder, Automatically classifying benign and harmful data racesallusing replay analysis, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 15: R. H. B. Netzer and B. P. Miller. Detecting data races in parallel program executions. In In Workshop on Advances in Languages and Compilers for Parallel Computing, 1990.
• 16: Robert H. B. Netzer , Barton P. Miller, Improving the accuracy of data race detection, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.133-144, April 21-24, 1991, Williamsburg, Virginia, United States
• 17: Robert O'Callahan , Jong-Deok Choi, Hybrid dynamic data race detection, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 18: M. Prvulovic. CORD: Cost-effective (and nearly overhead-free) order-recording and data race detection. In International Symposium on High-Performance Computer Architecture, February 2006.
• 19: Milos Prvulovic , Josep Torrellas, ReEnact: using thread-level speculation mechanisms to debug data races in multithreaded codes, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 20: Milos Prvulovic , Zheng Zhang , Josep Torrellas, ReVive: cost-effective architectural support for rollback recovery in shared-memory multiprocessors, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 21: Feng Qin , Joseph Tucek , Yuanyuan Zhou , Jagadeesan Sundaresan, Rx: Treating bugs as allergies—a safe method to survive software failures, ACM Transactions on Computer Systems (TOCS), v.25 n.3, p.7-es, August 2007 [doi>10.1145/1275517.1275519]
• 22: Michiel Ronsse , Koen De Bosschere, RecPlay: a fully integrated practical record/replay system, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.133-152, May 1999 [doi>10.1145/312203.312214]
• 23: Daniel Sanchez , Luke Yen , Mark D. Hill , Karthikeyan Sankaralingam, Implementing Signatures for Transactional Memory, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.123-133, December 01-05, 2007 [doi>10.1109/MICRO.2007.20]
• 24: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 25: Sudarshan M. Srinivasan , Srikanth Kandula , Christopher R. Andrews , Yuanyuan Zhou, Flashback: a lightweight extension for rollback and deterministic replay for software debugging, Proceedings of the annual conference on USENIX Annual Technical Conference, p.3-3, June 27-July 02, 2004, Boston, MA
• 26: Sun Microsystems. Sun Studio Thread Analyzer. http://developers.sun.com/sunstudio, 2007.
• 27: Christoph von Praun , Thomas R. Gross, Object race detection, Proceedings of the 16th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.70-82, October 14-18, 2001, Tampa Bay, FL, USA
• 28: Luke Yen , Jayaram Bobba , Michael R. Marty , Kevin E. Moore , Haris Volos , Mark D. Hill , Michael M. Swift , David A. Wood, LogTM-SE: Decoupling Hardware Transactional Memory from Caches, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.261-272, February 10-14, 2007 [doi>10.1109/HPCA.2007.346204]
• 29: Yuan Yu , Tom Rodeheffer , Wei Chen, RaceTrack: efficient detection of data race conditions via adaptive tracking, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 30: Pin Zhou , Radu Teodorescu , Yuanyuan Zhou, HARD: Hardware-Assisted Lockset-based Race Detection, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.121-132, February 10-14, 2007 [doi>10.1109/HPCA.2007.346191]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.4 Reliability, Testing, and Fault-Tolerance**
          Subjects: Error-checking**

General Terms:
Design, Measurement, Reliability

Keywords:
SigRace, concurrency defect, data race, happened-before, signature, timestamp