Быстрый способ генерации псевдослучайных битов с заданной вероятностью 0 или 1 для каждого бита

как правило, генератор случайных чисел возвращает поток битов, для которых вероятность наблюдать 0 или 1 в каждой позиции равна (т. е. 50%). Давайте назовем это непредвзятым PRNG.



мне нужно сгенерировать строку псевдослучайных битов со следующим свойством: вероятность увидеть 1 в каждой позиции равна p (т. е. вероятность увидеть 0 равна 1-p). Параметр p является вещественным числом от 0 до 1; в моей задаче бывает, что он имеет разрешение 0,5%, т. е. он может принимать значения 0%, 0.5%, 1%, 1.5%, ..., 99.5%, 100%.



обратите внимание, что P-это вероятность, а не точное отношение. Фактическое число битов, равное 1 в потоке из n битов, должно следовать биномиальному распределению B (n, p).



существует наивный метод, который может использовать несмещенный PRNG для генерации значения каждого бита (псевдокод):



generate_biased_stream(n, p):

  result = []

  for i in 1 to n:

    if random_uniform(0, 1) < p:

      result.append(1)

    else:

      result.append(0)

  return result


такая реализация намного медленнее, чем одна генерация несмещенного потока, так как она вызывает случайное число функция генератора один раз на каждый бит; в то время как генератор несмещенного потока вызывает его один раз на размер слова (например, он может генерировать 32 или 64 случайных бита с одним вызовом).



Я хочу более быструю реализацию, даже она немного жертвует случайностью. Идея, которая приходит на ум, состоит в том, чтобы предварительно вычислить таблицу поиска: для каждого из 200 возможных значений p вычислите 8-битные значения C с помощью более медленного алгоритма и сохраните их в таблице. Тогда быстрый алгоритм просто выберет один из них наугад чтобы создать перекос 8 бит.



задняя часть вычисления конверта, чтобы увидеть, сколько памяти необходимо:
C должно быть не менее 256 (количество возможных 8-битных значений), вероятно, больше, чтобы избежать эффектов выборки; скажем, 1024. Возможно, число должно варьироваться в зависимости от p, но давайте оставим его простым и скажем, что среднее значение равно 1024.
Так как есть 200 значений p = > общее использование памяти составляет 200 КБ. Это не плохо, и может поместиться в кэш L2 (256 КБ). Мне все еще нужно оценить его, чтобы увидеть, есть ли являются ли эффекты выборки, которые вводят смещения, и в этом случае C должен быть увеличен.



недостатком этого решения является то, что он может генерировать только 8 бит сразу, даже с большим количеством работы, в то время как непредвзятый PRNG может генерировать 64 сразу с помощью всего нескольких арифметических инструкций.



Я хотел бы знать, есть ли более быстрый метод, основанный на битовых операциях вместо таблиц поиска. Например, изменение кода генерации случайных чисел непосредственно для введения смещение для каждого бита. Это позволит достичь той же производительности, что и беспристрастный PRNG.




Редактировать 5 Марта



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




  • измените требования к проблеме так, чтобы P имел разрешение 1/256 вместо 1/200. Это позволяет использовать биты более эффективно, а также дает больше возможностей для оптимизации. Я думаю, что смогу сделать это изменение.

  • используйте арифметическое кодирование для эффективного использования битов от несмещенного генератора. С вышеуказанным изменением разрешения это становится намного проще.

  • несколько человек предположили, что PRNGs очень быстры, поэтому использование арифметического кодирования может фактически замедлить код из-за введенных накладных расходов. Вместо этого я всегда должен использовать наихудшее количество битов и оптимизировать этот код. См. ниже контрольные показатели.

  • @rici предложил использовать SIMD. Это хорошая идея, которая работает только в том случае, если мы всегда потребляем фиксированное количество битов.


бенчмарки (без арифметического декодирования)



Примечание: как многие из вас предложили, я изменил резолюцию с 1/200 на 1/256.



я писал несколько реализаций наивного метода, который просто берет 8 случайных несмещенных битов и генерирует 1 смещенный бит:




  • без SIMD

  • С SIMD используя туман Agner библиотека векторного класса, как предложено @rici

  • С SIMD с помощью встроенных


я использую два несмещенных генератора псевдослучайных чисел:




Я также измеряю скорость непредвзятого PRNG для сравнения. Вот результаты:





RNG: Ranvec1(Mersenne Twister for Graphics Processors + Multiply with Carry)



Method: Unbiased with 1/1 efficiency, SIMD=vectorclass (incorrect, baseline)

Gbps/s: 16.081 16.125 16.093 [Gb/s]

Number of ones: 536,875,204 536,875,204 536,875,204

Theoretical   : 104,857,600



Method: Biased with 1/8 efficiency

Gbps/s: 0.778 0.783 0.812 [Gb/s]

Number of ones: 104,867,269 104,867,269 104,867,269

Theoretical   : 104,857,600



Method: Biased with 1/8 efficiency, SIMD=vectorclass

Gbps/s: 2.176 2.184 2.145 [Gb/s]

Number of ones: 104,859,067 104,859,067 104,859,067

Theoretical   : 104,857,600



Method: Biased with 1/8 efficiency, SIMD=intrinsics

Gbps/s: 2.129 2.151 2.183 [Gb/s]

Number of ones: 104,859,067 104,859,067 104,859,067

Theoretical   : 104,857,600


SIMD увеличивает производительность на a коэффициент 3 по сравнению со скалярным методом. Это в 8 раз медленнее, чем несмещенный генератор, как и ожидалось.



самый быстрый смещенный генератор достигает 2,1 Гбит/с.





RNG: xorshift128plus



Method: Unbiased with 1/1 efficiency (incorrect, baseline)

Gbps/s: 18.300 21.486 21.483 [Gb/s]

Number of ones: 536,867,655 536,867,655 536,867,655

Theoretical   : 104,857,600



Method: Unbiased with 1/1 efficiency, SIMD=vectorclass (incorrect, baseline)

Gbps/s: 22.660 22.661 24.662 [Gb/s]

Number of ones: 536,867,655 536,867,655 536,867,655

Theoretical   : 104,857,600



Method: Biased with 1/8 efficiency

Gbps/s: 1.065 1.102 1.078 [Gb/s]

Number of ones: 104,868,930 104,868,930 104,868,930

Theoretical   : 104,857,600



Method: Biased with 1/8 efficiency, SIMD=vectorclass

Gbps/s: 4.972 4.971 4.970 [Gb/s]

Number of ones: 104,869,407 104,869,407 104,869,407

Theoretical   : 104,857,600



Method: Biased with 1/8 efficiency, SIMD=intrinsics

Gbps/s: 4.955 4.971 4.971 [Gb/s]

Number of ones: 104,869,407 104,869,407 104,869,407

Theoretical   : 104,857,600


для xorshift SIMD увеличивает производительность в 5 раз по сравнению со скалярным методом. Это в 4 раза медленнее, чем беспристрастный генератор. Обратите внимание, что это скалярная реализация xorshift.



самый быстрый смещенный генератор достигает 4,9 Гбит/с.





RNG: xorshift128plus_avx2



Method: Unbiased with 1/1 efficiency (incorrect, baseline)

Gbps/s: 18.754 21.494 21.878 [Gb/s]

Number of ones: 536,867,655 536,867,655 536,867,655

Theoretical   : 104,857,600



Method: Unbiased with 1/1 efficiency, SIMD=vectorclass (incorrect, baseline)

Gbps/s: 54.126 54.071 54.145 [Gb/s]

Number of ones: 536,874,540 536,880,718 536,891,316

Theoretical   : 104,857,600



Method: Biased with 1/8 efficiency

Gbps/s: 1.093 1.103 1.063 [Gb/s]

Number of ones: 104,868,930 104,868,930 104,868,930

Theoretical   : 104,857,600



Method: Biased with 1/8 efficiency, SIMD=vectorclass

Gbps/s: 19.567 19.578 19.555 [Gb/s]

Number of ones: 104,836,115 104,846,215 104,835,129

Theoretical   : 104,857,600



Method: Biased with 1/8 efficiency, SIMD=intrinsics

Gbps/s: 19.551 19.589 19.557 [Gb/s]

Number of ones: 104,831,396 104,837,429 104,851,100

Theoretical   : 104,857,600


этот реализация использует AVX2 для параллельного запуска 4 несмещенных генераторов xorshift.



самый быстрый смещенный генератор достигает 19,5 Гб/с.



бенчмарки для арифметического декодирования



простые тесты показывают, что арифметический код декодирования является узким местом, а не PRNG. Поэтому я только сравниваю самый дорогой PRNG.





RNG: Ranvec1(Mersenne Twister for Graphics Processors + Multiply with Carry)



Method: Arithmetic decoding (floating point)

Gbps/s: 0.068 0.068 0.069 [Gb/s]

Number of ones: 10,235,580 10,235,580 10,235,580

Theoretical   : 10,240,000



Method: Arithmetic decoding (fixed point)

Gbps/s: 0.263 0.263 0.263 [Gb/s]

Number of ones: 10,239,367 10,239,367 10,239,367

Theoretical   : 10,240,000



Method: Unbiased with 1/1 efficiency (incorrect, baseline)

Gbps/s: 12.687 12.686 12.684 [Gb/s]

Number of ones: 536,875,204 536,875,204 536,875,204

Theoretical   : 104,857,600



Method: Unbiased with 1/1 efficiency, SIMD=vectorclass (incorrect, baseline)

Gbps/s: 14.536 14.536 14.536 [Gb/s]

Number of ones: 536,875,204 536,875,204 536,875,204

Theoretical   : 104,857,600



Method: Biased with 1/8 efficiency

Gbps/s: 0.754 0.754 0.754 [Gb/s]

Number of ones: 104,867,269 104,867,269 104,867,269

Theoretical   : 104,857,600



Method: Biased with 1/8 efficiency, SIMD=vectorclass

Gbps/s: 2.094 2.095 2.094 [Gb/s]

Number of ones: 104,859,067 104,859,067 104,859,067

Theoretical   : 104,857,600



Method: Biased with 1/8 efficiency, SIMD=intrinsics

Gbps/s: 2.094 2.094 2.095 [Gb/s]

Number of ones: 104,859,067 104,859,067 104,859,067

Theoretical   : 104,857,600


простой метод фиксированной точки достигает 0,25 Гбит / с, в то время как наивный скалярный метод в 3 раза быстрее, а наивный метод SIMD В 8 раз быстрее. Возможно, есть способы оптимизировать и/или распараллелить метод арифметического декодирования дальше, но из-за его сложности я решил остановиться здесь и выбрать наивную реализацию SIMD.



спасибо всем за помощь.

881   0  

Comments

    Ничего не найдено.
Click here to cancel reply.