An Optimization Approach to the Development of Parallel Algorithms for Digital Signal Processing Operations

O. V. Klimova

doi:10.17804/2410-9908.2022.1.006-015

O. V. Klimova

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

DOI: 10.17804/2410-9908.2022.1.006-015

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.

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

Keywords: optimization approach, decomposition, internal structure of algorithms, composition form, model description

References:

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).
Voevodin V.V. Computational Mathematics and Algorithm Structure. Moscow, MGU Publ., 2006, 112 p. (In Russian).
Voevodin V.V., Voevodin Vl.V. Parallel Computing. St. Petersburg., BHV-Peterburg Publ., 2002, 608 p. (In Russian).
Kung S.Y. VLSI Array Processors, Englewood Cliffs, NJ, Prentice Hall, 1988.
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.
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.
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.
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.
Malyshkin V. Parallel computing technologies 2020. The Journal of Supercomputing, 2021. DOI: 10.1007/s11227-021-04014-w.
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.
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.
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.
Edward A. Lee. The Problem with Threads. Computer, 2006, vol. 39. iss. 5. pp. 33–42. DOI: 10.1109/MC.2006.180.
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).
Nussbaumer H.J. Fast Fourier Transform and Convolution Algorithms, Berlin Heidelberg, Springer-Verlag, 1982.
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.
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.
Klimova O.V. Fast parallel algorithms and recursive pseudo-two-dimensional convolution decomposition. Vestnik Tomskogo gosydarstvennogo universiteta, 2002, No. 1 (II), pp. 227–232.

О. В. Климова

ОПТИМИЗАЦИОННЫЙ ПОДХОД К РАЗРАБОТКЕ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ДЛЯ ОПЕРАЦИЙ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ

Рассмотрены оптимизационные возможности подхода, позволившего разработать формальный инструмент – модель организации вычислений для операций цифровой обработки сигналов (ЦОС) и операций структурно им подобных. Созданный формальный инструмент описывает внутреннюю параметризованную структуру операций и порождает адаптивные алгоритмы, способные настраиваться на различные режимы параллельных вычислений. Разработанный подход к построению таких алгоритмов наделяет их расширенной функциональностью, обеспечивающей реализацию следующих возможностей: изменения по параметрам структур алгоритмов; синтеза их разнообразия; оптимизации вариантов организации вычислений. Благодаря разнообразию функциональности определяются несколько направлений для реализации такой оптимизации. Приведено общее описание оптимизационного подхода к обоснованному выбору наилучшего в заданных условиях реализации варианта организации вычислений, а также рассмотрена схема действий, направленных на оптимизацию вычислений и позволяющих разработать различные классы параметризованных параллельных алгоритмов в рамках предложенного подхода.

Благодарность: Работа выполнена в соответствии с государственным заданием по теме № 122011100398-2.

Ключевые слова: оптимизационный подход, декомпозиция, внутренняя структура алгоритмов, композиционная форма, модельное описание

Библиография:

Марчук Г. И., Котов В. Е. Проблемы вычислительной техники и фундаментальные исследования // Автоматика и вычислительная техника. – 1979. – № 2. – С. 3–14.
Воеводин В. В. Вычислительная математика и структура алгоритмов. - М. : Изд-во МГУ, 2006. – 112 с.
Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. - СПб. : БХВ–Петербург, 2002. – 608 с.
Kung S. Y.VLSI Array Processors. – Englewood Cliffs, NJ : Prentice Hall, 1988.
Algorithm/Architecture Co-Exploration of Visual Computing on Emergent Platforms: Overview and Future Prospects / G. G. Lee, Y. K. Chen, M. Mattavelli, and E. S. Jang // IEEE Trans. Circuits and Systems for Video Technology : proceedings. – 2009. – Vol. 19 (11). – P. 1576–1587. – DOI: 10.1109/TCSVT.2009.2031376.
Quantifying Intrinsic Parallelism Using Linear Algebra for Algorithm/Architecture Coexploration / Gwo Giun Lee, He-Yuan Lin, Chun-Fu Chen, and Tsung-Yuan Huang. // IEEE Trans. on Parallel and Distributed Systems. – 2012. – Vol. 23, No. 5. – P. 944–957. – DOI: 10.1109/TPDS.2011.230.
Malyshkin V., Perepelkin V. Trace-Based Optimization of Fragmented Programs Execution in LuNA System // Parallel Computing Technologies PaCT 2021 : proceedings / ed. by V. Malyshkin. – Springer, 2021. – Series Lecture Notes in Computer Science. – Vol 12942. – DOI: 10.1007/978-3-030-86359-3_1.
Lookin N. A. Digital image processing systems based on functional-oriented processors with a homogeneous structure // Journal of Physics: Conference Series. – 2020. – Vol. 1680. – 012034. – DOI: 10.1088/1742-6596/1680/1/012034.
Malyshkin V. Parallel computing technologies 2020 // J Supercomput. – 2021. – DOI: 10.1007/s11227-021-04014-w.
Automated construction of high performance distributed programs in LuNA system / -Zaki D. Akhmed, D. Lebedev, V. Malyshkin, V. Perepelkin // International Conference on Parallel Computing Technologies, PaCT 2019: Parallel Computing Technologies, 2019 : Proceedings / ed. by V. Malyshkin. – Springer, 2019. – Series Lecture Notes in Computer Science (LNCS). – Vol. 11657. – P. 3–9. – DOI: 10.1007/978-3-030-25636-4_1.
Gergel V., Grishagin V., Israfilov R. Parallel Dimensionality Reduction for Multiextremal Optimization Problems // Parallel Computing Technologies. PaCT 2019 / ed. by V. Malyshkin. – Springer, 2019. – Series Lecture Notes in Computer Science. – Vol 11657. – DOI: 10.1007/978-3-030-25636-4_13.
Klimova O. V. A Methodology for Parallel Implementation of the Basic Operations of Digital Signal Processing // AIP Conference Proceedings. – 2019. – Vol. 2176. – 030023. – DOI: 10.1063/1.5135131.
Edward A. Lee. The Problem with Threads // Computer. – 2006. – Vol. 39, No. 5. – P. 33–42. – DOI: 10.1109/MC.2006.180.
Климова О. В. Параллельные вычисления и закон построения модельного описания для алгоритмов цифровой обработки сигналов // Информационные технологии и вычислительные системы. – 2016. – № 2. – С. 11–22.
Nussbaumer H. J. Fast Fourier Transform and Convolution Algorithms. – Berlin, Heidelberg : Springer–Verlag, 1982.
Макклеллан Дж. Г., Рейдер Ч. М. Применение теории чисел в цифровой обработке сигналов. – М. : Радио и связь, 1983. – 264 с.
Klimova O. V. Pseudo-two-Dimensional Decomposition Methods and Parallel Algorithms of Convolution // International Workshop on Spectral Methods and Multirate Signal Processing. – Tampere, Finland : TICSP Series, 2001.
Климова О. В. Быстрые параллельные алгоритмы и рекурсивная псевдодвумерная декомпозиция свертки // Вестник Томского государственного университета. – №1 (II). – Томск : Изд. ТГУ, 2002. – С. 227–232.

Библиографическая ссылка на статью

Klimova O. V. An Optimization Approach to the Development of Parallel Algorithms for Digital Signal Processing Operations // Diagnostics, Resource and Mechanics of materials and structures. - 2022. - Iss. 1. - P. 6-15. -
DOI: 10.17804/2410-9908.2022.1.006-015. -
URL: http://dream-journal.org/issues/2022-1/2022-1_351.html
(accessed: 30.12.2024).