Параллельный алгоритм вычисления циклической свертки
Предложена оптимизация алгоритма вычисления циклической свертки длины N=2ⁿ на основе быстрого преобразования Уолша (БПУ). Оптимизация заключается в использовании свойства предварительной корректировки сигнала длины M сигналом длины M/2 для получения суммарного результата БПУ двух сигналов на основе...
Gespeichert in:
| Veröffentlicht in: | Штучний інтелект |
|---|---|
| Datum: | 2012 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем штучного інтелекту МОН України та НАН України
2012
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/57078 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Параллельный алгоритм вычисления циклической свертки / А.Н. Терещенко, В.К. Задирака // Штучний інтелект. — 2012. — № 3. — С. 79-95. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-57078 |
|---|---|
| record_format |
dspace |
| spelling |
Терещенко, А.Н. Задирака, В.К. 2014-03-03T14:18:19Z 2014-03-03T14:18:19Z 2012 2012 Параллельный алгоритм вычисления циклической свертки / А.Н. Терещенко, В.К. Задирака // Штучний інтелект. — 2012. — № 3. — С. 79-95. — Бібліогр.: 6 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/57078 510.52 Предложена оптимизация алгоритма вычисления циклической свертки длины N=2ⁿ на основе быстрого преобразования Уолша (БПУ). Оптимизация заключается в использовании свойства предварительной корректировки сигнала длины M сигналом длины M/2 для получения суммарного результата БПУ двух сигналов на основе одного БПУ длины M . За счет этого уменьшается число БПУ более чем в два раза, что уменьшает сложность по числу операций сложения и вычитания. Показано, что алгоритм поддается распараллеливанию. Алгоритм проиллюстрирован на реализации сверток длины 4 и 8. Приведены оценки сложности при параллельном и последовательном вычислении. Запропонована оптимізація алгоритму обчислення циклічної згортки довжини N=2ⁿ на основі швидкого перетворення Уолша (ШПУ). Оптимізація полягає у використанні властивості попереднього корегування сигналу довжини M сигналом довжини M/2 для отримання сумарного результату ШПУ двох сигналів на основі одного ШПУ довжини M . За рахунок цього зменшується число ШПУ більш ніж у два рази, що зменшує складність за кількістю операцій додавання та віднімання при послідовному обчисленні. Показано, що алгоритм піддається розпаралелюванню. Алгоритм проілюстровано на реалізації згорток довжини 4 и 8. Наведені оцінки складності при послідовному та паралельному обчисленні. It is given the optimization of computation algorithm for convolution of length N=2ⁿ based on Fast Walsh transform (FWT). The optimization includes the use of the quality of pre-computational adjustment of multi-digit value of length M by multi-digit value of length M/2 to get the sum of FWTs both multi-digit values based on computation of one FWT multi-digit value of length M . The total number of FWTs is reduced more than twofold. That reduces the number of single precision additions and subtractions on sequential computation. It is shown that it is possible to compute algorithm in parallel. There are examples of computation algorithm of convolutions of length 4 и 8. Complexity of sequential and parallel computations is shown. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем Параллельный алгоритм вычисления циклической свертки Паралельний алгоритм обчислення циклічної згортки Parallel Computation Algorithm of Convolution Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Параллельный алгоритм вычисления циклической свертки |
| spellingShingle |
Параллельный алгоритм вычисления циклической свертки Терещенко, А.Н. Задирака, В.К. Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| title_short |
Параллельный алгоритм вычисления циклической свертки |
| title_full |
Параллельный алгоритм вычисления циклической свертки |
| title_fullStr |
Параллельный алгоритм вычисления циклической свертки |
| title_full_unstemmed |
Параллельный алгоритм вычисления циклической свертки |
| title_sort |
параллельный алгоритм вычисления циклической свертки |
| author |
Терещенко, А.Н. Задирака, В.К. |
| author_facet |
Терещенко, А.Н. Задирака, В.К. |
| topic |
Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| topic_facet |
Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| publishDate |
2012 |
| language |
Russian |
| container_title |
Штучний інтелект |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| format |
Article |
| title_alt |
Паралельний алгоритм обчислення циклічної згортки Parallel Computation Algorithm of Convolution |
| description |
Предложена оптимизация алгоритма вычисления циклической свертки длины N=2ⁿ на основе быстрого преобразования Уолша (БПУ). Оптимизация заключается в использовании свойства предварительной корректировки сигнала длины M сигналом длины M/2 для получения суммарного результата БПУ двух сигналов на основе одного БПУ длины M . За счет этого уменьшается число БПУ более чем в два раза, что уменьшает сложность по числу операций сложения и вычитания. Показано, что алгоритм поддается распараллеливанию. Алгоритм проиллюстрирован на реализации сверток длины 4 и 8. Приведены оценки сложности при параллельном и последовательном вычислении.
Запропонована оптимізація алгоритму обчислення циклічної згортки довжини N=2ⁿ на основі швидкого перетворення Уолша (ШПУ). Оптимізація полягає у використанні властивості попереднього корегування сигналу довжини M сигналом довжини M/2 для отримання сумарного результату ШПУ двох сигналів на основі одного ШПУ довжини M . За рахунок цього зменшується число ШПУ більш ніж у два рази, що зменшує складність за кількістю операцій додавання та віднімання при послідовному обчисленні. Показано, що алгоритм піддається розпаралелюванню. Алгоритм проілюстровано на реалізації згорток довжини 4 и 8. Наведені оцінки складності при послідовному та паралельному обчисленні.
It is given the optimization of computation algorithm for convolution of length N=2ⁿ based on Fast Walsh transform (FWT). The optimization includes the use of the quality of pre-computational adjustment of multi-digit value of length M by multi-digit value of length M/2 to get the sum of FWTs both multi-digit values based on computation of one FWT multi-digit value of length M . The total number of FWTs is reduced more than twofold. That reduces the number of single precision additions and subtractions on sequential computation. It is shown that it is possible to compute algorithm in parallel. There are examples of computation algorithm of convolutions of length 4 и 8. Complexity of sequential and parallel computations is shown.
|
| issn |
1561-5359 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/57078 |
| citation_txt |
Параллельный алгоритм вычисления циклической свертки / А.Н. Терещенко, В.К. Задирака // Штучний інтелект. — 2012. — № 3. — С. 79-95. — Бібліогр.: 6 назв. — рос. |
| work_keys_str_mv |
AT tereŝenkoan parallelʹnyialgoritmvyčisleniâcikličeskoisvertki AT zadirakavk parallelʹnyialgoritmvyčisleniâcikličeskoisvertki AT tereŝenkoan paralelʹniialgoritmobčislennâciklíčnoízgortki AT zadirakavk paralelʹniialgoritmobčislennâciklíčnoízgortki AT tereŝenkoan parallelcomputationalgorithmofconvolution AT zadirakavk parallelcomputationalgorithmofconvolution |
| first_indexed |
2025-11-25T21:12:15Z |
| last_indexed |
2025-11-25T21:12:15Z |
| _version_ |
1850548427760336896 |
| fulltext |
«Штучний інтелект» 3’2012 79
2Т
УДК 510.52
А.Н. Терещенко, В.К. Задирака
Институт кибернетики имени В.М. Глушкова НАН Украины, г. Киев
Украина, 03680, МСП, Киев-187, проспект Академика Глушкова, 40
Параллельный алгоритм вычисления
циклической свертки
A.N. Tereshchenko, V.K. Zadiraka
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
Ukraine, 03680, Kyiv, 40 Glushkova ave
Parallel Computation Algorithm of Convolution
А.Н. Терещенко, В.К. Задірака
Інститут кібернетики імені В.М. Глушкова НАН України, м. Київ
Україна, 03680, МСП, Київ-187, проспект Академіка Глушкова, 40
Паралельний алгоритм обчислення циклічної згортки
Предложена оптимизация алгоритма вычисления циклической свертки длины 2nN на основе быстрого
преобразования Уолша (БПУ). Оптимизация заключается в использовании свойства предварительной
корректировки сигнала длины M сигналом длины 2M для получения суммарного результата БПУ
двух сигналов на основе одного БПУ длины M . За счет этого уменьшается число БПУ более чем в два
раза, что уменьшает сложность по числу операций сложения и вычитания. Показано, что алгоритм
поддается распараллеливанию. Алгоритм проиллюстрирован на реализации сверток длины 4 и 8.
Приведены оценки сложности при параллельном и последовательном вычислении.
Ключевые слова: многоразрядная арифметика, циклическая свертка, многоразрядное умно-
жение.
It is given the optimization of computation algorithm for convolution of length nN 2 based on Fast Walsh
transform (FWT). The optimization includes the use of the quality of pre-computational adjustment of multi-digit
value of length M by multi-digit value of length 2M to get the sum of FWTs both multi-digit values based on
computation of one FWT multi-digit value of length M . The total number of FWTs is reduced more than twofold.
That reduces the number of single precision additions and subtractions on sequential computation. It is shown that it is
possible to compute algorithm in parallel. There are examples of computation algorithm of convolutions of length 4 и
8. Complexity of sequential and parallel computations is shown.
Key Words: multidigit arithmetic, cyclic convolution, multidigit multiplication.
Запропонована оптимізація алгоритму обчислення циклічної згортки довжини 2nN на основі швидкого
перетворення Уолша (ШПУ). Оптимізація полягає у використанні властивості попереднього корегування
сигналу довжини M сигналом довжини 2M для отримання сумарного результату ШПУ двох сигналів
на основі одного ШПУ довжини M . За рахунок цього зменшується число ШПУ більш ніж у два рази,
що зменшує складність за кількістю операцій додавання та віднімання при послідовному обчисленні.
Показано, що алгоритм піддається розпаралелюванню. Алгоритм проілюстровано на реалізації згорток
довжини 4 и 8. Наведені оцінки складності при послідовному та паралельному обчисленні.
Ключові слова: багаторозрядна арифметика, циклічна згортка, багаторозрядне множення.
Введение
Аппаратная часть совершенствуется с каждым годом. Применяются новые техно-
логии и методы, которые повышают производительность. Одновременно с повышением
быстродействия повышаются требования ко времени выполнения алгоритмов шиф-
Терещенко А.Н., Задирака В.К.
«Искусственный интеллект» 3’201280
2Т
А
рования-дешифрования, которые оперируют с более длинными ключами (не менее
1024 бит). Быстродействие операции умножения является актуальной задачей, так как
от быстродействия данной операции в основном зависит время выполнения операций
в криптоалгоритмах.
Операция быстрого умножения может быть реализована с помощью алгоритмов
вычисления свертки. Данная работа является продолжением работ [1-5] по вычислению
циклической свертки с целью максимального распараллеливания всех шагов алгоритма
и повышения эффективности алгоритма.
Постановка задачи. На основе БПУ вычислить циклическую свертку NR разряд-
ностью N , где 2nN , 0n – целые, двух последовательностей NX и NY , используя
следующее выражение N N NR X Y , 0 1( ... )N NR r r ,
1
0
N
N
k p p k
p
r x y
, 0, 1k N ,
при последовательном выполнении на одном процессоре и при параллельном выпол-
нении на P процессорах (графического ускорителя).
Обозначения.
Последовательности длины N могут быть представлены в виде векторов:
0
1
1
N
N
x
x
X
x
,
0
1
1
N
N
y
y
Y
y
.
Циклическую свертку разрядностью 4N можно представить в виде:
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
0 1 2 3
x y y y y
x y y y y
x y y y y
x y y y y
r r r r
или
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
0 1 2 3
y x x x x
y x x x x
y x x x x
y x x x x
r r r r
.
Далее будет использоваться именно это представление.
( , )X X Z обозначает, что к элементам X добавляются элементы Z справа.
Соответственно длина X увеличивается на число элементов Z .
(( ) )M iX обозначает, что в X рассматривается i -я секция. Считается, что X
разбит на секции длины 2dM , где 0d – целое.
ix обозначает i -й элемент X . При этом вектор X считается полнозаполненным
без учета мнимой разбивки на секции разрядностью степени двойки.
В выражениях последовательность операций будем разбивать на группы сим-
волом ‘;‘. Группы выполняются в обычном порядке слева направо. Операции внутри
группы разделяются запятой и выполняются в обратном порядке – справа налево.
Если операцию обозначить номером ее выполнения, то получим строку, которая опре-
деляет порядок выполнения операций:
2, 1; 6, 5, 4, 3; 8, 7.
Введем следующие операторы: E , O , U , L , H , S , A , W , B ( E Even (чет-
ный), O Odd (нечетный), U Up (вверх), L Low (младший), H High (старший),
Параллельный алгоритм вычисления циклической свертки
«Штучний інтелект» 3’2012 81
2Т
S Substruct (вычитание), A Addition (добавление), W Walsh (одна итерация пре-
образования Уолша), B Bit inverse order (бит-инверсная перестановка) и обозначим
их следующим образом:
2( )N kk
E X x , 2 1( )N kk
O X x , ( )N kk
L X x , 2( )N k Nk
H X x , 0, 2 1k N ;
циклический сдвиг элементов вверх – ( )N NV U X , 1
N
k kv x , 0, 1k N ;
( ) ( ) ( )N N NS Z E Z O Z , ( ) ( ) ( )N N NA Z E Z O Z ;
( )N NZ W X ,
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
N N N N
N N N N
E Z A X E X O X
O Z S X E X O X
.
Проиллюстрируем введенные операторы для случаев 4, 8N :
0
2
8
4
6
( )
x
x
E X
x
x
,
1
3
8
5
7
( )
x
x
O X
x
x
,
1
2
4
3
0
( )
y
y
U Y
y
y
,
0
1
8
2
3
( )
x
x
L X
x
x
,
4
5
8
6
7
( )
x
x
H X
x
x
,
0 1
2 3
8
4 5
6 6
( )
x x
x x
S X
x x
x x
,
0 1
2 3
8
4 5
6 6
( )
y y
y y
A Y
y y
y y
,
0 1
0 1
4
2 3
2 3
( )
x x
x x
W X
x x
x x
,
0
2
4
1
3
( )
x
x
B X
x
x
.
Матрицы дискретного преобразования Уолша (с упорядочиванием по Пели),
которые необходимо отличать от оператора W , обозначим следующим образом:
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
W
, 8
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
W
.
Лемма 1. При вычислении БПУ сигнала NX , где 2nN , 0n – целые, опера-
тор W длины N выполняется n раз над вектором NX .
Доказательство. Вычисление БПУ можно организовать следующим образом:
( (( ) ))
(( ) )
( (( ) ))
M j
M j
M j
B L X
X
B H X
, ( ) ) ( (( ) ))M j M jX B W X , 0, 2 1ij , 2n iM ,
0, 1i n .
Вычисление БПУ длины 22 4N согласно предыдущей формуле имеет вид:
Терещенко А.Н., Задирака В.К.
«Искусственный интеллект» 3’201282
2Т
А
4
4
4
4
4
ˆ( ( ( )))
ˆ( ( ( )))
ˆ
ˆ( ( ( )))
ˆ( ( ( )))
B L L X
B H L X
X
B L H X
B H H X
,
4
4
4
ˆ( ( ( )))
ˆ
ˆ( ( ( )))
B W L X
X
B W H X
,
4
4
4
ˆ( ( ))
ˆ
ˆ( ( ))
B L X
X
B H X
, 4 4
ˆ ( ( ))X B W X .
Так как оператор B (бит-инверсная перестановка) не переставляет элементы,
если длина вектора равна 1 или 2, то оператор B и сопутствующие ему операторы
L , H могут быть опущены в предыдущих выражениях, кроме 4 4
ˆ ( ( ))X B W X . Так
как
4
4
4
( ( ))
( )
( ( ))
W L Z
W Z
W H Z
, то окончательное выражение для вычисления БПУ длины 4
будет 4 4
ˆ ( ( ( )))X W B W X , где W применяется по всей длине вектора.
Более детально данное преобразование (справа налево) представлено ниже:
0 1 2 3 0 1
0 1 2 3 2 3
4
0 1 2 3 0 1
0 1 2 3 2 3
ˆ
x x x x x x
x x x x x x
X W
x x x x x x
x x x x x x
,
0 1 0 1
2 3 0 1
0 1 2 3
2 3 2 3
x x x x
x x x x
B
x x x x
x x x x
,
0 1 0
0 1 1
4
2 3 2
2 3 3
x x x
x x x
W X
x x x
x x x
.
В БПУ длины 8N оператор W также можно применять по всей длине:
8
8
8
ˆ( ( ))
ˆ
ˆ( ( ))
B L X
X W
B H X
,
8
8
8
ˆ( ( ))
ˆ
ˆ( ( ))
B L X
X W
B H X
, 8 8
ˆ ( ( ))X B W X .
В работе [6] используется алгоритм с высоким уровнем распараллеливания и
сохранением структуры графа преобразования Уолша с различными системами упоря-
дочивания по Пели, Уолшу – Качмажу и преобразование Уолша с четным – нечетным
упорядочиванием, которые требуют меньшее число перестановок для ускорения рас-
параллеливания.
Вычисление БПУ длины 16N будет следующим:
16
16
16
16
16
ˆ( ( ( )))
ˆ( ( ( )))
ˆ
ˆ( ( ( )))
ˆ( ( ( )))
B L L X
B H L X
X W
B L H X
B H H X
,
16
16
16
16
16
ˆ( ( ( )))
ˆ( ( ( )))
ˆ
ˆ( ( ( )))
ˆ( ( ( )))
B L L X
B H L X
X W
B L H X
B H H X
,
16
16
16
ˆ( ( ))
ˆ
ˆ( ( ))
B L X
X
B H X
,
16
16
16
ˆ( ( ))
ˆ
ˆ( ( ))
B L X
X W
B H X
, 16 16
ˆ ( ( ))X B W X .
Параллельный алгоритм вычисления циклической свертки
«Штучний інтелект» 3’2012 83
2Т
Продолжая по индукции, можно показать, что, применяя B , L и H , можно орга-
низовать вычисление таким образом, что W на каждой итерации применяется над
всеми элементами. Лемма доказана.
Следствие. При параллельном вычислении БПУ длины 2nN , где 0n –
целое, каждый из N процессоров выполнит только n операций сложения (вычитания).
Перед тем как перейти к описанию нового алгоритма, рассмотрим следующее
свойство сложения БПУ сигналов разной разрядности.
Лемма 2. Если сигналы
1
0
2
M
M k
k
Z z
,
2 1
2
0
2
M
M k
k
V v
, где – длина слова
в битах, 2 pM , 0p , формируют сигнал
1
0
2
M
M k
k
R r
вида: 2s s kr z v ,
2s t s t kr z v ,
k
s k t
t
, 0, 2 1k M , где
2
M
t
q
, 2mt , 1 ,
2
M
t q , 0m ,
то БПУ
1
0
ˆ ˆ 2
M
M k
k
Z z
,
2 1
2
0
ˆ ˆ 2
M
M k
k
V v
,
1
0
ˆ ˆ 2
M
M k
k
R r
связаны следующими вы-
ражениями:
ˆ ˆˆ2 2d d kr z v , ˆ ˆ2d q d qr z , 1
i
d k q
q
, 0, 2 1k M .1
Доказательство. Заметим, что выражения s k t k t , 1d k q k q
имеют одинаковую структуру, с учетом того, что t и q взаимосвязаны
2
M
t
q
и
определяют длину последовательности значений идущих по порядку (табл. 1).
Таблица 1 – Зависимость значений s и d от значений t , q , M
k 0 1 2 3 4 5 6 7
8M
4t s 0 1 2 3
1q d 1 3 5 7
8M
2t s 0 1 4 5
2q d 2 3 6 7
8M
1t s 0 2 4 6
4q d 4 5 6 7
16M
8t s 0 1 2 3 4 5 6 7
1q d 1 3 5 7 9 11 13 15
16M
4t s 0 1 2 3 8 9 10 11
2q d 2 3 6 7 10 11 14 15
16M
2t s 0 1 4 5 8 9 12 13
4q d 4 5 6 7 12 13 14 15
16M
1t s 0 2 4 6 8 10 12 14
8q d 8 9 10 11 12 13 14 15
Рассмотрим результаты сложения БПУ сигналов 8 (0, 0, 0, 0, 0, 0, 0, 0)Z и
4 (1, 4, 9, 25)V . Найдем сначала БПУ сигнала 4V .
Терещенко А.Н., Задирака В.К.
«Искусственный интеллект» 3’201284
2Т
А
4 4 4
1 1 1 1 1 39
1 1 1 1 4 29ˆ
1 1 1 1 9 19
1 1 1 1 25 13
V W V
.
Рассмотрим результаты сложения при 1, 2, 4q .2 Получим результат:
0
1
2
34, 1
8 8
0
1
2
3
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 4
1 1 1 1 1 1 1 1 9
1 1 1 1 1 1 1 1 25ˆ
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 4
1 1 1 1 1 1 1 1 9
1 1 1 1 1 1 1 1 25
t q
v
v
v
v
R W
v
v
v
v
0
1
2
3
00
ˆ78
00
ˆ58
2 .
00
ˆ38
0 0
26 ˆ
d
d
d
d
0
1
0 0
1 12, 2
8 8 8
2
3
2 2
3 3
01 0
04 0
ˆ1 78
ˆ4 58ˆ 2 ,
09 0
025 0
ˆ9 38
ˆ25 26
t q
v
v
v v
v v
R W W
v
v
v v
v v
0
0
1
11, 4
8 8 8
2 0
2 1
3 2
3 3
01 0
01 0
04 0
04 0ˆ 2 .
ˆ9 78
ˆ9 58
ˆ25 38
ˆ25 26
t q
v
v
v
v
R W W
v v
v v
v v
v v
Изучив исходные данные и результат выражений 1
8
ˆ qR , 2
8
ˆ qR , 4
8
ˆ qR , видим, что,
прибавив определенным образом элементы сигнала 4V к элементам сигнала 8Z , одно-
временно с вычислением преобразования Уолша сигнала 8Ẑ вычисляется преобразо-
вание сигнала 4̂V . Необходимо также использовать поправочный коэффициент 2 для
8Z , так как 1
8
ˆ qR , 2
8
ˆ qR , 4
8
ˆ qR содержат удвоенное значение 4̂V .
Указанное в лемме свойство сохраняется при больших разрядностях свертки,
рассматривая по индукции. Лемма доказана.
Примечание 1. Другими словами, q – длина секции ˆ
MR , к которой последова-
тельно добавляются элементы из 2M̂V .
Примечание 2. В представленном алгоритме используется только случай при
1q (см. также Шаг 9б алгоритма).
Вычисление циклической свертки разрядностью 4N на основе БПУ. В работе [3]
приведен метод вычисления циклической свертки с использованием БПУ, основанный
на вычислении сверток половинной длины. Алгоритм [3] осуществляет разбиение до
сверток длины 4N , для вычисления которой достаточно 5 операций однословного
умножения. Далее приведен новый алгоритм вычисления свертки на основе БПУ
Параллельный алгоритм вычисления циклической свертки
«Штучний інтелект» 3’2012 85
2Т
длины 4N , при котором обратное БПУ выполняется в качестве последней операции,
что гораздо удобнее при реализации параллельного алгоритма:
4 4 4
1 ˆ
8
R W A , 4 4 4 4
ˆ ˆ ˆ2A X Y T , 4
0
0
t
T
t
,
4 4
ˆ ˆ( ( )) ( ( ))t S O X A O Y ,
4 4 4
4 4 4
ˆ
ˆ
X W X
Y W Y
,
где 4X , 4Y – входные сигналы; 4R – результат вычисления циклической свертки
сигналов 4X и 4Y ; 1 3 0 2 1 0 3 2 1 2 3 0( ) ( )t x x y y x y x y x y x y .
Использование операторов S , A над векторами 4X̂ , 4̂Y для вычисления t яв-
ляется резервом оптимизации, так как дает возможность не сохранять 4X и 4Y .
Алгоритм 1. Реализация операции циклической свертки двух последовательностей
длины 2nN с использованием БПУ и параллельных вычислений.
Параметры: NX , NY – последовательности длины 2nN , где 3n , n – целое.
Результат: N N NR X Y – циклическая свертка сигналов NX , NY .
Шаг 0. Инициализация. 02
(( ) )n NN
X X X
; 02
(( ) )n NN
Y Y Y
.
Шаг 1. БПУ начальной секции 0(( ) )NX . 0 0(( ) ) (( ) )N N NX W X .
Шаг 2. ДПУ остальных секций вектора X как линейные комбинации секций X .
2( , )MX X V , 2 (( ) ) (( ) )M M j M jV L X H X ,
0, 1j T , 2n iM , 3iT , 0, 3i n .3,4
Шаг 3. БПУ секций вектора Y (за исключением двух последних итераций).
Шаг 3а. Для i с 0 по 3n
Шаг 3б. 2( , )MY Y V , 2 ( ( )) ( )M M MV U E Z E Z ,
Шаг 3в.
( (( ) ))
(( ) )
( (( ) ))
M j
M j
M j
B L Y
Y
B H Y
, (( ) ) ( ( ))M j MY B W Z ,
Шаг 3г. (( ) )M M jZ Y , 0, 1j T , 2n iM , 3iT .
Шаг 3д. Конец цикла по i .3,4
Шаг 4. Последние 2 итерации БПУ. 4 4(( ) ) ( ( (( ) )))j jY W B W Y , 20, 3 1nj
(см. Лемму 1).
Шаг 5. Дополнительные секции
2 23 4 3
( ( ))n nXADD S O X
, 2 23 4 3
( ( ))n nYADD A O Y
.
Шаг 6. Поэлементное умножение основных секций. 2 2 24 3 4 3 4 3
2n n nR X Y
.
Шаг 7. Поэлементное умножение дополнительных секций.
2 2 23 3 3n n nRADD XADD YADD .
Шаг 8. Подготовка к вычислению сверток длины 4.
4 1 4 1j j jr r radd , 4 3 4 3j j jr r radd , 20, 3 1nj .4
Терещенко А.Н., Задирака В.К.
«Искусственный интеллект» 3’201286
2Т
А
Шаг 9. Подготовка к вычислению сверток длины 8 и больше.
Шаг 9а. Для i с 3n до 0 шаг –1.
Шаг 9б.
2
2
( )
(( ) )
( )
M M
M j
M M
L Z V
R
H Z V
, (( ) )M M jZ R ,
2 2 2
1
(( ) )
2M M T jV R , 0, 1j T , 2n iM , 3iT .4
Шаг 9в. Конец цикла по i .
Шаг 10. Вычисление ОБПУ. 0
1 1
(( ) )
2N N NR W R
N
.
Примечание 3. Длина X (или Y ) после каждой итерации по i увеличивается
и равна
1
3
2
2
i
n
. По завершении цикла по i ( 3i n ) длина X (или Y ) равна
24 3n (см. Лемма 4 и Теорема 1).
Примечание 4. В алгоритме i соответствует номеру итерации, j – номеру обра-
батываемой секции на итерации i . При обработке Y мнимо разбивается на секции
одинаковой длины 2n iM . При вычислении X и R на итерации i рассматриваются
секции длины M и 2M .
Ниже приведена схема вычисления свертки длины 8N на основе приведен-
ного алгоритма.
Рисунок 1 – Схема вычисления свертки длины 8N на основе Алгоритма 1
Число операций при последовательном выполнении алгоритма.
Лемма 3. При последовательном вычислении свертки сложность по числу одно-
словных операций умножения равна 25 3n .
2
2
2
2
2
2
2
2
Вx0
x1
x2
x3
x4
x5
x6
x7
y0
y1
y2
y3
y4
y5
y6
y7
У
м
н
о
ж
е
н
и
е
Б
П
У
БПУ 4W
WB
r0
r1
r2
r3
r4
r5
r6
r7
r8
r9
r10
r11
radd0
radd1
radd2
2
2
2
2
Б
П
У
r0
r1
r2
r3
r4
r5
r6
r71/2
1/2
1/2
1/2
1/2
1/2
1/2
1/2
1/8
1/8
1/8
1/8
1/8
1/8
1/8
1/8
1/2
1/2
1/2
1/2
1/2
1/2
1/2
1/2
Параллельный алгоритм вычисления циклической свертки
«Штучний інтелект» 3’2012 87
2Т
Доказательство. Согласно Шагам 6 и 7 Алгоритма 1 число элементов основных и
дополнительных секций при поэлементном умножении равно 24 3n и 23n соответ-
ственно. Лемма доказана.
Лемма 4. При последовательном вычислении свертки сложность по числу одно-
словных операций сложения (вычитания) равна 25 3 ( 1) 2n nn для нахождения
элементов в основных 24 3nX
и дополнительных 23nXADD секциях.
Доказательство. В табл. 2 показана зависимость числа основных секций от длины
N входной последовательности и определено число итераций, необходимых для по-
строения основных секций X .
Таблица 2 – Итерационное вычисление вектора длин основных секций X
при вычислении сверток длины 2nN , 3,4,5,6n (Шаг 2)
i 8, 3N n
0 8, 4
i 16, 4N n
0 16, 8
1 8,8,8, 4,4,4
i 32, 5N n
0 32,16
1 16,16,16, 8,8,8
2 8,8,8, 8,8,8, 8,8,8, 4,4,4, 4,4,4,
4,4,4
i 64, 6N n
0 64,32
1 32,32,32, 16,16,16
2 16,16,16, 16,16,16, 16,16,16, 8,8,8, 8,8,8, 8,8,8
3 8,8,8, 8,8,8, 8,8,8, 8,8,8, 8,8,8, 8,8,8, 8,8,8, 8,8,8,
8,8,8,
4,4,4, 4,4,4, 4,4,4, 4,4,4, 4,4,4, 4,4,4, 4,4,4, 4,4,4, 4,4,4
Из табл. 2 видно, что на каждой итерации число элементов увеличивается в
3 2 раза, так как вычисление каждой свертки длины M (согласно методу Питасси [1])
основано на трех свертках половинной длины 2M . Число элементов X на последней
итерации 3n равно:
( 3) 1
23
2 4 3
2
n
n n
.
Алгоритм БПУ используется только для вычисления ДПУ начальной основной
секции X длины 2nN , для чего необходимо n N одноразрядных операций сло-
жения (вычитания). ДПУ всех остальных 24 3nX
и 23nXADD секций вычисляются как
линейные комбинации ДПУ начальной основной секции X на Шагах 2 и 5 с исполь-
зованием операторов L , H , S и O , что является резервом оптимизации и позволяет
уменьшить число вычислений ДПУ на треть, что существенно для длинных сверток.
С учетом числа операций для вычисления БПУ начальной секции длины N
общее число одноразрядных операций сложения (вычитания) для вычисления секций
в 24 3nX
(Шаги 1 и 2) будет равно 2 24 3 4 3 ( 1) 2n n nN n N n , где 2nN ,
0n – целое. При применении операторов S и O (каждый из которых уменьшает
24 3nX
в два раза) на Шаге 5 для вычисления секций 23nXADD необходимо 23n опе-
рации вычитания.5 Таким образом, общее число одноразрядных операций сложения
(вычитания) составляет 2 2 24 3 ( 1) 2 3 5 3 ( 1) 2n n n n nn n .
Лемма доказана.
Терещенко А.Н., Задирака В.К.
«Искусственный интеллект» 3’201288
2Т
А
Примечание 5. В отличие от алгоритма [3] в предложенном алгоритме БПУ в
дополнительных секциях ( 23nXADD и 23nYADD ) не выполняется, что также является
резервом оптимизации и значительно уменьшает общее число операций сложения
(вычитания).
Теорема 1. При последовательном вычислении свертки сложность по числу одно-
словных операций сложения (вычитания) равна 213 3 3 2n n для нахождения основ-
ных 24 3nY
и дополнительных 23nYADD секций.
Доказательство. Особенностью вычисления элементов Y является то, что на
Шаге 3б используется циклический сдвиг ( ( )) ( )M MU E Z E Z , который не может быть
получен как результат линейных комбинаций ДПУ секций Y . Поэтому в Y необходимо
выполнять БПУ в каждой секции полностью на Шаге 3в. Вычисление алгоритма можно
организовать таким образом, что на каждой итерации 0, 3i n для каждой секции Y
выполняется только один шаг БПУ
( (( ) ))
(( ) )
( (( ) ))
M j
M j
M j
B L Y
Y
B H Y
, (( ) ) ( (( ) ))M j M jY B W Y
(см. Лемму 1) за исключением секций длины 4.
В табл. 3 представлено по секциям число операций сложения (вычитания), необ-
ходимых для завершения одного шага БПУ. На каждой итерации i оператор W
применяется для секций одинаковой длины 2n iM . Разбиение на секции необходимо,
так как после применения оператора W применяется оператор B (бит-инверсная сор-
тировка), результат которого зависит от длины секции 2n iM .
Таблица 3 – Зависимость числа операций сложения (вычитания)
одного шага БПУ для каждой секции Y длины 2n iM , 0, 3i n ,
при вычислении сверток длины 2nN , 3,4,5,6n (Шаги 3в и 4)
i Шаг № 8, 3N n
0 Шаг 3в 8
Шаг 4 4,4,4
Шаг 4 4,4,4
i 16, 4N n
0 Шаг 3в 16
1 Шаг 3в 8,8,8
Шаг 4 4,4,4,4,4,4,4,4,4
Шаг 4 4,4,4,4,4,4,4,4,4
i 32, 5N n
0 Шаг 3в 32
1 Шаг 3в 16,16,16
2 Шаг 3в 8,8,8, 8,8,8, 8,8,8
Шаг 4 4,4,4,4,4,4, 4,4,4,4,4,4,
4,4,4,4,4,4, 4,4,4,4,4,4, 4,4,4.6
Шаг 4 4,4,4,4,4,4, 4,4,4,4,4,4,
4,4,4,4,4,4, 4,4,4,4,4,4, 4,4,4.6
i Шаг № 64, 6N n
0 Шаг 3в 64
1 Шаг 3в 32,32,32
2 Шаг 3в 16,16,16, 16,16,16, 16,16,16
3 Шаг 3в 8,8,8, 8,8,8, 8,8,8,
8,8,8, 8,8,8, 8,8,8,
8,8,8, 8,8,8, 8,8,8
Шаг 4 4,4,4,4,4,4, 4,4,4,4,4,4,
4,4,4,4,4,4, 4,4,4,4,4,4, 4,4,4
4,4,4,4,4,4, 4,4,4,4,4,4,
4,4,4,4,4,4, 4,4,4,4,4,4, 4,4,4
4,4,4,4,4,4, 4,4,4,4,4,4,
4,4,4,4,4,4, 4,4,4,4,4,4, 4,4,4.5
Шаг 4 4,4,4,4,4,4, 4,4,4,4,4,4,
4,4,4,4,4,4, 4,4,4,4,4,4, 4,4,4
4,4,4,4,4,4, 4,4,4,4,4,4,
4,4,4,4,4,4, 4,4,4,4,4,4, 4,4,4
4,4,4,4,4,4, 4,4,4,4,4,4,
4,4,4,4,4,4, 4,4,4,4,4,4, 4,4,4.6
Примечание 6. Пробелы добавлены для удобства восприятия.
Из табл. 3 видно, что на последующей итерации (Шаг 3в) длина секций умень-
шается в два раза и число секций увеличивается в три раза, следуя методу Питасси.
Параллельный алгоритм вычисления циклической свертки
«Штучний інтелект» 3’2012 89
2Т
Общее число операций сложения (вычитания), необходимых для пошагового вычис-
ления БПУ (только Шаг 3в) в каждой секции, может быть получено как сумма гео-
метрической прогрессии по следующей формуле:
1
3
1
( ) 2
1
i
n
Шаг в T i
q
Q Y
q
, 12n iT q , 0, 3i n ,
3
2
q ,
где 3 ( )Шаг в T iQ Y – сумма числа операций сложения (вычитания) над элементами
TY по i -ю итерацию включительно.
С учетом предыдущей формулы общее число операций сложения (вычитания) над
элементами Y на Шаге 3в по завершении итерации 3i n может быть выражено
как 2
2 1
3 4 3
( ) 8 3 2n
n n
Шаг вQ Y
при 2n .
На Шаге 3б длина Y увеличивается на каждой итерации по j и по i . Тогда для
нахождения остальных элементов (кроме исходной начальной секции длины 2nN )
необходимо 24 3 2n n операций по аналогии с X . По завершении Шагов 2 и 3а-3д
длины 24 3nX
и 24 3nY
равны. С учетом 23n операций сложения для нахождения
23nYADD на Шаге 4 общее число операций сложения (вычитания) основных 24 3nY
и
дополнительных 23nYADD секций5 будет следующим:
2 2 2 2 23 3 44 3 3 4 3 4 3 3
( , ) ( ) ( ) ( )n n n n nШаг б Шаг в ШагQ Y YADD Q Y Q Y Q YADD
.
2 2
2 2 1 2 2
4 3 3
( , ) 4 3 2 8 3 2 3 13 3 3 2n n
n n n n n n nQ Y YADD
.
Теорема доказана.
Теорема 2. При последовательном вычислении свертки сложность по числу опе-
раций сложения (вычитания) равна 210 3 ( 2) 2n nn для нахождения 24 3nR
.
Доказательство. Особенностью вычисления 24 3nR
является то, что нет необхо-
димости вычислять БПУ меньших сверток в основных секциях по аналогии с X .
Вычисляется БПУ только начальной основной секции 02
(( ) )nN
R
, используя свойство
сложения результатов БПУ векторов длин M и 2M , доказанное в Лемме 2. Значения
секций меньшей длины 2M добавляются последовательно к секциям длины M таким
образом, что после вычисления БПУ начальной основной секции 02
(( ) )nN
R
результат
начальной секции будет содержать корректировку, как если бы БПУ меньших секций
были вычислены и добавлены к секциям большей длины.
Общее число операций сложения (вычитания) на Шаге 9б (табл. 4), необходимых
для подготовки вычисления БПУ каждой секции, может быть получено как сумма
геометрической убывающей прогрессии по следующей формуле:
1
3
9
1
( ) 8 3
1
i
n
Шаг б T i
q
Q R
q
, 2 14 3n iT q , 0, 3i n ,
2
3
q ,
где 9 ( )Шаг б T iQ R – сумма числа операций сложения (вычитания) над элементами
R с итерации 0 по i включительно.
T отражает число элементов секций, которые были откорректированы значе-
ниями меньших секций на итерации i Шага 9б.
Терещенко А.Н., Задирака В.К.
«Искусственный интеллект» 3’201290
2Т
А
Таблица 4 – Итерационная обработка 24 3nR
(Шаг 9б)
перед вычислением ОБПУ при нахождении сверток
длины 2nN , 3,4,5,6n (число операций сложения и вычитания)
i 8, 3N n
0 +4,–4.7
i 16, 4N n
0 +4,–4, +4,–4, +4,–4.7
1 +8,–8.7
i 32, 5N n
0 +4,–4, +4,–4, +4,–4,
+4,–4, +4,–4, +4,–4,
+4,–4, +4,–4, +4,–4.7
1 +8,–8, +8,–8, +8,–8.7
2 +16,–16.7
i 64, 6N n
0 +4,–4, +4,–4, +4,–4, +4,–4, +4,–4, +4,–4, +4,–4, +4,–4, +4,–4,
+4,–4, +4,–4, +4,–4, +4,–4, +4,–4, +4,–4, +4,–4, +4,–4, +4,–4,
+4,–4, +4,–4, +4,–4, +4,–4, +4,–4, +4,–4, +4,–4, +4,–4, +4,–4.7
1 +8,–8, +8,–8, +8,–8, +8,–8, +8,–8, +8,–8, +8,–8, +8,–8, +8,–8.7
2 +16,–16, +16,–16, +16,–16.7
3 +32, –32.7
Примечание 7. Пробелы добавлены для удобства восприятия. Знаки «+» и «–»
обозначают число операций сложения и вычитания соответственно по секциям.
Общее число однословных операций сложения (вычитания) над элементами R
на Шаге 9б по завершении итерации 3i n может быть выражено формулой
2 1
9 ( ) 8 3 2n n
Шаг бQ R при 2n .
С учетом 23n операций сложения, 23n операций вычитания на Шаге 8 и 2nn
операций сложения (вычитания) на Шаге 10 для вычисления ОБПУ общее число
операций сложения (вычитания), необходимых для вычисления R , примет вид:
2 2 28 9 10 04 3 4 3 4 3 2
( ) ( ) ( ) (( ) )n n n nШаг Шаг б ШагQ R Q R Q R Q R
.
2
2 2 1 2
4 3
( ) 2 3 8 3 2 2 10 3 ( 2) 2n
n n n n n nQ R n n
.
Теорема доказана.
Теорема 3. При последовательном вычислении свертки общая сложность по числу
однословных операций сложения (вычитания) равна 2 128 3 ( 3) 2n nn .
Доказательство. Общее число операций сложения (вычитания) имеет вид:
X Y RQ Q Q Q ,
где , ,X Y RQ Q Q – число операций сложения (вычитания) при обработке X , Y и R .
При подстановке значений, полученных в Лемме 1 и Теоремах 2, 3, приходим к
следующему выражению:
2 2 25 3 ( 1) 2 13 3 3 2 10 3 ( 2) 2n n n n n nQ n n .
После суммирования приходим к искомому выражению. Теорема доказана.
Число операций при параллельном вычислении алгоритма. На данное время час-
тота процессора достигает своего физического предела. В то же самое время требования
по времени выполнения операций над большими числами усиливаются. Кластерные
решения позволяют достигать требуемых условий по быстродействию, но являются
дорогостоящими, что не дает возможности широкого применения. Одним из решений
является интегрирование большого числа ядер на одном кристалле, что удешевляет
аппаратную часть решения. Такие системы используют потоковые процессоры, особен-
Параллельный алгоритм вычисления циклической свертки
«Штучний інтелект» 3’2012 91
2Т
ностью которых является параллельное выполнение однотипной операции над большим
массивом данных. Примером таких плат можно привести графические ускорители
компаний NVIDIA и AMD (последние модели: GeForce GTX 580 с 512 потоковыми
процессорами, Radeon HD 6990 с 3072 потоковыми процессорами). Изначально гра-
фические ускорители (GPU – Graphic Processor Unit) разрабатывались для решения
задач быстрой обработки графической информации, которые могли быстро выполнять
параллельно небольшой набор арифметических операций над векторами и массивами.
Со временем графические ускорители переросли задачи графической обработки, набор
команд вырос до такой степени, что ускорители стали называть GPGPU (General
Purpose Graphic Processor Unit – графический ускоритель общего назначения). Методы,
эффективные при последовательном выполнении, не эффективно использовать при
реализации на параллельных (потоковых) процессорах графических ускорителей.
Последовательные методы используют большой набор арифметических операций и
функций на разных шагах алгоритма, что делает их сильно зависимыми друг от друга и
требует ожидания выполнения текущего шага перед тем, как перейти к вычислению
следующего шага, что ограничивает число одновременно задействованных потоковых
процессоров. Для использования графических ускорителей необходимы новые алгорит-
мы, которые распределяют вычисления таким образом, чтобы задействовать максимально
свободные процессоры, что в свою очередь уменьшает общее число операций, выпол-
ненных каждым из процессоров, и значительно уменьшает общее время выполнения
операции, реализуемой данным алгоритмом. При разработке таких алгоритмов необходи-
мо находить баланс между разбивкой на число таких шагов, каждый из которых имеет
однотипные независимые друг от друга операции, и числом операций на каждом шаге.
Особенностью представленного алгоритма является то, что все операции в итера-
ции по j являются независимыми. Если число параллельных (потоковых) процессоров
превышает число операций алгоритма, необходимых для завершения итерации i , то
достаточно одной операции (такта) потоковых процессоров для выполнения итерации i .
Если шаг алгоритма состоит из нескольких итераций по i (например 2n итерации)
и число задействованных потоковых процессоров превышает (или равно) число опера-
ций на каждой итерации i , то время выполнения данного шага будет равно времени
выполнения 2n операций потоковых процессоров с учетом того, что все процес-
соры работают параллельно. Продолжая данные рассуждения, рассмотрим сложность
по числу операций сложения (вычитания) и умножения каждого шага предложенного
алгоритма при параллельном выполнении в следующей теореме. Для удобства будем
считать, что освободившиеся процессоры не начинают вычислений по итерации 1i
до тех пор, пока не выполнится последняя операция на итерации i . Перед нахождением
оценок сложности при параллельной модели вычислений рассмотрим следующую лемму.
Лемма 5. Сложность по числу операций при параллельном вычислении I ите-
раций на P ( I P ) процессорах может быть получена на основе сложности по числу
операций при последовательном вычислении с учетом того, что процессоры не начинают
новую итерацию, пока не закончена текущая итерация, используя следующее выражение:
.
.
посл вычисление
парал вычисление
Q
Q I
P
,
где
1
. , .
0
I
посл вычисление i посл вычисление
i
Q Q
– общее число операций при последовательном
вычислении I итераций, каждая их которых поддается распараллеливанию.
Терещенко А.Н., Задирака В.К.
«Искусственный интеллект» 3’201292
2Т
А
Доказательство. Максимальное число операций, выполненное одним из парал-
лельных P процессоров, на I итерациях может быть представлено в следующем виде:
1
, .
.
0
I
i посл вычисление
посл вычисление
i
Q
Q
P
.
Изменим предыдущую формулу таким образом, чтобы использовать округление
к меньшему числу вместо округления к большему числу, что позволит избежать ис-
пользования знака суммы:
1
, . .
.
0
1 ( 1)I
i посл вычисление посл вычисление
посл вычисление
i
Q P Q I P
Q
P P P
.
Если I P , то приходим к искомому выражению. Лемма доказана.
Теорема 4. При параллельном вычислении свертки N N NR X Y длины 2nN
на P процессорах сложность по числу операций однословного сложения, вычитания
и умножения равна
2 1
,* 33 3 ( 3) 2
6 4
n nn
Q n
P
.
Доказательство. Число операций при параллельном вычислении можно пред-
ставить в виде:
1, 2 5 1 2 5( , ) ( ) ( ) ( )Шаг и Шаг Шаг ШагQ X XADD Q X Q X Q XADD ,
3 , 3 4 3 3 4( , ) ( ) ( ) ( )Шаг б в и Шаг б Шаг в ШагQ Y YADD Q Y Q Y Q YADD ,
8, 9 10 8 9 10( ) ( ) ( ) ( )Шаг б и Шаг Шаг б ШагQ R Q R Q R Q R ,
где 1 ( )ШагQ X , 2 ( )ШагQ X , 5 ( )ШагQ XADD – число операций на Шагах 1,2 и 5 для
X , XADD ; 3 ( )Шаг бQ Y , 3 ( )Шаг вQ Y , 4 ( )ШагQ YADD – число операций на Шагах 3б, 3в и
4 для Y , YADD ; 8 ( )ШагQ R , 9 ( )Шаг бQ R , 10 ( )ШагQ R – число операций на Шагах 8, 9б и
10 для R .
На Шаге 3б на одной итерации по j элементы добавляются к Y на основе эле-
ментов секции (( ) )M jY , которая модифицируется на Шаге 3в, поэтому Шаги 3б и 3в
являются зависимыми. При параллельном вычислении Шагов 3б и 3в нельзя гаран-
тировать, что элементы добавятся к Y до того, как секция будет модифицирована.
Поэтому считаем, что Шаги 3в и 3б выполняются последовательно и представляют
отдельные итерации. Выражения 4 1 4 1j j jr r radd , 4 3 4 3j j jr r radd на Шаге 8
не зависят друг от друга, поэтому они могут быть вычислены в одной итерации.
Таблица 5 – Число операций и итераций на Шагах 1, 2, 5, 3б, 3в, 4, 8, 9б, 10
при последовательном вычислении ,X XADD , ,Y YADD , R
,X XADD ,Y YADD R
Шаг
Ите-
раций
Операций Шаг Итераций Операций Шаг
Ите-
раций
Операций
1 n 2nn 3б 2n 24 3 2n n 8 1 22 3n
2 2n 24 3 2n n 3в 2n 2 18 3 2n n 9б 2n 2 18 3 2n n
5 1 23n 4 1 23n 10 n 2nn
Параллельный алгоритм вычисления циклической свертки
«Штучний інтелект» 3’2012 93
2Т
С учетом Леммы 5 и табл. 5 оценки для параллельной модели вычислений можно
представить в виде:
2 2
1, 2 5
2 4 3 2 3
( , ) 2 1
n n n n
Шаг и
n
Q X XADD n n
P P P
;
2 2 1 2
3 , 3 4
4 3 2 8 3 2 3
( , ) 2 2 1
n n n n n
Шаг б в иQ Y YADD n n
P P P
;
2 2 1
8, 9 10
2 3 8 3 2 2
( ) 1 2
n n n n
Шаг б и
n
Q R n n
P P P
;
2
* 5 3
1
n
Q
P
.
После группировки приходим к выражениям:
2
1, 2 5
5 3 ( 1) 2
( , ) 2 1
n n
Шаг и
n
Q X XADD n
P
,
2
3 ,3 4
13 3 3 2
( , ) 2 3
n n
Шаг б в иQ Y YADD n
P
;
2
8, 9 10
10 3 ( 2) 2
( ) 2 1
n n
Шаг б и
n
Q R n
P
;
2
* 5 3
1
n
Q
P
.
После суммирования всех выражений приходим к искомому выражению. Теорема
доказана.
Тестовый пример вычисления свертки длины 16N . В табл. 6 считается, что
индексирование в векторах начинается с нуля и элемент с нулевым индексом распо-
ложен слева. Длина одного разряда равна 32 бит.
Таблица 6 – Пример вычисления свертки предложенным алгоритмом
при 16N , 4n
Шаг № i , j Значение вектора после Шага № на итерации по i , j
Шаг 0
16X =1,2,3,4,5,6,7,8,0,0,0,0,0,0,0,0.8
16Y =0,0,0,0,0,0,0,0,8,7,6,5,4,3,2,1.8
Шаг 1
16 0(( ) )X =36,36,16,¯16,¯8,¯8,0,0,¯4,¯4,0,0,0,0,0,0
Шаг 2 0i , 0j
24X =36,36,¯16,¯16,¯8,¯8,0,0,¯4,¯4,0,0,0,0,0,0,40,40,¯16,¯16,¯8,¯8,0,0
Шаг 2 1i , 0j
28X =36,36,¯16,¯16,¯8,¯8,0,0,¯4,¯4,0,0,0,0,0,0,40,40,¯16,¯16,¯8,¯8,0,0,
44,44,¯16,¯16
Шаг 2 1i , 1j
32X =36,36,¯16,¯16,¯8,¯8,0,0,¯4,¯4,0,0,0,0,0,0,40,40,¯16,¯16,¯8,¯8,0,0,
44,44,¯16,¯16,¯4,¯4,0,0
Шаг 2 1i , 2j
36X =36,36,¯16,¯16,¯8,¯8,0,0,¯4,¯4,0,0,0,0,0,0,40,40,¯16,¯16,¯8,¯8,0,0,
44,44,¯16,¯16,¯4,¯4,0,0,48,48,¯16,¯16
Шаг 3б 0i , 0j
24Y =0,0,0,0,0,0,0,0,8,7,6,5,4,3,2,1,0,0,0,8,¯2,¯2,¯2,¯2
Шаг 3в 0i , 0j
24Y =0,0,0,0,15,11,7,3,0,0,0,0,1,1,1,1,0,0,0,8,¯2,¯2,¯2,¯2
Терещенко А.Н., Задирака В.К.
«Искусственный интеллект» 3’201294
2Т
А
Продолж. табл. 6
Шаг 3б 1i , 0j
28Y =0,0,0,0,15,11,7,3,0,0,0,0,1,1,1,1,0,0,0,8,¯2,¯2,¯2,¯2,0,15,¯8,¯7
Шаг 3в 1i , 0j
28Y =0,0,26,10,0,0,4,4,0,0,0,0,1,1,1,1,0,0,0,8,¯2,¯2,¯2,¯2,0,15,¯8,¯7
Шаг 3б 1i , 1j
32Y =0,0,26,10,0,0,4,4,0,0,0,0,1,1,1,1,0,0,0,8,¯2,¯2,¯2,¯2,0,15,¯8,¯7,0,1,0,¯1
Шаг 3в 1i , 1j
32Y =0,0,26,10,0,0,4,4,0,0,2,2,0,0,0,0,0,0,0,8,¯2,¯2,¯2,¯2,0,15,¯8,¯7,0,1,0,¯1
Шаг 3б 1i , 2j
36Y =0,0,26,10,0,0,4,4,0,0,2,2,0,0,0,0,0,0,0,8,¯2,¯2,¯2,¯2,0,15,¯8,¯7,0,1,0,¯1,
0,¯2,0,2
Шаг 3в 1i , 2j
36Y =0,0,26,10,0,0,4,4,0,0,2,2,0,0,0,0,0,8,¯4,¯4,0,¯8,0,0,0,15,¯8,¯7,0,1,0,¯1,
0,¯2,0,2
Шаг 4
36Y =36,¯36,16,¯16,8,¯8,0,0,4,¯4,0,0,0,0,0,0,0,16,¯8,¯8,¯8,¯8,8,8,
0,30,¯16,¯14,0,2,0,¯2,0,¯4,0,4
Шаг 5
9XADD =52,¯8,¯4,0,56,¯8,60,¯4,64 9YADD =¯52,¯8,¯4,0,8,0,16,0,0
Шаг 6
36R =2592,¯2592,¯512,512,¯128,128,0,0,¯32,32,0,0,0,0,0,0,0,1280,256,256,
128,128,0,0,0,2640,512,448,0,¯16,0,0,0,¯384,0,¯128
Шаг 7
9RADD =¯2704,64,16,0,448,0,960,0,0
Шаг 8
36R =2592,112,¯512,¯2192,¯128,64,0,64,¯32,16,0,16,0,0,0,0,0,832,256,704,
128,128,0,0,0,1680,512,1408,0,¯16,0,0,0,¯384,0,¯128
Шаг 9б 0i
24R =2592,952,¯256,¯1488,¯128,¯776,¯256,¯640,¯32,8,0,16,0,8,0,0,
0,640,256,640,128,320,0,64
Шаг 9б 1i
16R =2592,1272,¯128,¯1168,¯64,¯616,¯256,¯608,¯32,¯312,¯128,¯304,¯64,
¯152,0,¯32
Шаг 10
16R =0,64,112,145,164,170,164,147,120,84,56,35,20,10,4,1.8
Примечание 8. Результат вычисления свертки, взятый в обратном порядке, равен
произведению двух восьмиразрядных чисел, равных (1,2,3,4,5,6,7,8). Входные пара-
метры длины 2N могут быть преобразованы несложным образом так, что результат
циклической свертки длины N будет равен произведению двух восьмиразрядных чи-
сел [3]. Программная реализация (xx3fwalsh6u5g) алгоритма вычисления циклической
свертки на языке программирования APL занимает одну страницу.
Вывод
Рассмотрен новый алгоритм вычисления циклической свертки длины 2nN на
основе быстрого преобразования Уолша (БПУ) для параллельной модели вычислений
(SIMD – Single Instruction Multiple Data). Показано, что данный алгоритм позволяет
уменьшить более чем в два раза число вычислений БПУ, что значительно уменьшает
общую сложность по числу операций сложения и вычитания по сравнению с [3].
В новом алгоритме применены следующие резервы оптимизации: БПУ в дополни-
тельных секциях не вычисляются, в результирующих секциях вычисляется только одно
ОБПУ длины 2nN (за счет оригинального использования свойства корректировки
сигнала длины M значениями сигнала длины 2M перед вычислением ОБПУ боль-
шего сигнала). Метод проиллюстрирован на реализации сверток длины 4 и 8 в общем
виде, приведена схема вычисления свертки длины 8. Приведен тестовый пошаговый
пример для вычисления циклической свертки длины 16N предложенным методом.
В виде лемм и теорем приведены оценки сложности по числу операций при парал-
лельном и последовательном вычислении.
Параллельный алгоритм вычисления циклической свертки
«Штучний інтелект» 3’2012 95
2Т
Литература
1. David A. Pitassi. Fast convolution using the Walsh transform / David A. Pitassi // Applications of Walsh
Functions, Proceeding. – 1971. – April. – P. 130-133.
2. Davis W.F. A class of efficient convolution algorithms / W.F. Davis // Applicat. Walsh Functions. – 1972. –
March. – P. 318-329.
3. Реализация операции умножения с использованием преобразования Уолша / А.Н. Терещенко, С.С. Мель-
никова, Л.А. Гнатив [и др.] // Проблемы управления и информатики. – 2010. – № 2. – С. 102-126.
4. Терещенко А.Н. Оптимизация метода Питасси вычисления свертки / А.Н. Терещенко // Искусст-
венный интеллект. – 2009. – № 1. – С. 204-212.
5. Задирака В.К. Анализ сложности алгоритма умножения сверхбольших чисел на основе коэффици-
ентов Уолша / В.К. Задирака, С.С. Мельникова // Кибернетика и системный анализ. – 2001. – № 6. –
С. 99-110.
6. Гнатив Л.А. Эффективные алгоритмы быстрых преобразований Уолша с различными системами упо-
рядочивания / Л.А. Гнатив, В.Е. Коссов // Методы и средства обработки информации в системах
реального времени. – Киев : Ин-т кибернетики им. В.М. Глушкова АН УССР, 1990. – С. 43-49.
Literatura
1. David A. Applications of Walsh Functions. 1971. Proceeding. P.130-133. April. 1971.
2. Davis W. F. Applicat. Walsh Functions.1972. March. P.318-329.
3. Tereshhenko A. N. Mezhdunarodnyj nauchno-tehnicheskij zhurnal Problemy upravlenija i informatiki.
2010. № 2. S. 102-126.
4. Tereshhenko A. N. Iskusstvennyj intellekt. 2009. №1. S. 204-212.
5. Zadiraka V. K. Kibernetika i sistemnyj analiz. 2001. № 6. S. 99-110.
6. Gnativ L.A. Metody i sredstva obrabotki informacii v sistemah real’nogo vremeni. Kiev: In-t kibernetiki
im. V.M. Glushkova AN USSR. 1990. S. 43-49.
RESUME
A.N. Tereshchenko, V.K. Zadiraka
Parallel Computation Algorithm for Convolution
There is a new computation algorithm for cyclic convolution of length N=2n based on
Fast Walsh transformation (FWT) in parallel model (SIMD – Single Instruction Multiple
Data). The total number of FWTs in new algorithm is reduced more than twofold that de-
creases the number of single precision additions and subtractions on sequential computati-
on. There are several applied optimizations: FWTs are not computed in additional sections,
there is only one FWT of length N=2n in resulting sections. The last optimization uses the
feature of pre-computational adjustment of multi-digit value of length M by multi-digit
value of length 2M to get the sum of FWTs both multi-digit values based on computation
of one FWT multi-digit value of length M .
In the article, the new method of several FWTs computation in parallel is described.
The computation scheme for convolution of length 8 is shown. The operator W on the
scheme is applied for both FWTs of length 4 and 8 at the same time on parallel computa-
tion.
The method of getting complexity of parallel computation based on complexity of
consequential computation is described. With use of this method, complexity of sequential
and parallel computations is shown.
Статья поступила в редакцию 31.05.2012.
|