Methodology of data decomposition and general description of sequential and parallel algorithms for digital signal processing operations
The problem of parallel algorithm development is considered in this paper. The main content of solution is development of formal description of sequential and parallel algorithms. The solution is based on the methodology of data decomposition. The main peculiarities of methodology are its functional nature and the general approach to data decomposition of any dimension. The basic steps of methodology presented are considered. The methodology is the basis for development of the formal model of the parallel computation organization.
Download file
Counter downloads: 400
Keywords
параллельные алгоритмы, цифровая обработка сигналов, декомпозиция, параметризованный синтез алгоритмов, модель организации параллельных вычислений, parallel algorithms, digital signal processing, decomposition, parametrized synthesis of algorithms, model of the parallel computation organizationAuthors
| Name | Organization | |
| Klimova Olga V. | Institute of Engineering Science, Ural Branch of the Russian Academy of Sciences (Ekaterinburg) | klimova@imach.uran.ru |
References
Воеводин В.В. Вычислительная математика и структура алгоритмов. М.: Изд-во МГУ, 2006.
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002.
Кун С. Матричные процессоры на СБИС. М.: Мир, 1991.
Lee G.G., Chen Y.K., Mattavelli M., and 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. №. 11. P. 1576-1587.
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. 2012. V. 23. №. 5. P. 944-957.
Lee E.A. The problem with threads // IEEE Computer. 2006. V. 39. No. 5. P. 33-42.
Климова О.В. Единый подход к построению быстрых алгоритмов и распараллеливанию вычислений дискретного преобразования Фурье // Изв. РАН. Теория и системы управления. 1999. № 3. С. 68-75.
Климова О.В. Параллельная архитектура процессора свертки произвольной длины с использованием числовых преобразований Рейдера // Изв. РАН. Техн. кибернетика. 1994. №2. С. 183-191.
Klimova O. Decomposition on a group and parallel convolution and fast fourier transform algorithms // Parallel Computing Technologies 4th International Conference, PaCT-97: Proceedings. Berlin: Springer-Verlag, 1997. LNCS1277. P. 358-363.
Климова О.В. Способы управления изменениями структуры параллельных алгоритмов цифровой обработки сигналов // Параллельные вычисления и задачи управления PAC0'2008: труды IV Междунар. конф. М.: ИПУ РАН, 2008. С. 1033-1041.
Климова О.В. Эволюция способов организации вычислений для операций цифровой обработки сигналов: от алгоритма к модели // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2011. № 1(14). С. 31-38.
