Analysis of the efficiency of atomic operations in multi-core shared-memory computer systems.pdf К многоядерным вычислительным системам (ВС) с общей памятью относятся как автономные десктопные и серверные системы, так и вычислительные узлы в составе распределенных ВС (кластерные ВС, системы с массовым параллелизмом). Такие системы могут включать десятки и сотни процессорных ядер. Например, вычислительный узел суперкомпьютера Summit, занимающего первое место в рейтинге T0P-500 (более 2 млн процессорных ядер, 4 608 узлов), включает два 24-ядерных универсальных процессора IBM Power9 и шесть графических ускорителей NVIDIA Tesla V100 (640 ядер). Sunway TaihuLight (более 10 млн процессорных ядер, третье место в рейтинге T0P-500) укомплектован 40 960 процессорами Sunway SW26010, включающими 260 ядер. При реализации кэш-памяти в таких ВС применяются различные политики включения (инклюзивный и эксклюзивный кэш), протоколы когерентности (MESI, MOESI, MESIF, MOWESI, MERSI, Dragon) и топологии межпроцессорных шин в NUMA-системах (Intel QPI, AMD HyperTransport). Одной из наиболее значимых задач при разработке параллельных программ является создание эффективных средств синхронизации параллельных потоков. Основными методами синхронизации являются средства блокировки потоков (locks, mutexes), неблокируемые (non-blocking, lock-free) по-токобезопасные (concurrent, thread-safe) структуры данных и транзакционная память [1-5]. Атомарные операции (atomic operations, atomics) применяются при реализации всех методов синхронизации. Операция называется атомарной, если она завершается в один неделимый шаг относительно других потоков. Ни один из потоков не может наблюдать операцию «частично завершенной». Если два или более потоков выполняют операции над разделяемой переменной и хотя бы один выполняет операцию записи, то потоки должны использовать атомарные операции для избежания гонки данных (data race). ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2020 № 51 Управление, вычислительная техника и информатика К наиболее распространенным относятся атомарные операции «сравнение с обменом» (compare-and-swap, CAS), «выборка и сложение» (fetch-and-add, FAA), «обмен» (swap, SWP), «чтение» (load) и «запись» (store). Операция load(m, r) реализует чтение значения переменной из ячейки памяти m в регистр r; store(m, r) - запись значения переменной в ячейку памяти m из регистра r. FAA(m, r1, r2) увеличивает (уменьшает) на размещенное в регистре r1 значение в ячейке памяти m и возвращает предыдущее значение в регистр r2. SWP(m, r) - обмен значений между ячейкой памяти m и регистром r. CAS(m, r1, r2) реализует сравнение значения ячейки памяти m с регистром п; если значения равны, то в m устанавливается r2. При разработке параллельных программ необходимо учитывать влияние на эффективность атомарных операций таких аспектов, как выполнение механизма когерентности кэш-памяти, размер буфера, числа потоков, удаленности данных от ядра. Несмотря на широкое применение, эффективность атомарных операций не проанализирована в достаточной степени. Например, считается, что CAS медленнее FAA [6] и ее семантика позволяет ввести понятие «бесполезная работа» (wasted work) [7, 8], поскольку неудачные попытки сравнения данных в памяти и в регистре приводят к дополнительной нагрузке на ядро. В работе [8] анализируется производительность атомарных операций на графических процессорах, однако сегодня остро стоит задача оценки эффективности атомарных операций на универсальных процессорах. В [9] рассматривается эффективность выполнения операций CAS, FAA, SWP с целью анализа влияния динамических параметров программы на время выполнения атомарных операций. Результаты исследований демонстрируют недокументированные свойства тестируемых систем и оценки времени выполнения атомарных операций. Однако тесты проводились при фиксированной частоте процессорных ядер, использовании больших страниц памяти и с выключенной предварительной выборкой данных, что искажает результаты моделирования для реальных программ. Кроме того, не исследовались атомарные операции load и store. В работе рассматриваются операции CAS, FAA, SWP, load, store, при этом условия проведения экспериментов максимально приближены к реальным условиям выполнения параллельных программ, в частности не проводятся фиксация частоты ядер, изменение размера страниц, отключение предварительной выборки данных. Проводится анализ эффективности атомарных операций для процессоров архитектуры x86-64. Кроме того, рассматриваются разные варианты выполнения CAS (удачный и неудачный), а также выполнение атомарных операций при использовании данных локальной и удаленной кэш-памяти (по отношению к ядру, выполняющему операции). 1. Методика проведения экспериментов В качестве показателей эффективности используются латентность l выполнения атомарной операции и пропускная способность b. Пропускная способность b = n/t, где n - число выполненных операций за время t при реализации последовательного доступа к ячейкам буфера. Для точного измерения времени применялся набор инструкций RDTSCP. Для предотвращения переупорядочивания инструкций использовались полные барьеры памяти. Исследуется влияние состояния кэш-линии в рамках протоколов когерентности (M, E, S, O, I, F) на эффективность выполнения атомарных операций. Определим основные состояния кэш-линий. М (Modified) - кэш-линия модифицирована и содержит актуальные данные. O (Owned) - кэш-линия содержит актуальные данные и является их единственным владельцем. Е (Exclusive) - кэш-линия содержит актуальные данные, которые соответствуют состоянию памяти. S (Shared) - кэш-линия содержит актуальные данные, при этом другие процессорные ядра имеют копии этих данных в разделяемом состоянии. F (Forwarded) - кэш-линия содержит наиболее свежие, корректные данные, при этом другие ядра в системе могут иметь копии данных в разделяемом состоянии. I (Invalid) - кэш-линия содержит некорректные данные. Разработана тестовая программа. Перед началом выполнения организуется буфер q в виде целочисленного массива размера s = 128 Мб. Данные размещаются в кэш-памяти, кэш-линии переводятся в заданное состояние протокола когерентности. Подкачка страниц не применялась. Данные не выравнивались. Перевод кэш-линий в состояние M происходит при записи произвольных значений в ячейки буфера. Для перевода в состояние E выполняется запись в ячейки буфера, затем - инструкция clflush для перевода кэш-линий в состояние I, после этого - чтение ячеек буфера. Переход в состояние S происходит после чтения ячеек буфера из кэш-памяти в состоянии E одного ядра в кэш-память другого ядра. Перевод кэш-линий в состояние O достигается путем чтения из кэш-памяти в состоянии M одного ядра в кэш-память другого ядра, при этом кэш-линии ядра из M переключаются в состояние O. Для операции CAS выполняется два эксперимента: для успешной и неудачной операции. Неудачным считается CAS, при выполнении которого m Ф т\\. Заведомо неудачное выполнение CAS достигается путем сравнения адреса указателя с данными по этому указателю. В успешном CAS m = r\\. Эксперименты проводились на процессорах AMD Athlon II X4 640 (микроархитектура K\\0), AMD A10-4600M (микроархитектура Piledriver) (протокол когерентности MOESI [10]), Intel Xeon X5670 (микроархитектура Westmere-EP) и Intel Xeon E5540 (микроархитектура Nehalem-EP) (MESIF [\\\\]) (рис. \\). Размер кэш-линии 64 байта. В качестве компилятора использовался компилятор GCC 4.8.5, операционная система SUSE Linux Enterprise Server 12 SP3 (версия ядра 4.4.180). АМОАЮ-4600М (UK 11 tl 21 с, (■Щ0О Jl Ci Lid Lid Lid Lid iu 12 U НАМ a AMD А№п 2 УЛ 640 Co (ядро 11 =1 C? (адро 3] c> Lid Lid | tld Lid Ш * U1 E? Li 12 a RAM b Intel Хеол X5670 Iwol] l«ft»3J l«j»4J b4 (Щ» 5> M Lid Lid Ud Lid Lid Lid Ui Lll j 111. Lli Li, Lli LI II LI L2 L2 13 RAM c d Рис. 1. Исследуемые микроархитектуры: а - Piledriver, b - K10, c - Nehalem-EP, d - Westmere-EP Fig. 1. Target microarchitectures: а - Piledriver, b - K10, c - Nehalem-EP, d - Westmere-EP Опишем основные шаги алгоритма измерения времени выполнения атомарных операций для состояния E (рис. 2). Вспомогательная функция DoOper реализует выполнение заданной атомарной операции для всех элементов буфера (строки 1-4). Основной алгоритм выполняется до тех пор, пока размер буфера не достигнет максимального (строка 5). Задействованный диапазон тестового массива testSizeBuffer в экспериментах варьирует от 6 Кб (минимальный размер кэша первого уровня) до 128 Мб. Каждый эксперимент запускается nruns раз (строка 6). Выполняется запись произвольных данных в ячейки буфера для перевода кэш-линий ядра c0 в состояние M (для остальных ядер состояние кэш-линий переводится в I) (строка 7). Далее выполняется инвалидация кэш-линий (строка 12) с последующим чтением, что переводит кэш-линий ядра c0 в состояние E (строка 9). На следующем шаге над каждой переменной выполняется атомарная операция (строка 11). Вычисляется время выполнения операции и суммарное время выполнения (строка 13). Рассчитываются латентность (строка 15), пропускная способность (строка 16) и увеличивается текущий размер буфера на step = Lx / 8 (где Lx -размер кэш-памяти уровня х = 1, 2, 3)) (строка 17). Алгоритмы выполнения атомарных операций для состояний M и I аналогичны описанному, при этом для M строки 8, 9 не выполняются, для I не выполняются строки 7, 9. Intel Xeon E5M1 (ядро 11 1«Дро S) tг (nflfl? IjuukHI tid Lid Lid Lid 41 til Ш nsn U 11 L2 LI L3 RAM а b Рис. 2. Алгоритм измерения латентности и пропускной способности выполнения атомарных операций SWP/FAA/CAS/Load/Store: а - Exclusive c0, b - Shared C0 Fig. 2. Algorithm for measuring the latency and throughput of atomic operations SWP/FAA/CAS/Load/Store and throughput: а - Exclusive C0, b - Shared C0 Основные шаги алгоритма измерения времени выполнения атомарных операций для С0 в состоянии кэш-линий S (см. рис. 2, b). Алгоритм выполняется в двух потоках, привязанных к ядрам С0 и С2. Синхронизация реализуется посредством атомарных флагов. В первом потоке на ядре С0 выполняется запись произвольных данных в буфер, перевод кэш-линий в состояние M, при этом для остальных ядер состояние изменяется на I (строка 4). Далее выполняются очистка кэш-линий (сброс в I) (строка 5) и чтение данных для изменения состояния кэш-линий С0 в состояние E (строка 6). Во втором потоке (ядро c2) выполняется чтение данных, что изменяет состояние кэш-линий ядер С0 и С2 на S (строка 8). Далее первый поток на ядре С0 реализует атомарную операцию над элементами тестового буфера (строка 11). Вычисляются время выполнения операции и показатели эффективности (строки 15-17). На рис. 3, 4 приведены результаты экспериментов для операции SWP. 1 Первый поток на c0: 2 while d < testSizeBuffer do 3 for j = 0 to nruns do 4 DoOper(store(1 )) 5 CLFLUSH(bufer,d); 6 DoOper(load) 7 Второй поток на c2: 8 DoOper(load) 9 Первый поток на c0: 10 start = get_time(); 11 DoOpER(ATOMiCOp(bufer[i])) 12 end = get time(); 13 sumTime = sumTime + (end - start); 14 end for 15 latency = sumTime / nruns / d; 16 bandwidth = (d / sumTime / nruns) * 109 / 220; 17 d = d + step; 18 end while 1 Function DoOPER(oper) 2 for i = 0 to d do 3 buffer.oper() 4 end for 5 while d < testSizeBuffer do 6 for j = 0 to nruns do 7 DoOper(store(1 )) 8 CLFLUSH(bufer, d); 9 DoOper(load) 10 start = get_time(); 11 DoOpER(ATOMICOp(buffer[i])) 12 end = get time(); 13 sumTime = sumTime + (end - start); 14 end for 15 latency = sumTime / nruns / d; 16 bandwidth = (d / sumTime / nruns) * 109 / 220; 17 d = d + step; 18 end while Рис. 3. Латентность выполнения атомарной операции SWP для кэш-линий в состоянии Exclusive: а - Piledriver, b - K10, c - Nehalem-EP, d - Westmere-EP Fig. 3. Latency an atomic operation SWP for cache lines in the Exclusive state: а - Piledriver, b - K10, c - Nehalem-EP, d - Westmere-EP 10* 10е ios 1&4 ю1 с d Рис. 4. Латентность выполнения атомарной операции SWP для кэш-линий в состоянии Shared: а - Piledriver, b - K10, c - Nehalem-EP, d - Westmere-EP Fig. 4. Latency an atomic operation SWP for cache lines in the Shared state: а - Piledriver, b - K10, c - Nehalem-EP, d - Westmere-EP Опишем основные шаги алгоритма измерения времени выполнения атомарных операций для ядер c1 и c2 в состоянии S кэш-линий ядра c0 (рис. 5). Алгоритм выполняется в трех потоках, привязанных к ядрам c0, c1, c2. Первый поток (ядро c0) реализует запись в буфер, что переводит состояние кэш-линий c0 в M (для остальных ядер состояние изменяется на I) (строка 4). Далее выполняются сброс состояния в I (строка 5) и чтение данных, что переводит кэш-линии c0 в состояние E (строка 6). Во втором потоке (ядро c1) выполняется чтение данных (состояние кэш-линии c0 и c изменяется на S) (строка 8). На следующем шаге в третьем потоке (ядро c2) над каждым элементом буфера выполняется атомарная операция (строка 11). Вычисляются показатели эффективности (строки 15-17). Для измерения латентности выполнения атомарных операций на ядре c1 используется аналогичный алгоритм, в котором шаги для ядер c1 и c2 меняются местами. 1 Первый поток на cq: 2 while d < testSizeBuffer do 3 for j = 0 to nruns do 4 DoOper(store(1 )) 5 Второй поток на c2: 6 DoOper(load) 7 Первый поток на cq: 8 start = get_time(); 9 DoOPER(ATOMiCOp(bufer[i])) 10 end = get_time(); 11 sumTime = sumTime + (end - start); 12 end for 13 latency = sumTime / nruns / d; 14 bandwidth = (d / sumTime / nruns) x 109 / 22Q; 15 d = d + step; 16 end while 1 Первый поток на cq: 2 while d < testSizeBuffer do 3 for j = 0 to nruns do 4 DoOper(store(1 )) 5 CLFLUSH(buf%r,d); 6 DoOper(load) 7 Второй поток на a: 8 DoOper(load) 9 Третий поток на c2: 10 start = get_time(); 11 DoOPER(ATOMICOp(buffer[i])) 12 end = get time(); 13 sumTime = sumTime + (end - start); 14 end for 15 latency = sumTime / nruns / d; 16 bandwidth = (d / sumTime / nruns) x 109 / 22Q; 17 d = d + step; 18 end while а б Рис. 5. Алгоритм измерения латентности и пропускной способности выполнения атомарных операций: а - кэш-линии ядра c0 в состоянии Shared, измерения для ядер c1 и c2, b - состояние Owned Fig. 5. Algorithm for measuring the latency and throughput of atomic operations: а - Shared cq, measurements for c1 and c2, b - Owned state Опишем основные шаги алгоритма измерения времени выполнения атомарных операций в состоянии кэш-линий O на ядре С0 (см. рис. 5, b). Алгоритм выполняется в двух потоках, привязанных к ядрам С0 и С2. В первом потоке (ядро С0) произвольные данные записываются в буфер для изменения состояния кэш-линий ядра С0 в M (для остальных ядер состояние изменяется I) (строка 4). Во втором потоке (ядро С2) выполняется чтение данных, что изменяет состояние кэш-линий локального ядра С0 на O, а ядра С2 - на S (строка 8). На следующем шаге в первом потоке (ядро С0) над каждой переменной буфера выполняется атомарная операция (строка 9). Вычисляются время выполнения операции и показатели эффективности (строки 13-15). На рис. 6 приведены результаты для операции SWP, состояние O. Рис. 6. Латентность выполнения атомарной операции SWP кэш-линий в состоянии Owned: а - архитектура Piledriver, b - архитектура K10 Fig. 6. Latency of atomic operation SWP for cache lines in the Owned state: а - Piledriver, b - K10 Субоптимальные параметры для архитектуры Westmere-EP Таблица 1 Операция Субоптимальные параметры Общий уровень памяти l, нс b, Мб/с Состояние кэш-линий Размер буфера Ядро Load Exclusive L2 C0, C1, C2 L3 1,1-1,15 823-866 Store Modified RAM C0, C1, C2 L3 4,1-4,21 226 - 230 FAA Invalid L1 C0, C1, C2 L3 1,89-1,91 490-499 SWP Invalid, Modified RAM C0, C1, C2 L3 1,93 493 unCAS Exclusive L1, L2 C0, C1, C2 L3 2,55-2,59 367-372 CAS Invalid L2, L3 C0, C1, C2 L3 4,9-19,3 49-194 Таблица 2 Отношения максимальной и минимальной пропускной способности при выполнении атомарных операций Операция Piledriver K10 Nehalem-EP Westmere-EP bmax/bmin bmax/bmin bmax/bmin bmax/bmin Load 1,4 1,1 2,1 2 FAA 1,1 1,2 2,2 1,1 SWP 1,1 1,2 2,1 1,1 unCAS 1,1 1,2 2,4 2,0 Store 3,9 1,1 2,1 1,1 CAS 1,1 1,6 6,1 7,2 В табл. 1 представлены субоптимальные параметры выполнения атомарных операций на процессоре с микроархитектурой Westmere-EP. Аналогичные результаты получены и для других процессоров. Так, например, для процессоров микроархитектур K10, Nehalem-EP, Westmere-EP наименьшая латентность выполнения операции load получена в состоянии S на ядре С0 (от 1,14 до 1,81 нс), в то время как для процессора с микроархитектурой Piledriver данная операция имеет наименьшую латентность на ядрах c0 и c2 (от 1,8 до 2,4 нс). В табл. 2 даны отношения максимальной и минимальной пропускной способности. 2. Анализ результатов экспериментов Состояние кэш-линий M. Значения показателей эффективности для атомарных операций SWP, FAA, unCAS на ядре c0 архитектуры Piledriver незначительно варьируют при изменении размера буфера, в то время как для ядер c и c2 увеличение размера буфера более L2 приводит к сокращению ла-тентности до минимального значения для обоих ядер. Для K10 при размере буфера, превышающем L2, латентность операций SWP, FAA, unCAS различается в пределах погрешности для всех ядер. При выполнении load, SWP, CAS для Nehalem-EP латентность сопоставима для всех ядер при размере буфера более L3. При выполнении операций load, SWP для Westmere-EP наблюдается аналогичная ситуация, для остальных операций (store, CAS, FAA, unCAS) латентность является наименьшей для ядра c0 и не зависит от размера буфера. Состояние кэш-линий Е. При выполнении операций SWP, FAA, unCAS на архитектуре Piledriver и размере буфера более L2 для ядер c и c2 латентность сопоставима, при этом на ядре c0 получены максимальные значения. Для архитектуры K10 латентность операций SWP, FAA, unCAS аналогична для всех ядер при размере буфера, превышающем L2. Для Nehalem-EP латентность SWP, load сопоставима на всех ядрах при размере буфера более L3. Для Westmere-EP минимальная латентность для load, SWP, FAA, CAS получена на ядре c0, для ядер c и c2 при размере буфера более L3 латентность различается незначительно. Состояние кэш-линий S. При выполнении SWP, FAA на архитектуре Piledriver при размере буфера L1 латентность максимальна на ядре c0. Для K10 при размере буфера L2 наибольшая латент-ность получена на ядре c0 для SWP, FAA, store. Для Nehalem-EP и Westmere-EP при размере буфера L2 латентность выполнения SWP, FAA максимальна на ядрах ci, c2. Состояние кэш-линий I. При выполнении SWP, FAA, unCAS на архитектуре Piledriver размер буфера незначительно влияет на время выполнения для всех ядер, наименьшая латентность получена на ядрах c и c2. При выполнении load, SWP на K10 при размере буфера не более L2 латентность выполнения минимальна для ядра c0. Для Nehalem-EP латентность SWP, load сопоставима на всех ядрах при размере буфера более L3. При выполнении load, SWP, FAA, CAS на Westmere-EP наименьшая латентность получена на ядре c0. Состояние кэш-линий O. При выполнении атомарных операций SWP, FAA на архитектуре Piledriver при размере буфера L1 наибольшая латентность получена на ядре c0. Для ядра c размер буфера не влияет на время выполнения операций. Наибольшая латентность операций SWP, FAA, store на архитектуре K10 получена при размере буфера L2 на ядре c0. Наибольшей латентностью, по сравнению с другими операциями, характеризуется операция CAS (успешный). Операция load выполняется с наименьшей латентностью. Например, для процессоров K10, Westmere-EP минимальная латентность CAS получена для состояния S на ядре c0 и составляет от 18 до 24 нс, для процессора Piledriver CAS имеет наименьшую латентность на ядрах c0 и c (от 42 до 44 нс), на процессоре Nehalem-EP в состоянии S CAS выполняется с наименьшей латентностью на ядре c0 (от 22 до 46 нс), при этом наибольшая латентность (46 нс) получена при размере буфера L2. Для архитектуры Piledriver минимальная латентность операции load (1,76 нс) превышает минимальную латентность операции CAS (12,39 нс) в 7 раз. Для архитектуры K10 минимальная латентность load (1,72 нс) превышает минимальную латентность CAS (22,38 нс) в 13 раз. Для Nehalem-EP отношение минимальной латентности load (1,3 нс) к минимальной латентности CAS (9,86 нс) - 7,5. Для архитектуры Westmere-EP отношение минимальной латентности load (1,1 нс) к минимальной ла-тентности CAS (4,9 нс) - 4,5. Сравнивая микроархитектуры, отметим, что в среднем наименьшая латентность получена на процессоре Westmere-EP (MESIF), наибольшая - на Piledriver (MOESI). Заключение Разработан инструментарий и проведен анализ эффективности выполнения атомарных операций в многоядерных вычислительных системах с общей памятью в зависимости от размера буфера, состояния кэш-линий и локальности данных. Экспериментально показано, что операции «неудачный CAS», FAA и SWP характеризуются сопоставимой задержкой. Для операций load получена наименьшая латентность, для «удачный CAS» и store - наибольшая. В результате анализа результатов экспериментов построены рекомендации по увеличению пропускной способности и минимизации латентности выполнения атомарных операций на протестированных процессорах. Так, применение данных рекомендаций позволит увеличить пропускную способность на процессоре с микроархитектурой Piledriver от 1,1 до 3,9 раз, для процессора K10 - от 1,1 до 1,6 раз, для процессора Nehalem-EP от 2,1 до 6,1 раз, для процессора Westmere-EP - от 1,1 до 7,2 раз. Таким образом, полученные результаты показывают, что время выполнения атомарных операций может варьировать в широких пределах в зависимости от условий их выполнения (состояние кэш-линии, локализация и размер буфера). Это необходимо учитывать при разработке разделяемых структур данных и примитивов синхронизации.

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