An Efficient Algorithm for On-the-Fly Data Race Detection Using an Epoch-Based Technique
Joint Authors
Source
Issue
Vol. 2015, Issue 2015 (31 Dec. 2015), pp.1-14, 14 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2015-07-16
Country of Publication
Egypt
No. of Pages
14
Main Subjects
Abstract EN
Data races represent the most notorious class of concurrency bugs in multithreaded programs.
To detect data races precisely and efficiently during the execution of multithreaded programs, the epoch-based FastTrack technique has been employed.
However, FastTrack has time and space complexities that depend on the maximum parallelism of the program to partially maintain expensive data structures, such as vector clocks.
This paper presents an efficient algorithm, called iFT, that uses only the epochs of the access histories.
Unlike FastTrack, our algorithm requires O ( 1 ) operations to maintain an access history and locate data races, without any switching between epochs and vector clocks.
We implement this algorithm on top of the Pin binary instrumentation framework and compare it with other on-the-fly detection algorithms, including FastTrack, which uses a state-of-the-art happens-before analysis algorithm.
Empirical results using the PARSEC benchmark show that iFT reduces the average runtime and memory overhead to 84% and 37%, respectively, of those of FastTrack.
American Psychological Association (APA)
Ha, Ok-Kyoon& Jun, Yong-Kee. 2015. An Efficient Algorithm for On-the-Fly Data Race Detection Using an Epoch-Based Technique. Scientific Programming،Vol. 2015, no. 2015, pp.1-14.
https://search.emarefa.net/detail/BIM-1076504
Modern Language Association (MLA)
Ha, Ok-Kyoon& Jun, Yong-Kee. An Efficient Algorithm for On-the-Fly Data Race Detection Using an Epoch-Based Technique. Scientific Programming No. 2015 (2015), pp.1-14.
https://search.emarefa.net/detail/BIM-1076504
American Medical Association (AMA)
Ha, Ok-Kyoon& Jun, Yong-Kee. An Efficient Algorithm for On-the-Fly Data Race Detection Using an Epoch-Based Technique. Scientific Programming. 2015. Vol. 2015, no. 2015, pp.1-14.
https://search.emarefa.net/detail/BIM-1076504
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1076504