Как эффективно установить биты битового вектора параллельно?
Рассмотрим немного вектора N биты в нем (N большой) и массив M числа (M умеренный, обычно намного меньше, чем N), каждый в диапазоне 0..N-1 указывающий, какой бит вектора должен быть установлен в 1, Последний массив не отсортирован. Битовый вектор - это просто массив целых чисел, в частности __m256iгде 256 бит упакованы в каждый __m256i состав.
Как эффективно разделить эту работу на несколько потоков?
Предпочтительным языком является C++ (MSVC++2017 toolset v141), сборка также отличная. Предпочитаемый ЦП x86_64 (встроенные в порядке). AVX2 желателен, если какая-либо выгода от этого.
3 ответа
Давайте предположим, что вы хотите разделить эту работу между T потоки. Это довольно интересная проблема, поскольку ее нетрудно распараллелить с помощью разбиения, и для разных размеров могут применяться различные решения. N а также M,
Полностью параллельная базовая линия
Вы можете просто разделить массив M в T разделы и каждый поток работает на своем собственном разделе M с общим N, Основная проблема заключается в том, что с M не отсортирован, все потоки могут получить доступ к любому элементу N и, следовательно, топать друг друга работой. Чтобы избежать этого, вы должны использовать атомарные операции, такие как std::atomic::fetch_or за каждую модификацию общего N массив, или придумать какую-то схему блокировки. Оба подхода могут снизить производительность (т. Е. Использование атомарной операции для установки бита, вероятно, будет на порядок медленнее, чем эквивалентный однопоточный код).
Давайте посмотрим на идеи, которые, вероятно, быстрее.
Частный N
Одна относительно очевидная идея избежать проблемы "общего N", которая требует атомарных операций для всех мутаций N, состоит в том, чтобы просто дать каждому T частную копию N и объединить их в конце с помощью or,
К сожалению, это решение O(N) + O(M/T) тогда как оригинальное однопоточное решение O(M) и "атомное" решение выше - это что-то вроде O(M/T)4 Поскольку мы знаем, что N >> M это может быть плохой компромисс в этом случае. Тем не менее, стоит отметить, что скрытые константы в каждом термине очень разные: O(N) термин, который приходит из шага слияния0 может использовать 256-битную ширину vpor инструкции, означающие пропускную способность, близкую к 200-500 битам / цикл (если кэшируется), в то время как шаг установки битов, который O(M/T) Я оцениваю ближе к 1 бит / цикл. Таким образом, этот подход, безусловно, может быть лучшим для умеренного Т, даже если размер N в 10 или 100 раз больше M,
Перегородки М
Основная идея здесь состоит в том, чтобы разделить индексы в M так что каждый рабочий поток может затем работать на непересекающейся части N массив. Если M было отсортировано, это было бы тривиально, но это не так, так что...
Простой алгоритм, который будет хорошо работать, если M плавно распределяется в первом разделе, что значения M в T ведра, с ведрами, имеющими значения в диапазонах [0, N/T), [N/T, 2N/T], ..., [(T-1)N/T, N), То есть делим N в T разделить регионы, а затем найти значения M которые попадают в каждый из них. Вы можете распространить эту работу по всей T потоки, назначая каждому потоку кусок равного размера Mи каждый из них создает T разделы, а затем логически объединяя их1 в конце, так что у вас есть T перегородки M,
Второй шаг - установить все биты: вы назначаете один раздел каждому потоку. T который может устанавливать биты "однопоточным" способом, т. е. не беспокоиться о параллельных обновлениях, поскольку каждый поток работает на непересекающемся разделе N2
Оба шага O(M) и второй шаг идентичен однопоточному случаю, поэтому накладные расходы на распараллеливание это первый шаг. Я подозреваю, что первое будет иметь скорость примерно с той же скоростью, что и второе, и, возможно, в 2-4 раза медленнее, в зависимости от реализации и аппаратного обеспечения, поэтому вы можете ожидать ускорения на машине со многими ядрами, но только с 2 или 4 это может не будет лучше.
Если распределение M не является гладким, так что разделы, созданные на первом шаге, имеют очень разные размеры, это будет работать плохо, потому что некоторые потоки получат намного больше работы. Простая стратегия заключается в создании сказать 10 * T перегородки, а не только T и все потоки во втором проходе потребляют из одной и той же очереди разделов до завершения. Таким образом вы распределяете работу более равномерно, если только массив M очень сгруппирован. В этом случае вы могли бы рассмотреть уточнение первого шага, который сначала по существу создает гистограмму элементов с пакетами, а затем стадию сокращения, которая просматривает объединенную гистограмму для создания хорошего разбиения.
По сути, мы только постепенно совершенствуем первый этап в виде алгоритма параллельной сортировки / разбиения, для которого уже имеется много литературы. Вы можете даже обнаружить, что полная (параллельная) сортировка является самой быстрой, поскольку она очень поможет на этапе установки битов, так как доступы будут упорядочены и будут иметь лучшую пространственную локализацию (помогая с предварительной выборкой и кэшированием, соответственно).
0... а также из шага "выделить частный массив длины N", хотя, скорее всего, это будет довольно быстро.
1 Концептуально самой простой формой объединения было бы просто скопировать разделы M каждого потока так, чтобы у вас был непрерывный раздел всех M, но на практике, если разделы большие, вы можете просто оставить разделы там, где они есть, и связать их вместе, добавив некоторую сложность к потребляющему коду, но избегая этапа сжатия.
2 Чтобы сделать его действительно непересекающимся с точки зрения потоков, вы хотите обеспечить разделение N падает на "границы байтов" и, возможно, даже границы строк кэша, чтобы избежать ложного совместного использования (хотя последнее, скорее всего, не будет большой проблемой, поскольку это происходит только на границе каждого раздела, а порядок обработки означает, что вы вряд ли получит раздор).
4 На практике точный "порядок" базового параллельного решения с использованием общего N трудно определить, потому что будет раздор, поэтому O(M/T) масштабирование сломается на достаточно большой T, Если мы предположим, N довольно большой и T ограничено типичным аппаратным параллелизмом, состоящим не более чем из дюжины ядер, или, возможно, это нормальное приближение.
@IraBaxter опубликовал интересную, но ошибочную идею, которую можно заставить работать (при значительных затратах). Я подозреваю, что идея @BeeOnRope о частичной сортировке / разбиении массива M будет работать лучше (особенно для процессоров с большими частными кэшами, которые могут поддерживать части N горячими). Я суммирую измененную версию идеи Ира, которую я описал в комментариях к его удаленному ответу. (В этом ответе содержатся некоторые предположения о том, каким должно быть большое N, прежде чем оно станет многопоточным.)
Каждый поток записи получает кусок M без сортировки / разбиения.
Идея состоит в том, что конфликты очень редки, потому что N велико по сравнению с количеством магазинов, которые могут быть в полете одновременно. Поскольку установка бита идемпотентна, поэтому мы можем обрабатывать конфликты (когда два потока хотят установить разные биты в одном и том же байте), проверяя значение в памяти, чтобы убедиться, что он действительно имеет установленный бит, который мы хотим после операции RMW, например or [N + rdi], al (без lock префикс).
Например, поток 1 пытался сохранить 0x1 и наступил на нить 2 х магазина 0x2, Поток 2 должен заметить и повторить чтение-изменение-запись (возможно, с lock or для простоты и невозможности многократных повторов) 0x3 в конфликте байт.
Нам нужен mfence инструкция перед чтением. В противном случае пересылка из магазина даст нам значение, которое мы только что написали, прежде чем другие потоки увидят наш магазин. Другими словами, поток может наблюдать свои собственные хранилища раньше, чем они появляются в глобальном порядке. x86 имеет общий заказ для магазинов, но не для нагрузок. Таким образом, нам нужно mfence для предотвращения переупорядочения StoreLoad. (Гарантия Intel "Загрузка не переупорядочивается со старыми хранилищами в одно и то же место" не так полезна, как кажется: сохранение / перезагрузка не является барьером памяти; они просто говорят о неупорядоченном выполнении, сохраняющем порядок программы семантика.)
mfence это дорого, но хитрость, которая делает это лучше, чем просто использование lock or [N+rdi], al в том, что мы можем выполнять пакетные операции. например, до 32 or инструкции, а затем 32 для чтения. Это компромисс между mfence накладные расходы на операцию в сравнении с увеличением вероятности ложного совместного использования (чтение строк кэша, которые уже были признаны недействительными другим процессором, запрашивающим их)
Вместо фактического mfence инструкция, мы можем сделать последнее or группы как lock or, Это лучше для пропускной способности как AMD, так и Intel. Например, согласно таблицам Агнера Фога, mfence имеет одну пропускную способность 33c на Haswell/Skylake, где lock add (та же производительность, что и or) имеет пропускную способность 18c или 19c. Или для Рызена ~70с (mfence) против ~17с (lock add).
Если мы сохраняем количество операций на забор очень низким, индекс массива (m[i]/8) + маска (1<<(m[i] & 7)) можно хранить в регистрах для всех операций. Это, вероятно, не стоит того; заборы слишком дороги, чтобы делать так часто, как каждые 6 or операции. С использованием bts а также bt Строковые инструкции означают, что мы можем хранить больше индексов в регистрах (потому что результат сдвига не требуется), но, вероятно, не стоит, потому что они медленные.
Использование векторных регистров для хранения индексов может быть хорошей идеей, чтобы избежать необходимости перезагружать их из памяти после барьера. Мы хотим, чтобы адреса загрузки были готовы, как только загрузочные операции чтения будут выполняться (потому что они ждут, когда последнее хранилище перед барьером перейдет в L1D и станет глобально видимым).
Использование однобайтового чтения-изменения-записи делает реальные конфликты настолько маловероятными, насколько это возможно. Каждая запись байта делает неатомарную RMW только на 7 соседних байтах. Производительность все еще страдает от ложного разделения, когда два потока изменяют байты в той же строке кэша 64B, но по крайней мере мы избегаем необходимости фактически повторять столько or операции. 32-битный размер элемента сделает некоторые вещи более эффективными (например, использование xor eax,eax / bts eax, reg чтобы генерировать 1<<(m[i] & 31) только с 2 мопами, или 1 для BMI2 shlx eax, r10d, reg (где r10d=1).)
Избегайте строковых инструкций, таких как bts [N], eax: пропускная способность хуже, чем при вычислении индексации и маски or [N + rax], dl, Это идеальный вариант использования (за исключением того, что мы не заботимся о старом значении бита в памяти, мы просто хотим установить его), но его багаж CISC слишком велик.
В C функция может выглядеть примерно так:
/// UGLY HACKS AHEAD, for testing only.
// #include <immintrin.h>
#include <stddef.h>
#include <stdint.h>
void set_bits( volatile uint8_t * restrict N, const unsigned *restrict M, size_t len)
{
const int batchsize = 32;
// FIXME: loop bounds should be len-batchsize or something.
for (int i = 0 ; i < len ; i+=batchsize ) {
for (int j = 0 ; j<batchsize-1 ; j++ ) {
unsigned idx = M[i+j];
unsigned mask = 1U << (idx&7);
idx >>= 3;
N[idx] |= mask;
}
// do the last operation of the batch with a lock prefix as a memory barrier.
// seq_cst RMW is probably a full barrier on non-x86 architectures, too.
unsigned idx = M[i+batchsize-1];
unsigned mask = 1U << (idx&7);
idx >>= 3;
__atomic_fetch_or(&N[idx], mask, __ATOMIC_SEQ_CST);
// _mm_mfence();
// TODO: cache `M[]` in vector registers
for (int j = 0 ; j<batchsize ; j++ ) {
unsigned idx = M[i+j];
unsigned mask = 1U << (idx&7);
idx >>= 3;
if (! (N[idx] & mask)) {
__atomic_fetch_or(&N[idx], mask, __ATOMIC_RELAXED);
}
}
}
}
Это примерно соответствует тому, что мы хотим с помощью gcc и clang. Asm ( Godbolt) может быть более эффективным в нескольких отношениях, но может быть интересно попробовать это. Это небезопасно: я просто взломал это вместе в C, чтобы получить asm, который я хотел для этой автономной функции, без встраивания в вызывающую функцию или что-то еще. __atomic_fetch_or не является надлежащим барьером компилятора для неатомарных переменных способ asm("":::"memory") является. (По крайней мере, C11 stdatomic версия не.) Я должен был бы использовать наследие __sync_fetch_and_or, что является полным барьером для всех операций с памятью.
В нем используются атомарные встроенные функции GNU C для выполнения атомарных операций RMW, где это необходимо, для переменных, которые не являются atomic_uint8_t, Запуск этой функции сразу из нескольких потоков был бы C11 UB, но он нам нужен только для работы на x86. я использовал volatile чтобы получить часть, разрешенную для асинхронной модификации atomic без принуждения N[idx] |= mask; быть атомным. Идея состоит в том, чтобы убедиться, что проверки на повторное чтение не оптимизируются.
я использую __atomic_fetch_or как барьер памяти, потому что я знаю, что это будет на x86. С seq_cst это, вероятно, будет и на других ISA, но это большой хак.
Есть несколько операций, включенных в наборы (A,B = набор, X = элемент в наборе):
Set operation Instruction
---------------------------------------------
Intersection of A,B A and B
Union of A,B A or B
Difference of A,B A xor B
A is subset of B A and B = B
A is superset of B A and B = A
A <> B A xor B <> 0
A = B A xor B = 0
X in A BT [A],X
Add X to A BTS [A],X
Subtract X from A BTC [A],X
Учитывая тот факт, что вы можете использовать логические операторы для замены операций множества, вы можете использовать VPXOR, VPAND и т.п.
Чтобы установить, сбросить или проверить отдельные биты, которые вы просто используете
mov eax,BitPosition
BT [rcx],rax
Вы можете установить, если набор (равен) пуст (или что-то еще), используя следующий код
vpxor ymm0,ymm0,ymm0 //ymm0 = 0
//replace the previous instruction with something else if you don't want
//to compare to zero.
vpcmpeqqq ymm1,ymm0,[mem] //compare mem qwords to 0 per qword
vpslldq ymm2,ymm1,8 //line up qw0 and 1 + qw2 + 3
vpand ymm2,ymm1,ymm2 //combine qw0/1 and qw2/3
vpsrldq ymm1,ymm2,16 //line up qw0/1 and qw2/3
vpand ymm1,ymm1,ymm2 //combine qw0123, all in the lower 64 bits.
//if the set is empty, all bits in ymm1 will be 1.
//if its not, all bits in ymm1 will be 0.
(Я уверен, что этот код можно улучшить с помощью инструкций смешивания / сбора и т. Д.) Отсюда вы можете просто расширить наборы или выполнить другие операции.
Обратите внимание, что bt, btc, bts с операндом памяти не ограничивается 64 битами.
Следующее будет работать просто отлично.
mov eax,1023
bts [rcx],rax //set 1024st element (first element is 0).