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