Оптимізація паралельних алгоритмів цифрової фільтрації великих масивів даних

R. R. Vdovych, M. S. Yadzhak

Анотація


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

 

Зразок для цитування: Р. Р. Вдович, М. С. Яджак, “Оптимізація паралельних алгоритмів цифрової фільтрації великих масивів даних”, Прикл. проблеми механіки і математики, Вип. 23, 87–93 (2025), https://doi.org/10.15407/apmm2025.23.87-93


Ключові слова


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

Посилання


A. O. Azarova, I. V. Krak, L. O. Nikiforova, O. D. Azarov, K. S. Belyakova, "Applying system analysis and mathematical apparatus of fuzzy logic to model the process of evaluating the financial state of the enterprise," Kibern. Syst. Anal., 60, No. 6, 2024, 154–168 (in Ukrainian), https://doi.org/10.34229/KCA2522-9664.24.6.13; English translation: Cybern. Syst. Anal., 60, No. 6, 978-990 (2024), https://doi.org/10.1007/s10559-024-00734-y.

R. Vdovych, M. Yadzhak, "Analysis of the implementation of parallel algorithms for digital filtering of large arrays of distorted data," Fiz.-Mat. Model. Inform. Tekhnol., Issue 40, 47-52 (2025) (in Ukrainian), https://doi.org/10.15407/fmmit2025.40.047

S. S. Gasanov, A. V. Kulyk, V. V. Kulyk, "Systems analysis and modeling a multi-sectoral economy based on the input-output model (An example of Japanese economy)," Kibern. Syst. Anal., 59, No. 2, 2023, pp. 72–86 (in Ukrainian); English translation: Cybern. Syst. Anal., 59, No. 2, 238-250 (2023), https://doi.org/10.1007/s10559-023-00558-2.

M. V. Demydyuk, B. A. Lytwyn, "The problems of human gait mathematical modeling subject to biomechanical experimental data," Prykl. Probl. Mekh. Mat., Issue 10, 123-134 (2012) (in Ukrainian).

D. O. Polishchuk, Informational Technology for Complex Deterministic Evaluation of Complex Hierarchical Network Systems [in Ukrainian], Abstract of PhD dissertation, 05.13.06 - Informational Technologies, Ukrainian Printing Academy, Lviv (2017).

O. D. Polishchuk, M. S. Yadzhak, Models and Methods of Comprehensive Investigation of Complex Network Systems and Intersystem Interactions [in Ukrainian], Pidstryhach Institute of Applied Problems of Mechanics and Mathematics of NAS of Ukraine, Lviv (2023).

S. Skorobohatko, H. Fesenko, V. Kharchenko, S. Yakovlev, "Architecture and Reliability Models of Hybrid Sensor Networks for Environmental and Emergency Monitoring Systems," Kibern. Syst. Anal., 60, No. 2, 2024, 147-159 (in Ukrainian), https://doi.org/10.34229/KCA2522-9664.24.2.13; English translation: Cybern. Syst. Anal., 60, No. 2, 293-304 (2024), https://doi.org/10.1007/s10559-024-00670-x

O. V. Tymchenko, Difference Methods of Digital Filtering, Feniks, Lviv (1999).

M. I. Tyutyunnyk, Parallel Algorithms for Complex Evaluation of the State and Operation Quality of Complex Systems Functioning [in Ukrainian], Abstract of PhD dissertation, 01.05.03 - Mathematical and Software of Computational Machines and Systems, Taras Shevchenko National University of Kyiv, Kyiv (2020).

M. S. Yadzhak, "Modification of the pyramids method for loop parallelization: organizing exchanges between branches," Mat. Met. Fiz.-Mekh. Polya, 43, No. 4, 68-72 (2000).

M. S. Yadzhak, "Parallel algorithms for data digital filtering," Kibern. Syst. Anal., 59, No. 1, 2023, 46-56 (in Ukrainian); English translation: Cybern. Syst. Anal., 59, No. 1, 39-48 (2023), https://doi.org/10.1007/s10559-023-00540-y

M. M. Yatsymirskyy, The Fast Orthogonal Trigonometric Transform Algorithms [in Ukrainian], Academic Express LTD, Lviv (1997).

N. K. Cheryala, Systolic Arrays and the TPU. Academia Letters, Article 1403, 9 p. (2001), https://doi.org/10.20935/AL1403

M. O. Jackson, Social and Economic Networks, Princeton University Press, Princeton (2010), https://doi.org/10.2307/j.ctvcm4gh1

H. T. Kung, C. E. Leiserson, "Systolic arrays (for VLSI)," Sparse Matrix Proceedings 1978, Proc. Symposium on Sparse Matrix Computions, (Knoxville, 1978), SIAM, Philadelphia (1979), 256-282.

S. Osat, F. Radicchi, F. Papadopoulos, "k-core structure of real multiplex networks," Physical Review Research, 2, No. 2, Article 023176 (2020), https://doi.org/10.1103/PhysRevResearch.2.023176

M. Szell, S. Thurner, "Measuring social dynamics in a massive multiplayer online game," Social Networks, 32, No. 4, 313-329 (2010), https://doi.org/10.1016/j.socnet.2010.06.001

The List Top500 [Electronic resource], http://www.top500.org

L. D. Valdez, L. A. Braunstein, S. Havlin, "Epidemic spreading on modular networks: The fear to declare a pandemic," Phys. Rev. E, 101, No. 3, Article 032309 (2020), https://doi.org/10.1103/PhysRevE.101.032309

V. A. Valkovskii, “An optimal algorithm for solving the problem of digital filtering,” Pattern Recognit. Image Anal., Vol. 4, No. 3, 241–247 (1994).


Посилання

  • Поки немає зовнішніх посилань.


Creative Commons License
Ця робота ліцензована Creative Commons Attribution 3.0 License.