Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.iki.rssi.ru/seminar/2015042123/presentation/guskova.pdf Дата изменения: Thu May 7 21:25:54 2015 Дата индексирования: Sun Apr 10 08:51:50 2016 Кодировка: Windows-1251 Поисковые слова: генератора

A VX2 и эффективная генерация псевдослучайных чисел

Гуськова М.С.
НИУ ВШЭ,101000 Москва, Россия НЦЧ РАН, 142432 Черноголовка, Россия

23 апреля 2015


Содержание

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Случайные числа и генераторы Расширения Intel Intel SSE Intel AVX2 Реализация генератора GM31 на AVX2.0 Описание генератора GM31 Результат

Случайные числа и генераторы Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат

Работа выполнена совместно с Л.Ю. Барашом, Л.Н. Щуром


Случайные числа

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Некоторые применения случайных чисел: Моделирование Выборочный метод Численный анализ Компьютерное программирование Принятие решений

Случайные числа и генераторы Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


Определение генераторов псевдослучайных чисел

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Генератор
это структура g = (S , s0 , T , U , G )

Случайные числа и генераторы Расширения Intel

S - конечное множество состояний s0 S - начальное состояние.
преобразование T : S S - функция перехода.

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

U - конечное множество выходных символов. G : S U - выходная функция генератора sn = T (sn-1 )- состояние генератора вычисляется на каждом шаге. un = G (sn )- случайное число

Описание генератора GM31 Результат


Типы генераторов псевдослучайных чисел

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Случайные числа и генераторы Расширения Intel

Все генераторы принадлежат либо двум следующим классам, либо являются их модификациями и комбинациями.

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Линейно-конгруэнтные генераторы (Linear Congruential Generators) самые известные и распространенные. Последовательность случайных чисел вычисляется по следующей формуле x n + 1 = (axn + c ) mod m. Простейшим примером этого класса является генератор rand из стандартной библиотеки xn+1 = (11035155245xn + 12356) mod 231 .

Случайные числа и генераторы Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Генераторы, основанные на сдвиговом регистре (Generalized Feedback Shift Register), обладают огромным периодом, если верно выбрать примитивный полином. Этот полином P (z ) = z k - a1 z k -1 - . . . - ak , где коэффициенты ai Z2 , лежит в основе таких генераторов и является характеристическим для последовательности xn = a1 xn-1 + . . . + ak xn-k . Тогда случайное число можно получить следующим образом un =
L

Случайные числа и генераторы Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

xns
i =1

+i -1

2

-i

Описание генератора GM31 Результат


Расширения Intel

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Streaming SIMD Extensions (SSE) SIMD расшифровывается как Single Instruction - Multiple Data. Это потоковые расширения, способные обрабатывать большое количество данных одной командой. Intel Advanced Vector Extensions (Intel AVX) это новый набор 256-битных команд для Intel SSE, предназначенный для приложений, интенсивно использующих операции с плавающей запятой.

Случайные числа и генераторы Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


Intel SSE

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

SSE работает с такими типами данных, как упакованные числа с плавающей запятой одинарной точности. В одном регистре одновременно могут находиться сразу 4 таких числа. Среди команд SSE различают команды: пересылки данных (MOVAPS,. . . ) арифметические команды (ADDPS, SUBPS, . . . ) команды сравнения (CMPPS,. . . ) команды преобразования типов (CVTPS2PS,. . . ) логические операции (ANDPS,. . . ) команды упаковки (SHUFPS,. . . )

Случайные числа и генераторы Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


Intel A VX2

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Случайные числа и генераторы Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

AVX-расширение включает в себя 256-битные регистры (YMM0-YMM7 для 32-битных систем, YMM0-YMM15 для 64-разрядных систем). Младшие 128 бит YMM регистров называются соответственно 128-битными XMM регистрами.

Описание генератора GM31 Результат


Особенности AVX2.0

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Intel AVX2.0 содержит следующие улучшения: Теперь возможна параллельная обработка восьми чисел типа с плавающей точкой или беззнаковых целых, четырех чисел с плавающей точкой двойной точности. Синтаксис инструкций является трех-операндным для увеличения гибкости и эффективности новых инструкций расширения. Теперь возможны не только операции вида A = A + B , но и A = B + C , т.к. исходные операнды остаются нетронутыми, то в некоторых случаях можно избавиться от теперь уже лишних операций копирования.

Случайные числа и генераторы Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


Особенности AVX2.0

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Intel AVX2.0 содержит следующие улучшения: Теперь возможна параллельная обработка восьми чисел типа с плавающей точкой или беззнаковых целых, четырех чисел с плавающей точкой двойной точности. Синтаксис инструкций является трех-операндным для увеличения гибкости и эффективности новых инструкций расширения. Теперь возможны не только операции вида A = A + B , но и A = B + C , т.к. исходные операнды остаются нетронутыми, то в некоторых случаях можно избавиться от теперь уже лишних операций копирования.

Случайные числа и генераторы Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


Особенности AVX2.0

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Intel AVX2.0 содержит следующие улучшения: Теперь возможна параллельная обработка восьми чисел типа с плавающей точкой или беззнаковых целых, четырех чисел с плавающей точкой двойной точности. Синтаксис инструкций является трех-операндным для увеличения гибкости и эффективности новых инструкций расширения. Теперь возможны не только операции вида A = A + B , но и A = B + C , т.к. исходные операнды остаются нетронутыми, то в некоторых случаях можно избавиться от теперь уже лишних операций копирования.

Случайные числа и генераторы Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


Продолжение

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Некоторые инструкции принимают четыре регистра в качестве операндов, делая код меньше и быстрее. SIMD инструкции имеют 128-битные эквиваленты в расширении AVX, поддерживающие трех-операндный синтаксис. Новый префикс VEX призван упростить дальнейшую переработку кода. Все инструкции SSE, SSE2, SSE3, SSE4 представлены и в AVX. Добавлены принципиально новые инструкции (VPERMD Permute doublewords, VPSLLVD Shift doublewords, и прочие)

Случайные числа и генераторы Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


Продолжение

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Некоторые инструкции принимают четыре регистра в качестве операндов, делая код меньше и быстрее. SIMD инструкции имеют 128-битные эквиваленты в расширении AVX, поддерживающие трех-операндный синтаксис. Новый префикс VEX призван упростить дальнейшую переработку кода. Все инструкции SSE, SSE2, SSE3, SSE4 представлены и в AVX. Добавлены принципиально новые инструкции (VPERMD Permute doublewords, VPSLLVD Shift doublewords, и прочие)

Случайные числа и генераторы Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


Продолжение

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Некоторые инструкции принимают четыре регистра в качестве операндов, делая код меньше и быстрее. SIMD инструкции имеют 128-битные эквиваленты в расширении AVX, поддерживающие трех-операндный синтаксис. Новый префикс VEX призван упростить дальнейшую переработку кода. Все инструкции SSE, SSE2, SSE3, SSE4 представлены и в AVX. Добавлены принципиально новые инструкции (VPERMD Permute doublewords, VPSLLVD Shift doublewords, и прочие)

Случайные числа и генераторы Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


Продолжение

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Некоторые инструкции принимают четыре регистра в качестве операндов, делая код меньше и быстрее. SIMD инструкции имеют 128-битные эквиваленты в расширении AVX, поддерживающие трех-операндный синтаксис. Новый префикс VEX призван упростить дальнейшую переработку кода. Все инструкции SSE, SSE2, SSE3, SSE4 представлены и в AVX. Добавлены принципиально новые инструкции (VPERMD Permute doublewords, VPSLLVD Shift doublewords, и прочие)

Случайные числа и генераторы Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


Описание генератора GM31

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Функция перехода генератора определяется таким преобразованием.

Случайные числа и генераторы Расширения Intel

xi ( yi

(n) n)

=M

xi (n yi

(n-1) -1)

( mod g )

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Выходная функция генератора:
s -1

u

(n)

=
i =0

2

(n ) xi

/g ћ 2

i

Описание генератора GM31 Результат

m- мерсеновская экспонента, значит, g = p = 2m - 1 являются простыми.


Состояние генератора состоит из s точек, лежащих на решетке g Ч g на торе. Решетка на торе L = {0, 1, . . . , g - 1} Ч {0, 1, . . . , g - 1} (0) xi Начальное состояние задается точками (0) , где yi

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Случайные числа и генераторы Расширения Intel

xi , yi {0, 1, . . . , g - 1}, i = 0, 1, . . . , s - 1. Эти точки лежат на целочисленной решетке, их координаты целые и положительные. Начальными точками на единичном двумерном торе (0) xi /g (0, 1] Ч (0, 1] являются , i = 0, 1, . . . , s - 1 (0) yi /g

(0)

(0)

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

В данной реализации вычисляются параллельно 32 рекуррентных соотношения.

Случайные числа и генераторы Расширения Intel

x y

(n) (n)

= kx = ky

n -1 n -1

- qx n - 2 mod g - qy n - 2 mod g

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

k = Tr (M ), q = det (M )

Описание генератора GM31 Результат


SSE
" " " " " " " " " " " " " movaps (%1), %%xmm0\n"\ movaps %%xmm0, %%xmm7\n"\ movaps (%2), %%xmm6\n"\ pmuludq 16(%3), %%xmm0\n"\ pmuludq 32(%3), %%xmm6\n"\ paddq (%3), %%xmm0\n"\ psubq %%xmm6, %%xmm0\n"\ movaps %%xmm0, %%xmm6\n"\ psrlq $31, %%xmm6\n"\ andps %%xmm5, %%xmm0\n"\ paddq %%xmm6, %%xmm0\n"\ movaps %%xmm0, (%1)\n"\ movaps %%xmm7, (%2)\n"\

AVX2
"vmovaps (%1), %%ymm0\n"\ "vmovaps (%2), %%ymm6\n"\ "vmovaps %%ymm0, (%2)\n"\ "vpmuludq 32(%3), %%ymm0, %%ymm0\n"\ "vpmuludq 64(%3), %%ymm6, %%ymm6\n"\ "vpaddq (%3), %%ymm0, %%ymm0\n"\ "vpsubq %%ymm6, %%ymm0, %%ymm0\n"\ "vmovaps %%ymm0, %%ymm6\n"\ "vpsrlq $31, %%ymm6, %%ymm6\n"\ "vandps %%ymm5, %%ymm0, %%ymm0\n"\ "vpaddq %%ymm6, %%ymm0, %%ymm0\n"\ "vmovaps %%ymm0, (%1)\n"\


SSE
" " " " " " " " " "

AVX2
" \ " \ " " " " " " " " " "

vshufps $136, %%ymm1, %%ymm0, %%ymm0\n"\ shufps $136, %%xmm2, %%xmm1\n" vpermpd $216, %%ymm0, %%ymm0\n" shufps $136, %%xmm4, %%xmm3\n" vshufps $136, %%ymm3, %%ymm2, %%ymm2\n"\ psrld $30, %%xmm1\n"\ vpermpd $216, %%ymm2, %%ymm2\n"\ psrld $30, %%xmm3\n"\ vpsrld $30, %%ymm0, %%ymm0\n"\ packssdw %%xmm3, %%xmm1\n"\ vpsrld $30, %%ymm2, %%ymm2\n"\ \n"\ vpackssdw %%ymm2, %%ymm0, %%ymm0\n"\ packsswb %%xmm1, %%xmm0\n"\ vpermpd $216, %%ymm0, %%ymm0\n" psllw $7, %%xmm0\n"\ vpacksswb %%ymm0, %%ymm7, %%ymm0\n"\ pmovmskb %%xmm0, %0\n"\ vpermpd $216, %%ymm0, %%ymm0\n" shll $16, %0\n"\ vpsllw $7, %%ymm0, %%ymm0\n"\ vpmovmskb %%ymm0, %0\n"


Тестирование проводилось на машине со следующими характеристиками
Таблица: Информация о процессоре

Name Codename Specication Instructions sets

Intel Core i5-5200U Broadwell-U Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz MMX, SSE, SSE2, SSE3, SSSE3, SSE4.1, SSE4.2, EM64T, VT-x, AES, AVX, AVX2, FMA3


AVX2 и эффективная генерация псевдослучайных чисел

N = 108 количество генерируемых случайных чисел. Используется компилятор gcc (GNU Compiler Collection). Цифра после -о определяет уровень оптимизации. Время указано в секундах.
h gcc gcc gcc gcc -o0 -o1 -o2 -o3 AVX2 2,1332 2,0896 2,086 2,1012 SSE 3,5406 3,453 3,3322 3,327

Гуськова М.С.

Случайные числа и генераторы Расширения Intel

% 40 39 37 37

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


Заключение

AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Случайные числа и генераторы

Использование расширения AVX2 позволило получить идентичную последовательность случайных чисел. Причем время уменьшилось на 40%, а строк кода стало в два раза меньше (264 - 129).

Расширения Intel

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат


AVX2 и эффективная генерация псевдослучайных чисел Гуськова М.С.

Случайные числа и генераторы Расширения Intel

Спасибо за внимание!

Intel SSE Intel AVX2
Реализация генератора GM31 на AVX2.0

Описание генератора GM31 Результат