Evolution of computation organization methods for digital signalprocessing basic operations: from algorithm to model.pdf В статье рассматривается эволюция формальных основ, отвечающих за орга-низацию вычислений базовых операций цифровой обработки сигналов (ЦОС).Дело в том, что эта бурно развиваемая уже не одно десятилетие область всегдавыдвигала жесткие требования к скорости обработки информации, что в своюочередь приводило к интенсификации исследований по созданию быстрых алго-ритмов [1], ориентированных на последовательную обработку и реализуемых наспецпроцессорах. Таким образом, при последовательной обработке данных быст-рые алгоритмы стали основой организации вычислений для операций ЦОС. Сей-час на современном этапе развития средств обработки информации ЦОС являетсяодной из наиболее заинтересованных областей в эффективном использовании та-кого резерва повышения быстродействия как параллельная обработка. Одной изважнейших проблем, стоящих на пути использования этого резерва, является про-блема согласования алгоритмических и архитектурных характеристик параллель-ных вычислительных систем. Эта проблема может быть решена с помощью соз-дания самостоятельных основ организации параллельных вычислений, изначаль-но ориентированных на описание вычислительных процессов в пространственно-временной среде. Таким образом, эволюция рассматриваемых формальных основ,отвечающих за организацию вычислений базовых операций ЦОС, не должна про-ходить мимо пути решения указанной проблемы, а должна привести к созданиюновых формальных основ для организации именно параллельных вычислений.Так как переход к параллельным вычислениям сделал саму их организацию объ-ектом исследований, характеризующимся множеством решений, то для обеспече-ния возможности их описания необходимо разрабатывать формальные инстру-менты синтеза и анализа этих решений. Каким должен быть разрабатываемый ин-струмент, каковы пути его создания и каковы его отношения с богатой предысто-рией - алгоритмами последовательной обработки, являющимися базисом для еёорганизации? Ответы на эти вопросы еще предстоит получить, но исследования,проводимые в этой области [2 - 5], свидетельствуют о чрезвычайной важности исложности задачи создания такого инструмента, а опыт практического использо-вания [6] параллельной обработки говорит о необходимости решения данной за-дачи. Анализируя общие результаты исследований, связанные с реструктуризаци-ей [2 - 4] известных последовательных алгоритмов и их программ и направлен-ные на построение параллельных алгоритмов, можно отметить, что они не приво-дят к созданию общего формального описания различных вариантов организациивычислений. Эти результаты характеризуются адаптацией структур последова-тельных алгоритмов к условиям параллельной обработки. В статье будет предло-жено направление развития основ организации вычислений и представлена новаяформа описания организации параллельных вычислений - формальная модель,полученная для операций ЦОС в процессе исследований по указанному направ-лению. Базой для создания указанного формального инструмента, позволившегопостроить такую модель, стало развитие принципов преемственности описаниявычислительной среды, её модульности и масштабирования. Соблюдение прин-ципа преемственности в рамках искомого решения означает, что оно формируетединое описание как для последовательных, так и для параллельных алгоритмов,последовательная обработка при этом рассматривается как частный случай парал-лельной, а исходный последовательный алгоритм представляется некоторой ком-позиционной формой, состоящей из детерминированного набора отдельных неза-висимых по времени вычислительных компонентов. Установление формальныхправил образования таких композиционных форм позволит создать искомый ин-струмент для синтеза и анализа различных структур параллельных алгоритмов.Наличие такого инструмента обеспечит возможность построения новой формаль-ной основы, позволяющей задавать как последовательные, так и параллельные ал-горитмы и представляющей собой модель организации вычислений в пространст-венно-временной среде, характеризуемую набором параметров и их отношений.Таким образом, для создания такой модели необходимо разработать взаимноодно-значные процедуры перехода из временной области представления вычислений впространственно-временную. Именно эти параметризованные процедуры станутбазисом для организации параллельных вычислений. Такие процедуры были раз-работаны для базовых операций ЦОС, описания некоторых из них приведены вработах [7 - 13]. Порождаемые этими процедурами структуры параллельных ал-горитмов будут содержать в качестве своих компонент алгоритмы выполненияисходных операций ЦОС, сжатые во времени пропорционально расширению про-странственной структуры конкретного параллельного алгоритма. Тогда привыч-ный последовательный алгоритм будет лишь компонентой модели, позволяющейформировать, а в последующем и анализировать различные варианты организа-ции параллельных вычислений. Таким образом, переход от последовательной об-работки к параллельной привел к качественному изменению самого пониманиябазиса для организации вычислительного процесса. И если для последовательнойобработки таким базисом был алгоритм, то для параллельных вычислений такимбазисом должна стать модель. Кратко проследим вышеописанный путь от алго-ритма к модели для базовых операций ЦОС.1. Обоснование необходимости измененияоснов организации вычисленийРассмотрим причины, заставляющие говорить о необходимости перехода оталгоритма к модели. Эти причины, прежде всего, являются следствием изменениясамой вычислительной среды. Действительно, последовательная обработка харак-теризуется временной средой для реализации вычислений, в то время как парал-лельная обработка предоставляет для этого пространственно-временную среду.Эта среда, описываемая параметрами (j, t) и характеризуемая возможностью од-новременной реализации вычислений для множества из L последовательных вы-числительных процессов, каждый из которых определяется конкретным значени-ем параметра j, j = 0,…, L−1, порождает многообразие вариантов организации вы-числений. Это приводит к тому, что организация вычислений при параллельнойобработке выступает в качестве объекта исследований, направленных на выборнаилучших вариантов в рамках заданных ограничений на реализацию вычисле-ний. Для выполнения таких исследований необходимы формальные модели, спо-собные синтезировать необходимое многообразие вариантов и анализироватьоценки сложности их пространственно-временных архитектурно-независимыхреализаций. Создание формальной модели, обеспечивающей выполнение такихисследований, создаст базу для реализации обоснованного выбора вариантов ор-ганизации вычислений, приводящего к повышению эффективности параллельнойобработки, за счет появления возможности гибкого согласования алгоритмиче-ских и архитектурных параметров параллельных вычислительных систем. Дости-жение такого результата возможно на основе проектирования вариантов, выпол-няемого на базе симбиоза формальной модели и параметров, определяющих кон-кретные условия реализации вычислений. В каждом конкретном случае модельможет быть расширена путем введения в её структуру указанных параметров. Та-ким образом, установленными причинами необходимости перехода от алгоритмак модели, диктуемыми средой выполнения параллельной обработки, являются: необходимость синтеза множества пространственно-временных вариантовреализации вычислений; необходимость выполнения исследований организации параллельныхния единого описания последовательных и параллельных алгоритмов необходимопостроить композиционные формы известных последовательных алгоритмов иустановить детерминированные правила координации их детерминированныхкомпонент. Такая формальная основа организации параллельных вычислений по-зволит избежать проблем параллельной потоковой организации вычислений, рас-сматриваемых в работе [6] и связанных с недетерминированностью такой обра-ботки. Рассмотрим требования к создаваемой формальной модели, характеризуе-мой архитектурной независимостью, детерминированностью правил композициии координации своих компонент и единством описания параллельных и последо-вательных алгоритмов.2. Требования к модели организации вычисленийв пространственно-временной средеСформулируем требования, которыми должна обладать формальная модельорганизации вычислений в пространственно-временной среде: преемственность (единое описание последовательных и параллельных вы-числений); масштабирование; обеспечение структурного разнообразия вычислений; децентрализация; детерминизм описания компонент и законов их координации; модульность; обеспечение технологии синтеза структур параллельных вычислений.Разработав модель, отвечающую представленным требованиям, можно полу-чить формальный инструмент, позволяющий повысить эффективность параллель-ной обработки и расширить сферу её использования за счет внедрения технологийпроектирования алгоритмов параллельных вычислений. Действительно, модель,предполагающая формальный синтез множества вариантов реализации парал-лельных вычислений, позволит решать проблему обоснованного выбора наилуч-шего варианта. Модель, удовлетворяющая таким требованиям, была построенадля базовых операций ЦОС. Представим путь построения такой модели.3. Последовательные алгоритмы - база построения моделиорганизации вычислений для операций ЦОСВышеупомянутый путь связан с разработкой формального инструмента дляперевода вычислений операций ЦОС в пространственно-временную среду. Пред-ставляемый путь может быть охарактеризован двумя этапами, приводящими кформированию композиционных форм представления операций свертки:10( ) ( ) ( )NqC t x t q y q−==ƒ − ⋅и дискретного преобразования Фурье (ДПФ)10( ) ( ) ,NtqNtS q x t W−==ƒ ⋅где 2 / i NWN =e− ƒ ,характеризующихся многомасштабным представлением внутренней структурыпоследовательных алгоритмов. Первым этапом пройденного пути стала декомпо-зиция входной последовательности данных, основанная на их масштабировании, врезультате выполнения которого область задания данных была преобразована вдвумерную решетку размера N = Lh1, то есть была сжата по временному и расши-рена по пространственному аргументам. В результате был сформирован наборукороченных последовательностей данных xj(t1), j = 0,…, L−1, t1 = h1−1, компози-ция которых приводит к исходной последовательности x(t). Иллюстрация выпол-ненной декомпозиции представлена на рис. 1. Данный этап характеризуется одно-временным использованием объектно-ориентированного подхода и функциональ-ной декомпозиции данных. Полученная форма задания входной последовательно-сти x(t) стала основой для разработки процедур создания композиционных формпредставления базовых операций ЦОС - свертки и ДПФ. Именно благодаря такойдекомпозиции данных удалось реализовать второй этап данного пути и получитьискомые композиционные формы. На этом пути были разработаны процедуры,описания некоторых из них приведены в работах [7 - 13], в результате использо-вания которых и были выявлены эти пространственно-временные композицион-ные формы. Эти формы, эквивалентные исходным формам задания названныхопераций, позволяют синтезировать различные варианты организации вычисле-ний от последовательного до многомасштабного, порождающего различные па-раллельные структуры, а следовательно, описывают как последовательную, так иа. . 0 . N-1t0 h1-1t1L-1j...x(t)x0(t1)xL-1(t1)Масштабированиеh1=N/Lб0 15t0 7t1j0t1j0t17j1. . .1 231 2 3 1......x(t)x0(t1)x7(t1)x(t)x0(t1)x3(t1)x t ( )x0(t1)x1(t1)Рис. 1. Перевод отсчетов входной последовательности из временной средыв пространственно-временную (а), варианты перевода для N=16 (б)параллельную обработку данных. Полученные композиционные формы представ-ления операций ЦОС характеризуются созданием нового класса алгоритмов, на-званных алгоритмами с изменяемой структурой. Можно сказать, что эти алгорит-мы являются моделью организации вычислений операций ЦОС, изначально за-данных в пространственно-временной среде. Эти алгоритмы характеризуютсямногомасштабным описанием внутренней структуры исходного последовательно-го алгоритма. На основе этого описания можно синтезировать различные парал-лельные вычислительные структуры, состоящие из множества однотипных функ-циональных компонент, подобных исходному последовательному алгоритму,сжатых во времени и распределенных в пространстве.Множество разработанных алгоритмов с изменяемой структурой позволилопостроить формальную модель организации параллельных вычислений операцийЦОС. В укрупненном виде созданную модель можно представить с помощьюпространственно-временной среды, ею порождаемой. На основе этой среды про-демонстрируем возможности построенной формальной архитектурно-независи-мой модели.4. Пространственно-временная среда для организации вычисленийопераций ЦОС и возможности моделиПредставленная на рис. 2 пространственно-временная среда сформирована наоснове полученных композиционных форм задания операций свертки и ДПФ,описанных в работах [7 - 13]. Данная среда представляет собой многомасштабноепредставление внутренней структуры пространственно-временной среды после-довательного алгоритма. Эта среда изначально ориентирована на параллельнуюобработку данных. Основываясь на представленной на рис. 2 внутренней струк-туре вычислительной среды, порожденной созданной моделью, можно сделатьследующие выводы. Полученная формальная модель позволяет исследовать раз-личные варианты организации параллельных вычислений путем синтеза и анализапорождаемых ею вычислительных структур, предоставляя возможность обосно-ванного выбора варианта реализации вычислений. Приведем более широкийспектр возможностей, предоставляемых созданной моделью: управление изменениями структуры вычислений  обоснованный выбор проектирование вариантов  решение проблемы согласования между алгорит-мом и архитектурой  повышение эффективности параллельной обработки; сокращение сложности проектирования вычислительных систем и повыше-ние надежности их функционирования за счет представления сложной системысуммой простых; использование всей базы последовательных алгоритмов, благодаря единствуфункциональных компонент модели и известных последовательных алгоритмов; сокращение сложности обработки и повышение её надежности; предоставление более тонкого инструмента для анализа обрабатываемой ин-формации; повышение гибкости вычислений.Широкий спектр представленных возможностей созданной модели позволяетрешать различные задачи, ориентированные на повышение качества параллель-ной обработки информации, её анализа, сокращения сложности обработки данныхи проектирования вычислительных систем, а также качества их эксплуатации ирасширение сферы использования параллельных вычислений.Рис. 2. Пространственно-временная среда для организации вычислений операций ЦОСЗаключениеПоказана необходимость изменения основ организации вычислений при пере-ходе к параллельной обработке данных. Сформулированы требования к характерупредполагаемых изменений, направленных на эффективное использование потен-циальных возможностей параллельной обработки. Предложен путь выполнениятаких изменений для класса операций ЦОС, характеризующийся созданием фор-мальной модели организации параллельных вычислений. Этот путь связан с соз-данием формального инструмента перевода вычислений в пространственно-временную среду. Отличительной особенностью этого пути является его изна-чальная ориентация на создание архитектурно-независимой формальной модели,способной описывать разнообразие вариантов организации вычислений, порож-даемых пространственно-временной средой. Именно эта среда характеризует па-раллельную обработку данных, поэтому, погрузив созданные последовательныеалгоритмы в эту среду, можно обеспечить возможность их реализации путем од-новременной обработки множества подобных им последовательных алгоритмов,сжатых во времени пропорционально расширению пространственной среды. Объ-единение результатов, полученных в отдельных пространственных ветвях, путемих суммирования позволит сформировать общее решение исходного последова-тельного алгоритма. Основой для реализации предложенной схемы вычислений впространственно-временной среде является разработка композиционных формпредставления последовательных алгоритмов. Такие формы были созданы дляопераций ЦОС. Это позволило создать формальную модель организации их вы-числений в пространственно-временной среде, позволяющую синтезировать ианализировать множество возможных вариантов реализации вычислений. Показа-ны возможности разработанной модели. Одной из основных её возможностей яв-ляется возможность выполнения обоснованного выбора варианта вычислений.Реализация этой возможности позволяет повысить эффективность параллельнойобработки за счет согласования архитектурных и алгоритмических характеристиквыбранной параллельной вычислительной системы.

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