Algorithms of optimization of scalable thread-safe pool based on diffracting trees for multicore computing systems.pdf Современные многоядерные вычислительные системы (ВС) [1] являются большемасштабными и мультиархитектурными. Эффективность использования таких систем существенно зависит от средств синхронизации потоков в параллельных программах. С увеличением количества процессорных ядер в современных ВС особенно остро ставится задача обеспечения масштабируемого доступа к разделяемым структурам данных. Одной из наиболее используемых структур данных на сегодняшний день является потокобезопасный пул. Пул (pool) - это неупорядоченная коллекция объектов, реализующая операции добавления (push) и извлечения (pop) объектов [2]. Пулы широко применяются при реализации модели производитель - потребитель (producer - consumer) в многопоточных программах. В данной модели один или несколько потоков-производителей порождают объекты, которые используются потоками-потребителями. Наиболее простым подходом к реализации пулов является использование потокобезопасных очередей. Существующие реализации пулов, основанные на блокируемых очередях [3, 4], обеспечивают высокую производительность при незначительной частоте выполнения операций, однако недостаточно масштабируются для большого количества потоков и высокой интенсивности обращений к пулу. Методы workpile и work-stealing [5, 6] характеризуются прогнозируемым временем выполнения операций, но неэффективны при низкой частоте обращений к пулу. Для повышения масштабируемости широко применяются потокобезопасные пулы на основе линейных списков, свободных от блокировок (lockfree). Одним из наиболее распространенных способов снижения конкурентного доступа (access contention) параллельных потоков к разделяемым областям памяти является метод обработки комплементарных операций (elimination backoff) добавления и удаления элементов в отдельном массиве [7, 8]. В работе [9] предложена усовершенствованная версия данного метода, основанная на использовании циклического буфера. К альтернативным подходам для создания масштабируемых пулов можно отнести реализации на базе устраняющих деревьев (elimination trees) [10]. Хотя использование неблокируемых потокобезопасных списков позволяет обеспечить прогнозируемое выполнение операций, однако при реализации неблокируемых пулов с помощью линейных списков вершины этих списков становятся «узкими местами» (bottleneck), что приводит к увеличению конкурентности доступа и снижению эффективности использования кэш-памяти. Этим же недостатком обладает метод делегирования выполнения операций с пулом потокам-серверам, выполняющихся на выделенных процессорных ядрах [11, 12]. Одним из перспективных подходов для сокращения конкурентного доступа параллельных потоков является применение распределяющих деревьев (diffraction tree) [13]. В статье [14] предложена возможная реализация потокобезопасных пулов на основе распределяющих деревьев с использованием метода устранения комплементарных операций. К недостаткам реализации можно отнести дополнительные накладные расходы, связанные с активным ожиданием в массиве устранения комплементарных операций, а также синхронизацией атомарных переменных на каждом уровне распределяющего дерева в худшем случае, что существенно увеличивает трудоёмкость обхода дерева от корня к листьям. Эффективность распределяющего дерева значительно снижается с увеличением его размера. Кроме того, в работе [13] существенно нарушается FIFO/LIFO порядок выполнения операций, а также не учитывается возможность использования пула для добавления и удаления элементов одним потоком. Также к недостаткам относится необходимость подбора таких параметров, как время ожидания поступления комплементарных операций, допустимое количество коллизий и т. д. В работах [15, 16] с целью снижения вышеописанных накладных расходов предлагается оптимизация в виде адаптивного распределяющего дерева (self-tuning reactive diffraction tree), размер которого определяется текущим уровнем конкурентного доступа потоков к его листьям. Тем не менее такие пулы характеризуются существенными накладными расходами вследствие синхронизации во вспомогательных массивах и в узлах дерева. В данной статье предложены оригинальный подход к реализации потокобезопасного пула без использования блокировок на основе распределяющих деревьев и методы его оптимизации для постоянного числа активных потоков. Подход основан на локализации обращений к узлам дерева и использовании локальной памяти потоков. Предлагаемый подход позволяет повысить пропускную способность при высоких и низких загрузках пула, обеспечивает приемлемый уровень FIFO/LIFO-порядка выполнения операций и характеризуется незначительной временной задержкой прохода от корня распределяющего дерева к его листьям. 1. Потокобезопасный пул на основе распределяющего дерева Пусть имеется многоядерная ВС, состоящая из n процессорных ядер. Считаем, что система функционирует в монопрограммном режиме решения одной параллельной задачи [1], которая включает в себя p параллельных потоков. Привязка потоков к процессорным ядрам определяется функцией a(i), ставящей в соответствие потоку i процессорное ядро w е {1, 2, ..., n}, к которому привязан поток. Будем называть производителем (producer) поток, выполняющий операцию добавления (push) элементов в пул, и потребителем (consumer) - поток, выполняющий операцию удаления (pop) элементов из пула. Распределяющее дерево (diffraction tree) [13-16] представляет собой бинарное дерево высотой h, в каждом узле которого находятся биты, определяющие направления обращений потоков (рис. 1). Узлы дерева (balancers) перенаправляют поступающие от потоков запросы на добавление (push) или удаление (pop) элементов поочередно на один из узлов-потомков: если значение бита равно 0, то поток обращается к узлу правого поддерева, если 1 - левого поддерева, и так далее до тех пор, пока потоки не дойдут до листьев дерева. После прохождения каждого узла потоки инвертируют в нём соответствующий бит. Листьям распределяющего дерева соответствуют потокобезопасные очереди q = {1, 2, ..., 2h} (рис. 2). При выполнении операций потоки проходят дерево от корня к листьям и помещают (извлекают) элемент в соответствующую очередь. В состоянии покоя (quiescent state), при котором дерево сбалансировано и не содержит поступающих от потоков запросов, выходящие из дерева элементы распределяются между очередями таким образом, что количество элементов в верхней очереди превышает количество элементов в нижних очередях не более, чем на один. Таким образом, распределяющее дерево позволяет сократить конкурентность доступа к структуре данных. бит потока-потребителя Рис. 1. Узел распределяющего дерева Рис. 2. Потокобезопасный пул на основе распределяющего дерева (h = 2) Для практических целей последовательный порядок распределения потоков по листьям, как правило, не требуется [17, 18], и им можно пренебречь с целью повышения пропускной способности пула. На основе данного допущения авторами предложены алгоритмы реализации потокобезопасного пула на базе распределяющего дерева. В основе алгоритмов лежат идея локализации обращений к узлам дерева и использование локальной памяти потока (thread-local storage, TLS). TLS применяется с целью сокращения накладных расходов, связанных с доступом из разных потоков к разделяемым атомарным переменным и использованием массива устранения комплементарных операций в каждом узле дерева. 2. Оптимизированный пул на основе распределяющего дерева Авторами был разработан пул LocOptDTPool, в котором каждый узел распределяющего дерева содержит два массива атомарных битов (для потоков-производителей и потоков-потребителей) размера m 0) { 5 array[level][node] = (id >> (level - 1)) & 1 6 } else { 7 array[level][node] = id % 2 8 } 9 } 10 } Рис. 4. Распределение потоков по узлам дерева в пуле TLSDTPool Бит 0 или 1 в узлах дерева означает соответственно правый или левый узел-потомок, к которому обращается поток после прохождения данного узла. Проходя через каждый узел дерева, поток инвертирует соответствующий локальный бит в этом узле. Для более равномерного распределения потоков по дереву вводится также дополнительный бит, (листинг 7, строка 7), который размещается в корне дерева. Аналогично другим битам с каждым увеличением идентификатора он переключается на противоположный (0, 1, 0, 1 и т.д.). Описанный алгоритм в случае постоянно активных потоков позволяет равномерно распределить обращения потоков к узлам дерева для предотвращения дисбаланса загрузки очередей в листьях дерева. 4. Результаты экспериментов Организация экспериментов Моделирование пулов LocOptDTPool и TLSDTPool проводилось на узле вычислительного кластера Jet Центра параллельных вычислительных технологий Федерального государственного бюджетного образовательного учреждения высшего образования «Сибирский государственный университет телекоммуникаций и информатики». Узел кластера укомплектован двумя 4-ядерными процессорами Intel Xeon E5420 (2,5 GHz; Intel-64). Тестовая программа была разработана на языке программирования C++ и скомпилирована с использованием компилятора GCC 4.8.2. В качестве элементов, помещаемых (извлекаемых) в пул, использовались переменные целочисленного типа. Под количеством p потоков подразумевается число потоков, помещающих элементы и извлекающих объекты из пула. В качестве показателя эффективности пула использовалась пропускная способность b = N / t пула, где N - суммарное число выполненных операций добавления (извлечения), а t -время моделирования. Пропускная способность показывает, сколько операций было выполнено за 1 с. Реализовано сравнение эффективности пула при использовании различных типов очередей (с блокировками и без блокировок) в листьях дерева. Сравнение используемых в пуле очередей объясняется тем, что от выбора очередей во многом зависит пропускная способность пула; такой подход к моделированию применялся в других работах [16]. Также для сравнения представлены результаты моделирования пула на основе одной неблокируемой очереди Lockfree queue из библиотеки boost [19]. Для каждого пула проводились две серии экспериментов: для числа потоков p = 1, 2, ..., 8, не превышающего число процессорных ядер вычислительного узла, и для большого количества потоков p = 10, 20, ..., 200. Пул LocOptDTPool на основе массивов атомарных битов Результаты тестирования пропускной способности реализованного пула с использованием массивов атомарных битов в узлах дерева показаны на рис. 5. Ь, I О6 опер./с h, I О6 опер./с Рис. 5. Пропускная способность пула LocOptDTPool: a - число потоков не превышает количество процессорных ядер; б - число потоков превышает количество процессорных ядер. 1 - LocOptDTPool, неблокируемые очереди Lockfree queue из библиотеки boost; 2 - LocOptDTPool, блокируемые очереди на основе PThreads mutex; 3 - очередь Lockfree queue без использования блокировок из библиотеки boost Реализованная структура данных хорошо масштабируется для большого количества потоков и демонстрирует рост пропускной способности по мере достижения числа потоков, равного количеству процессорных ядер. Максимальная пропускная способность, равная 170 млн опер./с, была получена при количестве потоков, равном количеству ядер процессора или незначительно его превышающем. Пул TLSDTPool на основе Thread-local storage На рис. 6 представлены результаты моделирования пропускной способности пула TLSDTPool с использованием локально-поточных битов. b, 106 опер./с 200 80 120 б Рис. 6. Пропускная способность пула TLSDTPool: a - число потоков не превышает количество процессорных ядер; б - число потоков превышает количество процессорных ядер. 1 - TLSDTPool, неблокируемые очереди Lockfree queue из библиотеки boost; 2 - TLSDTPool, блокируемые очереди на основе PThreads mutex; 3 - очередь Lockfree queue без использования блокировок из библиотеки boost Пропускная способность пула LocOptDTPool на всем диапазоне числа потоков соответствует пропускной способности пула TLSDTPool с применением локально-поточных битов. При этом также была достигнута максимальная пропускная способность, равная 170 млн опер./с, при количестве потоков, равном числу процессорных ядер или незначительно его превосходящем. В разделе 3 была рассмотрена ситуация, когда при использовании поточно-локальных переменных число потоков, одновременно обращающихся к одному листу дерева, может значительно превосходить число потоков, выполняющих операции с другими листьями дерева. Однако в ходе выполнения экспериментов такой случай не был зафиксирован и снижения пропускной способности пула не наблюдалось. Тем не менее при построении пулов необходимо учитывать, что с увеличением количества уровней распределяющего дерева вероятность появления «худшего случая» уменьшается (при этом возрастают затраты по памяти). При большом количестве потоков применение неблокируемых очередей Lockfree queue в пулах LocOptDTPool и TLSDTPool обеспечивает большую пропускную способность, по сравнению с блокируемыми потокобезопасными очередями (см. рис. 5, б; 6, б). Во всех случаях эффективность отдельной потокобезопасной очереди Lockfree queue значительно уступает эффективности разработанных пулов (рис. 5, 6). Заключение Разработаны алгоритмы реализации масштабируемых потокобезопасных пулов на основе распределяющих деревьев без использования блокировок. Суть оптимизаций заключается в локализации обращений потоков к разделяемым областям памяти с целью максимизации пропускной способности пула. Разработанные пулы могут применяться при реализации модели производитель - потребитель в многопоточных программах с постоянным числом активных потоков, где требуются высокая пропускная способность и быстрый возврат потоков из структуры с целью минимизации времени выполнения операций. Пул обеспечивает большую масштабируемость при выполнении многопоточных программ по сравнению с аналогичными реализациями пула на основе распределяющих деревьев. Наибольшая эффективность алгоритмов достигнута при числе активных потоков, равном количеству процессорных ядер в системе. Увеличение размеров дерева в пуле не снижает пропускную способность пула. В качестве структур данных в листьях дерева для хранения объектов пула рекомендуется использовать потокобезопасные очереди без использования блокировок. 180 h, 10'' опер./с 1 2 3 4 5 6 7 а

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