Определение задержки и пропускной способности для модульного умножения на CPU и CUDA

Мне нужно определить как задержку, так и пропускную способность для (беззнакового) модульного умножения в CUDA и на процессоре (i5 750).

Для ЦП я нашел этот документ, стр. 121, для Sandy Bridge я не действительно уверен, к какому из них я должен обратиться, однако для «MUL IMUL r32» я получаю 4 цикла для задержки и обратной пропускной способности, равной 2. Тогда «DIV r64» имеет задержку 30-94 и rec.thr. 22-76.

Худший вариант развития событий:

  • задержка 94+4

  • рек.тр. 76+2

Верно? Хотя я использую OpenSSL для их выполнения, я почти уверен, что на самом низком уровне они всегда выполняют простые модульные умножения.

Что касается CUDA, в настоящее время я выполняю модульное умножение в PTX: умножаю 2 числа 32b, сохраняю результат в регистре 64b, загружаю 32b по модулю в регистр 64b, а затем выполняю 64b по модулю.

Если посмотреть здесь, стр. 76, то говорят пропускная способность на Fermi 2.x для 32b целочисленное умножение равно 16 (за такт на MP). По модулю просто говорят: "менее 20 инструкций на устройствах с вычислительной мощностью 2.x"...

что это значит? В худшем случае 20 циклов по модулю на MP задержки? А пропускная способность? Сколько модулей на MP?

Редактировать:

А что, если у меня есть варп, где только первые 16 потоков варпа должны выполнять умножение 32b (16 единиц за такт на MP). Будет ли GPU занят на один или два такта, хотя вторую половину ему делать нечего?


throughput cuda multiplication modular modulo
person elect    schedule 06.11.2012    source источник
comment
Возможно, вы могли бы попробовать использовать функцию clock() и усреднить полученные значения.   -  person Reguj    schedule 06.11.2012
comment
@Reguj К сожалению, мне нужно записать теоретическую модель.   -  person elect    schedule 06.11.2012

Ответы (1)


arrow_upward
1
arrow_downward

[Поскольку вы также задавали тот же вопрос на форумах NVIDIA, http://devtalk.nvidia.com, я просто скопировал ответ, который я дал там, в StackOverflow. Как правило, перекрестные ссылки полезны, когда вопросы задаются на нескольких платформах.]

Задержка практически бессмысленна с такой пропускной архитектурой, как GPU. Самый простой способ определить показатели пропускной способности для любой интересующей вас операции — измерить ее на устройстве, на которое вы планируете ориентироваться. Насколько я знаю, именно так создаются таблицы для документа ЦП, на который вы ссылались.

Чтобы изучить машинный код, вы можете дизассемблировать машинный код (SASS) для операции по модулю, используя cuobjdump --dump-sass. Когда я делаю это для sm_20, я насчитываю в общей сложности шестнадцать инструкций для 32/32->32-битного модуля без знака. Судя по набору инструкций, я бы оценил пропускную способность примерно в 20 миллиардов операций в секунду на Tesla C2050 для всего графического процессора (обратите внимание, что это приблизительная оценка, а не измеренное число!).

Что касается 64/64->64-битного модуля без знака, который называется подпрограммой, я недавно измерил пропускную способность 6,4 миллиарда операций в секунду на C2050 с использованием CUDA 5.0.

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

person njuffa    schedule 06.11.2012
comment
Привет, нюффа, приятно снова тебя видеть :), спасибо за ответ (+1). Я написал это, потому что мне нужно записать математическую модель, которая оценивает скорость GPU для конкретного алгоритма (RNS Montgomery Exponentiation). Пока я хотел бы использовать закон Амдала (сильное масштабирование), который вычисляет максимальное теоретическое ускорение. Проблема заключается в сравнении нагрузки процессора с нагрузкой графического процессора. Предположим, что у вас есть модульное умножение k, если, например, k = 34, на процессоре у меня будет 34 * (умножение 32b + 64b по модулю). На GPU 2.0 как я мог оценить? Думал сделать так: первый варп полностью - person elect; 07.11.2012
comment
выполняется, поэтому, если наша пропускная способность составляет 16 целочисленных умножений по 32b за такт на SM, то нам нужно потратить 2 цикла на выполнение первых 32 умножений + еще один цикл на оставшиеся 2 mul (мы пока не учитываем модуль). Это верно? Или есть лучший способ оценить это? При этом если пропускная способность 16 инт.мульт. /clock/MP, правильно ли говорить, что для i-го варпа необходимо выполнить не менее 16+1 mul. задержит МП на 2 такта, даже если есть другие варпы, готовые к подаче? - person elect; 07.11.2012
comment
Боюсь, я не знаю, что означает k-модульное умножение. Масштабирование, которое вы увидите, будет зависеть от того, сколько параллелизма вы можете выставить. Для относительно коротких операндов (скажем, до 512 бит) вы можете выполнить возведение в степень для каждого потока, но тогда потребуется порядка 10 000 потоков, чтобы хорошо заполнить GPU (например, 512 потоков на SM, каждый из которых использует 64 регистра). Поскольку каждый поток в этой схеме обрабатывает одно возведение в степень, требуется столько независимых возведений в степень, сколько существует потоков. - person njuffa; 07.11.2012
comment
Извините, я постараюсь внести ясность. Что касается шага алгоритма, k указывает количество модульных умножений 32b, которые мне нужно выполнить параллельно. Каждое модульное умножение подразумевает простое целочисленное умножение 32b. Поскольку я запускаю поток на модульное умножение, у меня есть поток на 32b int. мул. Теперь он выглядит лучше? - person elect; 07.11.2012
comment
C2050 может выполнять 515,2e9 простых целочисленных операций в секунду, и половина этой пропускной способности доступна для инструкций целочисленного умножения (IMUL или IMAD), то есть 257,6e9 целочисленных инструкций умножения в секунду. Например, для умножения 256x256->256 бит требуется 2 32-битных инструкции IMUL и 62 32-битных IMAD, всего 64 инструкции типа целочисленного умножения. Таким образом, C2050 сможет выполнять около четырех миллиардов операций умножения 256x256->256 бит в секунду. В быстром эксперименте я измерил 3,94e9 таких умножений в секунду (без вычитания крошечных накладных расходов моей тестовой среды). - person njuffa; 07.11.2012
comment
Хорошо, я думаю, что понял вашу точку зрения. Спасибо за информацию, нюффа :) У вас также есть какие-то измерения на коммерческих картах Ферми и Кеплера? - person elect; 11.11.2012
comment
Если под коммерческими картами вы подразумеваете потребительскую карту, то нет. Я просто измерял на C2050 на своей рабочей станции, которую использую на работе. Довольно просто настроить simep, тест пропускной способности для измерения интересующих вас данных, но у меня нет времени на измерение дополнительных операций. - person njuffa; 12.11.2012
comment
njuffa, я сделал некоторую оценку, основанную на ваших результатах относительно 64/64-64-битного беззнакового модуля. Как это возможно? Я имею в виду: 6,4 миллиарда/14 см = 450 млн/см. Тактовая частота составляет 1150 МГц, поэтому если мы делаем 1150/450 = 2,5. Это означает, что средняя пропускная способность по модулю составляет 2,5 такта... Я ожидаю, что это будет результат для умножения, а не по модулю... Хорошо, переключение контекста работает параллельно со многими деформациями, скрывая задержку и т. д., но честно говоря, поскольку по модулю очень дорого (почти 20 инструкций), я не понимаю, как это возможно. - person elect; 18.11.2012
comment
У меня нет дизассемблирования передо мной, но, насколько я помню, 64/64->64 без знака по модулю составляет около 65 инструкций или около того, почти все они являются целочисленными инструкциями: некоторые простые, некоторые типа целочисленного умножения. Как я уже отмечал, C2050 может выполнять 515,2e9 простых целочисленных операций в секунду или 257,6e9 операций целочисленного умножения в секунду. 6,4e9 по модулю/сек * 65 импульсов/по модулю = 416e9 импульсов/сек, поэтому указанная пропускная способность правдоподобна. Я могу перепроверить пропускную способность по модулю и количество инструкций в следующий раз, когда у меня будет доступ к C2050. Ваша оценка, кажется, полностью исключает параллелизм внутри каждой SM. - person njuffa; 18.11.2012
comment
Я перепроверил 64-битный модуль без знака с помощью CUDA 5.0 на C2050. Разборка подпрограммы для sm_20 показывает 67 инструкций, из которых 36 имеют тип целочисленного умножения (IMUL или IMAD). Измеренная пропускная способность составляет 6,384e9 операций по модулю в секунду. - person njuffa; 21.11.2012
comment
Спасибо njuffa за интересную информацию, последний вопрос: сколько блоков и потоков вы запускаете? - person elect; 21.11.2012
comment
Если я правильно помню, я использовал 65520 блоков по 256 потоков в каждом. - person njuffa; 21.11.2012
comment
В эти дни я запускаю небольшую программу для проверки пропускной способности. Сейчас я использую 580. Чтобы получить максимальную загрузку от каждого SM (максимальное количество потоков/SM = 1536 и максимальное количество потоков/блок = 1024), я решил создать блоки по 512 потоков каждый. Таким образом, я надеюсь, что каждый SM запускает 3 блока, достигая максимальной производительности (1536 потоков/SM). Итак, я запускаю 16 SM * 3 блока/SM = всего 48 блоков. Но глядя на ваш последний комментарий, у вас совсем другое: огромное количество блоков с меньшим количеством потоков в каждом... почему? - person elect; 01.03.2013
comment
На C2050 для оптимального заполнения SM, помимо используемой вами конфигурации, можно использовать 4 блока по 384 потока, 6 блоков по 256 потоков или 8 блоков по 192 потока. В качестве эвристики, если есть ограничение ресурсов, которое не позволяет запускать максимальное количество потоков на SM, блоки потоков с меньшей степенью детализации облегчают достижение высокой занятости. Поскольку 192 потока — это размер блока, который не всегда соответствует естественному отображению потока в память приложения, я часто использую 256 потоков на блок в качестве отправной точки. Использование большого количества блоков потоков полезно для максимизации производительности памяти. - person njuffa; 01.03.2013
comment
Ах, интересно, в этом есть смысл... но ограничение ресурсов также может иметь место при использовании выделенного графического процессора? (т.е. второй графический процессор без подключенного монитора) - person elect; 02.03.2013
comment
Когда каждый поток использует много регистров или каждый блок потока использует много разделяемой памяти, невозможно запустить максимально возможное количество потоков на SM. В этих случаях занятость ограничивается одним или несколькими ресурсами на SM. - person njuffa; 03.03.2013