Параллельный алгоритм вычисления циклической свертки
Предложена оптимизация алгоритма вычисления циклической свертки длины N=2ⁿ на основе быстрого преобразования Уолша (БПУ). Оптимизация заключается в использовании свойства предварительной корректировки сигнала длины M сигналом длины M/2 для получения суммарного результата БПУ двух сигналов на основе...
Saved in:
| Published in: | Штучний інтелект |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/57078 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Параллельный алгоритм вычисления циклической свертки / А.Н. Терещенко, В.К. Задирака // Штучний інтелект. — 2012. — № 3. — С. 79-95. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862553221040439296 |
|---|---|
| author | Терещенко, А.Н. Задирака, В.К. |
| author_facet | Терещенко, А.Н. Задирака, В.К. |
| citation_txt | Параллельный алгоритм вычисления циклической свертки / А.Н. Терещенко, В.К. Задирака // Штучний інтелект. — 2012. — № 3. — С. 79-95. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| 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.
|
| first_indexed | 2025-11-25T21:12:15Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-57078 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-11-25T21:12:15Z |
| publishDate | 2012 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| 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 |
| spellingShingle | Параллельный алгоритм вычисления циклической свертки Терещенко, А.Н. Задирака, В.К. Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| title | Параллельный алгоритм вычисления циклической свертки |
| title_alt | Паралельний алгоритм обчислення циклічної згортки Parallel Computation Algorithm of Convolution |
| title_full | Параллельный алгоритм вычисления циклической свертки |
| title_fullStr | Параллельный алгоритм вычисления циклической свертки |
| title_full_unstemmed | Параллельный алгоритм вычисления циклической свертки |
| title_short | Параллельный алгоритм вычисления циклической свертки |
| title_sort | параллельный алгоритм вычисления циклической свертки |
| topic | Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| topic_facet | Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/57078 |
| 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 |