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




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

Модель производительности


На рис. 17 представлена экспериментальная зависимость времени работы ядра от числа блоков в конфигурации для разных размеров блоков. Ступенчатый характер этой зависимости объясняется описанным выше эффектом: при увеличении общего числа блоков время работы ядра не изменяется до определенного момента благодаря тому, что вычисления добавляемых блоков выполняются во время «простоя» мультипроцессоров.



Рис. 17. Экспериментальная зависимость времени работы ядра от числа блоков в конфигурации (для разных размеров блоков)

Попытаемся получить зависимость, представленную на рис. 17, в виде формулы, учитывая тот факт, что первое «насыщение» мультипроцессоров должно происходить в тот момент, когда общее число блоков, приходящееся на мультипроцессор, требует количество ресурсов большее имеющегося на мультипроцессоре. Иначе говоря, в этот момент все блоки не могут работать на мультипроцессоре одновременно. Таким образом, становится верным неравенство

, (13)

где nblocks – общее число блоков в конфигурации ядра; blockSize – число потоков в блоке, warpSize – число потоков в основе (определяется архитектурой GPU-устройства); M – число мультипроцессоров данного GPU-устройства; mWarpsмаксимальное число основ, которое может одновременно работать на одном мультипроцессоре GPU-устройства данной архитектуры; occupancy – отношение максимального числа основ, которое можно запустить на одном мультипроцессоре, исходя из использования данным ядром ресурсов и количеством доступных ресурсов на мультипроцессоре, к mWarps. Зная количество регистров и разделяемой памяти, используемых ядром, параметр occupancy можно подсчитать при помощи nVidia Occupancy Calculator [15].

Исходя из приведенных выше соображений, можно предложить следующую формулу для времени работы ядра:

, (14)

где t0 – «эффективное» время работы одного блока, которое вычисляется как время работы ядра при полной загрузке мультипроцессора перед насыщением (фактически – высота первой ступени графика), отнесенное к числу элементарных операций, выполняемых одним потоком; N – общее число элементарных операций, выполняемых ядром; workPerThread – число элементарных операций, приходящихся на один поток; warpsPerMP – количество основ, приходящихся на один мультипроцессор при данной конфигурации ядра.

Вычислив значения t0(blockSize) на основе экспериментальных данных, представленных на рис. 17, можно, используя формулу (14), построить теоретические графики зависимости времени работы ядра от его конфигурации для аналогичной задачи с другим числом элементарных операций, выполняемых ядром (для данной задачи варьировался размер области, в которой считался интеграл, при неизменном шаге интегрирования). Сравнение теоретической зависимости с зависимостью, полученной на практике, представлено на рис. 18. Как видно, теоретическая зависимость довольно хорошо совпадает с экспериментальными данными. Расхождения наблюдаются лишь в началах «ступеней» графика в случаях, когда блок содержит четное число основ. Причина этого расхождения является открытым вопросом.



Рис. 18. Сравнение теоретической и практической зависимостей времени работы ядра от конфигурации

Экспериментальные данные показывают, что параметр t0 в формуле (14) зависит от размера блока. Данная экспериментальная зависимость представлена на рис. 19.



Рис. 19. Экспериментальная зависимость t0(blockSize)

Заметим, что зависимость параметра occupancy от размера блока (рис. 20) носит похожий характер, согласно [13].



Рис. 20. Зависимость occupancy(blockSize)

Этот факт позволяет предположить, что параметры t0 и occupancy связаны линейным соотношением: . Приняв это предположение и вычислив значения ta и tb из экспериментальных данных, можно сравнить теоретическую зависимость t0(blockSize) с полученной экспериментально (рис. 21).



Рис. 21. Зависимость t0(blockSize) (теоретическая и экспериментальная)

Следует заметить, что хотя время t0 максимально при размерах блока соответствующих наибольшим значениям параметра occupancy, именно для этих размеров блока пиковая производительность является наибольшей. Это связано с тем, что при больших значениях этого параметра большее количество потоков может работать на одном мультипроцессоре. В качестве примера можно рассмотреть пиковые производительности ядра исследуемой задачи при размерах блока 32 и 64 (значения occupancy 0.17 и 0.34 соответственно). Согласно формуле (0) времена работы ядра T32 и T32 в момент «насыщения» (четыре основы и восемь основ на блок соответственно) рассчитываются как:

(15)

(16)

При этом из экспериментальных данных известно, что , таким образом производительности P32 и P64 для данных конфигураций ядра будут соотноситься как:

, (17)

то есть при блоке в 64 потока при достижении насыщения ядро выполняется в 1.33 раза дольше, но при этом делает в 2 раза больше работы. Поскольку параметры ta и tb всегда положительны (их отрицательность привела бы к возможности появления отрицательного времени работы), выигрыш за счет увеличения (пропорционально параметру occupancy) выполняемой ядром на пике производительности работы будет всегда больше проигрыша за счет линейного увеличения времени t0:

(18)

Таким образом, можно сделать заключение, что при решении задач, для которых при изменении конфигурации пропорционально изменяется количество входных данных, конфигурацию следует выбирать следующим образом: сначала выбрать размер блока с наибольшим значением occupancy, затем, в соответствии со значением occupancy выбрать количество блоков, при котором достигается насыщение. Тот факт что данный подход хорошо работает лишь для одного типа задач, нельзя с уверенностью назвать его недостатком, поскольку речь в данном случае идет о способе распараллеливания, который согласно монографии Фостера [26] является единственно приемлемым – если при увеличении количества входных данных, не увеличивается количество «заданий», а увеличивается лишь размер «задания», такой подход окажется неэффективным при решении больших задач на более мощных системах.
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
обратиться к администрации
Библиотека
Главная страница