Атомный, масштабируемый, монотонный счетчик с границей

Question

У меня есть критический путь кода, где потоки используют атомарный инкремент для целого числа, чтобы подсчитать количество событий, которые произошли в глобальном масштабе. Это достаточно быстро, но все же требует, чтобы строка кэша, содержащая целые числа, отскакивала между ядрами. В системе NUMA это создает много трафика MESI.

Псевдокод горячего следования состоит в том, что все потоки делают это:

const int CHECK_VALUE = 42;

int counterNew = counter++;
if (counterNew == CHECK_VALUE) {
  Do Final work
}

Счетчик монотонно увеличивается, и значение, которое он должен достичь, известно заранее.

По крайней мере, один поток должен сделать вывод, что глобальный счетчик достиг CHECK_VALUE после того, как он увеличился counter, Приемлемо, что более одного потока приходят к такому выводу (я всегда могу синхронизировать их в этот момент, поскольку это уже не горячий путь).

Возможно ли добиться большего успеха, чем использование атомарного приращения для отслеживания значения counter если я знаю, что это монотонный и конечное значение известно?

Answer 1

Без синхронизации возможно, что счетчик останется на уровне 0. На самом деле это состояние гонки будет не так часто, поэтому счетчик будет примерно точным. Я думаю, вы можете доказать, что никакое значение не будет пропущено в последовательности счетчиков: невозможно изменить счетчик на 2, если он не был ранее 1, что относится к каждому значению, которое может содержать счетчик. Таким образом, глобальный счетчик, использующий ++ вместо атомарного приращения, сработал бы, если бы можно было пропустить несколько событий. Тем не менее, даже при несинхронизации это все равно вызовет некоторые проблемы с памятью, которые вы хотите избежать (ресинхронизация строк кэша через процессоры).

Еще один способ сделать это опрос. Каждый поток может считать свои события в своих личных данных. Другой поток может опрашивать раз в минуту, чтобы узнать, является ли количество событий> пороговым.

Другой способ сделать это - увеличить внутренний счетчик в данных потока, а когда он достигнет 10, увеличить глобальный счетчик. Это уменьшит количество глобальных приращений на 10.

Другим способом было бы столкнуть внутренний счетчик в потоке. Выполните синхронизацию всякий раз, когда отдельный поток достиг cEvents / threadcount.

Другим способом было бы столкнуть внутренний счетчик в потоке. Всякий раз, когда отдельный поток достиг определенного предела, проверьте количество других потоков, чтобы увидеть, если они вместе> счетчик потоков. Это примерно то же самое, что и использование потока опроса, но без использования другого потока.

Есть много способов сделать что-то подобное с частными счетчиками. Все зависит от точности, которая вам нужна.

Answer 2

Вы можете сделать это с помощью атомарной операции CAS (сравните и подкачайте). На архитектуре i386 это инструкция CMPXCHG. При необходимости вы можете использовать функцию небольшой сборки, внедрить CAS на вашей платформе или спросить меня здесь о реализации Intel. Ваш код должен быть следующим:

int local_cnt;
// Atomic increment counter 
do {
  local_cnt = counter;
} while(cas(&counter, local_cnt, local_cnt + 1) != local_cnt);

// check old counter value
if(local_cnt == CHECK_VALUE) { 
  // do something
}