Parallel methods and algorithms for solving problems of digital filtering of data arrays
Abstract
A quasisystolic computation method for solving digital filtering problems of various dimensions on specialized computing means – quasisystolic structures is proposed. This method makes it possible to build parallel-pipeline computation algorithms that are optimal in speed and memory usage. Based on the ideas of the pyramid method for parallelization of cycles, parallel algorithms with autonomous branches were built for solving filtering problems on clusters, hybrid architectures and computers with a multi-core processor. Theoretical speed-up estimates were obtained, which confirm the high efficiency of the constructed parallel filtering algorithms. For individual algorithms with autonomous branches, real speed-up estimates were obtained, which are in good agreement with the theoretical ones. The obtained results can be used for preliminary processing of large arrays of input data in various subject areas
References
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.
Copyright (c) 2023 Михайло Яджак (Автор)
This work is licensed under a Creative Commons Attribution 4.0 International License.
