C&SA | Contents

Volume 59 >>> № 1 JANUARY — FEBRUARY 2023

-->

UDC 519.681.5

M.S. Yadzhak¹

¹ Pidstryhach Institute for Applied Problems of Mechanics and Mathematics, National Academy of Sciences of Ukraine, and Ivan Franko National University of Lviv, Lviv, Ukraine

yadzhak_ms@ukr.net

PARALLEL ALGORITHMS OF DIGITAL DATA FILTERING

Abstract. The paper proposes parallel algorithms for solving digital filtering problems of different dimensions using modern universal computing systems. Theoretical estimates of the complexity and speed-up are obtained, which confirm the high efficiency of these algorithms. The software implementation of some of the proposed parallel algorithms using computers with a multi-core processor is carried out, and real estimates of the speed-up are obtained, which agree well with the theoretical ones.

Keywords: digital filtering, parallel algorithm, speed up of computations, limited parallelism, equivalence of algorithms, computing system.

full text

REFERENCES

Tymchenko O.V. Different methods of digital filtering [in Ukrainian]. Lviv: Phoenix, 1999. 388 p.

Yaroslavsky L.P. Digital signal processing in optics and holography. Introduction to digital optics [in Russian]. Moscow: Radio i svyaz', 1987. 296 p.

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 .

Kalyaev A.V., Levin I.I. Modular-scalable multiprocessor systems with structural and procedural organization of calculations [in Russian]. Moscow: Janus-K, 2003. 380 p.

Steinberg B.Ya. Mathematical methods of parallelization of recurrent loops for supercomputers with parallel memory [in Russian]. Rostov on Don: Publishing house Rost. university, 2004. 192 p.

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.

Jadzhak M.S. Analysis of implementation of algorithms with limited parallelism for digital filtering. Vidbir i obrobka informatsiyi. 2009. Iss. 30 (106). P. 162–167.

Jadzhak M.S. Solving the problem of implementing some parallel digital data filtering algorithms. Vidbir i obrobka informatsiyi. 2011. Iss. 35 (111). P. 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.

Valkovskii V.A. Parallelization of algorithms and programs. Structural approach [in Russian]. Moscow: Radio i svyaz', 1989. 176 p.

Valkovskii V.O., Jadzhak M.S. Problems of further development and modification of the pyramid method for cycle parallelization. Mathematical methods and physical and mechanical fields. 2000. Vol. 43, N 1. P. 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.

Fainzilberg L.S. Adaptive noise smoothing in information technologies for processing physiological signals. Mathematical machines and systems. 2002. N 3. P. 96–104.

Steinberg B.Ya., Steinberg O.B. Program transformations are the fundamental basis for creating optimizing parallelizing compilers. Software systems: Theory and applications. 2021. Vol. 12, N 1. P. 21–113. https://doi.org/10.25209/2079 -3316-2021-12-1-21-113.