close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Особенности адаптации
вычислительных алгоритмов под
параллельную архитектуру
графических акселераторов
С.В. Ковальчук, С.М. Вишняков, А.С. Мордвинцев,
Р.В. Наумов
НИИ НКТ СПбГУ ИТМО
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Преимущества GPU-устройств
Большая производительность
1000
950
GPU по сравнению с CPU
900
GeForce
9800 GX2,
Tesla D870
850
Доступность по цене
800
750
GeForce 8800 GTX - €300
700
650
Развитие направления GPGPU
600
GFlops
Tesla C870 - €800
550
GPU
500
GeForce
8800 GTX
450
CPU
400
350
300
GeForce
7800 GTX
250
200
150
Intel Core 2
3MHz
100
50
0
Dec/02
GeForce
6800 Ultra
May/04
Sep/05
Feb/07
Jun/08
2
Научно-исследовательский институт наукоемких компьютерных технологий
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
CUDA
BrookGPU (Stanford University, 2004)
Sh Lib (Waterloo University, 2004-2006)
ATI Close-To-Metal/FireStream SDK (2007)
NVidia CUDA (2007)
Преимущества CUDA:
абстрагирование от терминологии компьютерной графики;
SDK разрабатывается производителем «железа»;
поддержка высокопроизводительных HPC-акселераторов
(Tesla).
NVidia GeForce 8800 GTX:
16 мультипроцессоров по 8 ядер
768 Mb памяти
3
Научно-исследовательский институт наукоемких компьютерных технологий
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Конфигурация GPU-устройства
CPU
GPU-устройство
Конфигурация ядра
Ядро 1
Программное ядро
Элементы конфигурации
Блок
Блок
(1, 0)
Блок
(2, 0)
Блок
(0, 1)
Блок
(1, 1)
Блок
(2, 1)
Конфигурация ядра
Ядро 2
Поток
Warp
Блок
(0, 0)
Блок (1, 1)
Поток
(0, 0)
Поток
(1, 0)
Поток
(2, 0)
Поток
(3, 0)
Поток
(0, 1)
Поток
(1, 1)
Поток
(2, 1)
Поток
(3, 1)
Поток
(0, 2)
Поток
(1, 2)
Поток
(2, 2)
Поток
(3, 2)
4
Научно-исследовательский институт наукоемких компьютерных технологий
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Отображение вычислительной задачи на GPU
Выделение вычислительного ядра
Определение конфигурации
Загрузка ядра и данных в GPU
GPU
CPU
Память
Xi
АЛУ
f(X)
X1
f'(X)
X2
f'(X)
X3
f'(X)
Память
...
XN
f'(X)
5
Научно-исследовательский институт наукоемких компьютерных технологий
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Пример: климатические спектры волнения
Аппроксимация нелинейной функции нескольких аргументов –
оптимизация методом линейного случайного поиска (алгоритм класса «б»)
Массив расчетных спектров волнения
Представление спектра
S (, ) p S p (, | p )
p
Аппроксимация
S ( , ) S ( )G ( , )
S () g 2
k
exp B G ( , ) C m ( ) cos
2m ()
n
()
( / 2)
Estimation
Сглаживание.
of prevailed peak
(1 , 1 )
Определение
position
положения
on the
главного
data sheet
пика
directly
Определение числа и
положения пиков методом
адаптивного случайного поиска
с линейной тактикой
k 1 k k ek k 1 k 1
for J N ( k 1 ) J N ( k ),
ek ek 1
k 1 k
k 1 k 2 for J ( k 1 ) J ( k )
e k 1 rand ( e i ) i 1 , m
Научно-исследовательский институт наукоемких компьютерных технологий
Оценка значимости
выявленных пиков
Набор
параметров
спектров
6
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Перенос алгоритма на архитектуру GPU
Распараллеливание по
данным
Выбор множества начальных точек {Xi} для N спектров
Вычислительное ядро
реализует подсчет
целевой функции в
заданной точке
GPU
Подсчет J(X1)
...
Подсчет J(XN)
Выбрать случайные {Xi}
[Иначе]
[Критерий останова выполнен для всех N спектров]
7
Научно-исследовательский институт наукоемких компьютерных технологий
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Измерение производительности
Получаемая производительность зависит не только от
реализации алгоритма, но и от загрузки GPU
8
Научно-исследовательский институт наукоемких компьютерных технологий
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Элементы времени работы
T T malloc T memcpyin T ker nel T memcpyout T free
Получаемый характер зависимости производительности
определяется временем работы ядра
9
Научно-исследовательский институт наукоемких компьютерных технологий
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Исследование производительности
производительность, операций за единицу времени
3000
2500
2000
32tpb
1500
64tpb
96tpb
1000
256tpb
500
0
16
32
48
64
80
96
112
128
144
160
176
192
208
224
240
256
272
288
304
320
число блоков
10
Научно-исследовательский институт наукоемких компьютерных технологий
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Исследование производительности
900
800
время работы, мс
700
600
500
32tpb
64tpb
96tpb
128tpb
160tpb
192tbp
224tpb
256tpb
400
300
200
100
0
16
32
48
64
80
96
112
128
144
160
176
192
208
224
240
256
272
288
304
320
число блоков
Научно-исследовательский институт наукоемких компьютерных технологий
11
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
«Конвейерный» эффект
Отрезки графика, на которых время работы постоянно
обусловлены:
«конвейерным» эффектом, компенсирующим задержки при
чтении данных из памяти устройства;
«конвейерным» эффектом, компенсирующим ожидание при
чтении из регистра.
B1
B1
b2 Object1
1 блок на мультипроцессор
B1
B2
Object
Object2
Object
b Object5
2 блока на мультипроцессор
B1
B2
B3
B2
B4
4 блока на мультипроцессор
Время
Ожидание данных из памяти
Последовательность арифметических операций
12
Научно-исследовательский институт наукоемких компьютерных технологий
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Модель производительности
Скачки на графике обусловлены «переполнением»
ресурсов GPU:
nblocks * ( blockSize / warpSize )
mWarps * occupancy
M
•
•
•
•
•
•
nblocks – общее число блоков в конфигурации
blockSize – размер блока согласно конфигурации
warpSize – размер warp’a, зависит от архитектуры
M – число мультипроцессоров GPU
mWarps – максимальное число warp’ов, которое может быть
одновременно запущено на мультипроцессоре
occupancy – определяет максимальное число одновременно
работающих warp’ов, обусловленное распределением ресурсов
GPU между потоками
13
Научно-исследовательский институт наукоемких компьютерных технологий
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Модель производительности
T
ker nal
t 0 ( blockSize ) occupancy
N
nblocks blockSize
nblocks blockSize
M
mWarps
occupancy
warpSize
warpsPerMP
(
blockSize
)
workPerThr
ead
t0
mWarps occupancy warpsPerBl ock min(lim itByWarps , lim itByShared Memory , lim itby Re gisters )
mWarps
lim itByWarps
min(lim itByBlocks , mWarps / warpsPerBl ock )
lim itByShared Memory max TotalShare dMemory
/ sharedMemo
ryPerBlock
lim itByShared Memory max Total Re gisters / registersP erBlock
Рассчитать значение occupancy для ядра можно при
помощи CUDA Occupancy Calculator.
14
Научно-исследовательский институт наукоемких компьютерных технологий
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Проверка модели производительности
180
160
время рботы, мс
140
theor32
120
exp32
theor64
100
exp64
theor96
80
exp96
theor128
exp128
60
theor160
exp160
40
20
0
16
32
48
64
80
96
112
128
144
160
176
192
208
224
240
256
272
288
304
320
число блоков
Научно-исследовательский институт наукоемких компьютерных технологий
15
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Определение времени t0
0.002
t 0 t a occupancy
t0, мс
0.0016
0.0012
0.0008
tb
t 0 T a mWarps T b
0.0004
0
32
64
96
128
160
192
224
256
потоков в блоке
t0
0.0035
ta*occupancy+tb
0.003
0.0025
0.3
t0
occupancy
0.4
0.002
0.2
0.0015
0.1
0.001
0
0.0005
32
64
96
128
160
192
224
256
потоков в блоке
0
0
2
4
6
t0
Научно-исследовательский институт наукоемких компьютерных технологий
8
10
12
mWarps
Ta*mWarps+Tb
2008
16
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Итоги
Адаптация алгоритма параметрической оптимизации к
архитектуре GPU позволяет получить ускорение более
30 раз по сравнению с реализацией без использования
GPU
Построена модель производительности, позволяющая
предсказывать время выполнения ядра
Открытые вопросы:
расхождение модели с результатами измерений при четном
числе warp’ов в блоке.
17
Научно-исследовательский институт наукоемких компьютерных технологий
2008
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Актуальные направления исследований
Уточнение и приведение к универсальному виду модели
производительности
Анализ особенностей адаптации различных классов
алгоритмов
Исследование методов балансировки при адаптации
вычислительных алгоритмов под параллельную
архитектуру графических акселераторов
Построение сложных вычислительных архитектур с
использованием графических акселераторов
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Параллельный алгоритм трассировки лучей
для гетерогенных Грид-архитектур,
использующих вычислительные акселераторы
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Постановка задачи
Перенос вычислительного алгоритма на архитектуру GPU
Построение вычислительной системы на основе Гридархитектуры, использующей вычислительные ресурсы
GPU
Адаптация алгоритма для Грид-архитектуры
Анализ эффективности функционирования
вычислительной системы
Цель: Определение основных аспектов переноса
вычислительных алгоритмов под параллельную Гридархитектуру, использующую графические акселераторы
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Обратная трассировка лучей
Учитывает физические
свойства сцены
Позволяет
неограниченно
увеличивать качество
получаемой картинки
Требует больших
вычислительных затрат
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Реализация
Для программирования GPU используется
высокоуровневое API – CUDA
На GPU производится только расчет пересечения луча с
объектами
vs
Алгоритм трассировки лучей полностью переносится на GPU
Использование Грид-архитектуры для организации
распределенных вычислений
Среда: PEG 2 (Parallel Execution GPE)
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Работа распределенного алгоритма
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Балансировка нагрузки при вычислениях
на GPU с использованием CUDA
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Проблема
GPU изначально предназначены для однородных
вычислений над большими объемами данных
(трансформация вершин, растеризация примитивов)
Для этого идеально подходят SIMD процессоры
А как эффективно решать неоднородные задачи?
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Отсутствие балансировки
f(x)
x0
x1
x2
x3
x4
x5
x6
x7
Работа
Ожидание или
бесполезные
вычисления
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Примеры неоднородных задач
Оптимизация функций случайным поиском
может сойтись быстро, а может медленно
Трассировка лучей
можем попасть в небо, а можем в сложную геометрию
...и так далее...
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Проблемы балансировки
Требуется когерентность между потоками,
работающими в одном warp'е SIMD-процессора
Нет асинхронного обмена сообщениями между
потоками
Сложность синхронизации между потоками,
работающими на разных процессорах
Атомарные функции появились только начиная с CUDA 1.1, и
недоступны на Geforce 8800 GTX и Ultra
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Подход к балансировке
Разбить вычисление на множество идентичных
шагов, требующих одинакового времени
Обращаться с каждым таким шагом, как с
отдельной задачей
Периодически останавливать вычисление на
границе шага и выдавать новые задания
свободным потокам
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Простейшая стратегия балансировки для GPU
x0
x8
x1
x 19
x 13
x2
x9
x3
x 10
x4
x 14
x 20
x 15
x 21
x5
x 11
x 16
x6
x 12
x 17
x7
x 18
Балансировка
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
Текущие задачи
Реализация алгоритма «глобальной»
балансировки (на CPU)
Реализация алгоритма «локальной»
балансировки (на GPU)
Построение теоретической модели времени
работы, учитывающей балансировку
Документ
Категория
Презентации по информатике
Просмотров
10
Размер файла
2 192 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа