Исследование и построение решения задачи

4.3.4 Алгоритм анализа доступов в глобальную память

Глобальная память обладает высокой латентностью, поэтому для достижения эффективной работы приложений доступ к ней необходимо оптимизировать.

Существует возможность объединения запросов всех нитей варпа в одно обращение к непрерывному блоку глобальной памяти (coalescing – выровненный доступ), что может на порядок ускорить работу приложения. Существуют определённые условия (для каждой версии compute capability ускорителя), при которых происходит объединение запросов в одну транзакцию. Эти условия проверяются для каждого варпа отдельно, но на практике обычно они выполняются либо для всех варпов сразу, либо не выполняются ни для одного.

Для того, чтобы GPU с compute capability 1.0 или 1.1 произвёл объединение запросов нитей полуварпа в одну транзакцию, необходимо выполнение следующих условий:

• 
  нити должны обращаться к 32-битным словам (или 64-битным словам), в результате получая 64-байтовый блок (или 128-байтовый соответственно);
  
• 
  полученный блок должен быть выровнен по размеру (адрес 64-байтного блока кратен 64, адрес 128-байтного – 128);
  
• 
  все 16 слов, к которым обращаются нити, находятся внутри блока;
  
• 
  нити обращаются к словам последовательно, т.е. нить с номером n обращается к n-ому слову. При этом допускается, что некоторые нити пропустят обращение к соответствующим словам.
  

Условия для compute capability 1.2 и 1.3 были ослаблены. При этом порядок обращения нитей словам (при условии попадания запросов в соответствующий сегмент) роли не играет. Также существенно, что доступ в случае отсутствия выровненности для всех нитей в варпе разбивается на наименьшее возможное число транзакций (в предыдущих версиях compute capability в случае невыровненности транзакция генерировалась для каждой нити).

Тогда размер сегментов (он же размер каждой из транзакций), к которым обращаются нити:

• 
  segment_size = 32, var_size = 1
  
• 
  segment_size = 64, var_size = 2
  
• 
  segment_size = 128, var_size >= 4 (2)
  

Размер смещения между обращениями соседних нитей:

Число транзакций для данной архитектуры – число обращений в различные сегменты размера segment_size. Отсюда, чем меньше смещение, тем больше адресов попадает в один сегмент. Количество транзакций:

4.3.5 Алгоритм подсчёта ресурсов, необходимых блоку.

Число ресурсов, необходимых активному блоку определяет количество блоков, которые могут обслуживаться одновременно на ускорителе. К сожалению, алгоритмы выделения регистров на потоковом процессоре ускорителя не являются общедоступными, поэтому были сделаны некоторые эвристические предположения.

Алгоритм подсчёта числа регистров, требуемых каждой нити

• 
  для локальной переменной, не являющаяся массивом, отводится 1, 2 или 4 регистра в зависимости от своего типа (INT, REAL, DOUBLE);
  
• 
  отводится регистр для хранения счётчиков итераций нити, в случае выполнения нитями блока нескольких витков;
  
• 
  отводится регистр для хранения индекса нити по каждому измерению решётки нитей;
  
• 
  регистр для хранения указателя инструкции;
  
• 
  вычисляется количество регистров, требуемых для хранения промежуточных результатов итераций;
  
• 
  регистр для хранения промежуточных результатов на каждые 10 строк цикла.
  

Общее число регистров, требуемых каждому блоку может быть подсчитано по формуле:

required_regs = ceil (regs_per_thread * threads_per_warp, 128) * threads_in_block / 32 (6)
при этом regs_per_thread подсчитано выше, threads_per_warp – введено выше, _in_block – общее число нитей в блоке, ceil(x,y) – округляет x до ближайшего целого, кратного y.
Другим важным ресурсом является разделяемая память. В системе DVM разделяемая память используется для проведения коллективных операций, для прочих не используется. Тем не менее, компилятор может выделить некоторое количество разделяемой памяти для нужд системы. В модели данное число оценивается, как required_shared_mem = block_dimensions * 32

4.3.6 Алгоритм анализа выполнения коллективных операций

В DVM-системе редукция осуществляется отдельным ядром, выполняющегося отдельным блоком размерности [threads_x 1 1], где threads_x – количество нитей по x-измерению блока; по y- и z- измерениям число нитей равно 1.

threads_x = _ )/ 2, (7)
где iterations_{i –} количество итераций ядровой функции по соответствующему измерению, а theads_i – количество нитей по измерению блоков, которые использовались для начальной обработки ядровой функции (i = 1..3). На каждом шаге активный варп формирует одно значение (из 32-х нитей). Если число варпов в блоке превышает 32 (размерность варпа), производится повторная редукция, иначе значения отсылаются хосту, где происходит финальный этап редукции.
Выделение разделяемой памяти для использования блока определяется формулой:
required_shared_mem += num_threads_in_block * reduction_var_size, (8)
где num_threads_per_block есть общее число нитей в блоке, а reduction_var_size – размер переменной в байтах, по которой производится коллективная редукция.

Задержки на синхронизацию при этом определяются так:

num_sync += log₂ (num_threads_in_block * num_iterations_per_thread) (9)
Аналогично определяется число арифметических операций, во время обработки данных:
num_arithm += log₂ (num_threads_in_block * num_iter_per_thread) (10)

4.3.7 Алгоритм использования кэш-памяти в модели

По умолчанию в модели предполагается использование 48 килобайтного кэша уровня L1 архитектуры Fermi (максимальное значение для L1), минимальный объём кэша составляет 16 килобайт. У пользователя имеется возможность запустить моделирование с учётом влияния кэш-памяти или указать предиктору не использовать кэш. Также имеется возможность задать размер кэша (значение в килобайтах, не меньше минимального и не больше максимального).

Допущения, принятые при моделировании:

• 
  для каждой переменной, адресующей массив, в кэш записывается сегмент памяти, начиная с адреса этой переменной. Длина сегмента зависит от базового типа переменной – соответствие определяется формулой (2);
  
• 
  переменная остаётся в кэше максимально долго, пока не будет замещена;
  
• 
  в первую очередь замещению подлежат наименее использовавшиеся переменные;
  
• 
  при добавлении в кэш нового значения производится вычисление свободного места. Если свободного места недостаточно, то происходит замещение одной или нескольких переменных (в зависимости от размера добавляемого сегмента), по принципу, описанному выше.
  

Предлагаемый алгоритм является эмпирическим. Как показывает данное исследование, прогноз с учётом таких предположений предполагает максимальное использование кэша и прогнозирует время в среднем меньшее, чем при реальном запуске. Прогноз времени работы с отключенным кэшем считает каждое обращение к массиву обращением в глобальную память, из-за чего время получается большее, чем при запуске, т.к. полностью использование кэша при запуске задачи из системы DVM отключить не получается, можно только ограничить использование. Для учёта эффекта, производимого кэшем при запуске на ускорителе, на простых задачах были вычислен поправочные коэффициенты.

4.3.7 Алгоритм построения вычислительной сетки нитей и блоков.

Построение вычислительной сетки нитей и блоков в модели осуществляется точно так, как это реализовано в системе DVM. Это было сделано для того, чтобы обеспечить сопоставимые условия для прогноза и запуска – соответствие размеров вычислительных блоков, их количества, порядка заполнения решётки. Соответствие вычислительных блоков, порядка их построения, - необходимые условия для адекватности анализа выровненности обращений нитей к памяти. Рассмотрим установки DVM, касающиеся отображения пространства витков цикла на блоки графического ускорителя.

Итак:

• 
  сетка блоков всегда является одномерной – т.е. [bloks_num 1 1] (где blocks_num – число блоков, необходимых для запуска функции-ядра на ускорителе);
  
• 
  размерность блока по числу нитей зависит от глубины вложенности параллельного цикла (функции-ядра в модели) отображаемого на ускоритель:
  
  • 
    для одномерного случая устанавливается сетка [448 1 1] (здесь и далее – сначала обозначается количество нитей по измерению X, затем по Y, затем по Z);
    
  • 
    для двумерного случая – [32 14 1];
    
  • 
    для глубины не менее 3 сетка нитей – [32 2 7];
    

Оптимальность данных установок не является предметом настоящего исследования. Чтобы иметь возможность адекватно сравнивать результаты запуска реальных программ с использованием системы DVM и прогноза предиктора, именно они были приняты по умолчанию. В DVM системе у пользователя имеется возможность вручную задать размерность блока по числу нитей для каждого цикла, такая же возможность реализована в предикторе.

В системе DVM пространство витков цикла заполняется по следующему алгоритму:

• 
  CUDA-блок переводится в пространство размерности цикла, при этом:
  
  • 
    размерностью цикла считается количество вложенных подциклов плюс 1 (сам цикл);
    
  • 
    младшим измерением цикла считается наиболее глубоко вложенное, старшим - внешнее измерении цикла, т.е. для гнезда циклов
    

do i = 1,3
do j = 1,6
   ...
enddo
enddo

старшим является измерение i, младшим – j;

• 
  если необходимо, при размерности цикла >= 3-м, по старшим измерениям блок дополняется единицами;
  
• 
  по самому младшему измерению будет взят размер блока по оси X, затем по оси Y, затем по Z;
  
• 
  таким образом получается необходимое для отображения замощение.
  

4.3.8 Алгоритм построения вычислительной решётки

Схема 1. Построение вычислительной решётки
Заполнение пространства витков блоками в предикторе происходит аналогично описанному выше. Мы имеем некоторый цикл, замощение по самому младшему измерению осуществляется с шагом X, следующему по старшинству с шагом Y, следующему – Z, где X, Y, Z – соответствующие размерности блока. По всем остальным измерениям шаг замощения равен единице. При этом могут получаться остатки от деления итераций цикла на соответствующую размерность блока, тогда образуются соответствующие блоки. На схеме остатки обозначены как x, y, z. Иллюстрация приведена для трёхмерного случая.
После чего одномерная решётка блоков формируется последовательным обходом по измерениям, начиная с самого младшего, т.е. того, которому соответствует наиболее быстроменяющийся индекс параллельного цикла.

жүктеу/скачать 1.18 Mb.

Достарыңызбен бөлісу: