автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Специализированные устройства предварительной обработки сигналов в системах реального времени

Я л

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ •ТОЧНОЙ МЕХАНИКИ И ОПТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

На правах рукописи

ТРОПЧЕНКО АЛЕКСАНДР ЮВЕНАЛЬЕВИЧ

СПЕЦИАЛИЗИРОВАННЫЕ УСТРОЙСТВА ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ СИГНАЛОВ В СИСТЕМАХ РЕАЛЬНОГО' ВРЕМЕНИ

Специальность 05.13.05 - Элементы и устройства вычислительной

техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Санкт-Петербург - 1995

Работа выполнена в Санкт-Петербургском Государственном Институте Точной Механики и Оптики (Техническом Университете)

Научный консультант:

доктор физико-математических наук,

ведущий научньм сотрудник Романов Ю. Ф.

Официальные оппоненты:

доктор технических наук профессор'Герман-Галкин С.Г. доктор технических наук профессор Лисс А. Р. доктор технических наук профессор Фомичев B.C.

Ведущее предприятие: Научно-исследовательский институт

Защита диссертации состоится .^с^рта 1995 г.

в I'5 — часов на заседании специализированного совета Д 053.26.02 при Санкт-Петербургском Государственном Институте Точной Механики и Оптики по адресу: 197101. Санкт-Петербург, ул. Саблинская 14.:

С диссертацией можно ознакомиться в библиотеке института

Автореферат разослан 1995 г.

телевидения (г. С. -Петербург)

I

Ученый секретарь

специализированного

совета

д.т.н., профессор

А. В.Ушаков

- г -

I. ВВЕДЕНИЕ

Актуальность проблемы. Прогресс вычислительной техники в последние десятилетия привел к широкому внедрению . методов цифровой обработки информации практически во все области научных исследований и народно-хозяйственной деятельности. При этом среди различных применений средств вычислительной техники одно из важнейших мест занимают системы цифровой обработки сигналов, нашедшие использование при обработке данных дистанционного зондирования, медико-биологических исследований, решении задач навигации аэрокосмических и морских объектов, связи, радиофизики и цифровой оптики.

Как правило, подобные системы содержат специализированные технические средства для цифровой предварительной обработки сигналов (ЦПОС) и специальные технические средства .для вторичной обработки сигналов. Средства предварительной обработки предназначены для обработки исходных сигналов, наблюдаемых в общем случае на фоне случайных шумов и помех различной физической природы и представленных в виде лискретных цифровых отсчетов, с целью обнаружения и выделения полезного сигнала, его пеленгования и оценки характеристик обнаруженного сигнала. Полученная в результате предварительной обработки полезная информация поступает в систему вторичной обработки для анализа, классификации и архивации.

Основными процедурами предварительной обработки сигналов являются процедуры дискретных ортогональных преобразований (ДОП) в различных функциональных базисах, процедуры линейной алгебры, линейной и нелинейной фильтрации.

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

порядка Ю9 - Ю11 оп/сек. Такое быстродействие может быть достигнуто лишь при использовании специальных функционально-ориентированных вычислительных средств параллельно-конвейерной архитектуры.

При проектировании специализированных функционально-ориентированных конвейерных к зистолическил устройств граф подлежащего реализации алгоритма отображается в совокупность связей конкретного типа вычислительных ячеек (ВЯ). что в конечном счете определяет структуру устройства.

Процедуры о&работки одномерных данных достаточно легко отображаются на структуры в виде цепочки последовательно-соединенных 'ВЯ, для которых ввод/вывод данных осуществляется единственны^ потоком. Однако процедуры.матричной алгебры реализуются 'на функционально-ориентированных устройствах, имеющих ортогональные или гексогональные связи между ВЯ. Подобные структуры требуют организации множества параллельных синхронных потоков ввода/вывода данных, что не учитывает реальные условия организации потоков входных/выходных данных в системах предварительной обработки данных, и . отличаются чрезмерными аппаратурными затратами.

Поэтому актуальной является разработка способе*, конвейеризации вычислительных процедур цифровой обработки сигналов' при их отображении на граф с линейно-последовательными связями между вершинами и единственным входным потоком данных, а также единых принципов построения систолических и конвейерных структур с линейно-последовательным типом связей между их ВЯ как для выполнения процедур одномерной обработки данных, так и для реализации процедур многомерных и быстрых преобразований,

Решение подобной проблемы позволяет достичь высокой производительности вычислительных средств, при приемлемых аппаратурных затратах и повысить тем самым технические характеристики устройств цифровой обработки сигналов.

Предметом исследования являются алгоритмы и устройства цифровой обработки сигналов в РМВ, а также способы конвейеризации вычислений при их выполнении.

Цель рабрты заключается в развитии алгоритмических методов и аппаратурных средств дл=- цифровой предварительной

обработки сигналов, позволяющих оптимизировать организацию вычислений и структуру вычислительных устройств за счет унификации базовых операций и способа конвейеризации процедур одномерных, многомерных ' и быстрых преобразований, -а также согласования структуры графов алгоритмов с организацией входного потока данных.

Задачи исследования:

- получение унифицированных способов конвейеризации и систолизации алгоритмов предварительной обработки сигналов;

- разработка унифицированных по структурной организации конвейерных и систолических вычислительных устройств для спектральных преобразований;

- разработка унифицированных структур конвейерных и-систолических вычислительных устройств для линейной и нелинейной .фильтрации сигналов;

- разработка структур и схемотехнических решений основных элементов предлагаемых устройств конвейерного и систолического типов для предварительной обработки сигналов.

Научная новизна полученных . результатов заключается в следующем:

- разработаны унифицированные способы конвейеризации алгоритмов предварительной обработки сигналов, включая алгоритмы дискретных ортогональных преобразований, линейной алгебры и нелинейной фильтрации, на основе принципов покомпонентно-независимого формирования результата и разрядно-сре-зовой обработки применительно к организации ввода/выаола данных б виде единого потока;

- получен новый тип полусистолических структур с линейно-последовательными связями между ВЯ, реализующих покомпонентно-независимый принцип формирования результатов обработки для выполнения алгоритмов многомерных и быстрых преобразований;

- разработаны единые принципы структурной организации высокопроизводительных конвейерных и■систолических' устройств для выполнения одномерных, одномерных многоканальных, многомерных. и быстрых дискретных ортогональных преобразований в Фурье-подобных базиса;-., включая преобразования Фурье, Хартли, Уолша-Адамара, а также для решения задам линейной филь-

трации и матричной алгебры - умножения и обращения матриц, решения систем линейных алгебраических уравнений:

- разработаны структуры ■ конвейерных -и систолических устройств для нелинейной (ранговой) фильтрации двумерных сигналов на основе культи:истограммных и разрядно-срезовых алгоритмов, реализующих принцип последовательного подсумми-рованкя результата, и универсальных устройств линейной и нелинейной фильтрации на их оснозе;

- получены аналитические выражения для оценки производительности и объема аппаратурных затрат для предлагаемых конвейерных и систолических устройств цифровой обработки сигналов;

- разработаны структуры макроконвейеркых устройств предварительной обработки сигналов на базе перспективных высокопроизводительных элементов - сигнальных транспьютеров.

Практическая ценность выполненных исследований состоит в следующем:

- разработаны схемотехнические решения унифицированных вычислительных и запоминающих ячеек вычислительных устройств различного назначения конвейерного и систолического типов;

- сформулированы рекомендации по выбору разр;:_' Гости вычислительных элементов систолических и полусистолических, устройств для обработки сигналов в реальном времени;

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

Полученные результаты находят применение при проектировании высокопроизводительных цифровых средств обработки сигналов для систем ЦПОС различного'назначения.

Основные научно-методические разработки, представленные в- диссертации, внедрены на предприятиях Ю-9317, А-1586. ККО БНЦ ГОИ им. С.И. Вавилова и в ЛИТМО.

На защиту выносятся:

- унифицированный способ конвейеризации вычислений одномерных. многомерных и быстрых ортогональных преобразований к процедур матричной алгебры на основе принципа покомпонентно-независимого Нормирования результата;

принцип единой структурной организации высокопроизво-

дительных конвейерных и систолических устройств для выполнения одномерных, одномерных многоканальных, многомерных и быстрых дискретных ортогональных преобразований в Фурье-подобных базисах, включая преобразования Фурье, "Хартли, Уол-ша-Адау.ара, а также для решения задач линейной фильтрации и матричной алгебры - умножения и обращения матриц, решения систем линейных алгебраических уравнений;

- способ конвейеризации и унификации процедур линейной и ранговой фильтрации на основе разрядно-срезозой обработки и последовательного подсуммирования результата;

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

-.структуры универсальных устройств линейной и нелинейной фильтрации, реализующих унифицированные разрядно-срезо-вые конвейерные процедуры;

- экспериментальные результаты моделирования процедур ЦПОС, положенных в основу структурной организации разработанных устройств;

- полученные оценки производительности й объема аппаратурных затрат предлагаемых конвейерных структур;

- принципы построения проблемно-ориентированных иерархических систем на перспективной элементной базе типа сигнальных транспьютеров.

Апробация работы. Основные положения и результаты исследований по теме диссертации докладывались и обсуждались на II Всесоюзной конференции "Методы и средства обработки сложной графической информации"(Горький, 1985), III и IV Всесоюзных конференциях "Методы и микроэлектронные средства цифрового преобразования и обработки сигналов" (Рига, 1986 йо 1989), VI Всесоюзной школе-семинаре "Распараллеливание обработки информации" (Львов, 1987), I Всесоюзной конференции "Проблемы создания суперЭВМ, суперсистем и эффективность их применения" (Минск, 1987), II Всесоюзном совещании "Высокопроизводительные вычислительные системы" (Таллинн, 1988), III Всесоюзном совещании "Конвейерные вычислительные системы" (Киев, 1988), IV Всесоюзной конференции "Математические ме-

тоды распознавания образов" (Рига, 1989), I Всесоюзной конференции "Однородные среды и систолические структуры" (Львов, 1990), II Всесоюзной конференции по оптической обработке информации (Фрунзе. 1990). II Региональной конференции "распределенная обработка информации" (Новосибирск, 1987), Отраслевой юбилейной конференции во ЕНИИ "Альтаир' (Москва. 1985). научных семинарах ЛИТМО, ВНИИ "Альтаир" и ЦНИИ "Мор-физприбор" (Ленинград).

Публикации. Основное содержание диссертации изложено в 34 работах, включая 1 книгу и 10 авторских свидетельств.

Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения и списка цитируемой литературы/ Она содержит 277 страниц машинописного текста, 71 рисунок и И таблиц. Список литературы включает 168 наименований.

'II. СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертации. формулируется направление проведенных исследований, дается общая характеристика работы и приводятся основные результаты.

Первая глава содержит аналитический обзор существующих алгоритмов и аппаратных средств для систем предварительной обработки сигналов.

В первом разделе первой главы рассматриваются алгоритмические методы предварительной обработки сигналов.

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

В начале раздела анализируются спектральные методы обработки сигналов. Вопросы приложений спектральных методов достаточно полно исследованы в работах Л.Рабинера, , Б.Гоулда, Л. П.Ярославского и ряда других отечественных и зарубежных специалистов.

Наиболее известным спектральным преобразованием является преобразование Фурье (ДШО. Для сокращения объема вычислительных затрат при выполнении ДПФ 'используются быстрые ал-

горитмы. Б основе процедур быстрого преобразования Фурье (БПФ) лежат свойства матрицы ядра преобразования, а именно, свойство цикличности используемых ортогональных функций и мультипликативности.

Бопросам синтеза быстрых алгоритмов, построения перестановочных матриц и факторизации матриц базисных функций посвящены работы Л. П.Ярославского, Г. А.Кухарева,.'Л. Рабинера и ряда других отечественных и зарубежных авторов/

Для обработки действительных данных более удобным является дискретное преобразование Хартли (ДПХ), позволяющее отображать действительные исходные данные в спектр, описываемый действительными числами. ' Важным свойством данного преобразования является простая и однозначная связь между компонентами спектра Хартли h"k и компонентами спектра Фурье fk.

Кроме ДПФ и ДПХ при обработке сигналов используются и другие типы дискретных ортогональных преобразований (ДОП) -косинусное преобразование, преобразования Адамара, Уолша, Хаара.

Вторую группу алгоритмов предварительной обработки составляют процедуры линейной фильтрации и адаптивной'обработки сигналов.

Основой одномерных процедур линейной фильтрации является операция умножения вектора на матрицу, к таким же операциям может быть сведена и процедура цифровой двумерной свертки. При размерах окна сканирования, значительно меньших размера всего изображения, предпочтителен прямой алгоритм вычисления свертки, обеспечивающий меньшее время вычисления. Дальнейшего сокращения времени выполнения свертки можно достичь за счет распараллеливания вычислений, что нашло отражение в работах Л. Г(. Ярославского, Е.Ф.Очина, С.Г.Седухина и других отечественных и зарубежных авторов.Наименьшее время вычисления свертки обеспечивается при распараллеливании по" разрядным срезам, поскольку в этом случае практически исключается операция умножения.

Среди алгоритмов адаптивной обработки важное место занимают, алгоритмы, основанные на формировании ковариационной матрицы помех и последующем ее обращении, Для обращения матриц используют, как правило, метод Гаусса или Гаусса-Жорда-

на. Однако процедура обращения матрицы является достаточно трудоемкой. Существенного .сокращения времени обращения ковариационной матрицы можно достичь, используя.параллельно-конвейерные процедуры. Большинство подобных процедур требует организации параллельного доступа к исходным данным, что трудно осуществить практически.

Третью группу алгоритмов составляют алгоритмы нелинейной фильтрации сигналов. В их основе лежат операции сортировки и поиска элемента с заданным рангом К, т.е. элемента, занимающего Р.-ю позицию в упорядоченном по возрастанию кортеже элементов, попавших в окно сканирования размером М х М элементов.' Среди работ, посвященных данным методам, следует выделить работы Л.П.Ярославского, Е..Ф. Очина, У.К.Прэтта, Делмана. Даниельсона. Подобные алгоритмы могут быть подразделены на гистограммные алгоритмы, в которых для поиска элемента заданного ранга в язном виде используется гистограмма распределения амплитуд элементов из окна сканирования, и безгистограммные, в которых в явной форме не строится гистограмма распределения. К последним относятся разрядно-сре-зозые и сортирующие алгоритмы.

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

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

В конце первого раздела рассматриваются способы конвейеризации алгоритмов ЦПОС.

Конвейеризация вычислений на уровне отдельной процедуры предусматривают декомпозицию ее алгоритма на ряд однотипных рекуррентко-связанных и простых вычислительных. операций еди-

наковой длительности, при этом граф вычислительной процедуры должен обладать свойством локальности связей.

Анализ различных способов конвейеризации вычислений показал, что для вычисления одномерных ДОП и свертки наиболее удобен .алгоритм прямого умножения вектора данных на матрицу ядра, который может выполняться.как в параллельной, так и в конвейерной форме.

Для конвейеризации двумерной линейной фильтрации удобен алгоритм с последовательным суммированием произведений столбцов ядра свертки и сканируемой полосы изображения. Конвейеризация процедур ранговой фильтрации вычислений по схожей схеме выполняется, в частности, в разрядно-срезовых алгоритмах, где каждый следующий разрядный срез обрабатывается отдельно с учетом результата обработки предыдущего среза. Подобным же образом может быть выполнена и конвейеризация разрядно-срезового алгоритма свертки.

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

Во втором разделе первой главы рассматриваются специализированные вычислительные средства для предварительной обработки сигналов.

' В начале раздела рассматривается современная элементная база, используемая для построения специализированных вычислительных средств обработки сигналов в реальном времени. Делается вывод о перспективности использования сигнальных процессоров типа ТМБЗго и транспьютеров типа Т9000 для построения аппаратных средств ЦПОС. Из отечественной элементной базы для построения специализированных аппаратных средств ЦПОС наиболее перспективны однородные среды типа. "Райта", комп-

лект СБИС для построения сигнальных процессоров типа К1843 и разрабатываемый отечественный сигнальный транспьютер.

Далее рассматриваются основные варианты построения систем предварительной обработки сигналов,.

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

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

Далее анализируются структуры функционально-ориентированных конвейерных устройств.

Сравнительно широкое распространение получили систоли-' ческие структуры с линейно-последовательным и ортогональным типами связей между ВЯ. Подобные структуры, ориентированные на выполнение тех или иных процедур предварительной обработки сигналов, например, вычисления свертки, перемножения матриц. выполнения спектральных преобразований исследовались в работах С. Г. Седухина, Ю.С.Каневского. М. А. Фрумкина. Гун Сун Юаня.

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

Так. большинство процессоров линейной фильтрации организовано по принципу линейно-последовательной связи между ВЯ. в то время как для процессоров БП£ и матричной■ алгебры ха-

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

Во второй главе рассматриваются вопросы конвейеризации и систолизации алгоритмов предварительной обработки сигналов применительно к реализации их на структурах конвейерного типа .с линейно-последовательным типом связей .между ВЯ. •

В первом разделе второй Главы рассматривается организация конвейерных вычислений при реализации ДОП.

Для процедур одномерных ДОП наиболее эффективным оказы- ■ вается конвейерный способ прямого умножения вектора данных на матрицу коэффициентов, в основе которого лежит итеративная схема вычислений с покомпонентно-независимым формированием результатов. Применительно к процедуре ДПФ ее можно представить в виде:

fk.il - Гк.п-1 + Хп-КМ И'»-1»«*-". П-7ЖГ (1)

где Гк.п - значение накопленной суммы в п-й такт для к-го отсчета спектра; Гк.п-1 ~ предыдущее значение суммы на (N-1)-м-такте: и(п*К)(К"п - значение весового множителя ядра преобразования Фурье, поступающего в п-й такт при вычислении к -го отсчета спектра, а х„.к+1 - значение элемента вектора исходных данных, участвующего в формировании к-го отсчета спектра на п-м такте, ^ г, = 0 для п < к , причем И* = ехр(-32як/Ю, к-Т7¥.

Далее рассматривается вычислительная процедура формирования результатов многоканального ДОП:

Г,(к>=1 Х1(п)¥(п-п(к-о< к,П=ПС (2)

где 1=1,М, 1 - индекс, указывающий на принадлежность результата ДПФ г„(1) и исходных данных х„(1) к 1-му каналу данных. "

Входные данные и результаты при такой обработке могут быть представлены в виде Х=£Х( 1' Х(2\.. ,Х(Н)]Т, Г=[ГГ1\ Г(2)... ,Р(И>]Т, где Х<п> = [х(п>1.х(п,г. ,х|п1,]тиГ(к1 = [Г«1"!.'^11^.--- Г( к >,.,]т, к, п= ГЛГ

При указанном представлении данных процедура многока-

нального ДПФ может быть записана для векторов: pti ) = i х("1.

р(2) _ | МП-1Х(Ч)>

р(3) _ £ W2(n-l)x(n),

р( И ) = j W( 11-1 ) ( n- 1 )Х( г ).

Особый интерес представляет конвейеризация вычислений при выполнении многомерного ДПФ.

При векторном (по строкам) представлении исходных данных и результатов преобразования Хц = t (xi j 2. • •. ХЩ) , (Хг 1 .х22...,хгм), ... (хи j,ХВ2,..,хНц )] FN=[ (ч 1- fia - • • • ГЩ) • <^21 ■ ^гг- • • ■ ¡"ги) • • • > (fui - Гц г - • • • ^нн ) 11 выражение для FH может быть записано следующим образом :

F„ = (Ей © Е„) Х„. (4)

где символ ® обозначает операцию прямого произведения матриц.

Из выражения (4) следует возможность использования следующей параллельно-конвейерной процедуры двумерного ДПФ: Fll) =1 ЕНХ(П>.

р(2) = р< 3 ) =

W""1 (ЕцХс"1 ). WZ(n-»>(ЕНХ<П>),

(5)

рои = ^ М<"-1>(П_1>(Е„Х(">)

л **

Важным достоинством представленной процедуры является отсутствие в явном виде операции транспонирования матрицы промежуточных результатов. В выражении (5) преобразование вида ЕНХ(П) для каждого п может быть выполнено всего лишь один раз с использованием полученного результата во всех параллельных ветвях вычисления Г(к) . Этот факт наряду с наличием рекуррентно связанных операций умножения и суммирования . частичных произведений позволяет использовать систолический принцип формирования результатов.

Аналогично выражению (5) может быть выполнено и трехмерное преобразование Фурье:

1} - I [Е» (Х„<п) Е„)].

рк(2) . £ мк-1 [еь (х„<»> £„)].

(6)

X М(н-»)(П-1)[ЕН(ХК(П) Ен)] матрица порядка N. определяющая К-ю страницу ку-

где FH(k)

ба результатов трехмерного ДПФ (к=1.Л): Х„<п) - матрица порядка N. определяющая п-ю страницу куба данных. В формуле (6) выражение в квадратных скобках есть не что иное, как двумерное ДПФ. выполняемое по странице данных с номером п (п-ПГ).. Анализ выражений (3).(5) и (6) свидетельствует об их вычислительной однотипности,, что позволяет использовать для их реализации унифицированные вычислительные средства.

Конвейерные алгоритмы БПФ так же могут быть построены при использовании принципов, положенных в основу предложенной конвейерной процедуры многомерного ДПФ. Однако в отличие от. ш-мерного ДПФ при конвейерном выполнении БПФ необходимо обеспечить умножение промежуточных данных после каждой итерации процедуры БПФ (после выполнения обработки по каждой из координат сформированного многомерного куба данных) на дополнительные фазирующие множители. _

Вычисления на каждой итерации ш Ш'= гм.т « 1.М) можно представить как единую процедуру:

к. т

.т

г к * г 1 . т

1 к«■ ( г-1 ) 1 .т

МРк

ЕГ

№ 0 0-••О

О Кк о---о

о о м2к о

,т- 1

,т- 1 + 2 1 .т-1

(7)

п-1

О 0 о- • -К""1 »4 Здесь 1УрК= ехр(~32ярк/Мп). р= О.г-1, 11т= гт, 1= И,,.,- гга" К = 0,1-1. Компоненты вектора с индексом (т-1) вычисляются на (т-1)-ой итерации. Элементы диагональной матрицы - это итерационные (поворачивающие) множители. Матрица Ег определяются следующим образом:- _

Ег = 11 ехр(-32згкп/г) II ; к.п = О.г-1 Перед первой итерацией исходные данные должны быть подвергнуты г-ичной инверсной перестановке.

Конвейеризация вычислений по выражению (7) с разделением операций умножения на диагональную матрицу и матрицу Е,. порождает комбинированную схему формирования результатов -г-точечное ДПФ реализуется по схеме покомпонентно независимого формирования результатов, а умножение на диагональную матрицу выполняется посредством рекурсивно-мультипликативного изменения множителей ядра преобразования..

Выполнив матричные операции, определяемые выражением (7). можно перейти к системе выражений, явно задающих индексные зависимости для входящих в вычисления операндов. В частном случае, при N = 3®, получаем:

fn.n-fk.B-! + Гк + 1.в-,ехр(.-32як/Мв) +

flfl.m-fk.B-l + Ги^.а-^ХРЕ-Згжк/Нп + 1/3)] +

.щ-^хрг-лглсгк/м,,, + 2/3)]; (8) ^♦21.™ = Гк.т-1 + 1"км ,гп-1ехр[-32Я(к/^. + 2/3) + Г к ♦ а I. а -1 ехР 3 (2к/|\ + 1/3). где Кт= Зп. 1 = Згп"1, к = 0, (3я1"1 - 1). Компоненты Гк.п.

»1.111 11 ^»¡л.т образуют подвектор длиной 3й. Так как N = 3м, то после.ш-ой итерации получается 3*!"т подвекторов. Каждая последующая итерация объединяет 3 подвектора, полученных на предыдущей итерации.

Выражение'(8) в явной форме определяет процедуру формирования результатов БПФ по схеме с покомпонентно-независимым формированием результата. ■

Если длина одномерной последовательности данных может .быть представлена в виде произведения взаимно-простц^ множителей N = М) х М2 х N3 х ... Лга. то организация вычисления БПФ в конвейерном режиме будет аналогична организации конвейерного режима вычислений ДПФ многомерных данных.

Принципиально важным при этом является то, что исходные данные перед их обработкой необходимо упорядочить предварительно -в лексикографическом порядке и представить в многомерной форме.

Далее рассматриваются процедуры быстрого преобразования Хартли при различных основаниях.

Алгоритм быстрого преобразования -Хартли (БПХ) отличается от БПФ. поскольку элементы матрицы Нм не обладают свойством мультипликативности, поэтому базовая операция типа "бабочка" видоизменяется по сравнению с процедурой БПФ и приобретает следующую форму для и-й итерации (при г = 2): Нц.п "Кц.п-1 +Нк,1>п_, соз(Як/1) +

Нр.т., зш (ЯП/1) - КК.В., + Бк . г, -1 (9) н*,1.а = - Нк<1.„., сс5(лк/1) -

НР.*-, э^^кЛ) . Нк .в.., • - в^...,.

где р = 1 + Ц-Юпоа 1: а индекс к =(п)то<3 ^ Бц_1 - сумма слагаемых, содержащих косинусные и синусные множители,

Выполненный анализ процедуры Хартли при различных основаниях алгоритма позволил установить, что для общего случая N = гм. бабочка БПФ трансформируется в бабочку БПХ заменой в свободных и косинусных слагаемых Гц4д1 на Нк<д1. а также заменой в синусных слагаемых на Нр(,.,>.

Вычисление БПХ при основании г, согласно изложенному алгоритму, также может быть реализовано в конвейерном режиме по способу покомпонентно-независимого формирования .результатов.

В конце раздела устанавливается взаимосвязь между традиционным двумерным преобразованием Хартли и модифицированным преобразованием Хартли. Если для выполнения двумерного ДПФ используется традиционный строчно-столбцовый метод, то для двумерного ДПХ такой подход не может быть использован, что связано с неразделимостью ядра преобразования по переменным суммирования. Поэтому на практике используется модифицированное двумерное преобразование Хартли:

¡Гк1 =1 I хтп саз(2якт/К) саэ(2я1п/Н), ' (10) где саэС...] = соз[.... ] + э1п [...].

Однако такое преобразование отличается своими свойствами от ■ традиционного двумерного преобразования Хартли с неразделимым ядром, что приводит к ряду особенностей при его использовании. В работе устанавливается взаимосвязь между традиционным двумерным ДПХ и модифицированным ДПХ, а также между модифицированным ДПХ и ДПФ.

Особенности двумерного модифицированного преобразования Хартли проявляются и при вычислении двумерных функций свертки и корреляции.

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

- вычисляется модифицированное двумерное преобразование Хартли Н~к,!:

- вычисляется модифицированное двумерное преобразование Хартли Скл от Функции ядра свертки дт_п;

- путем перекомпоновки матриц Нлк,! и .! находятся компоненты Н^.!. 1Г„к1, Сл.кЛ и С.* соответственно;

- по полученным компонентам и исходным матрицам Н" и

БЫЧИ^ ПЯРТПЯ Лучкттия . •

- вычисляется модифицированное двумерное преобразование Хартли от функции ФАк л.

Во втором разделе второй главы обсуждается конвейеризация алгоритмов линейной фильтрации и адаптивной обработки сигналов. В начале раздела приводятся итеративные алгоритмы вычисления свертки/корреляции и перемножения матриц с покомпонентно независимым формированием результатов.

Прямой алгоритм вычисления свертки может быть реализован путем суммирования скалярных произведений столбцов отсчетов .ядра свертки и соответствующих столбцов текущей полосы изображения. что оказывается удобным при относительно небольшом размере ядра по отношению к размеру всего кадра изооражения. Обсуждается организация вычислений на основе такого подхода для специальных случаев, когда ядро свертки обладает симметрией относительно одной или двух осей.

Дале$ рассматриваются итеративные алгоритмы обращения матриц и решения систем линейных алгебраических уравнений по модифицированному- методу Гаусса-Жордана.

При решении матричного уравнения вида:

.где - Ам"1. I, - единичная матрица, согласно методу Гаусса-Жордана вначале формируется дополненная матрица

Ал - [ А„ I 1„ ]. которая затем за N итераций приводится к матрице А!:

А* - [ 1н I 2Н ) . Такое приведение осуществляется по следующим соотношениям:

а» гм - 1н

Ь* » а* 'щ.

3 - Ой;

(12)

к - 1.-И

*Лк = ^"'ис- 1 = 1. N. (13)

[акп - ак"1!л - акк;)ик1к. 1 / к

где а0!;, = ал13.

Выражения (12) и (13) описывают процедуру обращения матрицы без выбора главного элемента. Если порядок N матрицы А достаточно большой, то каждую к-ю итерацию целесообразно начинать с поиска главного элемента, т.е. максимального элемента к-го столбца матрицы А~ ( при к= 1) или матрицы А* (при к > 1). В разделе представлены две модификации алгоритма - без поиска главного элемента на каждой итерации и с поиском главного элемента.

В последнем разделе второй главы рассматривается конвейеризация алгоритмов ранговой фильтрации изображений.

В начале данного раздела показана возможность конвейеризации мультигистограммкого алгоритма и предложены оригинальные алгоритм ранговой фильтрации с выборочным формирова-. нием мультигистограмм. Подобный систолический алгоритм с выборочным формированием мультигиотограмм. обличающийся большей глубиной конвейеризации, имеет вид: начало; Б0 = -И: цикл ЛО ч = 1. й если >= 0, то

{ 1Ч = м2а3 ... , 1; дб = о: цикл по 1. з = 1. м

ДБ = ДБ + 1,/\ Ьи; конец цикла по 1,3

Б, - Б,., - ДЭ;> ' иначе { = й,с!2с13 ... Од,10; ДБ - 0; цикл по 1,3 - 1, М

ДБ - ДБ + 1ЧА Ьи; конец цикла по 1.3

Б, - Б,., + ДБ;)

еср Б, >» о, то <зч -о. иначе <ач - 1: конец цикла по ц

" "^«Мз ... <30.,(10 ; конец.'

Здесь Ьи - элемент изображения с номером (1.3) в окне

сканирования, I8 - значение элемента R-ro ранга. Q - разрядность элементов изображения, символ Л соответствует операции совпадения q старших разрядов 1„ и bu.

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

Далее представлены модифицированные разрядно-срезовые алгоритма с последовательным маскированием разрядных срезов, отличающиеся от известных меньшим числом потоков данных, требуемых для модификации следующего среза.

В конце раздела рассматривается организация систолического режима вычислений при реализации разрядно-срезового алгоритма с последовательным маскированием.

.В таком алгоритме, в отличие от конвейерного алгоритма, допускается распараллеливание вычислений по отдельным битам разрядного среза и одновременно сводятся к однобитным базовые операции.

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

В первом разделе рассматриваются структуры конвейерного типа с линейно-последовательными связями между ВЯ для выполнения ДОП. ' реализующие покомпонентно-независимое формирование отсчетов результатов, а также различных вариантов их ВЯ. Приводятся временны" диаграммы работы таких структур и оценки их временных параметров и затрат аппаратуры.

Во втором разделе описывается структура конвейерного устройства для многоканальной спектральной обработки на основе рассмотренной в предыдущем разделе полусистолической структуры. В отличие от устройства одномерного ДОП, каждая ВЯ соединена с соответствующей ЗЯ, в каждой из которых хранятся промежуточные значения формируемых результатов. Подробно рассматривается организация таких ЗЯ, которые имеют двухсекционную структуру и могут быть построены на основе регистровой памяти типа FIFO либо на основе ЗУПВ.

Время разгона конвейерного устройства многоканальной спектральной обработки будет составлять:

Гр = ГМШ-n + 131 . (14)

а полное время цикла выполнения обработки по всем каналам: Тц = Тр + (NM-l)t - 2MNt. ' (15)

В третьем разделе обсуждаются вопросы структурной организации устройств для вычисления ш-мерного ДОП на основе разработанных во второй главе конвейерных алгоритмов (выражения (5) и (6)). Такие устройства являются многокаскадными структурами, содержащими ш последовательно соединенных каскадов. Каждый каскад построен на базе полусистолической структуры. При этом первый каскад представляет собой рассмотренное в первом разделе устройство одномерного ДПФ, а ' каждый из последующих каскадов аналогичен по структуре и по принципу работы с устройством многоканального „одномерного ДПФ.

Еремя разгона процессора с учетом (15) (в данном случае число каналов составляет N1"'1) будет равно

V = V'1 + CN1®"1 (N - 1) + l]t = (Nm + ш -l)t (16) где t - длительность такта.

Полное время обработки матрицы исходных данных с .учетом (16) составляет

V = Грт + (Г-Dt = (2МИ + ш - 2) t. (17)

Тем самым в процессоре достигается 100 % загрузка оборудования и ввод/вывод данных с постоянным темпом, без. пауз. Скважность в выдаче отсчетов результата в установившаяся режиме работы конвейера определяется величиной t.

Подобные устройства могут выполнять фурье-подобные преобразования. ядра которых обладают свойством разделимости при интегрировании по всем переменным.

Возможность модульного "наращивания числа каскадов и числа ВЯ в каждом из каскадов является важным преимуществом рассмотренного класса устройств.

Далее, в четвертом разделе третьей главы, рассматривается структурная организация устройств ЕДОП, построенных на основе многокаскадных»устройств полускстолического типа.

В начале раздела рассматривается структура устройства ЕПФ для случая, когда размерность вектора может быть представлена з виде произведения взаимно-простых мнежителей К -II, х 1<гх .. . !'м.

Исходные данные перед еводом их в устройство необходимо упорядочить предварительно в лексикографическом порядке, представив их тем самым в многомерной форме. В отличие от устройства т-мерного ДОП, в систолическом многокаскадном БПФ-процессоре первые ВЯ каждого каскада помимо своих основных функций осуществляют умножение данных и промежуточных результатов на межитерационные поворачивающие множители.

Для реализации БПФ по основанию Л для N = гм в подобной конвейерной структуре требуется всего М каскадов по г ВЯ в каждом каскаде. Это в Н/Мг раз меньше по сравнению с затратами оборудования для устройства ДПФ при той же длине вектора данных.

Далее рассматриваются особенности организации систолического устройства для БПФ по основанию г = 4. В этом случае вследствие особенности матрицы Е4, содержащей только тривиальные множители, в каждой из БЯ нет необходимости выполнять умножение при реализации базовой операции, что позволяет упростить структуру ВЯ и сократить затраты оборудования.

В конце раздела рассматриваются варианты устройств подобной структуры для выполнения БДОП Уолша-Адамара.

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

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

Четвертая глава посвящена вопросам структурной органи-

зации конвейерных устройств линейной фильтрации и адаптивной обработки сигналов.

В начале рассматривается структура полусистолич'еского устройства многофункционального назначения. В таком устройстве может выполняться перемножение матриц, вычисление одномерных и двумерных функций свертки и корреляции. Дайная полусистолическая структура в основном повторяет структуру устройства одномерного ДПФ и содержит N ВЯ, соединенных последовательно друг за другом, и две группы из N ЗЯ1 и ЗЯ2, каждая из которых соединена с соответствующей ВЯ.

В рассматриваемом устройстве реализуется вычислительный алгоритм умножения вектора на матрицу и осуществляется покомпонентно-независимое формирование отсчетов результата, когда вычисление каждого отсчета с номером к ( й " о. N-1 ) локализуется в ВЯ с номером 1 = к + 1 и связакйж с ней 1-х ЗЯ! и ЗЯ2 . Устройство имеет последовательный и параллельный выходы результатов, что позволяет осуществлят&'швоя результатов как последовательно по отсчетам в теч&шх N тактов, начиная с периого отсчета, так и в форме вектора яз К отсчетов за один такт.

Далее рассматриваются структуры конвейерного типа, позволяющие реализовать вычисление свертКй к корреляции для специального случая осесимметричного ядра. Ь основу работы положен изложенный во второй главе алгоритм вычисления свертки как суммы скалярных произведений.

Конвейерное устройство, в структуре которбго учитывается симметрия ядра- свертки относительно центрального столбца, характеризуется меньшим числом ВЯ. По сравнению с традиционной структурой число ВЯ сократилось с М до (М+1)/2. Если же ядро содержит ш вырожденых (нулевых) столбцов, то число ЕЯ составит (М - га +1)/2. Структура всех ВЯ одинакова; в общем случае каждая ВЯ содержит ПЗУ для хранения коэффициентов соответствующего столбца ядра свертки, умножитель, сумматор-накопитель и регистры Евода-вывода. В ВЯ рассматриваемого устройства скалярное произведение текущего столбца-полосы изображения и столбца матрицы ядра свертки Формируется за (М - т +1)/2 тактов работы модуля при симметрии ядра относительно центральной строки.

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

Во втором разделе четвертей глава рассматривается устройство для обращения матриц и решения систем линейных алгебраических уравнений, в основу функционирования которого положен конвейерный алгоритм Гаусса-Жордана. Данное устройство, как и устройство векторно-матричных операций, характеризуется последовательным соединением ВЯ в линейку и реализует принцип покомпонентно-независимого формирования результата. Последняя ВЯ в нем соединена шиной данных и шиной управления с первой БЯ, в результате чего организуется кольцевая структура. Данное устройство позволяет выполнять процедуру обращения матрицы как с поиском главного элемента, так и без поиска главного элемента. Приводятся алгоритмы функционирования ВЯ для обоих случаев процедуры обращения. Подробно обсуждаются стру: туры ВЯ и ЗЯ такого устройства, а также организация управления.

.Обращение матриц или решение системы ЛАУ в таком устройстве выполняется за К итераций, полное время обработки для алгоритмов без поиска главного элемента составляет:

Т = N(3N + l)t/2 . где t - длительность базовой операции. При поиске главного элемента время выполнения каждой итерации увеличивается на время поиска главного элемента.

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

мирование обратной ковариационной матрицы выполняется итеративно. с использованием сформированной на предыдущей итерации обратной ковариационной матрицы. Эта матрица, всвою очередь, вычисляется по значениям вектора входных сигналов и выходного вектора результатов, полученных на предшествующей итерации. Тем самым в процессе обработки учитывается "пре-дистория" сигнала в течении предшествующих временных интервалов. Время выполнения одной итерации обработки в предлагаемом устройстве составляет Т = 4N t.

В пятой главе рассматриваются структуры конвейерного, параллельно-конвейерного и систолического типов, реализующие описанные во второй главе алгоритмы нелинейной (ранговой) фильтрации, а также устройства для выполнения "унифицированных" конвейерных алгоритмов линейной и нелинейной фильтрации.

В первом разделе пятой главы рассматриваются конвейерные устройства для ранговой фильтрации, реализующие мультипрограммные и разрядно-срезовые алгоритмы.

Мультигистограммные алгоритмы ранговой фильтрации легко допускают конвейеризацию вычислений, что позволяет реализовать подобные алгоритмы на структурах с последовательным соединением ВЯ и обеспечить относительно небольшие затраты аппаратуры. Каждая ВЯЧ (q = 1.Q, где Q - разрядность данных) содержит схему формирования гистограммы и схему поиска ранга IR. Формирование гистограммы Hq выполняется как рекурсивная процедура, что позволяет получить новую гистограмму после замены удаляемого столбца на другой. Таким образом, для формирования гистограммы требуется порядка 2 М тактов. Для реализации такого режима формирования гистограммы Hq в состав формирователя включена регистровая память типа FIFO ёмкостью М слов. В АЛУ предусмотрено, помимо инкрементного наращивания содержимого ячейки памяти (элемента гистограммы} по адресу bj b2b3...ba, также декрементное уменьшение содержимого той же ячейки при корректировке гистограммы.' Корректировка производится каждый раз после ввода элемента столбца,- Элементы удаляемого столбца выводятся из регистра FIFO и используется как адрес элемента гистограммы Hq. Выбираемый из памяти элемент гистограммы затем уменьшается на единицу. Для

управления вычислениями используется формируемый в АЛУ знак результата. Полное время выполнения фильтрации в подобном устройстве составляет:

Т = d(2NM)t .

Пауза между появлениями " соседних " отсчетов результата на выходе устройства составляет 2Mb .

Далее рассматриваются структуры конвейерных устройств, реализующих разрядно-срезовые алгоритмы. На основе рассмотренных во второй главе разрядно-срезовых алгоритмов разработаны конвейерные структуры с поэлементным вводом и с параллельным вводом элементов столбца, содержащие Q последовательно соединенных ВЯ. В состав ВЯ входят блоки ПЗУ и регистровой памяти типа FIFO, два сумматора, коммутаторы, регистры и отдельные логические элементы. Каждая ВЯ (q=TTQ) обрабатывает q-й срез Bq матрицы исходных данных. Бинарный срез Bq вводится в течение М тактов последовательно по столбцам, при этом q-й срез и-го столбца Bq>m представлен в виде М-разрядного двоичного слова. Аналогичным образом представляется и бинарная каска Sq-i..

В каждой ВЯЧ формируется маска Sq, значение промежуточного результата 1„ и промежуточная сумма Dq, которые передаются в ВЯЧ», (q=i,Q-1). С выхода последней ВЯ снимается значение 10 =1а. Входящий в состав ВЯЧ блок ПЗУ обеспечивает вычисление табличным способом числа нулевых бит в каждом Затем производится суммирование числа единиц по всем столбцам Bq. После определения суммарного числа нулей в Bq (величины ADq) выполняется ее сравнение с величиной D„.,, передаваемой из BHq_t. Знак полученной разности используется для управления выходными коммутаторами в ВЯЧ и определяет q-й разряд промежуточного результата Iq.

■Время разгона конвейера, т.е. пауза от момента начала работы первой ВЯ до момента запуска последней ВЯ, в данном случае составит Т = 'MQt, где t - длительность такта работы ВЯ. определяемая временем записи/считывания ОЗУ и временем выполнения операций в АЛУ. Длительность цикла работы BHq, т.е. время от момента поступления столбца Bq,m до выдачи результата d,d2... dq. составляет Т = Mt. Пауза между появлениями ■ "соседних" отсчетов результата на выходе также соста-

вит Т = Mt. Достоинством разработанных конвейерных структур является возможность модульного наращивания при увеличении размера окна и разрядности данных.

Второй раздел пятой главы посвящен систолическим структурам для ранговой Фильтрации, реализующим рассмотренные во второй главе систолические алгоритмы.

В начале рассматривается систолический процессор, реализующий алгоритм выборочного формирования мультигистограмм. Такой процессор отличается линейно-последовательным типом связей между ВЯ и содержит 0. последовательно соединенных каскадов, каждый из которых содержит М одинаковых систолических матриц по М ВЯ и блок анализа. Систолические матрицы разделены блоками буферной памяти типа FIFO емкостью (M+N) элементов изображения. Между соседними каскадами включены дополнительные блоки буферной памяти типа FIFO для хранения N(И-1) - М промежуточных результатов. Время отклика такого устройства составляет:

Т = {(N + М)(М - 1) + M}Q t .

Другим вариантом процессора, реализующего тот же алгоритм, является устройство полусистолической структуры, предусматривающее распараллеливание обработки элементов bu по разрядам. В результате этого отпадает необходимость в дополнительных блоках БП сравнительно большой емкости, входящих в состав ранее рассмотренного процессора. Другим важным преимуществом полусистолической структуры является меньшее время . отклика, равное 2M2Qt .

Предлагаемые систолические устройства ранговой фильтрации отличаются высокой производительностью и позволяют выполнять обработку изображения в телевизионном темпе.

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

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

такие операции, как взвешенная ранговая фильтрация, скользя-тай эквализация гистограмм, вычисление двумерной свертки и корреляции, перемножение матриц.

Анализ алгоритмов указанных процедур свидетельствует о наличии ряда однотипных операторов, в связи с чем данные алгоритмы могут быть реализованы на практически однотипных аппаратных средствах.

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

Шестая .глава посвящена вопросам организации устройств макроконвейерного типа MISD-архитектуры и параллельно-конвейерных ГШШ-систем на базе сигнального транспьютера, являющегося мощным программируемым вычислительным средством.

В начале главы обсуждаются вопросы структурной организации макроконвейеркого устройства MISD архитектур« для выполнения быстрых алгоритмов ортогональных преобразований, построенного на базе универсальных ВЯ. Определяются временные характеристики функционирования такого устройства. Далее предлагается структура многокаскадной вычислительной системы для решения задач предварительной обработки сигналов, построенной путем комплектования макроконвейерных устройств. Подобная система псволяет реконфигурпровать связи между каскадами, обеспечивая как параллельное соединение каскадов при независимом функционировании их по отношению к остальным, так и последовательное соединение всех или части каскадов с возможностью организации замкнутой . кольцевой связи. .Пиковая производительность подобной системы при современном уровне развития спец СБИС может достигать 100 Гфлоп/с.

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

комплект таких модулей вычислительный модуль содержит четыре транспьютера для выполнения вычислений и дополнительно коммутатор Link-портов и транспьютер для управления коммутаций и функционированием модуля. Каждый транспьютер модуля имеет локальную память обьемом 32К слов по 32 бита.

Модуль буферной памяти предназначен' для создания буферных ЗУ большой емкости и содержит два транспьютера с локальной памятью у каждого в 400 К слов. Модуль управления содержит глобальный коммутатор Link-портов с управляющим транспьютером и набор шинных усилителей. Емкость локальной внешней памяти транспьютера - 32 К слов. Кроме указанных модулей, 'для построения распределенных транспьютерных МВФ-систем требуются модули питания, преобразования форматов данных из целочисленного представления в формат с плавающей точкой, являющийся осноеным форматом при обработке сигналов в CT, а также интерфейсные модули для связи с Host-ЭВЛ и периферийным оборудованием.

В последнем разделе главы рассматривается построение иерархических MIMD-систем на основе базового набора модулей.

Такие иерархические системы допускают наращивание как числа ступеней макроконвейера, так и числа модулей в каждой ступени,

' Предлагаемые базовые вычислительные средства -набор модулей различного назначения на базе CT - позволяют компоновать распределенные MIMD системы для цифровой обработки'сигналов практически любой конфигурации при наращивании суммарной вычислительной мощности до требуемого значения.

В заключении приведены основные результаты работы.

III. ЗАКЛЮЧЕНИЕ

Главный научный результат диссертационной работы заключается в разработке унифицированного способа конвейеризации различных процедур линейной предварительной обработки сигналов. в основу которого положен принцип покомпонентно-независимого формирования отсчетов результатов, и получения на его основе унифицированных по своей организации структур специализированных устройств различного назначения, что является

теоретическом обобщением и развитием такого способа конвейеризации для и многомерных и быстрых алгоритмов ЦПОС.

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

К основным научном результатам диссертационной работы в части конвейеризации и унификации алгоритмов относится следующее: ,

- разработаны конвейерные алгоритмы дискретного преобразования Фурье и многомерного дискретного преобразования Фурье, в основе которых лежит итерационная процедура покомпонентно-независимого формирования отсчетов результата: на базе этих алгоритмов разработаны конвейерные алгоритмы БГ№, БПХ- и других быстрых алгоритмов в фурье-подобных базисах;

- установлена взаимосвязь модифицированного двумерного преобразования Хартли с традиционным двумерным преобразованием Хартли и двумерным преобразованием Фурье; предложен алгоритм вычисления свертки (корреляции) через модифицированное двумерное преобразование Хартли;

- разработаны конвейерные алгоритмы процедур матричной алгебры, включая процедуры умножения матриц, вычисления двумерной скользящей свертки/корреляции, а также обращения матриц и решения систем линейных алгебраических уравнений, используемых при адаптивной обработке сигналов, основой для конвейеризации которых также является принцип покомпонентно-независимого формирования отсчетов результата;

- разработаны алгоритмы, конвейерного вычисления свертки с учетом симметрии ядра относительно одной и двух осей на основе принципов покомпонентно-независимого формирования результатов и последовательного формирования результата;

- разработаны конвейерные варианты алгоритмов ранговой фильтрации, основанные на выборочном формировании мультигис-тограмм, отличающиеся различной степенью конвейеризацией вычислений:

- разработаны модификации разрядно-срезового алгоритма ранговой фильтрации с последовательным маскированием, отличающиеся меньшим числом информационных потоков, а также

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

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

К основным результатам, связанным с разработкой функционально-ориентированных аппаратных средств ЦПОС. относится следующее:

- разработаны конвейерные однокаскадные устройства для вычисления одномерного и многоканального ДПФ. реализующие процедуру покомпонентно-независимого формирования результатов, выполнены оценки быстродействия и объема аппаратурных затрат применительно к таким структурам;

'- разработаны многокаскадные конвейерные устройства для выполнения многомерного ДПФ, унифицированные по структурной организации своих каскадов с однокаскадными устройствами- и допускающие наращивание размерности обрабатываемых массивов-данных за счет подключения дополнительных каскадов;

- разработаны многокаскадные конвейерные устройства д'ля! выполнения быстрых дискретных ортогональных преобразований Фурье, Хартли, .Адамара-Уолша, полностью унифйЩр'аванные по своей структуре с многокаскадными устройствами Ш ГоМерных ортогональных преобразований;

- разработаны структуры конвейерных устройств для реше^ ния задач адаптивной"обработки сигналов, включая процедуры обращения матриц и решения систем линейных алгебраических уравнений, а также устройства для вычисления двумерной скользящей свертки/корреляции, реализующих принцип покомпо-

нентно-независимого формирования•результата и однотипных по своей структурной организации с однокаскадными устройствами многоканальной обработки;

- разработаны структуры конвейерных процессоров свертки, в которых учитываются особенности ядра свертки - его осесимметричность и вырожденность; основанные на принципе последовательного подс^ммирования частичных результатов: .

- разработаны конвейерные устройства ранговой Фильтрации с поэлементным вводом данных, реализующие мультигисто-раммный алгоритм и алгоритм с выборочным формированием муль-тигистограмм, имеющие одинаковую структурную организацию и организацию входных потоков данных; при этом отличительной чертой конвейерного устройства с выборочным формированием мультигистограмм является простота вычислительной ячейки;

-- разработаны структуры устройств систолического и полусистолического типов, реализующих алгоритм ранговой фильтрации с выборочным формированием мультигистограмм, отличающиеся большей степенью конвейеризации и меньшим временем цикла в установившемся режиме вычислений при использовании того же структурного принципа организации последовательных связей между соседними вычислительными ячейками;

- разработаны структуры конвейерного разрядно-срезового процессора с параллельным вводом элементов столбца окна сканирования, имеющее высокое быстродействие при сравнительно небольших затратах оборудования, что обеспечивается табличным выполнением базо; :>й операции с использованием ОЗУ:

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

- предложены' структуры модулей базового набора.на основе перспективных отечественных сигнальных . транспьютеров, ориентированного на построение иерархических систем ИМО-ар-хитектуры;

- разработаны структуры иерархических макроконвейерных МПШ-систем на основе модулей базового набора, позволяющих выполнять широкий класс алгоритмов предварительной обработки сигналов.

Основные материалы диссертации опубликованы в следующих работах.

1. Донченко С. Е. .Кучеренко К.И., Очин Е.Ф. .Тропченко А.Ю. Программирование алгоритмов цифровой обработки изображений в процессоре скалярных произведений.// Тезисы докладов Всесоюзного симпозиума "Зрение алгоритмов и роботов", -Вильнюс',

1985. -Т. 2,- с. 160-161.

2. Кучеренко к. И.. Очин Е. Ф., Тропченко А.Ю. Конвейерная сортирующая сеть медианной фильтрации изображения (Тезисы докладоз) //Сборник трудов II Всесоюзной конференции "Методы и средства обработки сложной графической информации",- Горький, ГГУ. 1985, стр. 52-53.

3. Кухарев Г.А., Майоров С.А., Тропченко А.Ю. Принципы организации процессоров многомерного дискретного преобразования Фурье (Тезисы доклада)// Сборник трудов III Всесоюзной конференции "Методы и микроэлектронные средства- цифрового преобразования и обработки сигналов". Часть XIT». - Рига,

1986. стр.504-507.

4. Кухарев Г. А., Тропченко А. Ю. Методы построважт процессоров систолической архитектуры для дискретного преобразования Фурье // Тезисы докладов VI Всесоюзной конференции "Распараллеливание обработки информации". Часть II. - Л&&0&.. ФМИ'АН УССР. 1987. стр.219-220.

5. Кухарев Г. А., Тропченко А. D. Многоканальная систола^ ческая матрица для построения суперсистем реального вреиеш // Тезисы докладов I Всесоюзной конференции "Проблемы создания супер -ЭВМ, супер-систем и эффективности их применения". Часть II, - Шнек, 1987, стре. 79-81.

6. Кухарев Г.А.. Тропченко А.Ю. Принципы построения систолических процессоров для дискретного преобразования Фурье // "УС и М". 1988. N 4, стр. 3-8.

7. Кухарев Г.А.. Тропченко А.Ю. Мультипроцессорная конвейерная вычислительная система с перестраиваемой архитектурой для задач ЦОС // Тезисы докладов III Всесоюзного-совещания "Высокопроизводительные вычислительные системы", - М., ИЛУ АН СССР. 1988. стр.52-53.

8. Кухарев Г.А.. Тропченко А.Ю. Систолические матрицы

для процессоров дискретного преобразования Фурье // В сб. "Методы и средства преобразования информации". Вып. 8, - Рига, "Зинатне", 1988, стр.21-38.

9. Кухарев Г.А.. Тропченко А. Ю., Шмерко В. П. Систолические процессоры для обработки сигналов // - Минск. "Беларусь", 1988, - 127 с.

10. Кухарев Г.А., Тропченко А.Ю. Систолические многофункциональные матрицы для процессоров цифровой обработки сигналов // Тезисы докладов и сообщений III Всесоюзного совещания "Конвейерные вычислительные системы", - Киев, КПИ,

1988. стр. 69-71.

11. Кухарев Г.А., Тропченко А.Ю. Параллельно-конвейерный процессор для обращения матриц // Тезисы докладов IV Всесоюзной конференции "Математические методы распознавания образов".' Часть V. - Рига.РИО МИПКРРиС при СМ Лат. ССР,

1989, стр. 29-31.

12. Тропченко А.Ю. Систолический процессор для адаптивной обработки сигналов // Тезисы докладов IV Всесоюзной конференции "Методы и микроэлектронные средства цифрового преобразования и обработки сигналов". Том 1, - Рига, КЭиВТ АН Лат. ССР, 1989, стр.354-356.

* 13. Романов Ю.Ф., Тропченко А.Ю., Юсупов K.M. Систолические пржцессоры ранговой фильтрации // Тезисы докладов I Всесоюзной конференции "Однородные вычислительные среды. и систолические структуры"// -Львов, ИППМ АК УССР, 1990. стр.124-127.

14. Клочков B.C., -Романов Ю Ф.. Тропченко А.Ю., Юсупов K.M. Процессор взвешенной ранговой фильтрации изображений // Тезисы докладов II Всесоюзной конференции по оптической обработке информации, -Фрунзе, "ИЛИМ". 1990, стр. 35-38.

15. Романов'Ю.Ф., Тропченко А.Ю., Юсупов К. К. Конвейерный разрядно-срезовый процессор ранговой Фильтрации изображений// Тезисы докладов II Всесоюзной конференции по оптической обработке информации, - Фрунзе, "ИЛИМ". 1990. стр.33-35.

16. Романов Ю.Ф.. Тропченко А.Ю., Юсупов K.M. Конвейерные процессоры ранговой фильтрации изображений/'/ "Известия вузов СССР. - Приборостроение", 1990, т. 33, ¡1 9, стр. 28-33.

17. Кухарев Г.А., Тропченко А.Ю. Систолический процессор для обращения матриц// "Известия вузов СССР,- Приборостроение", 1990. Т. 33, N И, стр. 23 - 27.

18. Романов Ю.Ф.. Тропченко А.Ю., Юсупов" K.M. Систолические процессоры ранговой Фильтрации // "Известия вузов -СССР, - Приборостроение"; 1991,т. 34, N 1, стр.26-30.

19. Клочков В. С. .Романов Ю. Ф., Тропченко А.Ю., Юсупов K.M. Конвейерные разрядно-срезовые процессоры ранговой и взвешенней ранговой фильтрации изображений// "Известия вузов СССР. - Приборостроение". 1991, т. ЗА, Н 2, стр. 24-29.

20. Романов Ю.Ф.. Тропченко А.Ю., Юсупов K.M. Систолические мультигистограммные и разрядно-срезовые процессоры ранговой фильтрации // "Известия вузов СССР,- Приборостроение", 1991, Т. 34. N.12, стр. 26-34.

21. Тропченко А.Ю. Параллельно-конвейерный процессор для адаптивной обработки сигналов // "Известия вузов СССР. -Приборостроение", 1992, т. 35, N 2, стр.24-28.

22. Тропченко А.Ю.. Романов Ю.Ф. Конвейерный процессор быстрого преобразования Хартли //"Известия вузов-Приборост-роение", 1993, Т. 36, I! 3, стр. 37-42.

23. Тропченкс А. Ю., Романов Ю. Ф. Адзгвритмы быстрого преобразования Хартли при различных основаядаке и' конвейерные структуры для их реализации // "Известия вугов-йриборчетрое-ние\ 1993, т. 36, N 4, стр. 27-32.

24. Тропченко А.Ю., Клочков B.C.. Романов „Юсупов K.M. Конвейерный процессор для вычисления; свертки с- осесям-метричным ядром // "Известия, вузов - Приборостроение"'. 1903, т. 36. N 5. стр. 26-31.

25. А. с. N 1363243 СССР. Систолический процессор для дискретного преобразования Фурье//Кухарев Г.А.-, Тропченко А.Ю., Скорняков .B.C.. Опубл.30.12.1987, Бюл. N48/

26. А. с. N 1399764 СССР. Устройство для дис;.четных ортогональных преобразований. //Кухарев Г. А.. Тропченко А. Ю., Скорняков B.C. - Опубл. 30.05.1988. Бюл. N 20.

27. А. с. 1J 1425722 СССР. Устройство параллельной обработки видеоинформации //Донченко С.Е., Кучеренко К.И.. Очин Е. Ф., Тропченко А.Ю. - Опубл. 23. 09.1988, Бюл. U 35.

23. А. с. ü 1471200 с:ср. систолический процессор циф-

ровой обработки сигналов.// Кухарев Г. А., Тропченко А.Ю., Скорняков В. С., Голубев В. П. - Опубл. 07.04.1989. Бюл. N 13.

29. А. с. N 1608688 СССР. Систолический процессор двумерного дискретного преобразования Фурье //Кухарев Г. А. .Тропченко А.Ю. - Опубл. 23.11.1990, Бюл. N 43.

30. А. с. N 1608689 СССР. Систолический процессор для вычисления пoлинoмиaл^чых функций.//Кухарев Г.А.. Павловский В.Ф., Тропченко А.Ю. - Опубл. 23.11.1990, Бюл. N 43.

31. А. с. N 1615741 СССР. Многоканальный систолический процессор для дискретного преобразования Фурье // Кухарев Г. А., Тропченко А.Ю. - Опубл. 23.12.1990, Бюл. Н 47.

32. А. с. N 1621043 СССР. Систолический процессор четырехточечного ДПФ // Кухарев Г.А.. Новоселов Н.Д., Тропченко А.Ю. - Опубл. 15. 01.1991. БЮЛ. N 2.

- 33. А. с. N 1727137 СССР. Устройство для ранговой фильтрации с произвольным окном //Романов ¡0. Ф., Тропченко А.Ю., Юсупов К.М. - Опубл. 15.04.92, Бюл. Н 14.

34. Пат. К 2015551 РФ. Устройство для ранговой фильтрации изображений.//Романов Ю. Ф.. Тропченко А. Ю.. Юсупов К. И. - Опубл. 30. 06.94, Бвл. К 12.

Подписано к печати 30.01.95 г. Объем 2,1 п.л.

Заказ 15 Тираж 100 экз. Бесплатно

Ротапринт. ИТМО. 190000, С.-Петербург, пер.Гривцова, 14