Methodology of data decomposition and general description of sequential and parallel algorithms for digital signal processing operations.pdf В статье рассматривается проблема создания алгоритмов, изначально ориентированных на параллельную обработку, специально разработанных для реализации вычислений в пространственно-временной среде. Создание формальных инструментов для описания организации параллельных вычислений позволит повысить их эффективность. Действительно, путь повышения эффективности - согласование алгоритмических и архитектурных характеристик параллельных вычислительных систем. Такое согласование может быть выполнено в ходе совместных исследований алгоритмов и архитектур. Эти исследования можно проводить на основе формальных описаний, позволяющих выявлять внутреннюю структуру вычислительных алгоритмов, а также управлять этой структурой. Но для этого необходимо создать такие описания. Сложность этой задачи была отмечена многими исследователями [1-3]. Путь реструктуризации [1, 2] известных последовательных алгоритмов и их программ, направленный на построение параллельных алгоритмов, не привел к формированию общего описания различных вариантов организации вычислений. Более того, этот путь ориентирован на адаптацию структур последовательных алгоритмов к конкретным условиям их параллельной обработки. Поэтому результаты, полученные на этом пути, не могут быть рассмотрены в качестве основы для реализации совместных исследований алгоритмов и архитектур. В то же время во многих современных работах [4, 5] подчеркивается важность и актуальность таких исследований, а также приводятся результаты, обеспечивающие их реализацию на основе найденных приемов описания разнообразия параллельных алгоритмов. Эти приемы, позволяющие изучать внутреннюю структуру алгоритмов, всё же оставляют указанные исследования на том же алгоритмическом уровне абстракции. Для того чтобы перейти от алгоритма к модели организации параллельных вычислений, необходимо поднять процесс исследования структур алгоритмов на более высокий уровень абстракции. Однако, известных результатов, относящихся к области разработки моделей организации параллельных вычислений, чрезвычайно недостаточно. Очевидно, что такие модели не могут быть универсальными, они должны разрабатываться для выделенного класса операций. Для создания модели необходимо установить общий закон, позволяющий выявлять внутренний параллелизм последовательных алгоритмов и представлять их в виде композиционных форм. Компонентами этих форм должны стать независимые вычислительные процессы. Именно такой путь предлагается использовать в работе [6] для построения параллельных алгоритмов, изначально ориентированных на параллельную обработку. Основная сложность реализации этого пути заключается в установлении требуемого закона, приводящего к образованию композиционных форм. Обнаружение такого закона позволит установить связь между последовательной и параллельной обработкой данных. В свою очередь, именно эта связь позволит осуществить естественный переход от алгоритма к модели. Такие модели станут теми формальными инструментами, которые будут порождать алгоритмы (варианты организации вычислений), изначально ориентированные на параллельную обработку. С помощью таких моделей можно будет синтезировать множество алгоритмических решений и управлять по параметрам модели выбором и анализом их вариантов. В статье рассматривается методология декомпозиции данных, разработанная на основе теоретико-группового подхода к построению параллельных алгоритмов цифровой обработки сигналов (ЦОС) [7-11]. Предлагаемая методология стала ключевым этапом в процессе разработки формального инструмента, позволяющего раскрыть и изучать внутреннюю структуру алгоритмов. Она позволила подняться на более высокий уровень абстракции и создать единое формальное описание для последовательных и параллельных алгоритмов вычисления векторно-матричных операций. К указанному классу относятся алгоритмы вычисления базовых операций ЦОС и изображений (дискретные ортогональные преобразования, реализуемые в различных функциональных базисах, свертка, корреляция), а также операции произведения матриц и умножения матрицы на вектор. Созданное описание позволяет синтезировать алгоритмы, изначально ориентированные на параллельную обработку. следований является организация вычислений, характеризующаяся множеством различных вариантов. Для обеспечения возможности проведения совместных исследований на высоком уровне абстракции необходимо описать объект исследований в среде его изучения, то есть в пространственно-временной среде. Это означает, что требуемое описание должно порождать разнообразие вариантов организации вычислений, должно быть формальным и архитектурно-независимым. Наличие такого описания - формального инструмента - позволит синтезировать множество параллельных алгоритмов - вариантов организации вычислений для выбранной операции - и выполнять совместные исследования алгоритмов и архитектур. Таким формальным инструментом должна стать модель [11] организации параллельных вычислений, которая для вышеуказанного класса операций была создана на основе результатов, представленных в работах [7-11]. Был выполнен формальный переход от алгоритмов к модели, при реализации которого была разработана предлагаемая в данной статье методология декомпозиции данных. Прежде чем представить данную методологию, рассмотрим обобщенную схему перехода от алгоритма к модели организации параллельных вычислений. Схема, представленная на рис. 1, позволяет продемонстрировать ключевую роль разработанной методологии в процессе иллюстрируемого перехода. Рис. 1. Обобщенная схема перехода от алгоритмов к модели организации параллельных вычислений Приведем краткое описание данной схемы и раскроем используемые в ней сокращения и обозначения. Применение указанной методологии к набору входных данных х (t) длины N позволило построить пространственно-временные композиционные формы данных КДФ(tl, j), зависящие от временной t1 и пространственной j переменных. Замена входной последовательности х (t) на полученные КДФ(t1, j) в исходных формах представления операций (ИФО) вышеозначенного класса привело к созданию композиционных форм представления операции - КФО (Aj (t1), КВС (j, p)). Компонентами этих форм являются алгоритмы Ajp (t1), полученные для реализации последовательных вычислений выбранной операции из рассматриваемого класса и сжатые во времени, а также координационно-вычислительные среды KEC(i,p), формируемые в процессе образования КФО. Таким образом, множество алгоритмов Ai (t), разработанных для последовательной обработки, благодаря созданному механизму образования КФО, основанному на их сжатии во времени, может характеризовать модель организации параллельных вычислений, являясь компонентой этой модели. Таким образом, созданная база последовательных алгоритмов, разработанных как на основе ИФО, так и на основе преобразовательных форм представления операции (ПФО), полученных в результате применения к ИФО различных эквивалентных преобразований, может быть подвергнута сжатию во времени и погружена в КВС(j,p) для любой операции Om выделенного класса. Ключевым параметром, определяющим возможность и уровень сжатия вычислений во времени, является параметр L, задаваемый следующим образом: L = N/h1, где t1 = 0,... ,h1; j, p = 0,... ,L-1. Введение и использование этого параметра позволило установить связь между алгоритмическим описанием вычислений и описанием организации параллельных вычислений с помощью модели. Последовательная обработка соответствует значению параметра L=1, а параллельная L±\. Таким образом, полученную модель можно рассматривать как единое описание последовательных и параллельных алгоритмов для операций вышеозначенного класса. Базой для создания такого описания стала предлагаемая методология декомпозиции данных. В свою очередь, использование такой методологии для создания модели организации параллельных вычислений означает переход на более высокий уровень абстракции при описании вычислений. Поднявшись на этот уровень, мы смогли извлечь внутренний параллелизм последовательных алгоритмов, используя единые для различных операций законы образования КФО. Это единство определяется общей для различных операций и независящей от них методологией декомпозиции данных, описанию которой посвящен следующий раздел. 2. Методология декомпозиции данных Характерными особенностями представляемой методологии являются общий подход к декомпозиции данных произвольной размерности и её функциональный характер, приводящий к образованию композиционных форм представления входных данных. В основе синтеза этих форм лежат операции сдвига и масштабирования по времени входной последовательности. Проиллюстрируем базовые шаги разработанной методологии для одномерных и двумерных входных данных. Для этого предварительно представим преобразования над входными данными, в результате которых была получена новая композиционная форма их представления (структура). Иными словами, опишем процесс реструктуризации входной последовательности данных, в качестве которой будем рассматривать функцию x(t), заданную на отрезке [0, N-1]. Определим на отрезке [0, N-1] по функции x(t) функцию x (t) с помощью формулы *(t) = fx(tX t=t1 • L x (t) = \0, t Ф t1 • L, *, ч fx(t + j), t = t, • L, и систему функций xi (t) = < 1 (0, t ф ^ • L, где t = j+t1L; N = Lxh1; t1 = 0,. ,h1; j,p=0,..., L-1. Функции Xj'(t) характеризуются свойством композиции, с их помощью входную последовательность x(t) можно представить следующим образом: x(t) = Х х13 (t - j). j=0 Полученная композиционная форма позволяет реструктурировать входные данные, вид такой структурной организации данных определяется параметром L. Предложенный подход может быть использован для декомпозиции данных различных размерностей. Рассмотрим путь формирования композиционной формы для двумерной входной последовательности. Опираясь на рассмотренную выше декомпозицию одномерной функции x(t), выполним теоретико-групповую декомпозицию двумерной последовательности x(t1, t2). Функция x(t1, t2) задана на группе H = ZN х ZN порядка N = N1 х N2. Тогда соответствие вида t = t2 + t1N2 является для такой функции изначальным. Если порядки N1 и N2 можно представить в виде N1 = h11 • Lj, N2 = h21 • L2, то функцию x(t1, t2) можно декомпозировать по обеим координатам. Число t1 задается выражением t1 = j1 +111L1, где t11 = 0,...,h11 -1 и j1 = 0,...,L1 -1, а число t2 представляется в виде t2 = j2 +N2 t21L2, где j2 = 0,...,L2 -1, +N2 - операция суммирования на группе ZN^ и t21 = 0,...,h21 -1. Тогда t можно представить с помощью следующего выражения: t = j2 +Nj t21 L2 + j1 N2 +t11L1N2. Теперь, введя функции X*(t) = {x(t ^ t = t21L2 + 1L1N2, |0, t Ф t21L2 + t11L1N2, щью следующего выражения: t1 = (t-j)/L = ((t1 L+j)-j)/L. Иллюстрация описанной выше методологии декомпозиции одномерных и двумерных данных представлена на рис. 2. Иллюстрация выполнена для последовательностей размера N=16 и N1xN2=4x4 и следующих параметров декомпозиции: h1=L=4 для одномерных данных и h11=L1=2 и h21=L2=2 для двумерных данных. 1.а. » * О ♦ • 0 4 12 15 8 2.а. • lllalllallla^>t 2б. • • 0 4 8 12 -•- 1 1 1 -•- 1 1 1 -•- 1 1 1 -•- t t • • 1 5 9 13 MIII

Скачать электронную версию публикации