Decomposition approach to the construction of parallel algorithms for processing of two-dimensional data | Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitelnaja tehnika i informatika – Tomsk State University Journal of Control and Computer Science. 2020. № 52. DOI: 10.17223/19988605/52/14

Decomposition approach to the construction of parallel algorithms for processing of two-dimensional data

A way of constructing parallel algorithms for processing two-dimensional data (two-dimensional convolution and correlation, two-dimensional discrete Fourier transform (DFT) and other structurally similar operations) is considered. The proposed path is characterized by the use of a decomposition approach and the formation of compositional forms designed to describe parallel computations. New possibilities are presented, which open when these forms are used to implement computations of two-dimensional operations and allow to increase the efficiency of parallel processing.

Download file

Counter downloads: 110

Keywords

декомпозиционный подход, параллельные алгоритмы, композиционные формы, модельное описание

Authors

Name	Organization	E-mail
Klimova Olga V.	Institute of Engineering Science, Ural Branch of the Russian Academy of Sciences	ovk31@mail.ru

Всего: 1

References

Марчук Г.И., Котов В.Е. Проблемы вычислительной техники и фундаментальные исследования // Автоматика и вычисли тельная техника. 1979. № 2. С. 3-14.

Воеводин В.В. Вычислительная математика и структура алгоритмов. М. : Изд-во МГУ, 2006. 112 с.

Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб. : БХВ Петербург, 2002. 608 с.

Kung S.Y. VLSY Array Processors. Prentice Hall, 1987. 667 р.

Lee E.A. The problem with threads // IEEE Computer. 2006. V. 39, No. 5. P. 33-42.

Климова О.В. Методология декомпозиции данных и единое описание последовательных и параллельных алгоритмов вы числения операций цифровой обработки сигналов // Вестник Томского Государственного Университета. Управление, вычислительная техника и информатика. 2013. Т. 23., № 2. С. 112-120.

Lee G.G., Chen Y.K., Mattavelli M., Jang E.S. Algorithm / Architecture co-exploration of visual computing: Overview and future perspectives // IEEE Trans. Circuits and Systems for Video Technology. 2009. V. 19, No. 11. P. 1576-1587.

Gwo Giun (Chris) Lee, He-Yuan Lin, Chun-Fu Chen, Tsung-Yuan Huang. Quantifying intrinsic parallelism using linear algebra for algorithm/architecture coexploration // IEEE Trans. on Parallel and Distributed Systems. 2012. V. 23, No. 5. P. 944-957.

Климова О.В. Параллельные вычисления и закон построения модельного описания для алгоритмов цифровой обработки сигналов // Информационные технологии и вычислительные системы. 2016. № 2. С. 11-22.