Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

MATHEMATICAL MODEL OF PARALLEL COMPUTATION ORGANIZATION FOR DIGITAL SIGNAL PROCESSING OPERATIONS

Klimova O.V. 1
1 Institute of Engineering Science, Ural Branch of the Russian Academy of Sciences
The mathematical model of parallel computation organization for digital signal processing (DSP) operations is presented in this paper. The development of the formal instrument of computation transition from time domain to space-time domain enabled to create the model. This instrument allowed to reveal the intrinsic structure of algorithms and to present it using composition forms. These forms are equivalent to the original expressions that describe the sequential algorithm. Symbiosis of composition forms of data and composition forms of DSP operations represents the model. The model parameters describe the structure of parallel algorithms. The possibilities of the model developed allow one to describe set of variants of the parallel computation organization, to perform their synthesis and analysis. Moreover the possibilities of the model allow to control change of parallel algorithm structures. Model developed is the formal instrument for realization of co-exploration stage of algorithms and architectures. This stage is integral part of design process of modern computation systems. On an algorithmic level the stage permits to synthesize and evaluate design variants in an iterative mode. The use of such possibilities in the design allows to make a reasonable choice of the required solutions and to provide thus efficiency of parallel processing.
parallel processing
intrinsic algorithm structure
decomposition
parametrized synthesis of algorithms
composition form
algorithm and architecture co-design
1. Voevodin V.V. Vychislitel’naia matematika i struktura algoritmov. M.:Izd-vo MGU, 2006.
2. Voevodin V.V., Voevodin Vl.V. Parallel’nye vychisleniia. SPb.: BKHV – Peterburg, 2002.
3. Klimova O.V. The Unified Approach to the Development of Fast Algorithms and Parallel Implementation of Discrete Fourier Transformation. Journal of Computer and Systems Sciences International. Vol. 38, no. 3, 1999, pp. 402–408.
4. Klimova O.V. Parallel’naia arkhitektura protsessora svertki proizvol’noi dliny s ispol’zovaniem chislovykh preobrazovanii Reidera // Izv. RAN. Tekhn. kibernetika. 1994. no. 2. pp. 183–191.
5. Klimova O.V. Bystrye parallel’nye algoritmy i rekursivnaia psevdodvumernaia dekompozitsiia svertki // Vestnik Tomskogo gosydarstvennogo universiteta. no. 1 (II). Tomsk: Izd. TGU, 2002. pp. 227–232.
6. Klimova O.V. Metodologiia dekompozitsii dannykh i edinoe opisanie posledovatel’nykh i parallel’nykh algoritmov vychisleniia operatsii tsifrovoi obrabotki signalov // Vestnik Tomskogo gosydarstvennogo universiteta. Upravlenie, vychislitel’naia tekhnika i informatika. 2013. no. 2(23). pp. 112–120.
7. Kun S. Matrichnye protsessory na SBIS. M.: Mir, 1991.
8. Edward A. Lee. The Problem with Threads // IEEE Computer, Vol. 39, no. 5, pp. 33–42, may 2006.
9. 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, Vol. 19, no. 11, pp. 1576–1587, Nov. 2009.
10. 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.
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. 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, Vol. 1, pp. 429–430. ISBN: 978-966-335-412-5. IEEE Catalog Number: CFP14788.
13. Klimova O.V. Formal transition from algorithm to model for digital signal processing operations. 2014 24nd Int. Crimean Conference «Microwave & Telecommunication Technology» (CriMiCo’2014). Sevastopol, 2014, Crimea, Russia, Vol. 1, Р. 445–446. ISBN: 978-966-335-412-5. IEEE Catalog Number: CFP14788.

Переход к параллельной обработке данных сделал организацию вычислений объектом исследований, характеризующимся множеством вариантов. Для выполнения таких исследований необходим формальный инструмент, способный описать их разнообразие. Базой для разработки такого инструмента является множество алгоритмов, описывающих организацию последовательных вычислений. Реализуя переход от алгоритма к модели, можно создать такой инструмент. Путь реструктуризации [1, 2, 7] известных последовательных алгоритмов и их программ, пройденный для изучения вопросов построения параллельных алгоритмов, не привел к созданию общего формального описания – модели организации вычислений. Для погружения последовательных алгоритмов в пространственно-временную среду необходимо выделить то их общее свойство, которое может быть использовано для выявления единого правила такого погружения. Таким свойством является композиционность. Именно установление формальных законов образования композиционных форм в работе [8] связывается с получением возможности повышения эффективности параллельных вычислений. Действительно, установив такие законы, можно на их основе синтезировать различные варианты организации вычислений, предназначенные для выполнения одной и той же операции, и оценивать аппаратурно-временную сложность их реализации. Эти возможности, в свою очередь, позволяют выполнять совместное проектирование алгоритмов и архитектур, представляющее собой современное направление [9, 10] создания перспективных высокопроизводительных вычислительных систем.

Данная статья посвящена представлению модели организации вычислений для операций цифровой обработки сигналов (ЦОС), полученной на основе разработанного закона описания внутренней структуры их последовательных алгоритмов [3–5, 11]. Этот закон позволил реализовать переход от алгоритма к модели, путем построения композиционных форм, ориентированных на синтез параллельных алгоритмов.

Разнообразие вариантов организации вычислений и его формальное описание

Подойдем к представлению новой модельной формы описания структур алгоритмов, изначально ориентированной на параллельную обработку, отталкиваясь от объекта описания, коим является организация параллельных вычислений. Этот объект характеризуется разнообразием вариантов, следовательно, модель должна его описывать. На основе модели можно выполнять параметризованный синтез и анализ вариантов организации вычислений, а также управлять изменениями их структур. Такие возможности разработанной модели делают её основой для реализации совместных исследований алгоритмов и архитектур. Эти исследования, выполняемые в процессе совместного проектирования алгоритмов и архитектур, позволяют сделать обоснованным выбор варианта организации вычислений. На самом деле, проблема выбора является порождением разнообразия вариантов, следовательно, получив инструмент для его описания, мы тем самым создадим основу для реализации обоснованного выбора. На рисунке представлена укрупненная схема совместных исследований алгоритмов и архитектур. Схема представляет симбиоз компонентов, обеспечивающий обоснованный выбор вариантов. Схема носит итеративный характер. Совместное исследование алгоритмов и архитектур предполагает одновременный анализ параметров синтезируемых алгоритмических вариантов и параметров изучаемых архитектур и приводит к получению оценок аппаратурно-временной сложности реализации формируемых при этом решений. Выбор наилучших решений из множества осуществляется на основе заданных оптимизационных критериев реализации вычислений. Основной компонентой схемы, обеспечивающей её функционирование, является разработанная модель. Для построения модели была исследована внутренняя структура входных данных и операций ЦОС, в результате чего был установлен закон её описания. На основе этого закона данные и операции были представлены с помощью композиционных форм данных (КФД) и композиционных форм операций (КФО). В обобщенном виде созданная модель организации вычислений может быть представлена с помощью следующей формулы:

КФД + КФО = Модель.

Суть закона описания внутренней структуры данных и операций состоит в использовании многомасштабного представления этих структур. Для реализации закона были разработаны формальные инструменты – методология декомпозиции данных и методика синтеза композиционных форм операций. В работах [6, 12, 13] была представлена схема перехода от алгоритма к модели, базирующаяся на использовании этих инструментов. Выполненный переход от обычных форм к композиционным позволил говорить об эволюции формальных основ для описания организации вычислений [13], позволившей качественно изменить эти основы, подняв их на более высокий уровень абстракции. Таким образом, привычный алгоритм был заменен моделью, описывающей требуемое разнообразие структур параллельных алгоритмов. Эволюционный характер выполненного перехода свидетельствует о преемственности новых и исходных форм для представления операций ЦОС, формально проявляющейся в установленной параметрической зависимости между указанными формами. Эта зависимость связана с проявлением закона описания внутренней структуры алгоритмов для класса операций ЦОС. Основной характеристикой этого закона является параметризация структуры алгоритма. Введя для N-точечной операции ЦОС (свертки, корреляции, дискретного преобразования Фурье (ДПФ) и других ортогональных преобразований) параметр L, показывающий степень сжатия указанной операции во временной области до размера h1 = N/L, можно для выбранной операции синтезировать разнообразие структур параллельных алгоритмов на основе закона описания внутренней структуры исходного последовательного алгоритма. При этом значение параметра L = 1 соответствует последовательному алгоритму, а все возможные значения параметра L ≠ 1 формируют необходимое разнообразие вариантов организации вычислений для выбранной операции.

pic_23.tif

Укрупненная итеративная схема совместных исследований алгоритмов и архитектур, обеспечивающих обоснованный выбор вариантов организации вычислений

Завершая данный параграф, приведем следующее модельное описание алгоритмов Ai(t) – klimova01.wmf. Компонентами этого описания являются алгоритмы klimova02.wmf, полученные в результате декомпозиции, погружения в пространственную среду, характеризуемую параметрами j, p (j, p = 0, …, L – 1), и сжатия во времени до размера h1 (t1 = 0, …, h1 – 1) последовательных алгоритмов Ai(t) (t = 0, …, N –1), а также координационно-вычислительные среды КВСi(j, p). Тогда множество последовательных алгоритмов klimova03.wmf, разработанных для различных операций Оm, благодаря созданному механизму образования КФО, будет компонентой модельного описания для целого класса алгоритмов. Ключевым параметром, сформированного таким образом модельного описания

klimova04.wmf

определяющим возможность и уровень сжатия вычислений во времени, является параметр L, задаваемый следующим образом: L = N/h1. Именно введение и использование этого параметра позволило установить связь между алгоритмическим и модельным описаниями организации вычислений.

Методика совместного проектирования алгоритмов и архитектур

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

Разработанная модель организации вычислений для операций ЦОС может стать основой для реализации вышеназванной методологии проектирования. На основе предложенной модели была разработана общая методика совместного проектирования алгоритмов и архитектур, характеризующаяся совместной оптимизацией их параметров. Методика представляет проектирование в виде итеративного процесса, генерирующего и оценивающего различные варианты организации вычислений на основе совместных исследований алгоритмов и архитектур. Реализация такого процесса позволит на алгоритмическом уровне выявлять варианты, наилучшим образом удовлетворяющие проектным условиям. Основными шагами разработанной методики являются доопределение модели архитектурными параметрами и формирование параметрических зависимостей оценок аппаратурно-временной сложности реализации исследуемых вариантов. На основе такой доопределенной модели может быть реализован итеративный этап совместных исследований алгоритмов и архитектур, каждая итерация которого характеризуется синтезом, оценкой и анализом рассматриваемых вариантов. Внедрение такого этапа в процесс проектирования позволит повысить эффективность параллельной обработки, следовательно, этап должен стать неотъемлемой частью проектирования высокопроизводительных вычислительных систем.

Заключение

Представленная формальная модель позволяет описывать разнообразие вариантов организации вычислений для операций ЦОС, выполнять их синтез и анализ, а также управлять изменениями их структур. Модель является архитектурно-независимой и способной обеспечить реализацию обоснованного выбора варианта параллельной организации вычислений. Такой выбор может быть осуществлен в процессе выполнения этапа совместных исследований алгоритмов и архитектур. Предложенный путь реализации выбора позволяет повысить эффективность параллельной обработки за счет согласования архитектурных и алгоритмических параметров проектируемых вычислительных систем. Возможность реализации такого проектирования, основанного на совместной оптимизации алгоритмических и архитектурных параметров и отвечающего современным тенденциям развития данной области, обеспечивается свойствами разработанной модели.

Работа выполнена при частичной поддержке программы УрО РАН «Математические модели, алгоритмы, высокопроизводительные вычислительные и информационные технологии и приложения» (проект 15-7-1-20).