Б.А. Князев
8
Базовый алгоритм дерева редукций не эффективен по следующим
причинам. Максимальное количество обрабатываемых элементов
ограничено размерами сетки блоков (
grid
) (2
16
для процессоров
G80
и
GF104
) и потоков на один блок (2
9
и 2
10
для процессоров
G80
и
GF104
соответственно). Таким образом, максимальный размер вход-
ных данных 2
25
… 2
26
<3,3 … 6,7·10
7
, в то время как для рассматрива-
емой задачи необходимо 2·10
8
элементов. Каждый поток обрабатыва-
ет максимум 2
9
… 2
10
элементов и соответственно не полностью
использует ресурсы регистров и разделяемой памяти (
shared
memory)
, а также и всего процессора [11]. Следовательно, при этой
реализации сложность алгоритма будет стремиться к наихудшей
log
O N N
и проигрывать даже последовательной реализации
(см. рис. 4).
Названные ограничения можно обойти следующими способами.
С помощью технологии отображения памяти (
memory mapping
), т. е.
вызовом функций
cudaHostRegister
и
cudaHostGetDevicePointer
из
библиотеки параллельных вычислений
CUDA
для графических про-
цессоров
NVIDIA
, можно инициализировать значительно больше па-
мяти, поскольку ее объем ограничен лишь объемом глобальной па-
мяти процессора (640 Мб и 768 — 2048 Мб для процессоров
G80
и
GF104
соответственно). Кроме того, в соответствии с [10] необходи-
мо больше нагружать каждый поток, что позволит повысить про-
пускную способность процессора в целом. В [11] также показано, что
меньшее количество потоков в одном блоке ведет к увеличению про-
изводительности. Следовательно, для решения задачи необходимо
вычислять 1024 … 4096 элементов в потоке и от 64 до
W
блоков
по 128 … 256 потоков (рис. 5).
Рис. 5.
Алгоритм параллельной агрегации данных
6
10 отсчетов
i
х
Δ
∼
