Processor-Oblivious Record and Replay

Abstract

Record-and-replay systems are useful tools for debugging non-deterministic parallel programs by first recording an execution and then replaying that execution to produce the same access pattern. Existing record-and-replay systems generally target thread-based execution models, and record the behaviors and interleavings of individual threads. Dynamic multithreaded languages and libraries, such as the Cilk family, OpenMP, TBB, etc., do not have a notion of threads. Instead, these languages provide a processor-oblivious model of programming, where programs expose task-parallelism using high-level constructs such as spawn/sync without regard to the number of threads/cores available to run the program. Thread-based record-and-replay would violate the processor-oblivious nature of these programs, as they incorporate the number of threads into the recorded information, constraining the replayed execution to the same number of threads.

In this paper, we present a processor-oblivious record-and-replay scheme for such languages where record and replay can use different number of processors and both are scheduled using work stealing. We provide theoretical guarantees for our record and replay scheme --- namely that record is optimal for programs with one lock and replay is near-optimal for all cases. In addition, we implemented this scheme in the Cilk Plus runtime system and our evaluation indicates that processor-obliviousness does not cause substantial overheads.

References

1. K. Agrawal, J. T. Fineman, K. Lu, B. Sheridan, J. Sukha, and R. Utterback. Provably good scheduling for parallel programs that use data structures through implicit batching. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '14, pages 84--95, New York, NY, USA, 2014. ACM. ISBN 978-1-4503-2821-0. 10.1145/2612669.2612688. URL http://doi.acm.org/10.1145/2612669.2612688.
2. G. Altekar and I. Stoica. Odr: output-deterministic replay for multicore debugging. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating systems principles, SOSP '09, pages 193--206, New York, NY, USA, 2009. ACM. ISBN 978-1-60558-752-3. URL http://doi.acm.org/10.1145/1629575.1629594.
3. N. S. Arora, R. D. Blumofe, and C. G. Plaxton. Thread scheduling for multiprogrammed multiprocessors. In 10th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 119--129, 1998.
4. A. Aviram, S.-C. Weng, S. Hu, and B. Ford. Efficient System-Enforced Deterministic Parallelism. In USENIX Symposium on Operating Systems Design and Implementation, pages 1--16, 2010.
5. B. Awerbuch, Y. Azar, S. Leonardi, and O. Regev. Minimizing the flow time without migration. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 198--205, May 1999.
6. E. Ayguade, N. Copty, A. Duran, J. Hoeflinger, Y. Lin, F. Massaioli, X. Teruel, P. Unnikrishnan, and G. Zhang. The design of OpenMP tasks. IEEE Transactions on Parallel and Distributed Systems, 20 (3): 404--418, Mar. 2009. URL http://dx.doi.org/10.1109/TPDS.2008.105.
7. Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal. Balanced allocations. SIAM Journal Comput., 29 (1): 180--200, Sept. 1999. ISSN 0097-5397. 10.1137/S0097539795288490. URL http://dx.doi.org/10.1137/S0097539795288490.
8. Cavè, Chatterjee, Guo, Peixotto, Raman, Shirako, Taşırlar, Yan, Zhao, and Sarkar]BarikBuCa09R. Barik, Z. Budimlić, V. Cavè, S. Chatterjee, Y. Guo, D. Peixotto, R. Raman, J. Shirako, S. Taşırlar, Y. Yan, Y. Zhao, and V. Sarkar. The Habanero multicore software research project. In Proceedings of the 24th ACM SIGPLAN Conference Companion on Object Oriented Programming Systems Languages and Applications, OOPSLA '09, pages 735--736, Orlando, Florida, USA, 2009. ACM. ISBN 978-1-60558-768-4.
9. M. A. Bender, J. T. Fineman, S. Gilbert, and C. E. Leiserson. On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs. In 16th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 133--144, 2004.
10. Bergan, Anderson, Devietti, Ceze, and Grossman]coredet-2010T. Bergan, O. Anderson, J. Devietti, L. Ceze, and D. Grossman. CoreDet: A Compiler and Runtime System for Deterministic Multithreaded Execution. In ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 53--64, 2010\natexlaba. http://doi.acm.org/10.1145/1736020.1736029.
11. Bergan, Hunt, Ceze, and Gribble]dosT. Bergan, N. Hunt, L. Ceze, and S. D. Gribble. Deterministic process groups in dos. In Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation, OSDI'10, pages 177--191, Berkeley, CA, USA, 2010\natexlabb. USENIX Association. URL http://dl.acm.org/citation.cfm?id=1924943.1924956.
12. E. D. Berger, T. Yang, T. Liu, and G. Novark. Grace: Safe Multithreaded Programming for C/C
13. . In ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 81--96, 2009. http://doi.acm.org/10.1145/1640089.1640096.
14. C. Bienia and K. Li. Characteristics of workloads using the pipeline programming model. In Proceedings of the 3rd Workshop on Emerging Applications and Many-core Architecture, June 2010.
15. C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC benchmark suite: Characterization and architectural implications. In Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques, October 2008.
16. G. E. Blelloch, J. T. Fineman, P. B. Gibbons, and J. Shun. Internally deterministic parallel algorithms can be fast. In Proceedings of Principles and Practice of Parallel Programming, pages 181--192, 2012.
17. R. D. Blumofe. Executing Multithreaded Programs Efficiently. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, Sept. 1995. Available as MIT Laboratory for Computer Science Technical Report MIT/LCS/TR-677.
18. R. D. Blumofe and C. E. Leiserson. Scheduling multithreaded computations by work stealing. Journal of the ACM, 46 (5): 720--748, Sept. 1999.
19. R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul, C. E. Leiserson, K. H. Randall, and Y. Zhou. Cilk: An efficient multithreaded runtime system. Journal of Parallel and Distributed Computing, 37 (1): 55--69, 1996.
20. R. L. Bocchino, Jr., V. S. Adve, S. V. Adve, and M. Snir. Parallel Programming Must Be Deterministic by Default. In USENIX Conference on Hot Topics in Parallelism, pages 4--9, 2009.
21. and Huang]roctet-pppj-2015M. D. Bond, M. Kulkarni, M. Cao, M. Fathi Salmi, and J. Huang. Efficient Deterministic Replay of Multithreaded Executions in a Managed Language Virtual Machine. In ACM International Conference on Principles and Practice of Programming in Java, pages 90--101, 2015.
22. R. E. Bryant and D. R. O'Hallaron. Computer Systems: A Programmer's Perspective. Pearson, USA, 3rd edition, 2015.
23. S. Burckhardt, A. Baldassin, and D. Leijen. Concurrent programming with revisions and isolation types. In Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 691--707, Reno/Tahoe, Nevada, USA, Oct. 2010. URL http://doi.acm.org/10.1145/1869459.1869515.
24. t al.(2011)Cavé, Zhao, Shirako, and Sarkar]CaveZhSh11V. Cavé, J. Zhao, J. Shirako, and V. Sarkar. Habanero-Java: the new adventures of old X10. In Proceedings of the 9th International Conference on Principles and Practice of Programming in Java, PPPJ '11, pages 51--61, 2011.
25. P. Charles, C. Grothoff, V. Saraswat, C. Donawa, A. Kielstra, K. Ebcioglu, C. von Praun, and V. Sarkar. X10: An object-oriented approach to non-uniform cluster computing. In 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 519--538, 2005. URL http://doi.acm.org/10.1145/1094811.1094852.
26. G.-I. Cheng, M. Feng, C. E. Leiserson, K. H. Randall, and A. F. Stark. Detecting data races in Cilk programs that use locks. In Proceedings of the 10th ACM Symposium on Parallel Algorithms and Architectures, SPAA '98, 1998.
27. J. Devietti, B. Lucia, L. Ceze, and M. Oskin. DMP: Deterministic Shared Memory Multiprocessing. In ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 85--96, 2009. http://doi.acm.org/10.1145/1508244.1508255.
28. J. Devietti, J. Nelson, T. Bergan, L. Ceze, and D. Grossman. RCDC: A Relaxed Consistency Deterministic Computer. In ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 67--78, 2011. http://doi.acm.org/10.1145/1950365.1950376.
29. E. W. Dijkstra. Co-operating sequential processes. In F. Genuys, editor, Programming Languages, pages 43--112. Academic Press, London, England, 1968. Originally published as Technical Report EWD-123, Technological University, Eindhoven, the Netherlands, 1965.
30. G. W. Dunlap, D. G. Lucchetti, M. A. Fetterman, and P. M. Chen. Execution Replay of Multiprocessor Virtual Machines. In ACM/USENIX International Conference on Virtual Execution Environments, pages 121--130, 2008. http://doi.acm.org/10.1145/1346256.1346273.
31. M. Feng and C. E. Leiserson. Efficient detection of determinacy races in Cilk programs. In SPAA, 1997.
32. J. T. Fineman and C. E. Leiserson. Race detectors for Cilk and Cilk
33. programs. In D. Padua, editor, Encyclopedia of Parallel Computing, pages 1706--1719. Springer, 2011.
34. M. Frigo, C. E. Leiserson, and K. H. Randall. The implementation of the Cilk-5 multithreaded language. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 212--223, 1998.
35. M. Frigo, P. Halpern, C. E. Leiserson, and S. Lewin-Berlin. Reducers and other Cilk
36. hyperobjects. In 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures, pages 79--90, 2009.
37. A. Georges, M. Christiaens, M. Ronsse, and K. De Bosschere. JaRec: A Portable Record/Replay Environment for Multi-threaded Java Applications. Software Practice & Experience, 34 (6): 523--547, 2004. ISSN 0038-0644. 10.1002/spe.579.
38. Y. He, C. E. Leiserson, and W. M. Leiserson. The Cilkview scalability analyzer. In Proceedings of the Twenty-Second Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'10), pages 145--156, Santorini, Greece, June 13-15 2010. 10.1145/1810479.1810509.
39. D. R. Hower, P. Montesinos, L. Ceze, M. D. Hill, and J. Torrellas. Two Hardware-Based Approaches for Deterministic Multiprocessor Replay. Communications of the ACM, 52: 93--100, 2009. ISSN 0001-0782. http://doi.acm.org/10.1145/1516046.1516068.
40. J. Huang, C. Zhang, and J. Dolby. CLAP: Recording Local Executions to Reproduce Concurrency Failures. In ACM Conference on Programming Language Design and Implementation, pages 141--152, 2013. 10.1145/2491956.2462167.
41. ]Posix97Institute of Electrical and Electronic Engineers. Information technology -- Portable Operating System Interface (POSIX) -- Part 1: System application program interface (API) [C language]. IEEE Standard 1003.1, 1996 Edition.
42. TBB. Intel(R) Threading Building Blocks. Intel Corporation, 2009. Available from http://www.threadingbuildingblocks.org/documentation.php.
43. Intel. Intel Cilk Plus Language Specification. Intel Corporation, 2010. Document Number: 324396-001US. Available from http://software.intel.com/sites/products/cilk-plus/cilk_plus_language_specification.pdf.
44. O. Laadan, N. Viennot, and J. Nieh. Transparent, Lightweight Application Execution Replay on Commodity Multiprocessor Operating Systems. In ACM SIGMETRICS Joint International Conference on Measurement and Modeling of Computer Systems, pages 155--166, 2010. ISBN 978-1-4503-0038-4. 10.1145/1811039.1811057. URL http://doi.acm.org/10.1145/1811039.1811057.
45. T. J. LeBlanc and J. M. Mellor-Crummey. Debugging Parallel Programs with Instant Replay. IEEE Transactions on Computers, 36: 471--482, 1987. ISSN 0018-9340. http://dx.doi.org/10.1109/TC.1987.1676929.
46. D. Lee, B. Wester, K. Veeraraghavan, S. Narayanasamy, P. M. Chen, and J. Flinn. Respec: Efficient Online Multiprocessor Replay via Speculation and External Determinism. In ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 77--90, 2010. http://doi.acm.org/10.1145/1736020.1736031.
47. D. Lee, P. M. Chen, J. Flinn, and S. Narayanasamy. Chimera: Hybrid Program Analysis for Determinism. In ACM Conference on Programming Language Design and Implementation, pages 463--474, 2012. 10.1145/2254064.2254119.
48. I.-T. A. Lee and T. B. Schardl. Efficiently detecting races in cilk programs that use reducer hyperobjects. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA'15), pages 111--122, Portland, OR, USA, June 2015. 10.1145/2755573.2755599.
49. D. Leijen and J. Hall. Optimize managed code for multi-core machines. MSDN Magazine, 2007. Available from http://msdn.microsoft.com/magazine/.
50. C. E. Leiserson, T. B. Schardl, and J. Sukha. Deterministic parallel random-number generation for dynamic-multithreading platforms. In PPoPP, 2012.
51. P. Liu, X. Zhang, O. Tripp, and Y. Zheng. Light: Replay via Tightly Bounded Recording. In ACM Conference on Programming Language Design and Implementation, pages 55--64, 2015. ISBN 978-1-4503-3468-6. 10.1145/2737924.2738001.
52. T. Liu, C. Curtsinger, and E. D. Berger. Dthreads: Efficient Deterministic Multithreading. In ACM Symposium on Operating Systems Principles, pages 327--336, 2011. http://doi.acm.org/10.1145/2043556.2043587.
53. C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. Pin: building customized program analysis tools with dynamic instrumentation. In Proceedings of the ACM SIGPLAN 2005 Conference on Programming Language Design and Implementation (PLDI'05), pages 190--200, Chicago, IL, USA, June 11-15 2005. 10.1145/1065010.1065034.
54. J. Mellor-Crummey. On-the-fly detection of data races for programs with nested fork-join parallelism. In Proceedings of the 1991 ACM/IEEE Conference on Supercomputing (Supercomputing '91), pages 24--33, Albuquerque, NM, USA, Nov. 18-22 1991. 10.1145/125826.125861.
55. S. K. Muller and U. A. Acar. Latency-hiding work stealing: Scheduling interacting parallel computations with work stealing. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '16, pages 71--82, New York, NY, USA, 2016. ACM. ISBN 978-1-4503-4210-0. 10.1145/2935764.2935793. URL http://doi.acm.org/10.1145/2935764.2935793.
56. S. Narayanasamy, C. Pereira, and B. Calder. Recording Shared Memory Dependencies Using Strata. In ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 229--240, 2006. http://doi.acm.org/10.1145/1168857.1168886.
57. D. Nguyen, A. Lenharth, and K. Pingali. Deterministic galois: On-demand, portable and parameterless. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '14, pages 499--512, New York, NY, USA, 2014. ACM. ISBN 978-1-4503-2305-5. 10.1145/2541940.2541964. URL http://doi.acm.org/10.1145/2541940.2541964.
58. M. Olszewski, J. Ansel, and S. Amarasinghe. Kendo: Efficient Deterministic Multithreading in Software. In ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 97--108, 2009. http://doi.acm.org/10.1145/1508244.1508256.
59. S. Park, Y. Zhou, W. Xiong, Z. Yin, R. Kaushik, K. H. Lee, and S. Lu. PRES: Probabilistic Replay with Execution Sketching on Multiprocessors. In ACM Symposium on Operating Systems Principles, pages 177--192, 2009. http://doi.acm.org/10.1145/1629575.1629593.
60. H. Patil, C. Pereira, M. Stallcup, G. Lueck, and J. Cownie. PinPlay: A framework for deterministic replay and reproducible analysis of parallel programs. In Proceedings of the 8th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO '10, pages 2--11, Toronto, Ontario, Canada, 2010. ACM. ISBN 978-1-60558-635-9. 10.1145/1772954.1772958. URL http://doi.acm.org/10.1145/1772954.1772958.
61. G. Pokam, C. Pereira, K. Danne, R. Kassa, and A.-R. Adl-Tabatabai. Architecting a Chunk-based Memory Race Recorder in Modern CMPs. In IEEE/ACM International Symposium on Microarchitecture, pages 576--585, 2009. http://doi.acm.org/10.1145/1669112.1669183.
62. R. Raman, J. Zhao, V. Sarkar, M. Vechev, and E. Yahav. Efficient data race detection for async-finish parallelism. In H. Barringer, Y. Falcone, B. Finkbeiner, K. Havelund, I. Lee, G. Pace, G. Rosu, O. Sokolsky, and N. Tillmann, editors, Runtime Verification, volume 6418 of Lecture Notes in Computer Science, pages 368--383. Springer Berlin / Heidelberg, 2010. ISBN 978-3-642-16611-2.
63. R. Raman, J. Zhao, V. Sarkar, M. Vechev, and E. Yahav. Scalable and precise dynamic datarace detection for structured parallelism. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '12, pages 531--542, 2012.
64. M. C. Rinard and M. S. Lam. The Design, Implementation, and Evaluation of Jade. ACM Transactions on Programming Languages and Systems, 20: 483--545, 1998. ISSN 0164-0925. http://doi.acm.org/10.1145/291889.291893.
65. A. D. Robison. Cilk Plus solver for a chess puzzle or: How i learned to love fast rejection. https://software.intel.com/en-us/articles/cilk-plus-solver-for-a-chess-puzzle-or-how-i-learned-to-love-rejection, Feb. 2013.
66. M. Ronsse and K. De Bosschere. RecPlay: A Fully Integrated Practical Record/Replay System. ACM Transactions on Computer Systems, 17: 133--152, 1999. ISSN 0734-2071. http://doi.acm.org/10.1145/312203.312214.
67. T. B. Schardl, B. C. Kuszmaul, I.-T. A. Lee, W. M. Leiserson, and C. E. Leiserson. The Cilkprof scalability profiler. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA '15), SPAA '15, pages 89--100, Portland, Oregon, USA, June 2015. 10.1145/2755573.2755603.
68. J. Shun, G. E. Blelloch, J. T. Fineman, P. B. Gibbons, A. Kyrola, H. V. Simhadri, and K. Tangwongsan. Brief announcement: the Problem Based Benchmark Suite. In Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '12, 2012.
69. N. R. Tallent and J. M. Mellor-Crummey. Effective performance measurement and analysis of multithreaded applications. In Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '09, pages 229--240, Raleigh, NC, USA, 2009. ACM. ISBN 978-1-60558-397-6. 10.1145/1504176.1504210. URL http://doi.acm.org/10.1145/1504176.1504210.
70. R. Utterback, K. Agrawal, J. T. Fineman, and I.-T. A. Lee. Provably good and practically efficient parallel race detection for fork-join programs. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '16, pages 83--94, New York, NY, USA, 2016. ACM. ISBN 978-1-4503-4210-0. 10.1145/2935764.2935801. URL http://doi.acm.org/10.1145/2935764.2935801.
71. K. Veeraraghavan, D. Lee, B. Wester, J. Ouyang, P. M. Chen, J. Flinn, and S. Narayanasamy. DoublePlay: Parallelizing Sequential Logging and Replay. In ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 15--26, 2011. http://doi.acm.org/10.1145/1950365.1950370.
72. M. Xu, R. Bodik, and M. D. Hill. A "Flight Data Recorder" for Enabling Full-system Multiprocessor Deterministic Replay. In ACM/IEEE International Symposium on Computer Architecture, pages 122--135, 2003. http://doi.acm.org/10.1145/859618.859633.
73. Z. Yang, M. Yang, L. Xu, H. Chen, and B. Zang. ORDER: Object Centric Deterministic Replay for Java. In USENIX Annual Technical Conference, pages 30--30, 2011.
74. C. S. Zakian, T. A. K. Zakian, A. Kulkarni, B. Chamith, and R. R. Newton. Concurrent Cilk: Lazy Promotion from Tasks to Threads in C/C++, pages 73--90. Springer International Publishing, Cham, 2016. ISBN 978-3-319-29778-1. URL http://dx.doi.org/10.1007/978-3-319-29778-1_5.

Index Terms

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms