Раздел: Документация
0 ... 21 22 23 24 25 26 27 ... 78 2.Специальные алгоритмы обработки сигналов [7, 14, 15]: решения теп-лицевых систем; линейной свертки; рекурсивной фильтрации; циклической свертки; дискретного преобразования Фурье. 3.Другие алгоритмы [12]: решения уравнений в частных производных; сортировки и т. д. 7.4.6. Архитектура и язык волновой обработки Понятие волнового фронта вычислений, являясь прочным теоретическим фундаментом для разработки процессоров с высокопараллельной структурой и языков параллельной обработки, имеет две отличительные черты. 1.Использование понятия волнового фронта приводит к архитектуре, основанной на волновой обработке, которая удовлетворяет принципу Гюйгенса и обеспечивает то, что волновые фронты никогда не пересекаются. Более точно, передача информации между каждым ПЭ и его ближайшими соседями является взаимно согласованной. Всякий раз, когда данные готовы, передающий ПЭ информирует приемник об этом факте, и приемник принимает данные по мере необходимости, а отправителю сообщается о том, что данные использованы. Эта схема может быть выполнена средствами простого протокола установления связи [7, 12, 18]. Волновая архитектура способна обеспечить режим асинхронного ожидания И, следовательно, инвариантна к временной неопределенности, связанной с локальным тактированием, случайной задержкой при передаче и флюктуацией времени вычислений [12, 17 - 19]. Короче говоря, это понятие, по определению, приводит к асинхронной структуре с вычислениями, управляемыми потоком данных, которая хорошо согласуется с технологией СБИС [7, 16]. 2.Использование понятия волнового фронта помогает значительно уменьшить сложность описания параллельных алгоритмов. Для этого предназначен язык MDFL [7] описания вычислительных волновых фронтов и соответствующих потоков данных большого класса алгоритмов, обладающих ранее упомянутыми свойствами локальности и рекурсивности. Вместо программы для каждого процессора в структуре язык MDFL позволяет программисту обращаться к всему фронту процессоров. В противоположность тяжелому бремени составления расписаний решения задач, разделения ресурсов и управления взаимодействием процессоров, часто встречающихся при программировании универсальных многопроцессорных систем, введение понятия волнового фронта может облегчить описание параллельных и конвейерных алгоритмов и значительно уменьшить сложность параллельного программирования. Полное описание перечня операторов языка MDFL и подробности синтаксиса могут быть найдены в более ранних публикациях [7, 12]. Например, полная MDFL-программа для умножения матриц имеет следующий вид: Программа матричного умножении на нзыке MDFL Размер структуры: NX.N Bi k- Выполняемая операция: С = АХ В k-й волновой фронт: с © = с Й-1) + аЪц, к = 1, 2,..., N. Исходные данные: матрица А хранится в модуле памяти (МП) слева (хранится строка за строкой). Матрица В хранится столбец за столбцом в МП сверху. Выходные данные: результат получается в регистрах С каждого ПЭ. 1:BEGIN SET COUNT N; REPEAT; WHILE WAVEFRONT IN ARRAY DO 5:BEGIN FETCH A. LEFT; FETCH B. UP; FLOW A. RIGHT; FLOW B. DOWN; (* Now form С: = С + A x B) 10:MULT A. B, D; ADD C. D, C; END; DECREMENT COUNT; UNTIL TERMINATED; 15:ENDPROGRAM. Мощность и гибкость программирования на языке MDFL для волновых процессоров лучше всего демонстрируется широким перечнем алгоритмов, которые могут быть запрограммированы на этом языке [7]. Примеры программ приведены в [7,12]. 7.5. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ И СРЕДСТВА АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ ДЛЯ РАЗРАБОТКИ СБИС-СТРУКТУР Для развития высокопараллельных матричных процессоров совершенно необходим рывок в программном обеспечении и технологии автоматизированного проектирования. С одной стороны, наиболее важным архитектурным вопросом при разработке СБИС-структур является обеспечение модульности, связей и системной синхронизации. С другой стороны, алгоритмы должны обладать свойствами рекурсивности и локальности. Таким образом, совместное архитектурное и алгоритмическое рассмотрение формирует основу для развития программного обеспечения и техники автоматизированного проектирования структур процессоров на СБИС. Алгоритмические свойства естественно приводят к систолическим и волновым процессорным матрицам, в которых эффективно используется большое число модульных и локально связанных СБИС-процессоров. Для разработки гибких и экономичных структур необходимо тщательное исследование требований, относящихся к программному обеспечению матричных процессоров. Основная проблема состоит в том, чтобы найти выразительную, легко понимаемую форму записи параллельного алгоритма, допускаю- 149 щую возможность компиляции из нее эффективных СБИС-схем и (или) машинных команд. Для этого предлагаем методологию, которая позволяет, используя мощную абстрактную систему обозначений иерархически и рекурсивно переходить от алгоритмов к графам потока сигналов (ГПС). Предлагаем также процедуры преобразования ГПС в систолические или волновые матрицы и, в конечном счете, в их аппаратную реализацию на СБИС. Основой системы проектирования HIFI (иерархической интерактивной по-токографовой интеграции) [24] является представление параллельных алгоритмов в форме, которая бы легко понималась человеком и давала возможность компилировать из них эффективные СБИС-схемы и (или) машинные команды для процессоров. По существу, структурные свойства параллельных рекурсивных алгоритмов указывают на осуществимость иерархического и итеративного потокографового метода проектирования матричных процессоров на СБИС. Метод проектирования HIFI основан на этом иерархическом итеративном и рекурсивном отображении. Во-первых, требуется, чтобы способ описания алгоритма позволял выражать параллельное пространственно-временное распределение операций, встречающихся в алгоритмах обработки сигналов, в простой и ясной форме. Затем из этого алгоритмического описания вьшодится детальное структурное описание, основанное на предварительном определении примитивных модулей. Имеются два основных класса параллельных алгоритмов обработки сигналов: локально рекурсивные и "идеальной тасовки"; оба класса основаны на рекурсивном вычислительном принципе "разделяй и властвуй". Эти структурные свойства приводят к идее системы проектирования HIFI, в которой осуществляется тесная взаимосвязь между представлением рекурсивных алгоритмов в абстрактном виде, графовым и функциональным описаниями, процедурами преобразования, взаимооднозначным отображением между графическими и текстурными кодами, моделированием, верификацией и кремниевой компиляцией. Система проектирования HIFI предлагает разработчику механизмы для временного и структурного разложения алгоритмов и процессов. С помощью этих двух методов разработчик может выполнить пошаговое усовершенствование при иерархическом проектировании [24]. В окончательном виде система HIFI будет обладать следующими свойствами: 1)выразительностью: система HIFI должна дать средства для описания параллельных пространственно-временных процессов, встречающихся в алгоритмах обработки сигналов в естественном виде; 2)отсутствием чрезмерной детализации: иерархическое описание и четкое разделение между разработкой виртуальной и физической машины должны позволить разработчику акцентировать свое внимание на соответствующем уровне детализации; 3)простотой: ядро проектируемой системы, т.е. проектируемые объекты и операции над ними, должно быть простым, однако нужно позаботиться о том, чтобы операции были достаточно мощными. Наряду с алгоритмическими принципами в языке, используемом, в системе проектирования HIFI, большое значение придается аппликативному 150 функциональному описанию. Здесь под термином "аппликативное" просто подразумевается отсутствие последствия. (Другими словами, здесь нет памяти и, следовательно, краевых эффектов). В действительности при таком проектировании используется расширенная система функционального программирования (ФП). Система функционального программирования представляет собой простую аппликативную систему, в которой "программы" - простые функции без переменных; она основана на фиксированном множестве комбинационных форм, называемых функциональными формами. В терминологии системы проектирования HIFI вершины графов потока сигналов описываются на языке формального функционального програм-мировашя (ФФП) [25] с усилением понятия состояния (в котором отражается "история" системы). Программа, написанная на таком языке, может воздействовать на поведение последующих программ, изменяя содержимое памяти системы [25]. Это приводит к модели в виде апгшикативной системы с изменяемым состоянием (АСИС)1. В системе HIFI сложный граф потока сигналов предлагается рассматривать как совокупность аппликатив-ных систем с изменяемым состоянием, что позволяет разработчику мысленно охватить множество задач, выполняемых параллельно. Несколько упрощая (для наглядности), можно сказать, что граф потока сигналов, состоящий из вершин, соответствующих как бы мгновенному выполнению операции, и ребер, соответствующих временной задержке, достаточен для представления совокупности аппликативных систем с изменяемым состоянием. Кроме того, такой граф явно показывает структуру СБИС-матрицы. Далее кратко излагаются основные вопросы методологии проектирования в системе HIF1 [27]. 7.5.1. Отображение алгоритмов в процессорные матрицы В большинстве прикладных задач обработки сигналов многократно используются несколько основных алгоритмов с широким набором данных. К ним относятся алгоритмы преобразования Фурье, корреляции, матричного умножения, обращения матриц, метод наименьших квадратов. Поэтому необходимо провести полный Классификационный анализ наиболее часто встречающихся параллельных алгоритмов. Например, два известных класса алгоритмов могут быть идентифицированны как локально рекурсивные и идеальной тасовки. Оба класса принадлежат к важным схемам вычислений, в которых используется рекурсивный принцип "разделяй и властвуй", в конце концое приводящий к иерархическому и рекурсивному методу описания. Мы подчеркнули рекурсивную природу алгоритмов обработки сигналов. Инструментом прямого представления последовательности рекурсий яв- 1В оригинале "applicative state transition system (AST system)". С нашей точки зрения, русский эквивалент "аппликативная система с изменяемым состоянием" наиболее точно передает смысл, вложенный в этот термин его изобретателем Бэкусом в работе [25]. - Прим. ред. ляется граф потока сигналов, точнее, вход-выход вершин в графе указывает на порядок вычисления, а ребра, соответствующие задержке, обозначают разделение и упорядочение двух последовательных рекурсий. Эта точка зрения хорошо согласуется с точкой зрения Бэкуса, выраженной в статье [25], в которой он предлагает освободить программирование от "стиля Неймана" с помощью так называемых аппликативных систем с изменяемым состоянием. Таким образом, система HIFI лежит в основе разработки методов автоматизации программного и аппаратного обеспечения, поскольку, во-первых, граф потока сигналов обеспечивает мощный абстрактный аппарат для выражения параллелизма и, во-вторых, несмотря на это, переход от графов к реальным систолическим волновым матрицам достаточно прост [27]. 7.5.2.Сети, основанные на графах потоков сигналов и аппликативных системах с изменяемым состоянием Согласно системе обозначений, принятой в графе потоков сигналов, вершины соответствуют операциям, выполняемым с нулевой задержкой, и описываются в терминах аппликативных функциональных систем. Ребра временной задержки и функциональные вершины представляются совокупностью аппликативных систем с изменяемым состоянием [25, 26, 28]. В совокупности они полностью выражают последовательность операций внутри и между рекурсиями. Необходимо заметить, что оператор задержки D здесь рассматривается как оператор, указывающий последовательность действий (в противоположность синхронным устройствам), и может быть представлен или глобально тактируемой задержкой, или самотактируемым, управляемым данными разделителем (сравните с теоремой об эквивалентных преобразованиях [27, разд. V])." 7.5.3.Рекурсивные структуры и состояния Рекурсивное свойство алгоритмов естественно приводит к полезному понятию состояния, совместимому с тем, что используется в аппликативных системах с изменяемым состоянием. Короче говоря, анпдикативвые отображения часто удобо разложить на рекурсивно определяемые "подотоб-ражения". Определение состояния содержит в себе необходимую и достаточную информацию о предыстории вычислений. В примере на рис. 7.2 состояние естественно ассоциируется со значениями или обьектами, пршшеанны-ми ребрам-задержкам. Эти рекурсивные вычислительные схемы приводят к определенным примитивным структурам межсоединений. Семантика формальной записи таких структур может быть сделана очень сжатой и точной. (Семантика структурных примитивов также будет позволять дальнейшее структурное уточнение.) Например, введение понятия локальной рекурсивности приводит к локально связанным структурным примитивам, применимым к большинству алгоритмов обработки сигналов, таких как свертка, корреляция, LU- и QR-разложения. F 7.5.4. Иерархическое описание Методология иерархического проектирования на основе потоковых графов оказывается очень эффективной при описании сетей большой степени сложности. При такой методологии вершины графа описываются иерархически либо их "поведением" (ашшикативный тип описания), либо соответствующим этому поведению потоковым графом (структурный тип) [29, 30]. Чтобы описания были физически реализуемыми, вершины примитивного уровня должны быть описаны через модули с физически реализуемым поведением. Варьируя уровнем примитивных модулей, разработчик может выбрать предпочтительный уровень детализации. Структурное описание будет задано отображениями "выход-вход", в то время как описание поведения примитивного уровня будет задано отображениями "вход-выход". Иерархическое описание включает в основном последовательное пошаговое уточнение функциональных вершин. Иллюстрацией мощности такого описания может служить имеющееся в распоряжении разработчика право замены вершины линейным множеством вершин и создание при этом структуры новой размерности. Например, процессорная матрица для LU-разло-жения (см. [27, рис. 11]) имеет в действительности двухуровневое иерархическое представление: первый уровень - горизонтальная одномерная структура с N вершинами, а на втором уровне каждая вершина, кроме того, разложена на N вершин. Эта же схема непосредственно применима для вычислений QR-разложения и двух- (или трех-) мерной корреляции изображения и т.д. 7.5.5. Переход к СБИС-матрицам с конвейерной обработкой и устойчивостью к отказам В работе [27] развиты некоторые систематические процедуры преобразования графа потока сигналов в конвейерные структуры типа систолических или волновых матриц, приводящие к реализации их в виде СБИС-аппаратуры. Они включают в себя автоматическую процедуру систолизации (по так называемым правилам локализации сечений), оптимальное планирование, волновое квитирование и т.д. Иерархический анпликативный подход определяет простоту и гибкость, необходимые для того, чтобы расчленять большую задачу на подзадачи, пригодные к решению на небольших процессорных матрицах, и (или) для того, чтобы обеспечить отказоустойчивость. Эти дополнительные свойства могут иметь решающее значение для эффективности таких структур. Правила локализации сечений потенциально очень полезны для разработки отказоустойчивых структур. Для систолических структур без обратной связи показано, что изменение задержки в сечениях позволяет получить высокую степень отказоустойчивости. Исследование, проведенное в [27], дает теоретическую основу для повышения отказоустойчивости процессорных матриц с обратной связью с помощью процедуры изменения задержек в сечениях. Интересно то, что при незначительной модификации свойство самосинхронизации волновых структур позволяет достичь того же уровня отказоустойчивости без какого-либо изменения задержек. 0 ... 21 22 23 24 25 26 27 ... 78
|
