Швидке обчислення циклічної згортки багаторозрядних чисел на основі ШПФ у паралельній моделі обчислень

Аналізується складність за кількістю однослівних операцій при реалізації операції ЦЗ (циклічної згортки) у паралельній моделі обчислень. Розглянуто методи обчислення ЦЗ, коли кожна точка згортки є багаторозрядним числом. Запропоновано швидкий метод обчислення ЦЗ такого виду на основі ШПФ невеликої д...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2016
Автори:	Терещенко, А.М., Задірака, В.К.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут проблем штучного інтелекту МОН України та НАН України 2016
Назва видання:	Штучний інтелект
Теми:	Теорія та засоби обчислювального інтелекту
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/132054
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Швидке обчислення циклічної згортки багаторозрядних чисел на основі ШПФ у паралельній моделі обчислень / А.М. Терещенко, В.К. Задірака // Штучний інтелект. — 2016. — № 2. — С. 103-112. — Бібліогр.: 5 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-132054
record_format	dspace
spelling	irk-123456789-1320542018-04-11T03:03:32Z Швидке обчислення циклічної згортки багаторозрядних чисел на основі ШПФ у паралельній моделі обчислень Терещенко, А.М. Задірака, В.К. Теорія та засоби обчислювального інтелекту Аналізується складність за кількістю однослівних операцій при реалізації операції ЦЗ (циклічної згортки) у паралельній моделі обчислень. Розглянуто методи обчислення ЦЗ, коли кожна точка згортки є багаторозрядним числом. Запропоновано швидкий метод обчислення ЦЗ такого виду на основі ШПФ невеликої довжини. The complexity of number of single precision operations is analyzed in multidigit convolution computation in parallel computational model. Calculation methods of cyclic convolution elements are considered when every element is high precision value. The effective method based on FFT of small length of calculation of cyclic convolution is proposed. 2016 Article Швидке обчислення циклічної згортки багаторозрядних чисел на основі ШПФ у паралельній моделі обчислень / А.М. Терещенко, В.К. Задірака // Штучний інтелект. — 2016. — № 2. — С. 103-112. — Бібліогр.: 5 назв. — укр. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/132054 519.6 uk Штучний інтелект Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Теорія та засоби обчислювального інтелекту Теорія та засоби обчислювального інтелекту
spellingShingle	Теорія та засоби обчислювального інтелекту Теорія та засоби обчислювального інтелекту Терещенко, А.М. Задірака, В.К. Швидке обчислення циклічної згортки багаторозрядних чисел на основі ШПФ у паралельній моделі обчислень Штучний інтелект
description	Аналізується складність за кількістю однослівних операцій при реалізації операції ЦЗ (циклічної згортки) у паралельній моделі обчислень. Розглянуто методи обчислення ЦЗ, коли кожна точка згортки є багаторозрядним числом. Запропоновано швидкий метод обчислення ЦЗ такого виду на основі ШПФ невеликої довжини.
format	Article
author	Терещенко, А.М. Задірака, В.К.
author_facet	Терещенко, А.М. Задірака, В.К.
author_sort	Терещенко, А.М.
title	Швидке обчислення циклічної згортки багаторозрядних чисел на основі ШПФ у паралельній моделі обчислень
title_short	Швидке обчислення циклічної згортки багаторозрядних чисел на основі ШПФ у паралельній моделі обчислень
title_full	Швидке обчислення циклічної згортки багаторозрядних чисел на основі ШПФ у паралельній моделі обчислень
title_fullStr	Швидке обчислення циклічної згортки багаторозрядних чисел на основі ШПФ у паралельній моделі обчислень
title_full_unstemmed	Швидке обчислення циклічної згортки багаторозрядних чисел на основі ШПФ у паралельній моделі обчислень
title_sort	швидке обчислення циклічної згортки багаторозрядних чисел на основі шпф у паралельній моделі обчислень
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2016
topic_facet	Теорія та засоби обчислювального інтелекту
url	http://dspace.nbuv.gov.ua/handle/123456789/132054
citation_txt	Швидке обчислення циклічної згортки багаторозрядних чисел на основі ШПФ у паралельній моделі обчислень / А.М. Терещенко, В.К. Задірака // Штучний інтелект. — 2016. — № 2. — С. 103-112. — Бібліогр.: 5 назв. — укр.
series	Штучний інтелект
work_keys_str_mv	AT tereŝenkoam švidkeobčislennâciklíčnoízgortkibagatorozrâdnihčiselnaosnovíšpfuparalelʹníjmodelíobčislenʹ AT zadírakavk švidkeobčislennâciklíčnoízgortkibagatorozrâdnihčiselnaosnovíšpfuparalelʹníjmodelíobčislenʹ
first_indexed	2025-07-09T16:37:42Z
last_indexed	2025-07-09T16:37:42Z
_version_	1837188059351744512
fulltext	ISSN 1561-5359. Штучний інтелект, 2016, № 2 © А.М. Терещенко, В.К. Задірака 103 УДК 519.6 А.М. Терещенко, В.К. Задірака Інститут кібернетики ім. В.М. Глушкова НАН України, проспект Академіка Глушкова, 40, Київ, 03178 ШВИДКЕ ОБЧИСЛЕННЯ ЦИКЛІЧНОЇ ЗГОРТКИ БАГАТОРОЗРЯДНИХ ЧИСЕЛ НА ОСНОВІ ШПФ У ПАРАЛЕЛЬНІЙ МОДЕЛІ ОБЧИСЛЕНЬ A.M. Tereshchenko, V.K.Zadiraka VM Glushkov Institute of Cybernetics of NAS of Ukraine 40 Glushkov ave., Kyiv, Ukraine, 03187 FAST PROCEEDING OF CYCLIC CONVOLUTION OF MULTIDIGIT VALUES BASED ON FFT IN PARALLEL COMPUTATIONAL MODEL Аналізується складність за кількістю однослівних операцій при реалізації операції ЦЗ (циклічної згортки) у паралельній моделі обчислень. Розглянуто методи обчислення ЦЗ, коли кожна точка згортки є багаторозрядним числом. Запропоновано швидкий метод обчислення ЦЗ такого виду на основі ШПФ не- великої довжини. Ключові слова: багаторозрядне множення, паралельна модель обчислень, циклічна згортка, ШПФ. The complexity of number of single precision operations is analyzed in multidigit convolution computation in parallel computational model. Calculation methods of cyclic convolution elements are considered when every element is high precision value. The effective method based on FFT of small length of calculation of cyclic convolution is proposed. Key words: multidigit multiplication, parallel computational model, cyclic convolution, FFT. Вступ У багатьох задач цифрової обробки (ЦО) необхідно обчислювати циклічну згортку (ЦЗ). Деякі задачі ЦО можна звести до задачі обчислення ЦЗ. Оптимізації обчислення ЦЗ приділено багато уваги [1, 2]. При обчисленні згорток великої довжини (більше 1024 точок) з використанням звичайної арифметики з плаваючою комою оди- нарної (або подвійної) точності накопичується похибка заокруглення. Якщо похибка заокруглення є великою, то вона впливає на результат обчислення так, що результат обчислення втрачає достовірність [3]. Для уникнення похибки заокруглення, необхідно оперувати більшою кількістю розрядів у кожній операції. Використання операцій з більшою розрядністю значно уповільнює виконання багаторозрядної операції. Сучасні процесори дозволяють виконувати операції над числами, довжина яких не перевищує 64 біти (подвійна точність) на апаратному рівні. Роботи [4, 5] присвячені оптимізації обчислення ЦЗ, але з точністю операцій процесора. Для отримання більшої точності, необхідно використовувати спеціальну арифметику, реалізовану на програмному рівні. Окрім ЦО, згортка використовується для реалізації операцій багаторозрядної арифметики [3]. При реалізації криптографічних операцій найбільше навантаження лягає на операцію багаторозрядного множення. У роботах [4, 5] показано метод обчис- лення операції множення на основі ЦЗ. Найбільш швидкий метод реалізації багатороз- рядної операції множення базується на ШПФ (швидкому перетворенні Фур‘є). Метод множення «у стовпчик» є ефективним при множенні багаторозрядних чисел з кількістю слів 256M (де кожне слово має довжину у 32 біти). Метод ШПФ є ефективним, починаючи з 256M . Операція множення двох чисел довжиною 256M слів може бути реалізована на основі ШПФ довжиною 5122 M (метод Кулі-Туки). ISSN 1561-5359. Штучний інтелект, 2016, № 2 104 © А.М. Терещенко, В.К. Задірака При цьому треба враховувати, що при обчисленні ОШПФ (оберненого швидкого перетворення Фур‘є) необхідно виконувати ділення на 5122 M . При діленні на 512 відбувається зсув на 9512log2  бітів. В операціях одинарної точності (32 біта) мантиса займає 23 біти. Тобто, після ділення на 512 (або зсуву вправо на 9 бітів) залишається 92314  значущих бітів, що говорить про те, що на початку обчислень враховується тільки 7 значущих бітів, бо при кожному множенні довжина результату подвоюється, а кожне подальше додавання може збільшувати результат на один біт. Так, наприклад, при використанні 8 значущих бітів на початку обчислень після першого множення результат буде займати 16 значущих бітів. Якщо обчислення відбувається, наприклад, для обчислення ЦЗ довжиною 256 (8 бітів) точок, то після 8-ої ітерації ШПФ кількість заповнених значущих бітів буде більшою, ніж 24. При використанні операцій подвійної точності (64 біти) довжина мантиси складає 51 біт. Тобто, на початку обчислення ШПФ кількість значущих бітів не повинна перевищувати 2)951(21  при множенні 256-слівного числа на основі ШПФ довжиною 512. Зрозуміло, що при множенні чисел довжиною більшою, ніж 256 слів, кількість значущих бітів повинна бути меншою, ніж 21, для уникнення переповнення. Виходячи з попередніх міркувань, множення на основі ШПФ є найшвидшим методом, але існує апаратне обмеження довжини множників у 537621256  бітів, які можна перемножити на основі ШПФ, використовуючи операції подвійної точності. При реалізації множення чисел більших, ніж 5376 бітів, на основі ШПФ, мантиса повинна мати більше ніж 51 біт для уникнення переповнення. Виникає потреба використання арифметики з точністю, більшою ніж подвійна, яку необхідно реалізовувати програмно. На практиці це виглядає так, що багаторозрядне число ділиться на M секцій, де кожна секція займає більше ніж 128 бітів. Довжина ШПФ, на основі якої виконується обчислення, дорівнює числу секцій N . Можна використовувати різні методи обчислення для кожного «рівня». Один метод використовувати для реалізації багаторозрядної операції множення для M (множник з M секцій), а інший метод – для оперування розрядами для N (кожна секція складається з N слів, кожне з яких має 32 біти). Метод на основі ШПФ буде найефективнішим при довжинах, більших ніж 256 секцій (для рівня M ) та 256 слів (для рівня N ). Для довжин, менших ніж 256, для рівнів M та N метод на основі ШПФ програє методу множення «у стовпчик». Загальноприйнято, що ШПФ треба використовувати, коли довжина ШПФ перевищує 256 точок. У даній роботі показано, що використання ШПФ довжиною 16 є ефективним при обчисленні ЦЗ великих чисел. Запропонований метод дає меншу складність за кількістю однослівних операцій у порівнянні з методом «у стовпчик». Одним з методів прискорення обчислення багаторозрядних операцій є їх реалізація у паралельній моделі обчислення, окрім використання швидких методів, які є ефективними у своїх діапазонах довжин багаторозрядних чисел. Може здаватися, що при задіянні N паралельних процесорів, можна прискорити час виконання у N разів. Але, на практиці, це зовсім не так. По-перше, не всі методи можна розпаралелити. Так, деякі методи мають пов’язані кроки обчислення, коли наступний крок обчислення оснований на результаті попереднього і не може бути виконаний незалежно від інших кроків. По-друге, при більшій кількості задіяних процесорів необхідно враховувати більше обмежень. Так, наприклад, розмір кеш-пам’яті є постійним і збільшення кількості процесорів означає, що кожному процесору буде виділено менше кеш- пам‘яті. При розбитті процесорів у групи, необхідно виконувати синхронізацію між групами, що є дуже витратною операцією. При ще більшому збільшенні кількості ISSN 1561-5359. Штучний інтелект, 2016, № 2 © А.М. Терещенко, В.К. Задірака 105 процесорів необхідно враховувати, що кожен паралельний процесор потребує енергію. Далі у роботі багаторозрядними числами будемо називати числа, які займають більше ніж два слова у пам’яті комп’ютера. Великі цілі числа є багаторозрядними чис- лами. Далі у роботі використовується термін багаторозрядні числа без розділення на ве- ликі цілі числа та числа з плаваючою комою з великою мантисою. Отримані у роботі результати можуть бути використані як для оптимізації обчислень з великими цілими числами, так і для реалізації операцій для отримання більшої кількості розрядів після коми. Мета дослідження Метою даної роботі є знаходження швидкого алгоритму обчислення циклічної згортки багаторозрядних чисел у паралельній моделі обчислення. Швидкий алгоритм має бути ефективним, використовувати максимально кеш-пам’ять та векторні операції і задіяти невелику кількість паралельних процесорів для зменшення обсягу викори- стання електроенергії при реалізації у паралельній моделі обчислень. Для цього прове- дено аналіз складності реалізації операції циклічної згортки багаторозрядних чисел на основі двох методів реалізації багаторозрядної операції множення: множення «у стовпчик» та на основі ШПФ. Досліджено область диференційованої поведінки алго- ритмів на основі двох методів. Показано, що запропонований метод на основі ШПФ невеликої довжини є ефективним для умов, коли багаторозрядне число займає не менше восьми слів. Постановка задачі Нехай багаторозрядні числа iX , iY , 1,0  Mi складаються з M секцій. Кожна i секція є N -слівним числом, у свою чергу, де кожне число має довжину у  -біт. Необхідно побудувати швидкий алгоритм обчислення циклічної згортки довжиною M секцій, де кожна секція є N -слівним числом, у паралельній моделі обчислень:     1 0 )( M i jiij M YXR , 1,0  Mj , (1) де jR – N2 -слівне число. Наприклад, обчислення ЦЗ 444 YXR  довжиною 4M розрядів можна представити у наступному вигляді: 3210 21033 10322 03211 32100 RRRR YYYYX YYYYX YYYYX YYYYX Рис. 1. Обчислення ЦЗ довжиною у 4 точки Вираз (1) може бути обчислений, використовуючи метод «у стовпчик» при реалізації багаторозрядної операції множення. Розглянемо складність такої реалізації у паралельній моделі обчислень. еалізація на основі множення «у стовпчик» Знайдемо спочатку складність алгоритму множення двох N -слівних чисел YX  стандартним методом «у стовпчик». Для спрощення у наступному алгоритмі (і далі по тексту) вважаємо, що знак переносу у 12 N слово не виникає. Множення «у стовпчик» двох N -слівних чисел YX  можна представити у вигляді наступної ISSN 1561-5359. Штучний інтелект, 2016, № 2 106 © А.М. Терещенко, В.К. Задірака формули:     12 0 )2( N k k krR  ,                       Nkyx Nkyx r N Nkt tkt k t tkk k 1 1 0 )( )( , де R - N2 -слівне число. Використаємо наступні позначення: 01 )(,)( sSLsSH  – знаходження старшої та молодшої частин двослівного числа 01 2 ssS   . Алгоритм 1. Множення N -слівних чисел YX  стандартним методом «у стовпчик» при задіянні N -паралельних процесорів без врахування знаків переносу. На вході:     1 0 )2( N k k kxX  ,     1 0 )2( N k k kyY  , p – індекс процесора. На виході:     12 0 )2( N k k krR  – результат множення YX  . Крок 1. 0122  pp rr . // Ініціалізація Крок 2. Для 0k по 1N Крок 3. kp yxSS  // Множення Крок 4. )(SLrr kpkp   , )(11 SHrr kpkp   . // Додавання Крок 5. Кінець циклу по k . Примітка. Алгоритм 1 не є оптимальним за кількістю операцію запису у пам’ять. Головною метою Алгоритму 1 є представлення загальної кількості операцій, необхідних для реалізації багаторозрядної операції. Лема 1. В Алгоритмі 1 при множенні двох N -слівних чисел стандартним методом «у стовпчик» кожен з N паралельних процесорів виконає N однослівних операцій множення та N2 однослівних операцій додавання. Доведення. На кроках 2-5 необхідно виконати N ітерацій циклу. З врахуванням того, що результатом множення двох однослівних чисел є двослівне число, необхідно виконати у два рази більшу кількість однослівних операцій додавання. Лема доведена. Далі розглянемо алгоритм, який обчислює циклічну згортку (1), при задіянні MN паралельних процесорів. Алгоритм знаходить суми добутків N -слівних чисел Mjii YX  , 1,0  Mi , 1,0  Mj , на основі стандартного методу множення «у стовпчик». Алгоритм 2. Знаходження суми добутків N -слівних чисел на основі методу множення «у стовпчик» при задіянні MN паралельних процесорів без врахування знаків переносу. На вході: iX , iY , 1,0  Mi ; 1,0  Mj – індекси ряду та стовпчика групи процесорів, яку можна інтерпретувати у вигляді матриці. На виході:     1 0 )( M i jiij M YXR , 1,0  Mj . ISSN 1561-5359. Штучний інтелект, 2016, № 2 © А.М. Терещенко, В.К. Задірака 107 Крок 1. 0jR . // Ініціалізація Крок 2. Для 0i по 1M Крок 3. Mjiijj YXRR  . // N -слівне множення Крок 4. Кінець циклу по i . // на основі Алгоритму 1 Лема 2. В Алгоритмі 2 при знаходженні сум множень N -слівних чисел на основі методу множення «у стовпчик» кожен з MN паралельних процесорів виконає MN однослівних операцій множення та MN2 однослівних операцій додавання. Доведення. Згідно з Лемою 1 при множення двох N -слівних чисел необхідно виконати N однослівних операцій множень та N2 однослівних операцій додавання. Таких ітерацій необхідно виконати M . Лема доведена. Реалізація на основі ШПФ У даній роботі пропонується обчислювати ЦЗ (1) великих чисел, використовуючи метод множення на основі ШПФ, у паралельній моделі обчислень. Розглянемо алгоритм множення N -слівних чисел YX  на основі ШПФ довжини N2 . Обчислення на основі ШПФ можна представити наступним чином: ))),(()),((( 2 1 2,22,2 * 2,2 ZYWZXWW N YXR NNNNNN  , (2) де NNW 2,2 та * 2,2 NNW ˗ матриці ДПФ та ОДПФ, які складаються з елементів rk N i rk N eW N   2 2 2 2  , 12,0,  Nrk ; Z складається з N нульових слів. Лема 3. При множенні двох N -слівних чисел на основі ШПФ довжиною N2 кожен з N паралельних процесорів виконає N2log32 2 комплексних однослівних операцій множення та N2log62 2 комплексних однослівних операцій додавання/віднімання. Доведення. У (2), для виконання одного ШПФ(ОШПФ) довжиною N2 , необхідно виконати N2log2 ітерацій ШПФ. На кожній ітерації «метелика»1 виконується N комплексних множень, результати яких додаються/віднімаються до/з N2 комплексних елементів. Загалом, кожен паралельний процесор виконає N2log2 комплексних операцій множення та N2log2 2 комплексних операцій додавання/віднімання при обчисленні одного ШПФ (ОШПФ). Усього необхідно виконати два ШПФ та одне ОШПФ. Також, кожному з N процесорів необхідно виконати додатково по дві поелементні комплексні операції множення. Лема доведена. Представимо (1) для 0j у наступному вигляді з врахуванням (2):      1 0 2,22,2 * 2,20 )))),(()),((( 2 1( M i iNNiNNNNj ZYWZXWW N R . У попередньому виразі множник * 2,22 1 NNW N  , що відповідає операції ОШПФ, можна винести за знак суми, що значно спрощує обчислення. 1 «Метелик» – стандартна операція алгоритму ШПФ. ISSN 1561-5359. Штучний інтелект, 2016, № 2 108 © А.М. Терещенко, В.К. Задірака      1 0 2,22,2 * 2,20 ))),(()),((( 2 1 M i iNNiNNNNj ZYWZXWW N R . (3) Окрім (3), можна отримати ще більше спрощення при реалізації операції багаторозрядного множення на основі ШПФ при обчисленні (1), якщо передобчислити всі ДПФ jX̂ , jŶ , 1,0  Mj . Використовуючи передобчислені ДПФ jX̂ , jŶ , 1,0  Mj , можна швидко знайти суми добутків ДПФ     1 0 )ˆˆ(ˆ M i jiij M YXR , 1,0  Mj , а потім на їх основі обчислювати елементи ЦЗ jNNj RW N R ˆ 2 1 * 2,2  , 1,0  Mj . На прикладі обчислення ЦЗ довжини чотири, пропонується одним з кроків виконувати наступне обчислення: 3210 21033 10322 03211 32100 ˆˆˆˆ ˆˆˆˆˆ ˆˆˆˆˆ ˆˆˆˆˆ ˆˆˆˆˆ RRRR YYYYX YYYYX YYYYX YYYYX Рис. 2. Обчислення ДПФ елементів ЦЗ довжиною у 4 точки На рис. 2 0X̂ , 1X̂ , 2X̂ , 3X̂ , 0̂Y , 1̂Y , 2̂Y , 3̂Y , 0R̂ , 1R̂ , 2R̂ , 3R̂ є ДПФ відповідних елементів ЦЗ 0X , 1X , 2X , 3X , 0Y , 1Y , 2Y , 3Y , 0R , 1R , 2R , 3R (див. рис. 1). У кожному стовпчику елементи 0̂Y , 1̂Y , 2̂Y , 3̂Y циклічно повторюються. Тому замість 16 ШПФ, у яких використовуються 0̂Y , 1̂Y , 2̂Y , 3̂Y , їх достатньо передобчилити 1 раз. Таким чином, для обчислення ЦЗ (1) довжини 4 (рис. 1) на основі ШПФ (рис. 2) необхідно передобчислити 8 ДПФ jX̂ , jŶ , 3,0j , та обчислити 4 ОШПФ jNNj RW N R ˆ 2 1 * 2,2  , 3,0j . Загалом, необхідно виконати 12 ШПФ(ОШПФ) замість 32 ШПФ (16 багаторозрядних множень) та 4 ОШПФ. Розглянемо загальний випадок, коли необхідно обчислити M сум, у яких використовуються iX , MjiY  , 1,0  Mi , 1,0  Mj :     1 0 2,22,2 * 2,2 ))),(()),((( 2 1 M i jiNNiNNNNj ZYWZXWW N R M , 1,0  Mj . (4) Лема 4. При знаходженні сум (4) співмножників N -слівних чисел на основі ШПФ довжини N2 , кожен з MN паралельних процесорів виконає NM 2log32 2 комплексних однослівних операцій множення та NM 2log232 2 комплексних однослівних операцій додавання/віднімання у послідовній моделі обчислень. Доведення. У (4) необхідно передобчислити M2 ШПФ для iX , iY , 1,0  Mi , та обчислити M ОШПФ довжини N2 . Згідно з Лемою 3, при задіянні процесорів, ISSN 1561-5359. Штучний інтелект, 2016, № 2 © А.М. Терещенко, В.К. Задірака 109 кожен з процесорів N при обчисленні одного ШПФ (ОШПФ) виконає N2log2 комплексних операцій множення та N2log2 2 комплексних операцій додаван- ня/віднімання. Також, кожен з N процесорів виконає додатково по два поелементних комплексних множення при реалізації багаторозрядної операції множення на основі ШПФ. Таких додаткових обчислень необхідно виконати M . Лема доведена. Порівняння методів Далі порівняємо складності обчислення ЦЗ (1) за кількістю однослівних операцій при реалізації багаторозрядної операції множення на основі методу множення «у стовпчик» (Лема 2) з реалізацією (4) на основі ШПФ (Лема 4) для одного процесора в багатопроцесорній моделі обчислень. Знайдемо агреговані коефіцієнти кількості операцій додавання/віднімання та множення. Агрегований коефіцієнт для Леми 4 може бути виражений наступним чином: )),(),(2(2),(4),( 4 * 4 * 44 NMONMONMONMO  , (5) де ),(* 4 NMO , ),(4 NMO ˗ загальна кількість комплексних однослівних операцій множення та додавання/віднімання у Лемі 4. Коефіцієнт 4 у доданку ),(4 * 4 NMO та коефіцієнт 2 у доданку ),(2 * 4 NMO у співвідношенні (5) позначають, що для реалізації однієї операції множення над комплексними числами необхідно чотири однослівні операції множення над дійсними числами (алгоритм Винограда дозволяє це зробити за три операції) та дві комплексні операції додавання. Двійка перед скобками у доданку )),(),(2(2 4 * 4 NMONMO  означає, що комплексні числа мають дійсну та уявну частини, тому для їх реалізації необхідно використати у два рази більшу кількість операцій над дійсними числами. Вважаємо, що однослівні операції додавання та множення над дійсними числами займають однаковий час за швидкодією. Після розкриття дужок, отримуємо наступний вираз: ),(2),(8),( 444 * NMONMONMO  . Після використання Леми 4, отримаємо наступне співвідношення: )2log232(2)2log32(8),( 225 NMNMNMO  . Після спрощення, отримуємо наступний агрегований коефіцієнт: NMNMO 2log3620),( 24  . Агрегований коефіцієнт Леми 2 дорівнює MNNMO 3),(2  , вважаючи, що час виконання операцій множення та додавання/віднімання на сучасних комп’ютерах однаковий. Знайдемо умови, при яких запропонований метод на основі ШПФ (Лема 4) є більш ефективним, ніж метод, заснований на методі множення «у стовпчик» (Лема 2), тобто ),(),( 24 NMONMO  . NM MN NMO NMO k 2log3620 3 ),( ),( 2 42 4 2   . ISSN 1561-5359. Штучний інтелект, 2016, № 2 110 © А.М. Терещенко, В.К. Задірака Таблиця 1. Значення коефіцієнту прискорення ),(42 NMk N M 4 8 16 32 64 128 256 1 0,09375 0,14634 0,24000 0,40678 0,70588 1,24675 2,23256 2 0,16216 0,26087 0,43636 0,75000 1,31507 2,34146 4,21978 3 0,21429 0,35294 0,60000 1,04348 1,84615 3,31034 6,00000 4 0,25532 0,42857 0,73846 1,29730 2,31325 4,17391 7,60396 5 0,28846 0,49180 0,85714 1,51899 2,72727 4,94845 9,05660 6 0,31579 0,54545 0,96000 1,71429 3,09677 5,64706 10,37838 7 0,33871 0,59155 1,05000 1,88764 3,42857 6,28037 11,58621 8 0,35821 0,63158 1,12941 2,04255 3,72816 6,85714 12,69421 16 0,44860 0,82759 1,53600 2,86567 5,37063 10,10526 19,08075 32 0,51337 0,97959 1,87317 3,58879 6,88789 13,24138 25,49378 36 0,52174 1,00000 1,92000 3,69231 7,11111 13,71429 26,48276 37 0,52358 1,00452 1,93043 3,71548 7,16129 13,82101 26,70677 64 0,55331 1,07865 2,10411 4,10695 8,02089 15,67347 30,64339 128 0,57571 1,13609 2,24234 4,42651 8,73969 17,25843 34,08599 256 0,58761 1,16717 2,31849 4,60570 9,14966 18,17751 36,11462 512 0,59374 1,18336 2,35854 4,70084 9,36942 18,67477 37,22226 1024 0,59685 1,19162 2,37909 4,74990 9,48331 18,93374 37,80196 Аналізуючи табл. 1, бачимо, що при обчисленні циклічної згортки довжини M багаторозрядних чисел довжиною N слів, запропонований метод є ефективним, починаючи зі згорток, довжиною у 37M точок та багаторозрядних чисел з 8N (у 256832  бітів) слів на початку обчислень. Цікаво, що коефіцієнт прискорення у паралельній моделі повністю співпадає з коефіцієнтом прискорення у послідовній моделі за однакових умов (однакових M , N ). Зазвичай, коефіцієнти прискорення для різних моделей обчислень відрізняються. Висновок У даній роботі проаналізовано складність обчислення ЦЗ (циклічної згортки) багаторозрядних чисел за кількістю однослівних операцій (множення, додавання та віднімання) у паралельному модулі обчислень. На основі ЦЗ можна побудувати швидкий алгоритм багаторозрядної операції множення. Розглянуто два методи обчислення циклічної згортки з реалізацією багаторозрядної операції множення на основі множення «у стовпчик» та на основі ШПФ. Надано алгоритми реалізації операції множення на основі двох методів у паралельній моделі обчислень. Запропоновано швидкий метод на основі ШПФ, який дозволяє реалізувати обчислення циклічної згортки багаторозрядних чисел зі складністю, меншою, ніж складність на основі методу множення «у стовпчик». Розглянуто умови, при яких ШПФ є швидким. Показано, що використання ШПФ довжиною 16 є вже ефективним при обчисленні ЦЗ, починаючи з довжин згортки у 37 точок, де кожна точка є багаторозрядним числом у 8 слів (256 біт) на початку обчислень. Програмна реалізація на GPU (графічних прискорювачах) для ядра (паралельного процесора) на основі ШПФ довжиною 16 дозволяє виконати обчислення з використанням векторних операцій довжиною 16, що дозволяє будувати ще більш швидкі алгоритми. При реалізації алгоритму на основі ШПФ, знаки переносу між машинними словами необхідно враховувати тільки на етапі обчислення ОШПФ, що є перевагою, у ISSN 1561-5359. Штучний інтелект, 2016, № 2 © А.М. Терещенко, В.К. Задірака 111 порівнянні з реалізацією алгоритму на основі множення «у стовпчик», коли знаки переносу необхідно враховувати на всіх етапах обчислення ЦЗ багаторозрядних чисел. Це також дає перевагу при реалізації у паралельній моделі обчислень, де операції врахування знаку переносу можуть займати більший час, ніж всі інші операції загалом. Довжини багаторозрядних множників при реалізації множення на основі ШПФ обмежені довжиною машинного слова, яку може обробляти процесор за одну команду. Запропонований метод дозволяє будувати алгоритми множення ще більших багаторозрядних чисел на основі ШПФ, яка використовується для обчислення циклічної згортки, що саме реалізує багаторозрядну операцію множення у паралельній моделі обчислень. Література 1. David A. Pitassi. Fast convolution using the Walsh transform. – Applications of Walsh Functions, 1971, Proceeding, pp.130–133, April, 1971. 2. Davis W. F. A class of efficient convolution algorithms // Applicat. Walsh Functions. – 1972. – March. – pp.318–329. 3. Задірака В., Олексюк О. Комп′ютерна арифметика багаторозрядних чисел. – К.: Наук. думка, 2003. – 263 с. 4. Терещенко А. Н. Оптимизация метода Питасси вычисления свертки // Искусственный интеллект. – 2009. – № 1 – С. 204–212. 5. Терещенко А. Н., Мельникова С. С., Гнатив Л. А., Задирака В. К., Кошкина Н. В. Реализация операции умножения с использованием преобразования Уолша // Международный научно- технический журнал Проблемы управления и информатики. – 2010. – № 2. – С. 102–126. Literatura 1. David A. Pitassi. Fast convolution using the Walsh transform. – Applications of Walsh Functions, 1971, Proceeding, pp.130–133, April, 1971. 2. Davis W. F. A class of efficient convolution algorithms // Applicat. Walsh Functions. – 1972. – March. – pp.318–329. 3. Zadiraka V., Oleksyk О. Multidigit computational arithmetic. – К.: Science opinion, 2003. – 263 p. 4. Tereshchenko A. N. Optimization of Pitassi method of convolution calculation // Artificial intellect. – 2009. – N 1 – P. 204–212. 5. Tereshchenko А. N., Melnikova S. S., Hnatyv L. A., Zadiraka V. K., Koshkina N. V. Calculation of multiplication, using walsh transform // Journal of automation and information sciences. – 2010. – N 2. – P. 102–126. RESUME A.M. Tereshchenko, V.K.Zadiraka Fast proceeding of cyclic convolution of multidigit values based on FFT in parallel computational model In this paper the complexity of calculation of the circular convolution of multidigit values in terms of single precision operations (multiplication, addition and subtraction) in parallel computational model is analyzed. Based on the circular convolution the fast algorithm of multidigit multiplication could be built. Two circular convolution calculation methods with the implementation of multidigit multiplication based on multiplication "in the column" and based on FFT e considered. Provided algorithms implement multidigit multiplication operation based on two methods in parallel computational model. A rapid method based on FFT calculation allows implementing the calculation of cyclic convolution of multidigit values with complexity less than complexity of method based on multiplication "in the column." The conditions under which the FFT is fast are considered. It is shown that using FFT length of 16 is effective in calculating circular convolution starting from the length of 37 points, where each point is a multidigit value of the length of 8 words (256 bits) in the beginning of computation. Software implementation on GPU based on FFT length of 16 allows using GPU vector operations of the length of 16 that speeds up algorithm sharply. ISSN 1561-5359. Штучний інтелект, 2016, № 2 112 © А.М. Терещенко, В.К. Задірака On implementing the algorithm based on FFT the carry flag between machine words is taken into account only at the stage of calculating IFFT, which is an advantage compared to the algorithm based on multiplication "in the column" when the carry flag is considered at all stages of computation. It also gives advantage of implementing on parallel computational model when operation for taking care of carry flag may take more time than all the other operations in general. The lengths of multidigit multipliers in the implementation of multiplication based on FFT limited by the length of the machine word processor that can process in a single command. The proposed method broadens this restriction and allows building algorithms based on FFT for much bigger numbers. Надійшла до редакції 04.09.2016

Швидке обчислення циклічної згортки багаторозрядних чисел на основі ШПФ у паралельній моделі обчислень

Репозитарії

Схожі ресурси