Паралельні методи та алгоритми розв’язання задач цифрової фільтрації масивів даних

  • Михайло Яджак
Ключові слова: цифрова фільтрація, квазісистолічний метод, паралельноконвеєрний алгоритм, метод пірамід, розпаралелювання циклів, прискорення обчислень, автономні гілки, кластер

Анотація

Запропоновано квазісистолічний метод обчислень для розв’язання задач цифрової фільтрації різної розмірності на спеціалізованих обчислювальних засобах – квазісистолічних структурах. Цей метод дозволяє будувати оптимальні за швидкодією та використанням пам’яті паралельно-конвеєрні алгоритми обчислень. На основі ідей методу пірамід для розпаралелювання циклів побудовано паралельні алгоритми з автономними гілками для розв’язання задач фільтрації на кластерах, гібридних архітектурах та комп’ютерах з багатоядерним процесором. Одержано теоретичні оцінки прискорення, що підтверджують високу ефективність побудованих паралельних алгоритмів фільтрації. Для окремих алгоритмів з автономними гілками одержано реальні оцінки прискорення, які добре узгоджуються з теоретичними. Одержані результати можна використати для попереднього опрацювання великих масивів вхідних даних у різних предметних галузях.

Посилання

Polishchuk O. D., Yadzhak M. S. Merezhovi strukturi ta systemy: IV. Paralelne opratsiuvannia rezultativ neperevnoho monitoringu. Systemni doslidzhennia ta informatsiyni tekhnolohii. 2019. No. 2. S. 105-114. https://doi.org/10.20535/SRIT.2308-8893.2019.2.09

Kanevskyi Yu. S. Systolicheskie protsessory. Kyiv: Tekhnika, 1991. 173 s.

Valkovskii V. A. An optimal algorithm for solving the problem of digital filtering. Pattern Recognition and Image Analysis. 1994. Vol. 4, No. 3. P. 241-247.

Tymchenko O. V. Riznitsevi metody tsyfrovoi filtratsii. Lviv: Feniks, 1999. 388 s.

Anisimov A. V. and Yadzhak M. S. Construction of optimal algorithms for mass computations in digital filtering problems. Cybernetics and Systems Analysis. 2008. Vol. 44, No. 4. P. 465-476. https://doi.org/10.1007/s10559-008-9018-8

Yadzhak M. S. Visokoparalelni alhorytmy ta zasoby dlia rozv'yazannia zadach masovykh arifmetychnykh i lohichnykh obchyslen. Avtoref. dys. ... d. f.-m. n.: spetsialnist 01.05.03 - matematychne ta prohramne zabezpechennia obchysliuvalnykh mashyn i system. Kyiv: KNU imeni Tarasa Shevchenka, 2009.

Yadzhak M. S. Deiaki paralelni alhorytmy rozv'yazannia zadach tsyfrovoi filtratsii. Materialy VIII mizhnar. nauk.-prakt. konf. "Matematyka v suchasnomu tekhnichnomu universyteti", Kyiv, 27-28 hrudnia 2019 r. Vinnytsia: Vydavets FOP Kushnir Yu. V., 2020. S. 172-176.

Valkovskii V. A. Rasparallelivanie alhorytmov i programm. Strukturnyi podkhod. M.: Radio i sviaz, 1989. 176 s.

Yadzhak M. S., Tiutiunnik M. I., Bekas B. O. Aparatni zasoby realizatsii paralelno-konveiernykh alhorytmiv tsyfrovoi filtratsii z vykorystanniam adaptivnoho zhladzhuvannia. Naukovyi visnyk NLTU Ukrainy. 2014. Vyp. 24.6. S. 335-344.

Tiutiunnik M. I. Paralelni alhorytmy kompleksnoho otsiniuvannia stanu ta yakosti funktsionuvannia skladnykh system. Avtoref. dys. ... k. t. n.: spetsialnist 01.05.03 - matematychne ta prohramne zabezpechennia obchysliuvalnykh mashyn i system. Kyiv

Вальковський В. О., Яджак М. С. Проблеми подальшого розвитку та модифікації методу пірамід для розпаралелювання циклів. Математичні методи та фізико-механічні поля. 2000. 43, № 1. С. 68-75.

Попов О. В., Рудич О. В. До розв'язування систем лінійних рівнянь на комп'ютерах гібридної архітектури. Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. праць. 2017. Вип. 15. С. 158-164.

Опубліковано
2023-03-15