Electronic Scientific Journal
 
Diagnostics, Resource and Mechanics 
         of materials and structures
Рус/Eng  

 

advanced search

IssuesAbout the JournalAuthorContactsNewsRegistration

2022 Issue 1

All Issues
 
2024 Issue 2
 
2024 Issue 1
 
2023 Issue 6
 
2023 Issue 5
 
2023 Issue 4
 
2023 Issue 3
 
2023 Issue 2
 
2023 Issue 1
 
2022 Issue 6
 
2022 Issue 5
 
2022 Issue 4
 
2022 Issue 3
 
2022 Issue 2
 
2022 Issue 1
 
2021 Issue 6
 
2021 Issue 5
 
2021 Issue 4
 
2021 Issue 3
 
2021 Issue 2
 
2021 Issue 1
 
2020 Issue 6
 
2020 Issue 5
 
2020 Issue 4
 
2020 Issue 3
 
2020 Issue 2
 
2020 Issue 1
 
2019 Issue 6
 
2019 Issue 5
 
2019 Issue 4
 
2019 Issue 3
 
2019 Issue 2
 
2019 Issue 1
 
2018 Issue 6
 
2018 Issue 5
 
2018 Issue 4
 
2018 Issue 3
 
2018 Issue 2
 
2018 Issue 1
 
2017 Issue 6
 
2017 Issue 5
 
2017 Issue 4
 
2017 Issue 3
 
2017 Issue 2
 
2017 Issue 1
 
2016 Issue 6
 
2016 Issue 5
 
2016 Issue 4
 
2016 Issue 3
 
2016 Issue 2
 
2016 Issue 1
 
2015 Issue 6
 
2015 Issue 5
 
2015 Issue 4
 
2015 Issue 3
 
2015 Issue 2
 
2015 Issue 1

 

 

 

 

 

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.

Acknowledgments: 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:

  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.


PDF      

Article reference

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://eng.dream-journal.org/issues/2022-1/2022-1_351.html
(accessed: 06/22/2024).

 

impact factor
RSCI 0.42

 

MRDMS 2024
Google Scholar


NLR

 

Founder:  Institute of Engineering Science, Russian Academy of Sciences (Ural Branch)
Chief Editor:  S.V. Smirnov
When citing, it is obligatory that you refer to the Journal. Reproduction in electronic or other periodicals without permission of the Editorial Board is prohibited. The materials published in the Journal may be used only for non-profit purposes.
Contacts  
 
Home E-mail 0+
 

ISSN 2410-9908 Registration SMI Эл № ФС77-57355 dated March 24, 2014 © IMACH of RAS (UB) 2014-2024, www.imach.uran.ru