Optimization method of remote core locking.pdf В настоящее время имеет место значительное увеличение количества процессорных ядер в вычислительных системах (ВС) с общей памятью [1], относящихся к классам SMP и NUMA. В связи с этим возрастает потребность в создании масштабируемых параллельных программ, эффективных при большом количестве параллельных потоков. Среди перспективных подходов, позволяющих обеспечить высокую масштабируемость параллельных программ, следует в первую очередь выделить алгоритмы и структуры данных, свободные от блокировок (lock-free) [2], и программную транзакционную память (software transactional memory) [3]. Недостатками неблокируемых алгоритмов и структур данных являются ограниченная область их применения и существенные трудозатраты, связанные с разработкой параллельных программ. Кроме того, пропускная способность таких структур часто сопоставима с аналогичными структурами данных, основанными на блокировках. Программная транзакционная память на сегодняшний день не обеспечивает достаточный уровень производительности многопоточных программ и не получила широкого применения в реальных приложениях. Традиционный подход организации критических секций в многопоточных программах с помощью блокировок сегодня остаётся наиболее распространённым в многопоточном программировании. Блокировки проще в использовании по сравнению с неблокируемыми алгоритмами и структурами данных и обеспечивают высокий уровень производительности. Кроме того, основная часть существующих многопоточных программ разработана с использованием блокировок. Поэтому востребованным является создание масштабируемых алгоритмов реализации взаимного исключения. Масштабируемость блокировок существенно зависит от решения проблем, связанных с конкурентным доступом (access contention) параллельных потоков в разделяемых областях памяти и пространственной локализацией обращений к кэш-памяти (cache locality). Конкурентный доступ имеет место при одновременном обращении нескольких потоков к критической секции, защищённой одним объектом синхронизации, что приводит к увеличению загруженности кэш-памяти. Локальность кэша имеет существенное значение в том случае, когда внутри критической секции выполняется обращение к разделяемым данным, которые перед этим использовались на другом ядре. Данное обстоятельство приводит к промахам по кэшу (cache misses) и значительному увеличению времени выполнения критических секций. Среди наиболее эффективных подходов к реализации масштабируемых блокировок можно выделить CAS spinlocks, MCS-locks [4], Flat combining [5], СС-Synch [6], DSM-Synch [6], Oyama lock [7]. Отдельно необходимо выделить ряд методов, предполагающих делегирование выполнения критических секций выделенному процессорному ядру для повышения локальности кэша [5, 8-10]. Работы [9, 10] посвящены разработке потокобезопасных структур данных (списков и хеш-таблиц) на основе делегирования выполнения критических секций. В статье [8] предлагается универсальное аппаратное решение, включающее набор процессорных инструкций для передачи управления выделенному ядру процессора. Flat Combining [5] относится к программно-реализуемым методам. В роли сервера, выполняющего критические секции, выступают все потоки. Однако выполнение процедуры передачи управления критической секцией между потоками приводит к снижению производительности даже при незначительном конкурентном доступе. Кроме того, данные алгоритмы не поддерживают блокировки потоков внутри критических секций как вследствие активного ожидания, так и из-за блокировки потока на уровне ядра операционной системы. 1. Метод делегирования выполнения критических секций на выделенных процессорных ядрах Время выполнение критических секций в многопоточных программах складывается из времени передачи права выполнения блокировкой и времени выполнения инструкций критической секции (рис. 1). При передаче права владения блокировкой возникают накладные расходы вследствие переключения контекста, загрузки кэш-линии, содержащей глобальную переменную синхронизации, из оперативной памяти, активизации потока, выполняющего критическую секцию. На время выполнения инструкций критической секции существенно влияет пространственная локализация обращений к глобальным переменным. Традиционные алгоритмы взаимного исключения предполагают частое переключение контекста, которое приводит к вытеснению разделяемых переменных из кэш-памяти. T2 21 T3 CS1 t CS2 CS3 - выполнение критическои секции - передача права выполнения критической секции Рис. 1. Критический путь выполнения критических секции В работе рассматривается метод выполнения критических секций на выделенных узлах процессора (Remote Core Locking - RCL) [11], позволяющий минимизировать время выполнения существующих многопоточных программ за счет уменьшения критического пути выполнения критических секций. Данный метод предполагает замену в существующих программах высоконагруженных критических секций на удалённый вызов процедур для выполнения на выделенных процессорных ядрах (рис. 2). Все критические секции, защищённые одной блокировкой, выполняются потоком-сервером, работающим на выделенном ядре. Поскольку критические секции выполняются в отдельном потоке, отсутствуют накладные расходы на передачу права владения критической секцией. RCL также позволяет сократить время выполнения инструкций критических секций. Это достигается тем, что разделяемые данные, защищённые блокировкой, с большой вероятностью находятся в локальной кэш-памяти ядра, на котором функционирует RCL-сервер, что обеспечивает снижение числа промахов по кэшу. Конкурентность доступа снижается за счёт использования отдельной выделенной кэш-линии для каждого потока-клиента, которая отвечает за хранение информации о критической секции и активного ожидания потока-клиента (рис. 3). и £ T2 T3 S ......J ...... CS1 1 CS2 1 CS3 T1-T3 - рабочие потоки S - сервер, функционирующий на выделенном ядре CS1-CS3 - выполнение критических секций vl, v2 - разделяемые переменные T1 t vl v2 Рис. 2. Делегирование выполнения критических секций на выделенном процессорном ядре Блокировка Аргументы Функция NULL NULL NULL &lock1 0x34dcf8af &func1 &lock2 0x45adcf9e &func2 NULL NULL NULL Размер кэш-линии reqi req2 req3 req« Рис. 3. Таблица запросов на выполнение критических секций в RCL В существующей реализации RCL не учитывается неоднородный доступ к памяти в NUMA-системах. В данной работе предлагаются алгоритмы, позволяющие минимизировать время доступа к памяти в системах с неоднородным доступом к памяти при выполнении многопоточных программ на базе RCL. 2. Оптимизация алгоритмов делегирования выполнения критических секций в NUMA-системах В настоящее время вычислительные системы с неоднородным доступом к общей памяти (Nonuniform memory access - NUMA) (рис. 4) получили широкое распространение. Такие системы представляют собой композиции многоядерных процессоров, каждый из которых связан с локальной областью глобальной памяти. Процессор вместе с его локальной памятью формирует NUMA-узел (NUMA-node). Взаимодействие между процессорами и обращение к памяти осуществляются через шину (AMD Hyper-Transport, Intel Quick Path Interconnect). Обращение к «локальной» области памяти выполняется непосредственно, обращение к «удалённой» области памяти является более трудоёмким, поскольку выполняется через транзитные узлы. В многопоточных программах при выполнении критических секций на выделенных процессорных ядрах существенную роль играет латентность при обращении RCL-сервера к участкам памяти внутри критических секций. Поэтому в таких программах важно выделять память в области памяти, локальной узлу, на котором функционирует сервер RCL. Это позволяет сократить время обращений к памяти и минимизировать время выполнения многопоточной программы. В настоящей статье исследуется влияние политики выделения памяти в NUMA-системах на эффективность метода делегирования выполнения критических секций. Предложен алгоритм RCLA-wareMalloc, позволяющий минимизировать время выполнения параллельных программ за счет оптимизации выделения памяти в NUMA-системах. Суть алгоритма заключается в следующем. При выполнении многопоточной программы память выделяется на том NUMA-узле, на котором функционирует RCL-сервер. Основные шаги алгоритма RCLAwareMalloc: 1. При выполнении функции выделения памяти проверяется, инициализированы ли в программе RCL-блокировки (запущены ли RCL-серверы). Рис. 4. Функциональная схема многопроцессорной NUMA-системы 2. Если в программе не инициализированы RCL-блокировки, то используется функция Default-Malloc выделения памяти по умолчанию и указатель на выделенный сегмент памяти добавляется в список AllocList. 3. Если в программе инициализированы RCL-блокировки, то проверяется, выполняются ли все RCL-серверы на одном NUMA-узле. 4. Если все RCL-серверы выполняются на одном NUMA-узле, то устанавливается политика выделения памяти на данном NUMA-узле. В противном случае используется функция DefaultMalloc. 5. Если после очередного запуска RCL-блокировки обнаружено, что не все RCL-серверы выполняются на одном узле, то осуществляется привязка выделения памяти к NUMA-узлу. 6. При инициализации первой RCL-блокировки проверяется, пустой ли список AllocList. Если список не пустой, то выполняется миграция блоков выделенной памяти на NUMA-узел, на котором функционирует RCL-сервер. 3. Результаты экспериментов Эксперименты проводились на узле вычислительного кластера Oak Центра параллельных вычислительных технологий Федерального государственного бюджетного образовательного учреждения высшего образования «Сибирский государственный университет телекоммуникаций и информатики». Узел укомплектован двумя четырёхъядерными процессорами Intel Xeon E5420, 24 Гб памяти. Соотношение скорости доступа к локальному и удалённому сегментам памяти 2:1. Моделирование алгоритмов выполнялось на основе синтетического теста. Тест реализует итеративный доступ к элементам массива длины b = 5 х 108. Использовалось три шаблона доступа к элементам: - случайный: на каждой итерации выбирается случайный элемент массива; - последовательный: на каждой новой итерации выбирается элемент, следующий за предыдущим; - с интервалом: на каждой новой итерации выбирается элемент, расположенный на расстоянии s = 1000 элементов от предыдущего. Число p параллельных потоков варьировалось от 1 до 8 (количество процессорных ядер на вычислительном узле). Каждый поток выполнял n = 108 / p операций инкремента соответствующего элемента тестового массива. Индекс элемента массива определялся шаблоном доступа к массиву. Проводилось сравнение двух алгоритмов выделения памяти: 1. Выделение памяти по умолчанию (DefaultMalloc). 2. Выделение памяти с учётом расположения RCL-сервера (RCLAwareMalloc). Выполнялась привязка потоков к процессорным ядрам вычислительного узла: - поток, выполняющий выделение памяти: NUMA-узел 0, процессорное ядро 0; - RCL-сервер: NUMA-узел 1, процессорное ядро 0; - тестовый поток 0: NUMA-узел 0, процессорное ядро 0; - тестовый поток 1: NUMA-узел 0, процессорное ядро 1; - тестовый поток 2: NUMA-узел 0, процессорное ядро 2; - тестовый поток 3: NUMA-узел 0, процессорное ядро 3; - тестовый поток 4: NUMA-узел 1, процессорное ядро 1; - тестовый поток 5: NUMA-узел 1, процессорное ядро 2; - тестовый поток 6: NUMA-узел 1, процессорное ядро 3. В качестве показателей эффективности использовалась пропускная способность b = n / t (t - время выполнения экспериментов) и m - процент промахов по кэшу (cache misses). ^ Р Рис. 5. Эффективность выполнения тестовой параллельной программы: а - пропускная способность, б - промахи по кэшу. -X- - DefaultMalloc, случайный доступ; ~ - DefaultMalloc, последовательный доступ; - И" 1 - DefaultMalloc, доступ с интервалом; X - RCLAwareMalloc, случайный доступ; - ® - - RCLAwareMalloc, последовательный доступ; - - RCLAwareMalloc, доступ с интервалом б а Эксперименты показали (рис. 5), что алгоритм RCLAwareMalloc выделения памяти, учитывающий размещение RCL-сервера в NUMA-системе, позволяет повысить (по сравнению с алгоритмом DefaultMalloc) пропускную способность критической секции за счёт сокращения времени выполнения обращений RCL-сервера к памяти. Предложенный подход наиболее эффективен при случайном доступе к элементам массива и в случае доступа к элементам массива с интервалом. Эффективность RCLAwareMalloc увеличивается с ростом числа потоков. Заключение Разработан алгоритм выделения памяти в вычислительных системах с неоднородным доступом к памяти при выполнении критических секций на выделенных процессорных ядрах (RCL). Алгоритм позволяет минимизировать время выполнения критических секций по сравнению с выделением памяти по умолчанию за счёт минимизации количества обращений к удалённым NUMA-сегментам памяти. Алгоритм реализован в виде библиотеки и может быть использован с целью минимизации существующих многопоточных программ.

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