Brief Announcement: Performance prediction for coarse-grained locking

conference paper Brief Announcement: Performance prediction for coarse-grained locking published yes Vitaly Aksenov author Dan-Adrian Alistarh author 4A899BFC-F248-11E8-B48F-1D18A9856A870000-0003-3650-940X Petr Kuznetsov author DaAl department PODC: Principles of Distributed Computing A standard design pattern found in many concurrent data structures, such as hash tables or ordered containers, is an alternation of parallelizable sections that incur no data conflicts and critical sections that must run sequentially and are protected with locks. A lock can be viewed as a queue that arbitrates the order in which the critical sections are executed, and a natural question is whether we can use stochastic analysis to predict the resulting throughput. As a preliminary evidence to the affirmative, we describe a simple model that can be used to predict the throughput of coarse-grained lock-based algorithms. We show that our model works well for CLH lock, and we expect it to work for other popular lock designs such as TTAS, MCS, etc. ACM2018Egham, United Kingdom eng Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18 9781450357951 00045818690005210.1145/3212734.3212785 411-413 V. Aksenov, D.-A. Alistarh, P. Kuznetsov, in:, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC ’18, ACM, 2018, pp. 411–413. V. Aksenov, D.-A. Alistarh, and P. Kuznetsov, “Brief Announcement: Performance prediction for coarse-grained locking,” in Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC ’18, Egham, United Kingdom, 2018, pp. 411–413. Aksenov, Vitaly, Dan-Adrian Alistarh, and Petr Kuznetsov. “Brief Announcement: Performance Prediction for Coarse-Grained Locking.” In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC ’18, 411–13. ACM, 2018. <a href="https://doi.org/10.1145/3212734.3212785">https://doi.org/10.1145/3212734.3212785</a>. Aksenov V, Alistarh D-A, Kuznetsov P. Brief Announcement: Performance prediction for coarse-grained locking. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC ’18. ACM; 2018:411-413. doi:<a href="https://doi.org/10.1145/3212734.3212785">10.1145/3212734.3212785</a> Aksenov V, Alistarh D-A, Kuznetsov P. 2018. Brief Announcement: Performance prediction for coarse-grained locking. Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC ’18. PODC: Principles of Distributed Computing, 411–413. Aksenov, Vitaly, et al. “Brief Announcement: Performance Prediction for Coarse-Grained Locking.” Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC ’18, ACM, 2018, pp. 411–13, doi:<a href="https://doi.org/10.1145/3212734.3212785">10.1145/3212734.3212785</a>. Aksenov, V., Alistarh, D.-A., & Kuznetsov, P. (2018). Brief Announcement: Performance prediction for coarse-grained locking. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC ’18 (pp. 411–413). Egham, United Kingdom: ACM. <a href="https://doi.org/10.1145/3212734.3212785">https://doi.org/10.1145/3212734.3212785</a> 59642019-02-13T10:08:19Z2025-06-03T11:58:00Z