Ответ 1

Предположим, вы хотите разделить эту работу среди потоков 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) ⁴. Поскольку мы знаем, что N >> M, вероятно, это плохой компромисс в этом случае. Тем не менее, стоит отметить, что скрытые константы в каждом члене очень разные: термин O(N), который приходит с шага слияния ⁰ может использовать 256-битные команды ширины vpor, что означает пропускную способность что-то близкое к 200-500 бит/цикл (если кэшировано), а шаг установки бит, который O(M/T), я оцениваю ближе к 1 бит/цикл. Таким образом, этот подход, безусловно, может быть лучшим для умеренного T, даже если размер N равен 10 или 100 раз больше M.

Разделы 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, а затем логически объединяет ¹ их в конце поэтому у вас есть T разделы M.

Второй шаг - фактически установить все биты: вы назначаете один раздел для каждого потока T, который может устанавливать биты по принципу "один поток", то есть не беспокоиться о параллельных обновлениях, поскольку каждый поток работает на непересекающемся разбиении N ².

Оба шага O(M), а второй шаг идентичен однопоточному случаю, поэтому накладные расходы для его распараллеливания являются первым шагом. Я подозреваю, что первый будет варьироваться от примерно той же скорости, что и второй, возможно, в 2-4 раза медленнее, в зависимости от реализации и аппаратного обеспечения, поэтому вы можете ожидать ускорения на машине со многими ядрами, но только с 2 или 4 она может не лучше.

Если распределение M не является гладким, так что разделы, созданные на первом шаге, имеют самые разные размеры, они будут работать плохо, потому что некоторые потоки получат намного больше работы. Простая стратегия состоит в том, чтобы создать say 10 * T разделы, а не только T и иметь потоки во втором проходе, которые все потребляют из одной очереди разделов до завершения. Таким образом, вы распределяете работу более равномерно, если массив M не сильно сгруппирован. В этом случае вы можете рассмотреть уточнение первого шага, который сначала, по существу, создает гистограмму элементов в квадратных скобках, а затем стадию уменьшения, которая рассматривает объединенную гистограмму для создания хорошего разбиения.

По сути, мы просто постепенно перерабатываем первый этап в тип параллельного алгоритма сортировки/разбиения, для которого уже имеется много литературы. Вы даже можете обнаружить, что полная (параллельная) сортировка является самой быстрой, так как она очень поможет в настройке бит-установки, поскольку доступ будет в порядке и иметь лучшую пространственную локальность (помогая с предварительной выборкой и кэшированием, соответственно).

⁰... а также из шага "выделить частный массив длины N", хотя это, вероятно, будет довольно быстрым.

¹ Концептуально простейшей формой слияния было бы просто скопировать все поточные разделы M так, чтобы у вас было непрерывное разделение всех M, но на практике, если разделы большие, вы могут просто оставить разделы, где они есть, и связать их вместе, добавив некоторую сложность в код потребления, но избегая шага уплотнения.

² Чтобы сделать его действительно непересекающимся с точки потоковой передачи, вы хотите, чтобы раздел N попадал на "границы байтов" и, возможно, даже границы линии кэша, чтобы избежать ложного обмена (хотя последнее, вероятно, не является большой проблемой, поскольку оно встречается только на краю каждого раздела, а порядок обработки означает, что вы вряд ли получите конкуренцию).

⁴ На практике точный "порядок" параллельного решения базовой линии с использованием общего N трудно определить, потому что будет существовать конфликт, поэтому масштабирование O(M/T) будет ломаться достаточно большим T. Если предположить, что N достаточно велико, а T ограничено типичным аппаратным обеспечением concurrency не более дюжины ядер или, следовательно, вероятно, приближается OK.

Ответ 2

@IraBaxter опубликовал интересную, но ошибочную идею, которую можно заставить работать (при значительной стоимости). Я подозреваю, что идея @BeeOnRope частичной сортировки/разбиения массива M будет работать лучше (особенно для процессоров с большими частными кэшами, которые могут содержать части N горячего). Я обобщу модифицированную версию идеи Иры, которую я описал в комментариях по его удаленному ответу. (В этом ответе есть некоторые предложения о том, как большой N должен быть, прежде чем он стоит многопоточность.)

Каждый поток писателей получает фрагмент M без сортировки/разбиения.

Идея состоит в том, что конфликты очень редки, потому что N велико по сравнению с количеством магазинов, которые могут быть в полете сразу. Поскольку установка бит является идемпотентной, поэтому мы можем обрабатывать конфликты (где два потока хотят установить разные биты в одном и том же байте), проверяя значение в памяти, чтобы убедиться, что на самом деле у него действительно установлен бит, который мы хотим после операции RMW, например or [N + rdi], al (без префикса lock).

например. thread 1 попытался сохранить 0x1 и наступил на хранилище 2-го потока 0x2. Thread 2 должен заметить и повторить запись read-modify-write (возможно, с lock or, чтобы она была простой и сделать несколько попыток невозможным), чтобы закончилось с 0x3 в байте конфликта.

Нам нужна команда mfence перед чтением. В противном случае сохранение в магазине даст нам то значение, которое мы только что написали прежде чем другие потоки видят наш магазин. Другими словами, поток может наблюдать свои собственные магазины раньше, чем они появляются в глобальном порядке. x86 имеет общий ордер для магазинов, но не для загрузки. Таким образом, нам нужно mfence, чтобы предотвратить переупорядочение StoreLoad. (Intel "Loads Are not Reordered with Older Stores to the same location" гарантия не так полезна, как кажется: store/reload не является барьером памяти, они просто говорят о нестандартном исполнении, сохраняя программный порядок семантика.)

mfence стоит дорого, но трюк, который делает это лучше, чем просто использование lock or [N+rdi], al, заключается в том, что мы можем выполнять пакетные операции. например выполните 32 or инструкций, а затем 32 чтения. Это компромисс между накладными расходами mfence на операцию и увеличением вероятности ложного обмена (чтение строк кэша, которые уже были признаны недействительными другим CPU, требующим их).

Вместо фактической инструкции mfence мы можем сделать последнюю or группы как lock or. Это лучше для пропускной способности как для AMD, так и для Intel. Например, согласно таблицы Agner Fog, mfence имеет один на 33c пропускную способность на Haswell/Skylake, где lock add (такая же производительность, как or) имеет пропускную способность 18c или 19c. Или для Рызена, ~ 70c (mfence) против ~ 17c (lock add).

Если мы ограничиваем количество операций на заборе очень низким, индекс массива (m[i]/8) + mask (1<<(m[i] & 7)) может храниться в регистре для всех операций. Это, вероятно, не стоит; заборы слишком дороги, чтобы делать так часто, как каждые 6 or операций. Использование инструкций бит-строки bts и bt означало бы, что мы могли бы хранить больше индексов в регистрах (потому что не требуется никакого сдвига-результата), но, вероятно, не стоит того, потому что они медленны.

Использование векторных регистров для хранения индексов может быть хорошей идеей, чтобы избежать необходимости перезагружать их из памяти после барьера. Мы хотим, чтобы адреса загрузки были готовы, как только могут быть загружены загрузочные файлы (поскольку они ждут последнего хранилища до того, как барьер зафиксирует L1D и станет глобально видимым).

Использование однобайтовой read-modify-write делает фактические конфликты настолько маловероятными, насколько это возможно. Каждая запись байта делает неатомный RMW на 7 соседних байтах. Производительность по-прежнему страдает от ложного обмена, когда два потока изменяют байты в одной и той же линии кэша 64B, но по крайней мере мы избегаем фактического повторения операций or. 32-разрядный размер элемента сделает некоторые вещи более эффективными (например, с помощью xor eax,eax/bts eax, reg для генерации 1<<(m[i] & 31) всего 2 uops или 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 отсутствует.) Вероятно, я бы использовал legacy __sync_fetch_and_or, который является полным барьером для всех операций с памятью.

Он использует GNU C atomic builtins для выполнения атомных операций RMW, где это необходимо, для переменных, которые не являются atomic_uint8_t. Запуск этой функции из нескольких потоков одновременно будет C11 UB, но нам нужно только его работать на x86. Я использовал volatile, чтобы получить разрешенную асинхронную модификацию часть atomic, не заставляя N[idx] |= mask; быть атомарной.. Идея состоит в том, чтобы убедиться, что проверки с обратным отсчетом не оптимизируются прочь.

Я использую __atomic_fetch_or как барьер памяти, потому что знаю, что он будет на x86. С seq_cst это, вероятно, будет и на других ISA, но это все большой взлом.

Ответ 3

В наборах есть несколько операций (A, B = set, X = element в наборе):

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 и т.д.
Чтобы установить, reset или проверить отдельные биты, вы просто используете

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.     

(Я уверен, что этот код можно улучшить с помощью команд blend/gather etc) Отсюда вы можете просто перейти к более крупным наборам или другим операциям.

Обратите внимание, что bt, btc, bts с операндом памяти не ограничено 64 битами.
Следующее будет прекрасно работать.

mov eax,1023
bts [rcx],rax   //set 1024st element (first element is 0).