Распределенная очередь без использования блокировок в модели удаленного доступа к памяти | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2023. № 62. DOI: 10.17223/19988605/62/2

Распределенная очередь без использования блокировок в модели удаленного доступа к памяти

При разработке программного обеспечения для распределенных вычислительных систем в стандарте MPI наравне с моделью передачи сообщений (message-passing) используется модель удаленного доступа к памяти (remote memory access, MPI RMA, RMA). Модель во многих случаях позволяет повысить эффективность и упростить разработку параллельных программ. В рамках RMA имеют место задачи синхронизации параллельных процессов и потоков при обеспечении доступа к разделяемым (распределенным) структурам данных. В системах с общей памятью для аналогичной задачи активно используется неблокирующая синхронизация (non-blocking), гарантирующая прогресс выполнения операций (lock-free, wait-free, obstruction-free). При таком подходе задержка выполнения операций одним процессом не останавливает выполнения остальных процессов. Мы предполагаем, что такой подход может быть эффективным и при построении распределенных структур данных в модели RMA. Нами рассматривается идея построения неблокируемых распределенных структур данных в RMA на примере очереди, описаны построенные алгоритмы для выполнения основных операций, исследуется эффективность структуры данных, приведено экспериментальное сравнение с блокируемыми аналогами. Вклад авторов: все авторы сделали эквивалентный вклад в подготовку публикации. Авторы заявляют об отсутствии конфликта интересов.

Скачать электронную версию публикации

Загружен, раз: 15

Ключевые слова

распределенная очередь, неблокирующие структуры данных, удаленный доступ к памяти, MPI, MPI RMA, lock-free, one-sided communications

Авторы

ФИО	Организация	Дополнительно	E-mail
Бураченко Александр Викторович	Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»	магистрант	ss47305@gmail.com
Пазников Алексей Александрович	Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»	кандидат технических наук, доцент	apaznikov@gmail.com
Державин Денис Павлович	Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»	магистрант	derzhavinden002@gmail.com

Всего: 3

Ссылки

Liu J., Wu J., Panda D.K. High performance RDMA-based MPI implementation over InfiniBand // International Journal of Parallel Programming. 2004. V. 32. P. 167-198.

Hoefler T., Dinan J., Thakur R., Barrett B., Balaji P., Gropp W., Underwood K. Remote memory access programming in MPI-3 // ACM Transactions on Parallel Computing. 2015. V. 2 (2). Art. 9. 26 р.

Gerstenberger R., Besta M., Hoefler T. Enabling Highly-Scalable Remote Memory Access Programming with MPI-3 One Sided // Scientific Programming. 2014. V. 2, is. 2. P. 75-91.

Herlihy M., Shavit N. The art of multiprocessor programming. Amsterdam et al.: Morgan Kaufmann, 2012. 537 p.

Schuchart J., Niethammer C., Gracia J., Bosilca G. Quo Vadis MPI RMA? Towards a More Efficient Use of MPI One-Sided Communication // arXiv: 2111.08142. 2021.

Mark M., Shavit N. Concurrent Data Structures. Chapman and Hall/CRC Press, 2004. 32 p.

Shavit N. Data structures in the multicore age // Communications of the ACM. 2011. V. 54. P. 76-84.

Пазников А.А. Оптимизация делегирования выполнения критических секций на выделенных процессорных ядрах // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2017. № 38. С. 52-58.

Аненков А.Д., Пазников А.А. Алгоритмы оптимизации масштабируемого потокобезопасного пула на основе распределя ющих деревьев для многоядерных вычислительных систем // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2017. № 39. С. 73-84.

Calciu I., Gottschlich J., Herlihy M. Using elimination and delegation to implement a scalable NUMA-friendly stack // 5th {USENIX} Workshop on Hot Topics in Parallelism (HotPar 13). 2013. P. 1-7.

Brock B., Buluc A. BCL: A cross-platform distributed data structures library // ICPP. 2019. P. 1-10.

Schuchart J., Bouteiller A., Bosilca G. Using MPI-3 RMA for active messages // ExaMPI. 2019. P. 47-56.

Diep T.D., Furlinger K. Nonblocking data structures for distributed-memory machines: stacks as an example // 2021 29th Euromicro Int. Conf on Parallel, Distributed and Network-Based Processing (PDP). IEEE, 2021. С. 9-17.