O. V. Klimova

AN OPTIMIZATION APPROACH TO THE DEVELOPMENT OF PARALLEL ALGORITHMS FOR DIGITAL SIGNAL PROCESSING OPERATIONS

The optimization possibilities of the approach, which made it possible to develop a formal tool - a model of computation organization for digital signal processing (DSP) operations and operations structurally similar to them are considered. The resulting formal tool describes the internal parameterized structure of operations and generates adaptive algorithms that can adjust to different conditions of parallel computation. The approach developed to the construction of such algorithms endows them with extended functionality, which ensures the implementation of the following capabilities: changes in the parameters of the algorithm structures; synthesis of their variety; optimization of variants of computation organization. Due to the variety of this functionality, several directions are identified for implementing this optimization. A general description of the optimization approach to the reasonable choice of the best variant of the computation organization under the given conditions of their implementation is given. We consider a scheme of actions aimed at computation optimization and enabling you to develop the various classes of parameterized parallel algorithms within the framework of the approach proposed.

Acknowledgments: The work was performed according to the state assignment on theme No. 122011100398-2

References:

1. Marchuk G.I., Kotov V.E. Problems of computers and fundamental research. Avtomatika i vychislitel'naya tekhnika, 1979, No. 2, pp. 3–14. (In Russian).
2. Voevodin V.V. Computational Mathematics and Algorithm Structure. Moscow, MGU Publ., 2006, 112 p. (In Russian).
3. Voevodin V.V., Voevodin Vl.V. Parallel Computing. St. Petersburg., BHV-Peterburg Publ., 2002, 608 p. (In Russian).
4. Kung S.Y. VLSI Array Processors, Englewood Cliffs, NJ, Prentice Hall, 1988.
5. Lee G.G., Chen Y.K., Mattavelli M., and Jang E.S. Algorithm/Architecture Co-Exploration of Visual Computing on Emergent Platforms: Overview and Future Prospects. In: IEEE Trans. Circuits and Systems for Video Technology, 2009, vol. 19 (11), pp. 1576–1587. DOI: 10.1109/TCSVT.2009.2031376.
6. Lee Gwo Giun, Lin He-Yuan, Chen Chun-Fu, and Huang Tsung-Yuan. Quantifying Intrinsic Parallelism Using Linear Algebra for Algorithm/Architecture Coexploration. In: IEEE Trans. on Parallel and Distributed Systems, 2012, vol. 23, iss. 5, pp. 944–957. DOI: 10.1109/TPDS.2011.230.
7. Malyshkin V., Perepelkin V. Trace-Based Optimization of Fragmented Programs Execution in LuNA System. In: PaCT 2021: Parallel Computing Technologies: Proceedings of 16th International Conference, PaCT 2021, Kaliningrad, Russia, September 13–18, 2021, Book Ser. Lecture Notes in Computer Science, Springer, 2021, vol. 12942. DOI: 10.1007/978-3-030-86359-3_1.
8. Lookin N.A. Digital image processing systems based on functional-oriented processors with a homogeneous structure. Journal of Physics: Conference Series, 2020, vol. 1680, pp. 012034. DOI: 10.1088/1742-6596/1680/1/012034.
9. Malyshkin V. Parallel computing technologies 2020. The Journal of Supercomputing, 2021. DOI: 10.1007/s11227-021-04014-w.
10. Akhmed-Zaki D., Lebedev D., Malyshkin V., Perepelkin V. Automated construction of high-performance distributed programs in LuNA system. In: Malyshkin, V., ed. International Conference on Parallel Computing Technologies, PaCT 2019: Parallel Computing Technologies, 2019, book ser. Lecture Notes in Computer Science (LNCS), Springer, 2019, vol. 11657, pp. 3–9, DOI: 10.1007/978-3-030-25636-4_1.
11. Gergel V., Grishagin V., Israfilov R. Parallel Dimensionality Reduction for Multiextremal Optimization Problems. In: Malyshkin V., ed. Parallel Computing Technologies: PaCT 2019, ser. Lecture Notes in Computer Science, Springer, 2019, vol 11657. DOI: 10.1007/978-3-030-25636-4_13.
12. Klimova O.V. A Methodology for Parallel Implementation of the Basic Operations of Digital Signal Processing. In: AIP Conference Proceedings, 2019, vol. 2176, 030023. DOI: 10.1063/1.5135131.
13. Edward A. Lee. The Problem with Threads. Computer, 2006, vol. 39. iss. 5. pp. 33–42. DOI: 10.1109/MC.2006.180.
14. Klimova O.V. Parallel computations and construction law of model description for digital signal processing algorithms. Informatsionnye Tekhnologii i Vychslitel'nye Sistemy, 2016, No. 2, pp. 11–22. (In Russian).
15. Nussbaumer H.J. Fast Fourier Transform and Convolution Algorithms, Berlin Heidelberg, Springer-Verlag, 1982.
16. McClellan J.H., Rader C.M. Primenenie teorii chisel v tsifrovoy obrabotke signalov [Application of number theory in digital signal processing]. Moscow, Radio i Svyaz Publ., 1983, 264 p.
17. Klimova O.V. Pseudo-two-Dimensional Decomposition Methods and Parallel Algorithms of Convolution. In: International Workshop on Spectral Methods and Multirate Signal Processing, Tampere, Finland, TICSP Series, 2001.
18. Klimova O.V. Fast parallel algorithms and recursive pseudo-two-dimensional convolution decomposition. Vestnik Tomskogo gosydarstvennogo universiteta, 2002, No. 1 (II), pp. 227–232.

Article reference