Знакомство с Numa

Во время конкурса Acceler8 были обсуждения векторизации, разворотов циклов, и различных микрооптимизаций. Но, наверное, многие, как и я, сталкивались с проблемой, что какие бы оптимизации они не делали, программа на компьютере с небольшим числом ядер разгонялась, а на MTL скорость лишь неумолимо падала. Тогда стало ясно, что нужно каким-то образом разгружать RAM, иначе какой-либо прогресс невозможен. Я добавил в программу только 2 оптимизации работы с RAM, но благодаря ним становятся возможными и следующие улучшения программы, такие как векторизация.

Numa система на MTL.


На MTL стоит 256 ГБ оперативной памяти, но в системе 4 процессора Xeon, каждый из них имеет прямой доступ только к своим 64 гб оперативной памяти, а доступ к остальным 192 гб занимает вдвое больше времени.

node 0 size: 64485 MB
node 1 size: 64640 MB
node 2 size: 64640 MB
node 3 size: 64640 MB

node distances:
node 0 1 2 3
0: 10 21 21 21
1: 21 10 21 21
2: 21 21 10 21
3: 21 21 21 10


Распределение процессоров по узлам(40 - 79 есть только на логин сервере, где включен HT):

node 0: 0-9, 40-49
node 1: 10-19, 50-59
node 2: 20-29, 60-69
node 3: 30-39, 70-79


Естественно хочется избегать ситуаций, когда процессор лезет в чужую память. Возможно, OpenMP разбирается с такими проблемами автоматически, но своё решение я писал с помощью pthreads и для них решение проблемы оказалось следующим:

  1. При вызове malloc отображение виртуальной памяти на физическую ещё не строится.

  2. Когда какой-то процессор обращается к куску памяти, для которого отображения ещё нет, это отображение строится на память в Numa узле этого процессора.

  3. Поэтому выгодно генерировать в каждом потоке ту часть матрицы, которая будет им чаще всего использоваться, осуществить эту параллельную генерацию нам позволяет наличие периода в матрице. В общем случае пришлось бы делать memset своего куска матрицы в каждом потоке, и только потом генерировать всю матрицу в каком-то одном потоке.

  4. Для того, чтобы потоки не бродили по процессорам и тем более по numa узлам, нужно их привязать к конкретным процессорам. Например, можно привязать поток номер k к процессору номер k, это даст ещё одно преимущество - мы будем знать у каких потоков есть разделяемый кэш и можем более эффективно распределять операции. В случае pthreads привязка потока к процессору осуществляется при помощи библиотеки sched.h:




CPU_ZERO(&affinity);

CPU_SET(args->thread_number, &affinity);

sched_setaffinity(0, sizeof(cpu_set_t), &affinity);



Блочный метод.



Даже разобравшись с Numa системой, векторизация не даст никакого ощутимого выигрыша, пока мы не начнём по максимуму использовать кэш. Если написать стандартный метод Кадана в 3 цикла, то по сути никакие уровни кэша, кроме L3, программа использовать не будет. Естественно эта ситуация нас не устраивает, хочется изменить порядок, в котором мы обрабатываем элементы матрицы, чтобы каждый элемент, который мы положим в кэш, оставался там как можно дольше. Например, можно сделать метод Кадана блочным, т.е. выбрать некоторые размеры блока A и B, и работать с блоком, как с неделимой операцией, алгоритм в таком виде примет сложность 0.5 * (N/A)^2 * (M / B) * (A^2 * B). Естественно, сложность осталась прежней, но (A^2 B) - операции, в которых процессор не будет лезть дальше собственного кэша, и естественно эти операции будут работать эффективнее, чем если бы процессор всегда лез в оперативную память или L3 кэш. Осталось заметить только то, что блоки нужно заводить не одной операцией malloc(), а каждый поток должен сделать malloc() своих блоков. В Linux malloc() автоматически округляет выделенную память до ближайшей степени двойки, что позволит нам избежать эффекта false sharing.

Что же это дало?



По сути описанные выше 2 оптимизации не дают огромного прироста в скорости, но после них становится возможной эффективная векторизация, которая и даст желаемый прирост в скорости, в моём случае - в 3 раза. Так же стоит отметить, что при небольших периодах есть гораздо более эффективные методы, например за O(m^3), которые используют гораздо меньше памяти. Данные оптимизации рассчитаны скорее на задачу в общем случае, нежели на конкретную постановку.

Источники:


1. Об оптимизации вычислительных приложений для многопроцессорных систем с общей неоднородной памятью
2. Memory in a Linux/NUMA System
分类:
如需更全面地了解编译器优化,请参阅优化注意事项