An Efficient and Flexible Deterministic Framework for Multithreaded Programs
详细信息 查看全文
- 作者：Kai Lu (1) (2)
Xu Zhou (2)
Xiao-Ping Wang (1) (2)
Tom Bergan (3)
Chen Chen (1) (2)
1. Science and Technology on Parallel and Distributed Processing Laboratory ; National University of Defense Technology ; Changsha ; 410073 ; China
2. College of Computer ; National University of Defense Technology ; Changsha ; 410073 ; China
3. Department of Computer Science and Engineering ; University of Washington ; Seattle ; WA ; 98195-2350 ; U.S.A - 关键词：determinism ; multithreading ; framework ; flexible
- 刊名：Journal of Computer Science and Technology
- 出版年：2015
- 出版时间：January 2015
- 年：2015
- 卷：30
- 期：1
- 页码：42-56
- 全文大小：571 KB
- 参考文献：1. Lee E A. The problem with threads. / Computer, 2006, 39(5):33-42. CrossRef
2. Olszewski M, Ansel J, Amarasinghe S. Kendo: Efficient deterministic multithreading in software. In / Proc. the 14th ASPLOS, March 2009, pp.97-108.
3. Devietti J, Lucia B, Ceze L, Oskin M. DMP: Deterministic shared memory multiprocessing. In / Proc. the 14th ASP-LOS, March 2009, pp.85-96.
4. Aviram A, Weng S C, Hu S, Ford B. Efficient systemenforced deterministic parallelism. In / Proc. the 9th OSDI, October 2010, pp.193-206.
5. Veeraraghavan K, Lee D, Wester B, Ouyang J, Chen P M, Flinn J, Narayanasamy S. DoublePlay: Parallelizing sequential logging and replay. / ACM Transactions on Computer Systems, 2012, 30(1):3:1-3:24.
6. Bergan T, Anderson O, Devietti J, Ceze L, Grossman D. CoreDet: A compiler and runtime system for deterministic multithreaded execution. In / Proc. the 15th ASPLOS, March 2010, pp.53-64.
7. Bergan T, Hunt N, Ceze L, Gribble S D. Deterministic process groups in DOS. In / Proc. the 9th OSDI, October 2010, pp.177-191.
8. Hunt N, Bergan T, Ceze L, Gribble S D. DDOS: Taming nondeterminism in distributed systems. In / Proc. the 18th ASPLOS, March 2013, pp.499-508.
9. Bergan T, Devietti J, Hunt N, Ceze L. The deterministic execution hammer: How well does it actually pound nails? In / Proc. the 2nd Workshop on Determinism and Correctness in Parallel Programming, March 2011, pp.56-63.
10. Lu K, Zhou X, Bergan T, Wang X. Efficient deterministic multithreading without global barriers. In / Proc. the 19th PPoPP, February 2014, pp.287-300.
11. Cui H, Simsa J, Lin Y H, Li H, Blum B, Xu X, Yang J, Gibson G A, Bryant R E. PARROT: A practical runtime for deterministic, stable, and reliable threads. In / Proc. the 24th SOSP, November 2013, pp.388-405.
12. Chen Y, Chen H. Scalable deterministic replay in a parallel full-system emulator. / SIGPLAN Not., 2013, 48(8):207鈥?18. CrossRef
13. Cui H, Wu J, Tsai C C, Yang J. Stable deterministic multithreading through schedule memoization. In / Proc. the 9th OSDI, October 2010, pp.207-221.
14. Boehm H J, Adve S V. Foundations of the C++ concurrency memory model. In / Proc. the 29th PLDI, June 2008, pp.68-78.
15. Adve S V, Aggarwal J K. A unified formalization of four shared-memory models. / IEEE Trans. Parallel Distrib. Syst., 1993, 10(4):613-624. CrossRef
16. Keleher P, Cox A L, Zwaenepoel W. Lazy release consistency for software distributed shared memory. In / Proc. the 19th ISCA, May 1992, pp.13-21.
17. Keleher P, Cox A L, Dwarkadas S, Zwaenepoel W. Treadmarks: Distributed shared memory on standard workstations and operating systems. In / Proc. the 1994 USENIX Winter Technical Conf., November 1994, pp.10:1-10:17.
18. Liu T, Curtsinger C, Berger E D. Dthreads: Efficient deterministic multithreading. In / Proc. the 23rd SOSP, October 2011, pp.327-336.
19. Fidge C J. Partial orders for parallel debugging. In / Proc. the 1988 ACM SIGPLAN and SIGOPS Workshop on Parallel and Distributed Debugging, May 1988, pp.183-194.
20. Berger E D, Zorn B G, McKinley K S. Composing highperformance memory allocators. In / Proc. the 2001 PLDI, June 2001, pp.114-124.
21. Xiong W, Park S, Zhang J, Zhou Y, Ma Z. Ad hoc synchronization considered harmful. In / Proc. the 9th OSDI, October 2010, pp.163-176.
22. Adve S V, Hill M D. Weak ordering 鈥斺€?A new definition. / SIGARCH Comput. Archit. News, 1990, 18(2):2-14. CrossRef
23. Weaver V, McKee S. Can hardware performance counters be trusted? In / Proc. IEEE Int. Symp. Workload Characterization, September 2008, pp.141-150.
24. Bienia C, Kumar S, Singh J P, Li K. The PARSEC benchmark suite: Characterization and architectural implications. In / Proc. the 17th Int. Conf. Parallel Architectures and Compilation Techniques, October 2008, pp.72-81.
25. Woo S C, Ohara M, Torrie E, Singh J P, Gupta A. The SPLASH-2 programs: Characterization and methodological considerations. In / Proc. the 22nd ISCA, June 1995, pp.24-36.
26. Ranger C, Raghuraman R, Penmetsa A, Bradski G, Kozyrakis C. Evaluating MapReduce for multi-core and multiprocessor systems. In / Proc. the 13th HPCA, February 2007, pp.13-24.
27. Devietti J, Nelson J, Bergan T, Ceze L, Grossman D. RCDC: A relaxed consistency deterministic computer. In / Proc. the 16th ASPLOS, March 2011, pp.67-78.
28. Hower D, Dudnik P, Hill M, Wood D. Calvin: Deterministic or not? Free will to choose. In / Proc. the 17th HPCA, February 2011, pp.333-334.
29. Merrifield T, Eriksson J. Conversion: Multi-version concurrency control for main memory segments. In / Proc. the 8th ACM European Conf. Computer Systems, April 2013, pp.127-139.
30. Zhou X, Lu K, Wang X, Li X. Exploiting parallelism in deterministic shared memory multiprocessing. / Journal of Parallel and Distributed Computing, 2012, 72(5):716-727. CrossRef
31. Cui H, Wu J, Gallagher J, Guo H, Yang J. Efficient deterministic multithreading through schedule relaxation. In / Proc. the 23rd SOSP, October 2011, pp.337-351.
32. Bergan T, Ceze L, Grossman D. Input-covering schedules for multithreaded programs. In / Proc. the 2013 ACM SIG-PLAN Int. Conf. Object Oriented Programming Systems Languages and Applications, October 2013, pp.677-692.
33. LeBlanc T J, Mellor-Crummey J M. Debugging parallel programs with instant replay. / IEEE Trans. Comput., 1987, 36(4):471-482. CrossRef
34. Lee D, Chen P M, Flinn J, Narayanasamy S. Chimera: Hybrid program analysis for determinism. In / Proc. the 33rd PLDI, June 2012, pp.463-474.
35. Subhraveti D, Nieh J. Record and Transplay: Partial checkpointing for replay debugging across heterogeneous systems. In / Proc. ACM Int. Conf. Measurement and Modeling of Computer Systems, June 2011, pp.109-120.
36. Lu K, Zhou X, Wang X, Zhang W, Li G. RaceFree: An efficient multi-threading model for determinism. / SIGPLAN Not., 2013, 48(8):297-298. CrossRef - 刊物类别：Computer Science
- 刊物主题：Computer Science, general
Software Engineering
Theory of Computation
Data Structures, Cryptology and Information Theory
Artificial Intelligence and Robotics
Information Systems Applications and The Internet
Chinese Library of Science - 出版者：Springer Boston
- ISSN：1860-4749
文摘
Determinism is very useful to multithreaded programs in debugging, testing, etc. Many deterministic approaches have been proposed, such as deterministic multithreading (DMT) and deterministic replay. However, these systems either are inefficient or target a single purpose, which is not flexible. In this paper, we propose an efficient and flexible deterministic framework for multithreaded programs. Our framework implements determinism in two steps: relaxed determinism and strong determinism. Relaxed determinism solves data races efficiently by using a proper weak memory consistency model. After that, we implement strong determinism by solving lock contentions deterministically. Since we can apply different approaches for these two steps independently, our framework provides a spectrum of deterministic choices, including nondeterministic system (fast), weak deterministic system (fast and conditionally deterministic), DMT system, and deterministic replay system. Our evaluation shows that the DMT configuration of this framework could even outperform a state-of-the-art DMT system.