УДК 519.681.5
М.С. ЯДЖАК,
Інститут прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України; Львівський національний університет імені Івана Франка, Львів, Україна,
yadzhak_ms@ukr.net
ПАРАЛЕЛЬНІ АЛГОРИТМИ ЦИФРОВОЇ ФІЛЬТРАЦІЇ ДАНИХ
Анотація. Запропоновано паралельні алгоритми розв’язання задач цифрової фільтрації різної розмірності на сучасних обчислювальних засобах універсального призначення. Одержано теоретичні оцінки складності та прискорення, які підтверджують високу ефективність цих алгоритмів. Здійснено програмну реалізацію деяких із запропонованих паралельних алгоритмів на комп’ютерах із багатоядерним процесором і одержано реальні оцінки прискорення, які добре узгоджуються із теоретичними.
Ключові слова: цифрова фільтрація, паралельний алгоритм, прискорення обчислень, обмежений паралелізм, еквівалентність алгоритмів, обчислювальна система.
повний текст
СПИСОК ЛІТЕРАТУРИ
- Тимченко О.В. Різницеві методи цифрової фільтрації. Львів: Фенікс, 1999. 388 с.
- Ярославский Л.П. Цифровая обработка сигналов в оптике и голографии. Введение в цифровую оптику. Москва: Радио и связь, 1987. 296 с.
- Anisimov A.V., Yadzhak M.S. Construction of optimal algorithms for mass computations in digital filtering problems. Cybernetics and Systems Analysis. 2008. Vol. 44, N 4. P. 465–476. https://doi.org/10.1007/s10559-008-9018-8.
- Yadzhak M.S., Tyutyunnyk M.I. An optimal algorithm to solve digital filtering problem with the use of adaptive smoothing. Cybernetics and Systems Analysis. 2013. Vol. 49, N 3. P. 449–456. https://doi.org/10.1007/s10559-013-9528-x .
- Каляев А.В., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. Москва: Янус-К, 2003. 380 с.
- Штейнберг Б.Я. Математические методы распараллеливания рекуррентных циклов для суперкомпьютеров с параллельной памятью. Ростов н/Д: Изд-во Рост. ун-та, 2004. 192 с.
- Jadzhak M.S. On construction of algorithms with the bounded parallelism for solving problems of digital filtering. Journal of Automation and Information Sciences. 2002. Vol. 34, N 12. P. 12–21. https://doi.org/10.1615/JAutomatInfScien.v34.i12.20.
- Яджак М.С. Аналіз реалізації алгоритмів з обмеженим паралелізмом для цифрової фільтрації. Відбір і обробка інформації. 2009. Вип. 30 (106). С. 162–167.
- Яджак М.С. Вирішення проблеми реалізації деяких паралельних алгоритмів цифрової фільтрації даних. Відбір і обробка інформації. 2011. Вип. 35 (111). С. 116–121.
- Valkovskii V.A. An optimal algorithm for solving the problem of digital filtering. Pattern Recognition and Image Analysis. 1994. Vol. 4, N 3. P. 241–247.
- Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход. Москва: Радио и связь, 1989. 176 с.
- Вальковський В.О., Яджак М.С. Проблеми подальшого розвитку та модифікації методу пірамід для розпаралелювання циклів. Математичні методи та фізико-механічні поля. 2000. Т. 43, № 1. С. 68–75.
- Valkovskiy V.A., Yadzhak M.S. The optimal solution algorithm for the two-dimensional problem of digital filtering. Journal of Automation and Information Sciences. 1999. Vol. 31, N 12. P. 72–80. https://doi.org/10.1615/JAutomatInfScien.v31.i12.90.
- Toub S. Patterns of parallel programming. Microsoft Corporation, 2010. 118 p.
- Файнзильберг Л.С. Адаптивное сглаживание шумов в информационных технологиях обработки физиологических сигналов. Математичні машини і системи. 2002. № 3. С. 96–104.
- Штейнберг Б.Я., Штейнберг О.Б. Преобразования программ — фундаментальная основа создания оптимизирующих распараллеливающих компиляторов. Программные системы: теория и приложения. 2021. Т. 12, № 1. С. 21–113. https://doi.org/10.25209/2079 -3316-2021-12-1-21-113.
