Дистанционный практикум по программированию

CUDA — это программно-аппаратная архитектура, позволяющая использовать видеокарты корпорации nVidia для высокопараллельных вычислений в алгоритмах, никак не связанных с графикой. В этой задаче мы ограничимся описанием аппаратной архитектуры Fermi поколения видеокарт, появившегося в марте 2010 года. На смену ему в марте 2012 года пришла архитектура Kepler. Правда, в некоторых задачах видеокарты Fermi показывают лучшую производительность, чем видеокарты Kepler. Для таких задач вся надежда на следующее поколение видеокарт — Maxwell.

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

Для обеспечения максимальной производительности CUDA-программы программист должен внимательно следить за тем, чтобы используемые единицей запуска (ядром) ресурсы, например, количество регистров, используемых в каждом потоке, соответствовали аппаратным ограничениям. Если программное ядро будет использовать несколько больше регистров, то на одной аппаратной единице исполнения (мультипроцессоре) сможет поместиться меньше потоков исполнения, чем могло бы, и производительность от этого может страдать. Картина, конечно же, не является чёрно-белой — в отдельных случаях при менее чем 100% загруженности мультипроцессора удаётся достигать лучших результатов. Однако, это скорее исключение, так что каждый CUDA-программист должен внимательно следить за тем, как хорошо требования его программы соответствуют аппаратным возможностям.

Для того чтобы предоставить CUDA-программисту полную информацию о влиянии использования ресурсов на загруженность мультипроцессора, специалисты корпорации nVidia создали Excel-таблицу "CUDA Occupancy Calculator". В неё можно ввести параметры использования ресурсов и получить результат — отношение числа потоков, которые реально смогут быть запущены на мультипроцессоре, к максимальному числу потоков, которые могли бы быть запущены на мультипроцессоре. Точно такие же вычисления загруженности и Вам нужно будет произвести в этой задаче. Упомянутая Excel-таблица также строит графики, позволяющие понять, использование каких ресурсов можно уменьшить для увеличения загруженности мультипроцессора или использование каких ресурсов можно увеличить без ущерба для загруженности мультипроцессора. В этой задаче строить графики не потребуется.

Физической единицей исполнения является мультипроцессор. В архитектуре Fermi он способен исполнять до 1536 потоков одновременно. Заметим, что в одной видеокарте обычно содержится несколько мультипроцессоров — скажем, в GTX 580 их 16, так что общее число потоков исполнения в этой карте может достигать 24 576.

На мультипроцессоре имеется разделяемая память, которой можно использовать до 49 152 байт. Также на мультипроцессоре есть 4-байтовые регистры в количестве 32 768 штук.

Логической единицей исполнения является блок. Для каждого блока программист задаёт количество потоков, которые в рамках этого блока исполняются (для архитектуры Fermi количество потоков в блоке от 1 до 1024). Также программист определяет количество переменных, использующих разделяемую память, и, соответственно, объём разделяемой памяти, используемой одним блоком. Количество регистров, используемых блоком, обычно определяется компилятором CUDA, но в критических случаях программист может регулировать это значение с помощью ключей компиляции.

Одновременно на мультипроцессоре может исполняться целое количество блоков, для архитектуры Fermi — от 1 до 8. То есть если сделать очень маленький блок, то более 8 блоков всё равно запущено не будет, и большая часть ресурсов мультипроцессора не будет использована.

Гранулярность выделения физических потоков исполнения — 32 штуки, то есть если в блоке 225 потоков, то реально будет занято 256 физических потоков.  Гранулярность выделения разделяемой памяти — 128 байт, то есть если блоку нужно использовать 513 байт разделяемой памяти, то реально на блок будет выделено 640 байт. Гранулярность выделения регистров на поток — 2 штуки, то есть если блоку нужно использовать 21 регистр, то реально будут использоваться 22, причём в том числе и для тех потоков, которые были добавлены в силу гранулярности выделения физических потоков исполнения.

Приведём пример расчёта загруженности мультипроцессора для блока со следующими характеристиками: потоков на блок 400, регистров на поток 30, разделяемой памяти на блок 10 000 байт. Для начала найдём количество реально используемых для блока потоков. Это минимальное число, не меньшее исходного числа потоков на блок, и делящееся на 32. Это 416 потоков. Один мультипроцессор может исполнять одновременно до 1536 потоков, то есть если учитывать только число потоков, то можно сказать, что мультипроцессор может запустить до трёх таких блоков.

Количество регистров, используемых одним потоком,  30, уже делится на 2  —единицу гранулярности выделения регистров на поток, поэтому это значение не корректируем. В блоке всего используется 416 × 30 = 12 480 регистров. Всего в мультипроцессоре 32 768 регистров, то есть с учётом ограничения на регистры мультипроцессор может запустить до двух блоков.

Разделяемой памяти на блок 10 000 байт, с учётом гранулярности выделения разделяемой памяти одним блоком будет использоваться 10 112 байт. Всего в мультипроцессоре её 49 152 байта, то есть с учётом количества разделяемой памяти мультипроцессор может запустить до 4 блоков.

Итого максимальным числом блоков, подходящим под ограничения по потокам, регистрам и разделяемой памяти, является 2. Отсюда легко найти загруженность мультипроцессора. Умножаем число блоков 2 на число полезных потоков в блоке 400 и делим на число максимально возможных потоков исполнения 1536. Получаем 0.5208(3). В этой задаче нужно будет округлить результат до целого числа процентов— то есть ответ будет равен 52%.

Замечание. Реальный CUDA Occupancy Calculator в приведённом примере получил бы 54%, поскольку он полагает 32 потока исполнения (варп) настолько неделимой единицей, что число "полезных" потоков в блоке считает равным не 400, а 416 — минимальному числу, большему заданного и делящемуся на 32. Для всех практических целей такое допущение вполне подходит, поскольку в хорошо оптимизированных программах число потоков в блоке, как правило, кратно 32.

Входные данные: три числа через пробел: количество потоков на блок (от 1 до 1024), количество регистров на поток (от 1 до 63) и количество разделяемой памяти на блок в байтах (от 0 до 49152).

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

Примеры

Входные данные	Выходные данные
400 30 10000	52