Алгоритмы оптимизации потокобезопасных очередей с приоритетом на основе ослабленной семантики выполнения операций
При разработке масштабируемых потокобезопасных структур данных (concurrent data structures) для вычислительных систем с общей памятью перспективным является подход на основе ослабления порядка выполнения операций. Построенные на его основе ослабленные структуры данных (relaxed data structures) относятся к нелинеаризуемым (non-linearizable) и не ориентированы на обеспечение строгой семантики выполнения операций (порядок выполнения операции FIFO/LIFO для линейных списков, извлечение максимального (минимального) элемента для очередей с приоритетом и т. д.). В статье используется подход, основанный на представлении потокобезопасных структур данных в виде множества простых структур, распределенных между потоками. При выполнении операций (вставки, удаления элементов) случайным образом выбирается подмножество данных структур. Построены алгоритмы оптимизации потокобезопасных ослабленных очередей с приоритетом на основе данного подхода. Созданы алгоритмы оптимизации выбора очередей из множества при выполнении операций вставки и удаления элементов, а также предложен алгоритм балансировки элементов в очередях. Алгоритмы учитывают иерархическую структуру многоядерных вычислительных систем и обеспечивают локализацию доступа к данным за счет сокращения подмножества очередей для случайного выбора. Оптимизированные алгоритмы добавления и удаления элементов из очередей с приоритетом позволяют увеличить пропускную способность операций вставки/удаления в 1.2 и 1.6 раз соответственно.
Авторы: А. В. Табаков, А. А. Пазников
Направление: Информатика и компьютерные технологии
Ключевые слова: Многопоточность, потокобезопасные структуры данных, ослабленная семантика выполнения операций
Открыть полный текст статьи