принципы адаптации вычислительных алгоритмов




Скачать 413.33 Kb.
Названиепринципы адаптации вычислительных алгоритмов
страница3/10
Дата22.10.2012
Размер413.33 Kb.
ТипДокументы
1   2   3   4   5   6   7   8   9   10

Глава 1. Архитектура графических акселераторов, средства отображения на них вычислительных алгоритмов и исследуемые алгоритмы

    1. Краткое описание архитектуры графических акселераторов


Предметом исследования данной работы являются особенности отображения вычислительных алгоритмов на графические акселераторы («GPU-устройства») nVidia, представляющие собой набор вычислительных узлов – мультипроцессоров, имеющих доступ к данным, хранящимся в памяти самого GPU-устройства (рис. 2). Каждый мультипроцессор состоит из некоторого числа арифметико-логических устройств (АЛУ), набора регистров, кэша для специальных видов памяти и общей памяти, играющей роль управляемого кэша.

Мультипроцессоры работают по принципу Single Instruction, Multiple Thread (SIMT) [15], очень похожему на известный принцип организации параллельных архитектур Single Instruction, Multiple Data (SIMD). Ключевое отличие SIMT-организации архитектуры от SIMD состоит в том, принцип SIMD предполагает распараллеливание по данным на уровне инструкций, выполняющихся на векторном сопроцессоре и вызывающихся из одного потока управления. На мультипроцессоре SIMT-архитектуры, напротив, каждое АЛУ имеет свой собственный поток управления, но при этом наилучшая производительность достигается тогда, когда все АЛУ одного мультипроцессора выполняют одинаковую последовательность инструкций над разными наборами данных, расположенных в памяти GPU-устройства.

В данной работе использовались акселераторы GeForce 9800M GTX, 8800 GTX, которые имеют соответственно двенадцать и шестнадцать мультипроцессоров, по восемь АЛУ в каждом мультипроцессоре.



Рис. 2. Архитектура GPU-устройства.

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


При использовании nVidia CUDA SDK, процедура отображения алгоритма на GPU-устройство выглядит следующим образом (рис. 3): разработчик описывает вычислительное ядро (kernel), то есть процедуру, которая будет исполняться на GPU-устройстве над потоком данных. При запуске ядра на графическом акселераторе разработчик задает его конфигурацию на основе описанной ниже иерархии. Каждый поток, физически выполняющийся на АЛУ мультипроцессора, исполняет инструкции, описанные в ядре. При этом, благодаря SIMT-архитектуре, на каждом мультипроцессоре несколько потоков параллельно выполняют одну и ту же последовательность инструкций. Логически потоки объединяются в блоки, ограничивающие возможность обмена данными между потоками. Потоки могут обмениваться данными через общую память только внутри одного блока. Кроме того, потоки из одного блока выполняются на одном и том же мультипроцессоре.



Рис. 3. Иерархия элементов конфигурации GPU-устройства

Таким образом, перед запуском ядра разработчик задает его конфигурацию (grid): размер блока и общее число блоков. Для более удобного структурирования конкретных задач в CUDA предусмотрена возможность конфигурирования блоков и потоков в двумерные сетки. Данная возможность обеспечивает удобство при обработке данных, имеющих двумерную структуру: изображений, матриц и т.д.

Отметим так же еще один важный структурный элемент конфигурации ядра – основу (warp). Под основой (в терминологии nVidia) подразумевается набор потоков, инструкции которых выполняются на мультипроцессоре одновременно. Размер основы определяется архитектурой конкретного GPU-устройства и размер блока, определяемый при конфигурировании ядра должен быть пропорционален размеру основы.

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



Рис. 4. Общая схема отображения вычислительного алгоритма на GPU-устройство

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

Заметим также, что при описании вычислительного ядра необходимо учитывать ряд важных особенностей работы GPU-устройств. Во-первых, SIMT-архитектура накладывает ограничения на использование ветвящихся конструкций (if,else). Это связано с тем, что потоки, исполняющиеся на одном и том же мультипроцессоре, должны оперировать одной и той же последовательностью инструкций, что может нарушаться при несовпадении условий ветвления у разных потоков. При нарушении этого ограничения может происходить сильное ухудшение производительности. Во-вторых, следует учитывать особенности работы GPU-устройств с памятью: реализация ядра таким образом, чтобы одновременно выполняющиеся потоки читали данные из соседних участков памяти, существенно увеличивает производительность. Кроме того, необходимо учитывать трудоемкость обращения к памяти GPU-устройства: например, чтение из памяти для акселераторов nVidia занимает 400-600 тактов, тогда как операция сложения занимает всего 4 такта. В-третьих, следует учитывать архитектуру конкретного GPU-устройства, на котором выполняется вычислительная задача. Например, неэффективно задавать конфигурацию ядра с числом блоков меньшим числа мультипроцессоров, имеющимся на устройстве. Более подробно эти и остальные особенности GPU-архитектуры описаны в [13].

1   2   3   4   5   6   7   8   9   10

Похожие:

принципы адаптации вычислительных алгоритмов iconпринципы адаптации вычислительных алгоритмов к архитектуре графических акселераторов
Целью работы является изучение ключевых особенностей отображения вычислительных алгоритмов на gpu -архитектуру, выявление ряда факторов,...
принципы адаптации вычислительных алгоритмов iconЗадача параметрической аппроксимации двумерной функции с использованием метода случайного поиска 10
Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
принципы адаптации вычислительных алгоритмов iconОсобенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
В работе обсуждаются вопросы отображения вычислительных алгоритмов на параллельную архитектуру gpu-акселератора. В качестве примера...
принципы адаптации вычислительных алгоритмов iconПрограмма вступительного экзамена в магистратуру по направлению подготовки 231000. 68 «Программная инженерия»
...
принципы адаптации вычислительных алгоритмов icon1. цели и задачи дисциплины, ее место в учебном процессе согласно гос впо в дисциплину «Вычислительные системы, сети и телекоммуникации» должно включаться
Вычислительных машин: общие принципы построения и архитектуры вычислительных машин, информационно-логические основы вычислительных...
принципы адаптации вычислительных алгоритмов iconАлгоритмы
Основы алгоритмизации. Понятие об алгоритме. Применение алгоритмов. Свойства алгоритмов. Типы алгоритмов: линейные, циклические,...
принципы адаптации вычислительных алгоритмов iconСодержание, основные понятия
Понятие алгоритма, свойства алгоритмов. Использование алгоритмов, система команд исполнителя. Способы записей алгоритмов. Формальное...
принципы адаптации вычислительных алгоритмов iconОглавление 4
Архитектура графических акселераторов, средства отображения на них вычислительных алгоритмов и исследуемые алгоритмы 10
принципы адаптации вычислительных алгоритмов iconБилет №4
Понятие алгоритма: свойства алгоритмов, исполнители алгоритмов. Автоматическое исполнение алгоритма. Способы описания алгоритмов....
принципы адаптации вычислительных алгоритмов iconТическая логика и теория алгоритмов
Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница