Исследование эффективности потокобезопасных очередей на устройствах с асимметричным набором ядер
Аннотация
В рамках статьи было проведено исследование зависимости пропускной способности потокобезопасных очередей от количества push- и pop-потоков при различных сопровождающих нагрузках для каждого пропускаемого элемента. В результате поиска подходов к созданию потокобезопасных очередей для исследования были выбраны singlе lock queue, two lock queue и lock free queue, для каждого из них была проведена предварительная оценка преимуществ и недостатков, которые могут повлиять на итоговую производительность. Очереди были реализованы с учетом специфики работы с устройствами с асимметричным набором ядер и с минимально необходимыми накладными расходами по времени CPU. Для исследования пропускной способности были реализованы бенчмарки, которые отражают сценарии использования очередей одинаковым количеством push- и pop-потоков при различной полезной нагрузке. Параметризация нагрузки реализована при помощи множителя вычислений. Этот подход позволяет учесть различие ядер одного устройства в мощности. Измерения проводились на двух устройствах: P50pro и Mate60pro. Такой выбор обусловлен тем, что P50pro имеет меньше ядер, чем Mate60pro, однако частота ядер у P50pro выше. В результате была получена эмпирическая зависимость эффективности работы очередей, из которой можно сделать выводы об области применимости той или иной очереди на разных устройствах. Для устройства с большим числом ядер lock free queue очередь либо выигрывает, либо эквивалентна two lock queue очереди при любой нагрузке, кроме нулевой. На устройстве с небольшим числом ядер two lock queue очередь выигрывает при низких нагрузках, lock free queue выигрывает при высоких. Эта зависимость позволяет оценить наиболее эффективное количество ядер для работы с очередью при известных нагрузках на каждый пропускаемый элемент, а значит, позволяет получить максимальную производительность на одно ядро.
Литература
2. Sallow A.B. Android Multi-threading Program Execution on single and multi-core CPUs with Matrix multiplication. International Journal of Engineering & Technology. 2018;7(4):6603-6608. https://doi.org/10.14419/ijet.v7i4.29340
3. Marcu M., et al. Power Efficiency Study of Multi-threading Applications for Multi-core Mobile Systems. WSEAS Transactions on Computers. 2008;7(12):1875-1885. Available at: http://www.wseas.us/e-library/transactions/computers/2008/27-687.pdf (accessed 03.06.2024).
4. Herlihy M., Moss J.E.B. Transactional memory: architectural support for lock-free data structures. ACM SIGARCH Computer Architecture News. 1993;21(2):289-300. https://doi.org/10.1145/173682.165164
5. Barnes G. A method for implementing lock-free shared-data structures. In: Proceedings of the fifth annual ACM symposium on Parallel Algorithms and Architectures (SPAA '93). New York, NY, USA: Association for Computing Machinery; 1993. p. 261-270. https://doi.org/10.1145/165231.165265
6. Goncharenko E.A., Paznikov A.A., Tabakov A.V. Evaluating the performance of atomic operations on modern multicore systems. Journal of Physics: Conference Series. 2019;1399(3):033107. https://doi.org/10.1088/1742-6596/1399/3/033107
7. Hoseini F., Atalar A., Tsigas P. Modeling the Performance of Atomic Primitives on Modern Architectures. In: Proceedings of the 48th International Conference on Parallel Processing (ICPP '19). New York, NY, USA: Association for Computing Machinery; 2019. Article number: 28. https://doi.org/10.1145/3337821.3337901
8. Maffione V., Lettieri G., Rizzo L. Cache‐aware design of general‐purpose Single‐Producer-Single‐Consumer queues. Software: Practice and Experience. 2019;49(5):748-779. https://doi.org/10.1002/spe.2675
9. Koval N., Alistarh D., Elizarov R. Scalable FIFO Channels for Programming via Communicating Sequential Processes. In: Yahyapour R. (Eds.) Euro-Par 2019: Parallel Processing. Euro-Par 2019. Lecture Notes in Computer Science. Vol. 11725. Cham: Springer; 2019. p. 317-333. https://doi.org/10.1007/978-3-030-29400-7_23
10. Nikolaev R., Ravindran B. WCQ: A Fast Wait-Free Queue with Bounded Memory Usage. In: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '22). New York, NY, USA: Association for Computing Machinery; 2022. p. 307-319. https://doi.org/10.1145/3490148.3538572
11. Kogan A., Petrank E. Wait-free queues with multiple enqueuers and dequeuers. In: Proceedings of the 16th ACM symposium on Principles and practice of parallel programming (PPoPP '11). New York, NY, USA: Association for Computing Machinery; 2011. p. 223-234. https://doi.org/10.1145/1941553.1941585
12. Alistarh D., Censor-Hillel K., Shavit N. Are lock-free concurrent algorithms practically wait-free? Journal of the ACM. 2016;63(4):31. https://doi.org/10.1145/2903136
13. Michael M.M., Scott M.L. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing (PODC '96). New York, NY, USA: Association for Computing Machinery; 1996. p. 267-275. https://doi.org/10.1145/248052.248106
14. Rodrigues F.V., Guinde N.B. Performance Analysis of Big.LITTLE System with Various Branch Prediction Schemes. In: Verma G.K., Soni B., Bourennane S., Ramos A.C.B. (eds.) Data Science. Transactions on Computer Systems and Networks. Singapore: Springer; 2021. p. 59-72. https://doi.org/10.1007/978-981-16-1681-5_5
15. Pöter M., Träff J.L. Memory Models for C/C++ Programmers. arXiv:1803.04432. 2018. https://doi.org/10.48550/arXiv.1803.04432
16. Kamil S., et al. Impact of modern memory subsystems on cache optimizations for stencil computations. In: Proceedings of the 2005 workshop on Memory system performance (MSP '05). New York, NY, USA: Association for Computing Machinery; 2005. p. 36-43. https://doi.org/10.1145/1111583.1111589
17. Asgharzadeh A., et al. Free atomics: hardware atomic operations without fences. In: Proceedings of the 49th Annual International Symposium on Computer Architecture (ISCA '22). New York, NY, USA: Association for Computing Machinery; 2022. p. 14-26. https://doi.org/10.1145/3470496.3527385
18. Bolosky W.J., Scott M.L. False sharing and its effect on shared memory performance. In: 4th Symp. on Experiences with Distributed and Multiprocessor Systems (SEDMS'93). San Diego, CA, USA: USENIX Association; 1993. p. 1-15. Available at: https://www.cs.rochester.edu/u/scott/papers/1993_SEDMS_false_sharing.pdf (accessed 03.06.2024).
19. Michael M.M. Hazard pointers: Safe memory reclamation for lock-free objects. IEEE Transactions on Parallel and Distributed Systems. 2004;15(6):491-504. https://doi.org/10.1109/TPDS.2004.8
20. Herlihy M., Luchangco V., Martin P., Moir M. Nonblocking memory management support for dynamic-sized data structures. ACM Transactions on Computer Systems. 2005;23(2):146-196. https://doi.org/10.1145/1062247.1062249
21. Cohen N., Petrank E. Efficient Memory Management for Lock-Free Data Structures with Optimistic Access. In: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures (SPAA '15). New York, NY, USA: Association for Computing Machinery; 2015. p. 254-263. https://doi.org/10.1145/2755573.2755579
22. Gidenstam A., Papatriantafilou M., Sundell H., Tsigas P. Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting. IEEE Transactions on Parallel and Distributed Systems. 2009;20(8):1173-1187. https://doi.org/10.1109/TPDS.2008.167
23. Michael M.M. Scalable lock-free dynamic memory allocation. ACM SIGPLAN Notices. 2004;39(6):35-46. https://doi.org/10.1145/996893.996848
24. Miniskar N.R., Liu F., Vetter J.S. A Memory Efficient Lock-Free Circular Queue. In: 2021 IEEE International Symposium on Circuits and Systems (ISCAS). Daegu, Korea: IEEE Press; 2021. p. 1-5. https://doi.org/10.1109/ISCAS51556.2021.9401239
25. Schweizer H., Besta M., Hoefler T. Evaluating the Cost of Atomic Operations on Modern Architectures. In: Proceedings of the 2015 International Conference on Parallel Architecture and Compilation (PACT) (PACT '15). USA: IEEE Computer Society; 2015. p. 445-456. https://doi.org/10.1109/PACT.2015.24
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
