Б.А. Князев
6
Рис. 3.
Вычисление агрегирующей функции и последующее масштабирование
Модель визуализации данных
S
M
по сравнению с (5) будет от-
личаться только нижней строкой:
0
0
,
,
,
,
,
[
1
:
,
1: , , ,
:
:
],
,
,
j
i
j
i
i
i
i
s S s s
i j
s S s i
L s s i L s
i j
W P R F s S
R
i m i k i m
i
i
i
s
s r s
s
max min
(8)
где
1, 2;
2.
k
n
Тогда, в соответствии с (6)
2
N W
(9)
при разрешении дисплея
1920 1080
W H
2 ·1920 3840
N
точек.
Таким образом, при заданном
B
( например,
24)
B
имеем по-
стоянный объем визуализируемых данных в соответствии с форму-
лой (2):
/ 8 11, 25Кб,
V NB
не зависящий от масштаба
X
s
и коли-
чества отсчетов исходных данных
N
.
Реализация алгоритма Reduction Tree на GPU для поиска экс-
тремумов
.
При исходном
8
2 ·10
N
и количестве блоков
,
i
S
рав-
ном ширине окна в пикселах
W,
размер блоков, для которых приме-
няется правило
R
, может достигать значения 10
6
. При реализации
последовательного алгоритма применения данного правила для всех
блоков сложность операции
0
1,
0
(
|
)
( )
Х
i s
O W S
O N
x
, что будет
эффективно только для небольшого (~10
2
) количества элементов
(рис. 4). Для реализации алгоритма параллельной агрегации данных
предлагается использовать алгоритм дерева редукций (
reduction tree
)
[10], оптимизированного в данной работе под выполнение задачи по-
иска минимума и максимума массива данных.
