Development of lock-free approach for shared memory organisation in real-time multi-threading applications

Олександр Васильович Сиротюк

doi:10.15587/2706-5448.2024.309344

Автор(и)

Олександр Васильович Сиротюк Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Україна https://orcid.org/0000-0002-4531-6290

DOI:

https://doi.org/10.15587/2706-5448.2024.309344

Ключові слова:

багатопотоковість, динамічне виділення пам’яті, системи реального часу, неблокуючі алгоритми, ігрові рушії, високонавантажені обчислення

Анотація

Вектор розвитку сучасних центральних процесорів, котрий включає в себе використання все більшої кількості ядер, роблячи ставку на паралелізм, а не на високу потужність конкретної обчислювальної одиниці, ставить нові виклики перед історично-обумовленим дизайном вже існуючого програмного забезпечення. Дана робота зосереджується на дослідженні та вирішенні проблеми доступу до спільної пам’яті в багатопотокових середовищах, таких як операційні системи, інтерактивні розподілені обчислювальні системи, високоефективні системи для проведення симуляцій. Отже, об’єктом дослідження є неблокуючі підходи щодо організації доступу до пам’яті та виконання основних операцій з нею за допомогою неблокуючої синхронізації.

Методи дослідження включають в себе розробку підходу організації доступу до спільної пам’яті за допомогою алгоритму двійників, з подальшим теоретичним та практичним порівнянням отриманого результату зі звичайним алгоритмом двійників на основі блокуючого доступу до спільної пам’яті для різної конфігурації кількості потоків та кількості одночасних спроб доступу до пам’яті. Додатково проводилося тестування в рамках неназваного проекту з закритим кодом, у вигляді інтеграції даного рішення в нього, з подальшим A/B тестуванням.

Результати показали, що використання неблокуючих підходів є доцільним, особливо в порівнянні з підходами, що використовують блокування, котрі показали деградацію швидкодії відносно стандартного алгоритму алокації на більше ніж 300 %, в той час як неблокуючі підходи надали приріст в 40–90 %. Також було отримано, що використання гібридних підходів до організації системи спільної пам’яті на рівні програмного забезпечення може привести до більш стабільного результату та пом’якшити деградацію швидкодії застосунку в порівнянні з класичними підходами типу алгоритму двійників чи вільного списку.

Не дивлячись на отримані результати, автор все ще з застереженням відноситься до ідеї управління пам’яттю та організації пулів пам’яті на рівні програмного забезпечення, та не рекомендує використовувати спеціалізовані алгоритми алокації без нагальної потреба, з метою пришвидшення саме алокації пам’яті. Мета даних структур все ще залишається не в покращені швидкодії програмного забезпечення напряму, а в покращенні та пришвидшені доступу до даних, що зберігаються в них.

Біографія автора

Олександр Васильович Сиротюк, Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»

Аспірант

Кафедра системного проектування

Посилання

Ross, P. E. (2008). Why CPU Frequency Stalled. IEEE Spectrum, 45 (4), 72–72. https://doi.org/10.1109/mspec.2008.4476447
Efnusheva, D., Cholakoska, A., Tentov, A. (2017). A Survey of Different Approaches for Overcoming the Processor – Memory Bottleneck. International Journal of Computer Science and Information Technology, 9 (2), 151–163. https://doi.org/10.5121/ijcsit.2017.9214
Barnes, N., Brooksby, R. (2002). Thirty person-years of memory management development goes Open Source. Available at: https://www.ravenbrook.com/project/mps/doc/2002-01-30/ismm2002-paper/ismm2002.html
Ferreira, T. B., Matias, R., Macedo, A., Araujo, L. B. (2011). An Experimental Study on Memory Allocators in Multicore and Multithreaded Applications. 2011 12th International Conference on Parallel and Distributed Computing, Applications and Technologies. https://doi.org/10.1109/pdcat.2011.18
Carribault, P., Pérache, M., Jourdren, H. (2011). Thread-Local Storage Extension to Support Thread-Based MPI/OpenMP Applications. Lecture Notes in Computer Science. Springer, 80–93. https://doi.org/10.1007/978-3-642-21487-5_7
Von Puttkamer, E. (1975). A Simple Hardware Buddy System Memory Allocator. IEEE Transactions on Computers, C–24 (10), 953–957. https://doi.org/10.1109/t-c.1975.224100
Larson, P.-Å., Krishnan, M. (1998). Memory allocation for long-running server applications. Proceedings of the 1st International Symposium on Memory Management. https://doi.org/10.1145/286860.286880
Marotta, R., Ianni, M., Scarselli, A., Pellegrini, A., Quaglia, F. (2018). A Non-blocking Buddy System for Scalable Memory Allocation on Multi-core Machines. 2018 IEEE International Conference on Cluster Computing (CLUSTER). https://doi.org/10.1109/cluster.2018.00034
Devkota, P. P. (2023). Dynamic Memory Allocation: Implementation and Misuse. https://doi.org/10.13140/RG.2.2.34993.97129
Xu, J., Dou, Y., Song, J., Zhang, Y., Xia, F. (2008). Design and Synthesis of a High-Speed Hardware Linked-List for Digital Image Processing. 2008 Congress on Image and Signal Processing. https://doi.org/10.1109/cisp.2008.338
Braginsky, A., Petrank, E. (2011). Locality-Conscious Lock-Free Linked Lists. Lecture Notes in Computer Science. Springer, 107–118. https://doi.org/10.1007/978-3-642-17679-1_10
Senhadji-Navarro, R., Garcia-Vargas, I. (2018). High-Performance Architecture for Binary-Tree-Based Finite State Machines. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 37 (4), 796–805. https://doi.org/10.1109/tcad.2017.2731678
Klein, N., Harel, E., Levi, I. (2021). The Cost of a True Random Bit – On the Electronic Cost Gain of ASIC Time-Domain-Based TRNGs. Cryptography, 5 (3), 25. https://doi.org/10.3390/cryptography5030025
Beznosyk, O., Syrotiuk, O. (2023). Usage of a computer cluster for physics simulations using bullet engine and OpenCL. Technology Audit and Production Reserves, 4 (2 (72)), 6–9. https://doi.org/10.15587/2706-5448.2023.285543