Аннотация.

Предлагается формальное решение проблемы построения параллельных алгоритмов цифровой обработки сигналов, характеризующееся разработкой закона формирования модельного описания их внутренней структуры. Решение представляет теоретические основы для математического моделирования алгоритмов и открывает возможность проведения на формальной основе совместных исследований алгоритмов и архитектур перспективных вычислительных систем. Такой этап, являясь неотъемлемой частью процесса их проектирования, позволит повысить эффективность параллельной обработки данных.

Ключевые слова:

параллельная обработка, внутренняя структура алгоритмов, декомпозиция, параметризованный синтез алгоритмов, композиционная форма, модельное описание.

Стр. 13-24.

O.V. Klimova

"Parallel computations and construction law of model description for digital signal processing algorithms"

The formal solution of development problem of digital signal processing parallel algorithms is offered. The main content of solution presented is development of construction law of model description for algorithms. The study results of intrinsic algorithm structure are the basis of the solution. These results create the theoretical basis for mathematical modelling of algorithms. The development of the composition forms for description of intrinsic structure of operations defines the results. On the basis of the results the general construction law of model description of algorithms is formulated. The possibilities of the description are noted. The realization on formal basis of the concurrent optimization of both algorithms and architectures is one of the main possibilities. That coexploration of algorithms and architectures is integral part of design process of modern computation systems as its use at the design allows to raise efficiency of parallel processing.

Keywords: parallel processing, intrinsic algorithm structure, decomposition, parametrized synthesis of algorithms, composition form, model description. 

 Полная версия статьи в формате pdf.

 REFERENCES

1. Voevodin V.V. Vychislitelnaya matematika i struktura algoritmov. M.: Izd-vo MGU, 2006.
2. Voevodin V.V., Voevodin Vl.V. Parallelnye vychisleniya. SPb.: BKhV – Peterburg, 2002.
3. Kun S. Matrichnye protsessory na SBIS. M.: Mir,1991.
4. G.G. Lee, Y.K. Chen, M. Mattavelli, and E.S. Jang, Algorithm/Architecture Co-Exploration of Visual Computing: Overview and Future Perspectives // IEEE Trans. Circuits and Systems for Video Technology, vol. 19, no. 11, pp.1576-1587, Nov. 2009.
5. Gwo Giun (Chris) Lee, He-Yuan Lin, Chun-Fu Chen, and Tsung-Yuan Huang, Quantifying Intrinsic Parallelism Using Linear Algebra for Algorithm/Architecture Coexploration // IEEE Trans. on Parallel and Distributed Systems, vol. 23, no. 5, pp. 944–957, May 2012.
6. Virt N. Algoritmy+struktury dannykh = programmy. M.:Mir,1985.
7. Klimova O.V. Parallelnaya arkhitektura protsessora svertki proizvolnoy dliny s ispolzovaniem chislovykh preobrazovaniy Reydera // Izv. RAN. Tekhn. kibernetika. - 1994. - №2. – S. 183-191.
8. Klimova O.V. Teoretiko-gruppovaya dekompozitsiya i bystrye parallelnye algoritmy diskretnogo preobrazovaniya Fure. Izvestiya Akademii Nauk. Teoriya i Sistemy Upravleniya. 1997. №5. – S.158-162.
9. Klimova O.V. Yedinyy podkhod k postroeniyu bystrykh algoritmov i rasparallelivaniyu vychisleniy diskretnogo preobrazovaniya Fure // Izv. RAN. Teoriya i sistemy upravleniya. - 1999. - №3. – S. 68-75.
10. Klimova O. Decomposition on a Group and Parallel Convolution and Fast Fourier Transform Algorithms. Parallel Computing Technologies 4th International Conference,
PaCT-97. Proceedings, p.358-363 Springer-Verlag, Berlin, LNCS1277.
11. 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, June 2001.
12. Klimova O.V. Bystrye parallelnye algoritmy i rekursivnaya psevdodvumernaya dekompozitsiya svertki //Vestnik Tomskogo gosudarstvennogo universiteta. - №1 (II). - Tomsk: Izd. TGU, 2002. – S.227-232.
13. Klimova O.V. Metodologiya dekompozitsii dannykh i edinoe opisanie posledovatelnykh i parallelnykh algoritmov vychisleniya operatsiy tsifrovoy obrabotki signalov // Vestnik Tomskogo Gosudarstvennogo Universiteta. Upravlenie, vychislitelnaya tekhnika i informatika. 2013. № 2(23). S. 112-120.
14. Klimova O.V. Methodology of data decomposition and formal synthesis of composition forms for digital signal processing basic operations. 2014 24nd Int. Crimean Conference “Microwave & Telecommunication Technology” (CriMiCo’2014). Sevastopol, 2014, Crimea, Russia, V.1, pp. 429 -430. ISBN: 978-966-335-412-5. IEEE Catalog Number: CFP14788.
15. Edward A. Lee. The Problem with Threads // IEEE Computer, v. 39, № 5, pp. 33-42, may 2006.
16. Makklellan Dzh.G., Reyder Ch.M. Primenenie teorii chisel v tsifrovoy obrabotke signalov. - M.: Radio i svyaz, 1983. - 264 s.