etu_avtabakov_202001.pdf

Работа поддержана грантом РФФИ № 19-07-00784 «Разработка методов, алгоритмов и программного обеспечения масштабируемой синхронизации для многопроцессорных вычислительных систем», руководитель – Пазников А.А., 2019-2021

• Пазников Алексей Александрович, к.т.н., с.н.с. СПбГЭТУ «ЛЭТИ», руководитель
• Табаков Андрей Викторович, магистрант СПбГЭТУ «ЛЭТИ», исполнитель

При разработке масштабируемых потокобезопасных структур данных (concurrent data structures) для вычислительных систем с общей памятью перспективным является подход на основе ослабления порядка выполнения операций. Используется подход, основанный на представлении потокобезопасных структур данных в виде множества простых структур, распределенных между потоками. При выполнении операций (вставки, удаления элементов) случайным образом выбирается подмножество данных структур. Таким образом, ослабленные структуры данных позволяют избежать синхронизации выполнения операций несколькими потоками одновременно. На основе данного метода реализованы масштабируемые потокобезопасные очередь с приоритетами и стек. Созданы алгоритмы оптимизации выбора очередей из множества при выполнении операций вставки и удаления элементов, а также предложен алгоритм балансировки элементов в очередях. Алгоритмы учитывают иерархическую структуру многоядерных вычислительных систем и обеспечивают локализацию доступа к данным за счет сокращения подмножества очередей для случайного выбора. Разработанные алгоритмы вставки и удаления обеспечивают прирост пропускной способности в 1,2 и 1,6 раза соответственно, по сравнению с оригинальными алгоритмами вставки и удаления. Оптимизация достигается за счёт уменьшения конкуретности потоков (contention) и локализации обращений к памяти при ограничении диапазона выбора сегментов структуры.

• A. V. Tabakov and A. A. Paznikov, "Using relaxed concurrent data structures for contention minimization in multithreaded MPI programs" 2019 J. Phys.: Conf. Ser. 1399 033037
• A. V. Tabakov and A. A. Paznikov, "Modelling of Parallel Threads Synchronization in Hybrid MPI + Threads Programs" 2019 XXII International Conference on Soft Computing and Measurements (SCM)), St. Petersburg, Russia, 2019, pp. 197-199. doi: 10.1109/SCM.2019.8903806
• Табаков А. В., Пазников А. А. Моделирование синхронизации параллельных потоков при выполнения гибридных MPI+threads программ // Материалы XXI IEEE международной конференции по мягким вычислениям (SCM), 2019. – C. 293-295
• Tabakov A., Paznikov A. Algorithms for Optimization of Relaxed Concurrent Priority Queues in Multicore Systems // Proc. of the 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), 2019. – pp. 360-365. 10.1109/EIConRus.2019.8657105
• Табаков А. В., Пазников А. А. Алгоритмы оптимизации потокобезопасных очередей с приоритетом на основе ослабленной семантики выполнения операций // Известия СПбГЭТУ «ЛЭТИ». – 2018. – № 10. – С. 42-49