Decomposition approach to the construction of parallel algorithms for processing of two-dimensional data.pdf Использование параллельного принципа обработки информации позволяет значительно повысить производительность вычислений и открывает путь для решения задач больших размеров. Базой для внедрения параллельного принципа обработки данных стали архитектурные решения, формирующие пространственно-временные вычислительные среды, позволяющие выполнять вычислительные действия параллельно, но требующие внесения изменений в отношения между алгоритмом и архитектурами. Действительно, при последовательной обработке алгоритм и архитектура - это всего лишь отдельные компоненты вычислительной системы, а при использовании параллельной обработки они должны быть взаимосвязанными частями параметризованной пространственно-временной среды. Только совместное изучение алгоритмов и архитектур позволит сделать выбор варианта организации вычислений обоснованным, а параллельную обработку эффективной. Решение проблемы обоснованного выбора, впервые сформулированной в работе [1], может дать ключ к разработке эффективных реализаций параллельных вычислений. Однако упомянутая проблема в большинстве своем и по сей день ожидает требуемых формальных решений, сложность поиска которых подчеркивалась во многих исследованиях [2-5]. Поэтому для современных параллельных вычислений проблема повышения их эффективности является актуальной. Путь же решения этой проблемы характеризуется введением в процесс выбора варианта организации вычислений этапа совместных исследований алгоритмов и архитектур [6-8], для реализации которого необходимы формальные инструменты, позволяющие связать воедино алгоритмические и архитектурные параметры. Для разработки таких инструментов нужно изучать внутреннюю пространственно-временную структуру вычислительных алгоритмов. Создаваемые при этом новые формы описания организации вычислений должны быть архитектурно независимыми, тогда на их основе можно анализировать различные сценарии отношений между алгоритмом и архитектурой. Эти сценарии можно представить следующим образом: алгоритм задан - требуется установить наилучшую архитектуру для его реализации; архитектура задана - требуется определить для нее наилучший вариант организации вычислений (алгоритм); наилучший вариант отношений между значениями алгоритмических и архитектурных параметров устанавливается в процессе их взаимонастройки, который характеризуется изменениями значений как одних, так и других параметров. Последний сценарий отличается наибольшей гибкостью выбора вариантов организации вычислений, поэтому его реализация позволит достичь наибольшего эффекта от использования параллельного принципа обработки. На сегодняшний день можно выделить два пути, по которым идет разработка формальных инструментов, позволяющих выявить внутренний параллелизм последовательных алгоритмов и пред-114 Декомпозиционный подход к построению параллельных алгоритмов ставить их в виде, обеспечивающем проведение совместных исследований алгоритмов и архитектур. Эти пути отличаются формами представления алгоритмов (графовыми и аналитическими), изначально положенными в основу процессов указанной разработки. Результаты [8], связанные с использованием исходных графовых форм (графов потоков данных), характеризуются их анализом, в процессе которого с помощью аппарата линейной алгебры выявляется внутренний параллелизм алгоритмов и образуются эквивалентные им модели параллельных вычислений, позволяющие выполнять совместные исследования алгоритмов и архитектур. Представленная в работе [8] методика такого анализа характеризуется достаточно высокой сложностью реализации. В данной работе будет рассмотрен результат разработки формальных инструментов, полученный на пути, связанном с изучением аналитических выражений, представляющих алгоритмы, с целью поиска эквивалентных им композиционных форм. По-видимому, получить требуемые формальные описания организации параллельных вычислений можно лишь для алгоритмов определенного класса, изучив их внутреннюю пространственно-временную структуру. В работе [6] представлен общий путь формирования таких решений для операций цифровой обработки сигналов (ЦОС), основанный на предложенном декомпозиционном подходе. В данной статье показывается, как изучение с помощью этого подхода внутренней структуры вычислительных операций обработки двумерных данных (двумерных свертки и корреляции, двумерного дискретного преобразования Фурье (ДПФ) и других структурно подобных им операций) привело к построению их композиционных форм и открыло новые возможности для обработки данных больших размеров и размерностей. 1. Параллельная обработка и теоретико-групповой декомпозиционный подход Представим общие характеристики подхода, позволившего изменить отношения между алгоритмом и архитектурами и получить композиционные формы различных операций, характеризующиеся параметризованными пространственно-временными структурами. В работе [5] отмечается важность поиска путей создания таких форм для разработки эффективных способов реализации параллельных вычислений. Интерес к построению композиционных форм связан с тем, что на их основе формируются описания организации вычислений, не только эквивалентные исходным аналитическим описаниям последовательных алгоритмов, но и изначально ориентированные на представление параллельных вычислений и установление отношений между алгоритмическими и архитектурными параметрами. Таким образом, необходимость изменения отношений между алгоритмом и архитектурами привела к необходимости изменения форм для описания организации вычислений на композиционные формы, позволяющие исследовать различные варианты организации параллельных вычислений. На основе предложенного декомпозиционного подхода [9], нацеленного на изучение внутренней структуры операций и данных, были получены параметризованные композиционные формы для представления операций цифровой обработки сигналов (ЦОС). Эти формы позволяют описывать разнообразие вариантов организации параллельных вычислений, синтезировать их различные пространственно-временные структуры и гибко управлять их изменениями. Общность предложенного подхода к построению композиционных форм для различных операций, а также его характер позволили расширить применение подхода на область обработки многомерных данных. В статье будет в общем виде представлена схема его использования при построении композиционных форм для операций обработки двумерных данных. Указанная схема характеризуется следующими действиями: - изучением с помощью подхода внутренней структуры двумерных данных; - образованием композиционных форм данных (КФД); - изучением с помощью подхода внутренней структуры двумерных операций; - образованием композиционных форм операций (КФО). На основе этих действий можно также выполнить расширение подхода на область обработки многомерных данных с целью построения соответствующих им композиционных форм. Прежде чем перейти к представлению результатов использования подхода при изучении внутренней структуры двумерных данных и операций, приведем описание его характера. Это позволит выделить существенные особенности подхода, обеспечивающие возможность перехода к композиционным формам для различных операций и различных размерностей. 115 О.В. Климова Итак, предложенный подход к формированию композиционных форм носит, как и было указано выше, декомпозиционный характер, проявляющийся в способности выделения инвариантных компонентов рассматриваемой операции и установления правил их композиции в исходную операцию. Такие способности были установлены на основе использования аппарата теории групп, поэтому подход был назван теоретико-групповым. Основой подхода является декомпозиция данных, приводящая к построению их композиционных форм, обеспечивающих построение композиционных форм для различных операций. Важной чертой предложенного теоретико -группового декомпозиционного подхода является его эволюционный характер, с одной стороны, обеспечивающий преемственность форм (алгоритм и параметризованная композиционная форма) описания организации вычислений для последовательного и параллельного способов обработки данных, а с другой - способствующий его развитию путем расширения на большие размерности операций, а также на иные классы операций. Теперь, выявив эволюционный и теоретико-групповой характер предложенного декомпозиционного подхода, приведем результат его применения для установления и изучения внутренних структур одномерных операций вышеозначенного класса. Исходные структуры этих операций, действующих на входные данные длины N, можно представить с помощью операции умножения матрицы размера N х N на вектор x(t). Использование подхода позволило на основе выполненных эквивалентных преобразований соответствующих аналитических выражений перейти от матрицы, действующей во временной области на вектор x(t), к параметризованной пространственно-временной структуре, порождающей координационно-вычислительную среду. Эта двумерная среда состоит из L2 матриц размера hi х hi и характеризуется соответствующей исследуемому классу операций координацией результатов вычислений, полученных при умножении этих матриц на векторы Xj(ti) длины hi, образованные в результате теоретико-групповой декомпозиции входных данных x(t), где N = hiL, t = j + tiL, t = 0, ..., N - 1 и j = 0, ..., L - 1, ti = 0, ..., hi - 1. Установленная с помощью использования предложенного подхода внутренняя структура рассматриваемого класса одномерных операций представлена на рис. 1. а b Рис. 1. Иллюстрация двух структур для вычислительных операций - временной (а) и пространственно-временной (b) Fig. i. Illustration of two structures for computational operations - time (a) and space-time (b) Полученная структура может быть охарактеризована как параметризованная однородная вычислительная среда, представляемая с помощью двумерной решетки. В ее L2 узлах расположены вычислительные блоки, реализующие исследуемую операцию, сжатую до размера hi и представляемую с помощью полученной параметризованной среды, описываемой параметрами j, p. С помощью ii6 Декомпозиционный подход к построению параллельных алгоритмов этих параметров можно работать с установленной внутренней структурой операций как с целью выявления наиболее эффективных вариантов организации их параллельных вычислений, так и с целью выполнения более тонкого и гибкого анализа формируемых результатов вычислений. Представив в общем виде предложенный декомпозиционный подход и результат его использования при изучении внутренних структур операций - параметризованную пространственно-временную структуру, предназначенную для описания параллельной обработки одномерных данных, расширим применение подхода на область обработки двумерных данных с целью ее перевода в параметризованную координационно-вычислительную среду. 2. Декомпозиционный подход к обработке двумерных данных Для получения композиционных форм операций вышеуказанного класса, предназначенных для обработки двумерных данных и характеризующихся единой матричной структурой вычислений, необходимо в рамках представленного подхода выполнить ряд следующих действий: - формирование композиционных форм (КФ) двумерных данных; - использование этих форм в исходных аналитических выражениях, описывающих рассматриваемые операции, и образование их исходных КФ; - выполнение необходимых эквивалентных преобразований над этими формами; - формирование и анализ композиционных форм для представления изучаемых операций. Эти действия были выполнены с помощью предложенного декомпозиционного подхода и привели к формированию параметризованного описания пространственно-временных структур изучаемых операций. Так как нас интересуют структурные изменения, произошедшие при этом и являющиеся общими для операций этого класса, то для их иллюстрации можно без потери общности использовать аналитические выражения для любой операции из рассматриваемого класса. Приведем описание выполненных структурных преобразований для операции двумерной циклической свертки, определенной на некоторой абелевой группе H = ZN^ х ZN^ : CNiN2 (t ) = CNiN2 w2-1 ^-1 N 9b 12 - N 92) • У(9ь 92), (ti,h) =2 Е X (ti - 92=0 9i=0 где индексы -щ и -щ обозначают операции вычитания на группах ZNj и Zщ порядков Ni и N2 соответственно, ti, qi = 0, ..., Ni - 1, t2, 92 = 0, ..., N2 - 1. Используем для этого композиционную форму двумерных данных, представленную в работе [6] и полученную в результате теоретико-групповой декомпозиции функции x(t) = x(ti, t2) на группе H = ZN^ х ZN- : jl =0 j2 =0 jl =0j2 =0 x(t )= Е Е x*Jlj2 (t - j1N2 -N2 j2) = Е Е x*Jlj2 ((t2 -N2 j2 K(t1 - j1 )N2 )• В процессе декомпозиции выполняется разложение порядков Ni = hiiLi, N2 = h2iL2, числа ti и t2 представляются в виде: t1 = j1 + t11 • L1, t2 = j2 + N t21 • L2, где tii = 0, ., hii - i, ji = 0, ., Li - i, t2i = 0, ., h2i - i,J2 = 0, ., L2 - i, число t задается с помощью выражения t = j2 + щ t21L2 + j1N2 + t11L1N2 и вводятся специальные функции Xj j (t), описанные в работе [6] и характеризующиеся свойствами композиции и эквивалентности сдвигов на группах разной структуры, но одного порядка. Формирование представленной композиционной формы данных соответствует реализации первого из перечисленных выше действий. Выполнение этих действий в полном объеме позволило получить композиционные формы для указанного класса вычислительных операций. Описать произведенные при этом структурные преобразования можно, представив полученное выражение для композиционной формы циклической свертки L-1 ц-1 CNN2 (t) = CPi +N2 P2 (t11, t21) = Е Е Е XJ\\N1,J1 ((t21 -h 21 q21)L2 + k=0 j=0 qeH ’ ii7 О.В. Климова L -1L -1 +(/ll h„ q1l)' L ' N2)y- j - 'Jl N2 J2P1 ^N2 P2 , {q21 ' L2 + q11 ' L ' N2) “ ^ S CJ1j2P1P2(t11’ ^2l) Ji=0 J2 =0 и сравнив его с приведенным выше исходным выражением, определяющим эту операцию. Переход к композиционным формам данных и операций позволил выявить их внутреннюю вычислительную структуру и изменить форму представления организации вычислений при обработке двумерных данных с алгоритмической на модельную. Проиллюстрируем сказанное с помощью приведенного выше выражения для композиционной формы операции (КФО) циклической свертки, перейдем от частного к общему, основываясь на выявленном структурном единстве полученных композиционных форм для различных операций рассматриваемого класса и представим их общее параметризованное описание КФО(А/Р^п, t2i), КВС/ p)), имеющее модельный характер. Действительно, его компонентами являются алгоритмы Ajp(tii, t2i), полученные в результате декомпозиции, погружения в пространственную среду и сжатия во времени последовательных алгоритмов Ai(t), а также параметризованные координационно-вычислительные среды КВС(/, p), при этом значение индекса i определяет вид операции, а параметры (j, p) описываются следующими выражениями: Р = Р2 + P1N2, j = /2 + jlN2. Иллюстрация полученного параметризованного описания для операции двумерной свертки представлена на рис. 2, свертка представлена суммой L2 = (L1L2)2 независимых сверток C/p(tii, t2i), заданных на группе H" = Zh х Z . h 11 h21 Рис. 2. Параметризованное пространственно-временное описание внутренней вычислительной структуры для операции двумерной свертки Fig. 2. Parametrized space-time description of the internal computational structure for two-dimensional convolution operation Перейдя от алгоритмической формы представления двумерных операций вышеуказанного класса к модельной форме, мы не только увидели их внутреннюю пространственную структуру, но и получили возможность ее настройки по параметрам hii, Li, N1 = hiiLi и fei, L2, N2 = feiL2, обеспечив гибкость такой настройки вследствие отсутствия ограничений на их значения. Разработанная мо-ii8 Декомпозиционный подход к построению параллельных алгоритмов дельная форма описывает разнообразие вариантов организации вычислений, является формальной основой для синтеза параллельных алгоритмов и предлагает формальный инструмент для управления изменениями структур вычислений. Такие характеристики полученной формы описания организации вычислений двумерных данных открывают новые вычислительные возможности, краткому представлению которых посвящен следующий параграф. 3. Декомпозиционный подход и новые вычислительные возможности Анализируя созданную в рамках предложенного декомпозиционного подхода модель, можно увидеть вычислительные возможности, потенциально заложенные в ее параметризованное описание. Чтобы показать эти возможности, выделим три класса актуальных задач, решить которые можно путем их реализации. Представим эти задачи, а затем покажем, как с помощью полученной модели они могут быть решены. Прежде всего это задача обеспечения реализации этапа совместных исследований алгоритмов и архитектур, присущего современному проектированию вычислительных устройств и позволяющего выполнять по формальным правилам синтез, оценку и выбор наилучших в заданных условиях вариантов организации вычислений на высоком уровне абстракции. Решение этой задачи направлено на обеспечение эффективности параллельной обработки. Следующей из вышеуказанных задач является задача совершенствования формального инструмента, предназначенного для анализа двумерных данных. Решение этой задачи позволит реализовать гибкий и точный доступ к различным участкам обрабатываемой информации и выполнять оценку внутренней структуры проводимых вычислений и получаемых при этом результатов. И наконец, реализация полученных возможностей представленного модельного описания позволяет решить задачу управляемой по параметрам реструктуризации вычислений. Решение этой задачи дает ключ к сокращению сложности и повышению надежности вычислений. Теперь рассмотрим более подробно полученные возможности в свете решения вышеуказанных задач. Возможность решения задачи реализации совместных исследований алгоритмов и архитектур базируется на создании формального инструмента - модельного описания организации вычислений, характеристики которого позволяют выполнять такие исследования. Представим эти характеристики. Прежде всего это способность порождать разнообразие алгоритмов и их структур, а также способность управления их изменениями, основанные на полученном параметризованном описании. Следующей характеристикой полученного описания КФО(Л/р(1п, fo), КВСг(/, p)) является наличие в его составе в качестве компоненты параметризованной координационно-вычислительной среды КВС/ p), определяемой параметрами (/, p). Эта характеристика наделяет рассматриваемое описание способностью организации параллельно-конвейерной обработки за счет погружения вычислений в параметризованную пространственную среду и расширения самого описания путем введения в его состав архитектурных параметров. Следует отметить, что изначально полученное описание не зависит от архитектуры вычислительных устройств, но предполагает возможность внедрения в свой состав архитектурных параметров при выполнении совместных исследований алгоритмов и архитектур. Все вышесказанное свидетельствует о гибкости и адаптивности рассматриваемого описания. Таким образом, создание представленного модельного описания позволяет проектировать многопроцессорные вычислительные системы в едином пространстве, определяемом алгоритмическими и архитектурными параметрами, на основе алгоритмических оценок сложности реализации синтезируемых вариантов организации вычислений. Предлагаемый подход к проектированию отвечает современным тенденциям его развития [7, 8], при таком подходе поиск и выбор варианта осуществляются на этапе синтеза, оценки и анализа разнообразия вариантов на алгоритмическом уровне с учетом заданных ограничений на аппаратурно-временные затраты. Реализация возможности решения задачи проведения совместных исследований алгоритмов и архитектур наделяет процесс проектирования свойством адаптивности, позволяющим на основе формальных правил устанавливать наилучшие варианты организации вычислений. Обоснованный выбор таких вариантов на исследовательском этапе проектирования приводит к повышению эффективности параллельной обработки. 119 О.В. Климова Рассмотренное описание организации вычислений также предоставляет возможность решения вышеуказанной задачи совершенствования формального инструмента, предназначенного для анализа двумерных данных. Эта возможность формируется благодаря установлению на основе декомпозиционного подхода закона описания внутренней структуры для операций рассматриваемого класса. Можно сказать, что этот закон представляется с помощью полученного параметризованного описания композиционных форм операций КФО(Л/р(1п, fei), КВСг(/, p)), позволяющего реализовать гибкий доступ по параметрам к внутренней структуре вычислительного процесса, анализ композиционных форм, конструирование данных и корректировку результатов вычислений. Короче говоря, этот закон позволяет работать с элементами внутренней структуры вычислительных процессов и тем самым расширяет возможности для анализа двумерных данных. Решение последней задачи управляемой по параметрам реструктуризации вычислений, нацеленной на сокращение сложности и повышение надежности вычислений, также базируется на законе описания внутренней структуры операций и полученной при этом возможности управления изменениями этой структуры. Именно благодаря такой возможности мы можем сокращать сложность вычислений операции путем перехода к композиционной форме ее представления, описывающей длинную операцию с помощью композиции коротких операций. Также благодаря данной возможности мы получаем потенциальную способность предложенного описания организации вычислений к повышению надежности вычислений. Эта способность базируется на его готовности к управляемым по параметрам изменениям структуры вычислений. Таким образом, возможность перехода от одного структурного варианта к другому создает алгоритмический потенциал для повышения надежности вычислений. Заключение Представлено расширение теоретико-группового декомпозиционного подхода на область обработки двумерных данных. Подход был изначально разработан для построения композиционных форм базовых операций цифровой обработки сигналов. Его расширение выполнено с целью перевода обработки двумерных данных в параметризованную координационно-вычислительную среду, предназначенную для описания параллельных вычислений. В результате выполненного расширения сформирована система действий, порождаемых и реализуемых в рамках предложенного подхода и направленных на изучение внутренней структуры вычислительных операций обработки двумерных данных (двумерных свертки и корреляции, двумерного дискретного преобразования Фурье (ДПФ) и других структурно подобных им операций) с целью образования их композиционных форм. Проведен анализ структур полученных форм, в ходе которого выявлен их модельный характер. Таким образом, переход к композиционным формам позволил изменить форму представления организации вычислений при обработке двумерных данных с алгоритмической на модельную. Приведено общее модельное описание организации вычислений для различных операций рассматриваемого класса, отличительной особенностью которого является погружение вычислений в параметризованную координационно-вычислительную среду. Показано, что полученное модельное описание открывает новые вычислительные возможности, позволяющие решать актуальные задачи, нацеленные на повышение эффективности параллельной обработки, сокращение ее сложности, а также на повышение гибкости анализа обрабатываемых данных.

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