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

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

Анисимов Игорь Юрьевич

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ ПОВЕДЕНЧЕСКОГО СИНТЕЗА КОНВЕЙЕРНЫХ СХЕМ ДЛЯ ЦИФРОВОЙ ОБРАБОТКИ ВИДЕОИЗОБРАЖЕНИЙ

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

003445 Ю7

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

003445107

Работа выполнена на кафедре «Вычислительной техники» государственного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им В И Ульянова (Ленина)»

Научный руководитель доктор технических наук, профессор

Мурсаев Александр Хафизович

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

доктор технических наук, профессор Лыпарь Юрий Иванович

Ведущая организация

кандидат технических наук, Суворова Елена Александровна

ФГУП «ЦНИИ Электроприбор»,

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

Защита состоится^/ /О 2008 г в / часов на заседании диссертационного совета Д 212.229 18 ГОУ ВПО «Санкт-Петербургский государственный политехнический университет» по адресу 195251, Санкт-Петербург, ул Политехническая, 21, IX учебный корпус, ауд 325

С диссертацией можно ознакомиться в фундаментальной библиотеке ГОУ ВПО «Санкт-Петербургский государственный политехнический университет» Автореферат разослан «_»_2008 г

Ученый секретарь Диссертационного совета Д212 22918 кандидат технических наук доцент

Васильев А. Е.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы

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

• компенсацией погрешностей фотоприемного или отображающего устройства,

• улучшением качества визуального восприятия изображения,

• сжатием видеоданных,

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

В блоке цифровой обработки алгоритмы должны выполняться в реальном масштабе времени Это требование строго задает необходимую пропускную способность используемых вычислительных схем Например, поток изображений высокой четкости (HDTV), имеет интенсивность 110 Мбайт/с, такую же пропускную способность должен иметь вычислительный блок Для современных универсальных процессоров это практически невыполнимые требования Современный сигнальный процессор с производительностью 3 Млрд оп /с способен выполнять около 30 операций на такт Это эквивалентно всего лишь реализации фильтра 5 на 5, а для перечисленных выше задач требуется гораздо больше операций На современных вычислительных средствах для большинства алгоритмов предварительной обработки изображений достичь такой высокой пропускной способности можно только с помощью параллельной реализации алгоритмов, причем параллельной на уровне элементарных операций. Именно такой реализацией являются конвейерные схемы В силу сказанного предварительную обработку обычно выносят в отдельный специализированный блок, имеющий конвейерную архитектуру

Современной перспективной элементной базой для специализированных конвейерных схем являются ПЛИС (FPGA) и полузаказные СБИС (ASIC) Благодаря универсальности ПЛИС, они выпускаются большой серийностью, поэтому современной тенденцией является быстрое снижение цен на них при од-

новременном росте степени интеграции ПЛИС являются матрицей конфигурируемых элементарных однобитовых процессоров объединенных между собой конфигурируемой системой связей ПЛИС в основном ориентированы на изделия малой серийности, тогда как полузаказные СБИС - на изделия средней серийности

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

И в случае реконфигурируемых сопроцессоров, и в случае специализированных процессоров обработки видеоизображений остро стоит проблема проектирования Это связано в основном с тем, что большинство изделий в этой предметной области выпускается малой серийностью, и вклад проектирования в стоимость одного изделия оказывается существенным Проектирование конвейерных схем непростая задача, поскольку непосредственно связана с проблемой параллельной реализации алгоритмов Современные САПР используют в качестве исходных данных только уже готовую конвейерную реализацию алгоритма, описанную на специальном языке (VHDL, Verilog, System С, Handle С и т п ), и доведенную до уровня абстракции регистровых передач То есть задача конвейерной реализации алгоритма возлагается на пользователя Вместо этого хотелось бы задавать исходный алгоритм в последовательной форме (например, используя чистое поведенческое описание VHDL, System С, Handle С, или последовательные языки С++, MatLab, и др), а по ней получать конвейерную схему автоматически Это позволило бы значительно сократить срок проектирования и значительно снизить стоимость проектирования

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

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

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

• Impulse Accelerated Technologies - программный продукт ImpulseC

• Mentor Graphics - программный продукт Catapult С

• Mitrionics Inc - программный продукт Mitrion Software Development Kit

• Celoxica - программный продукт Agility Compiler

Кампания Mentor Graphics для своего продукта Catapult С утверждает, что размер автоматически сгенерированных схем оказывается на 20-50% больше, чем в случае ручного проектирования Таким образом, можно утверждать, что, несмотря на работы в данном направлении, поведенческий синтез требует дальнейшего исследования и развития Данная работа ограничена исследованием методов поведенческого синтеза только конвейерных схем, которые наиболее актуальны в предварительной обработке изображений

Цель работы

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

Основные задачи:

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

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

3. Исследование и разработка методов представления алгоритма в конвейерной форме

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

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

Методы исследований

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

Научная новизна работы

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

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

3. Предложен метод нахождения конвейерной развертки графа зависимостей программы

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

Практическая значимость

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

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

3. Исследованы алгоритмы, и получены конвейерные схемы для алгоритмов предварительной обработки изображений двумерной свертки, вычисления градиентного поля, корреляционной функции, внедренные в сетевые камеры высокого разрешения ЗАО «Ареконт Вижн» (Акт внедрения прилагается к диссертации)

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

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

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

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

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

Реализация результатов работы

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

Н264 кодера для камер высокого разрешения проводимой ЗАО «Ареконт

Вижн», в НИИ ВЦ «Карат» при проведении ОКР «Сфера», во ФГУП ВНЦ ГОИ

«Государственный оптический институт им С И Вавилова» при проведении ОКР «Сатрап» Акты внедрения приложены к диссертации

Апробация работы и публикации

По основным результатам работы были опубликованы 3 научные работы, и сделано 2 доклада

1 Анисимов И Ю Методика отображения алгоритмов на параллельные вычислительные структуры //VII Международная научно-техническая конференция «Распознавание-2005», 4-7 октября 2005 г, г Курск

2 Анисимов И Ю , Мурсаев А X Методика поведенческого синтеза конвейерных схем предварительной обработки изображений //61-я научно-техническая конференция профессорско-преподавательского состава СПбГЭТУ «ЛЭТИ», 29 января - 8 февраля 2008 г., г Санкт-Петербург

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения, списка литературы, приложений Она содержит 143 страницы машинописного текста (без приложений), 49 рисунков Список литературы содержит 127 наименований Нумерация формул и рисунков сквозная по всей диссертации.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

1 Разработка программы с однократным присваиванием и построение графа зависимостей

2 Построение графа потока сигнала (граф-машины) на основе графа зависимостей

3 Разработка матричного процессора по графу потока сигнала

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

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

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

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

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

Во второй главе описывается методика проектирования конвейерных вычислительных схем на ПЛИС и полузаказных СБИС, основанная на чистом поведенческом описании алгоритма (или последовательной программной форме алгоритма - ПФА), и ориентированная на алгоритмы предварительной обработки А также описываются методы положенные в основу методики

Для схем последовательного действия существуют формальные методы синтеза схем по программному представлению алгоритма, описанные, в частности, в работах Баранова С И , Майорова С А и Новикова Г И Эти известные

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

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

1 Описание алгоритма в последовательной форме (другими словами чистое поведенческое описание)

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

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

4 Нахождение конвейерной развертки графа зависимостей

5 Синтез граф-машины - структурной модели вычислительного устройства

6 Описание конвейерной схемы на предназначенном для этого языке (например, VHDL)

На уровне последовательной формы алгоритма должны быть определены

• Типы и разрядность данных, а также тип компьютерной арифметики и правила округления

• Содержание операций Все сложные операции должны быть разбиты на элементарные, принятые за таковые в целевой элементной базе

• Порядок элементарных операций.

• Программа должна быть приведена к линейному классу

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

for и - 1 nl р = 0; % VI for v = 1 .п2

р = р + х(и-v+l)*h(v), % 42 end;

у (и) = р, end,

Процесс построения графа зависимостей состоит из

• Разбиения программы на абстрактные элементарные программы, содержащие только два вхождения одной и той же переменной, слева и справа от оператора присваивания

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

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

Элементарные (абстрактные) программы выглядят следующим образом

for и = 1 nl for и = 1 nl

р = % VI for v = 1 .п2

for V = 1 р2 р = р % V2

= р % V2 end;

end, ела,

end,

Графы для этих программ изображены на рисунке 1

V2

Рисунок 1 Графы зависимостей элементарных программ

Результат объединения этих графов, и окончательный вариант графа с добавлением зависимостей от входных данных изображены на рисунке 2

V •""Ф* 9 Q Q Q Q

" -—t i. .____;;________I >—- .-*'

Рисунок 2 Объединение злементарных графов и граф зависимостей программы

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

Ф12п Г2->П, Ф„м(н,у) = и, г = 1 (1)

ФУ212 У2-*У2, Ф„^г(м,т) = (глг>-1),у = 2 и2, (2)

Ф,2Х VI —>X, Ф12Г(и,г) = 1/-у + 1; Ф„и К2->Я, Ф,м(И,у) = У, У -> У2, Фга(и) = («,й)

(3)

(4)

(5)

Здесь, например выражение (1) означает, что имеется дуга из вершины с координатой и принадлежащей множеству VI в вершину с координатами (и,у) из множества У2

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

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

ДФ,»1 (*))</«, (7) /(Ф«| 2 (*))</(*) (8)

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

/(и) = 0 на VI, (9)

/(и,у) = унаУ2 (10)

Линии уровня данной развертки изображены на рисунке 3 в виде горизонтальных линий, отмеченных переменной /

1—> 1=2 ' ^ 4 < 4 1 4 •. 4 \ 4 к 4

и ! 1=1 к 4 \ * » 4 \ 4 \ 4 \

4 » , * )

1=0

-I-

■VI

Рисунок 3 Линии уровня развертки

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

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

Р=и, (И)

где и - номер итерации внешнего цикла То есть в данном случае порядок поступления отсчетов совпадает с номером итерации внешнего цикла Конвейерная развертка будет иметь вид

/(и) = и на VI, (12)

Ди,у) = и + г на VI (13)

Линии уровня полученной развертки изображены на рисунке 4

Рисунок 4 Линии уровня конвейерной развертки

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

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

2 Перейти к новому координатному базису, связанному с конвейерной разверткой

3 Построить проекцию графа зависимостей

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

Ф12П((,у)=г-1, у = 1 (14)

(15)

(16) (17)

Переменная / здесь обозначает номер линии уровня развертки, и соответствует тактам срабатывания граф-машины Например, покрывающая функция (15) обозначает, что операция в узле V на текущем такте / зависит от результата операции в узле V-/ на такте и1 Структура граф-машины, восстанавливаемая по этим функциям, представлена на рисунке 5

-------V

Рисунок 5 Граф-машина свертки

На рисунке вершины графа, обозначенные кружками, соответствуют операционным устройствам (при переходе к У1ШЬ описанию им ставится в соответствие умножения с накоплением) Дуги указывают направление передачи данных (при переходе к УНБЬ - сигналы), веса на дугах - задержки на такты (при переходе к УНБЬ - регистры) В работе продемонстрировано также, что для получения последовательно-параллельных вычислительных структур может быть использована гомоморфная свертка граф-машины

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

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

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

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

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

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

Вычисление поля градиентов изображения является одним из распространенных способов подчеркивания границ на изображении для выделения контура объекта Алгоритм состоит в сворачивании изображения с восемью масками размером 3 на 3, и выбором максимального по модулю среди всех таких сверток Данный алгоритм был описан на языке системы MatLab В соответствии с предложенной методикой были выполнены этапы построения графа зависимостей, нахождения допустимого множества разверток, нахождения конвейерной развертки, синтеза граф-машины Для записи покрывающих функций, областей их определения, разверток, систем неравенств, а также всех преобразований была использована матричная форма, удобная для реализации методики на компьютере В результате формальным путем была получена конвейерная вычислительная структура для алгоритма вычисления градиентного поля изображения Каждая ступень конвейера по величине задержки срабатывание не превышает задержку срабатывания сумматора, более глубокая конвейеризация приводит к разрастанию аппаратных затрат Для семейств ПЛИС большой серийности Spartan3E или Сус1опе2 скорость работы полученной конвейерной схемы составит около 150 МГц, при затратах сравнимых с неконвейерными реализациями, то есть порядка 500 функциональных ячеек Частота работы конвейера 150 МГц вполне способна обеспечить обработку видеоизображений формата HDTV, либо монохромных размером 6 мегапикселей, идущих с частотой 25 кадров в секунду Данная структура внедрена в изделия НИИ ВЦ «Карат» при проведении ОКР «Сфера», а также ФГУП ВНЦ ГОИ «Государственный оптический институт им С И Вавилова» при проведении ОКР «Сатрап»

Был рассмотрен алгоритм быстрого вычисления двумерной корреляционной функции на основе использования преобразования с числами Ферма Прямое вычисление корреляционной функции, а также на основе БПФ (Быстрого Преобразования Фурье) сложны для аппаратной реализации, поскольку содержат много умножений, а БПФ к тому же оперирует с комплексными числами Указанных недостатков лишено БПФ в кольце вычетов по модулю числа Ферма, так называемое преобразование с числами Ферма (ПЧФ) Кольцо вычетов по модулю числа Ферма представляет собой конечное множество целых чисел, все элементы которого меньше заданного числа Ферма На этом множестве определены операции умножения и сложения, отличающиеся от обычных операций с целыми числами тем, что выполняются по модулю числа Ферма Умножение на матрицу коэффициентов ПЧФ, в отличие от БПФ, содержит умножения только на степень двойки, поэтому ПЧФ удобно для аппаратной реализации Вычисление корреляционной функции требует выполнения двух прямых и одного обратного ПЧФ С использованием предложенной методики была построена конвейерная вычислительная структура выполняющая прямое и обратное быстрое ПЧФ Степень конвейеризации схемы доведена до уровня элементарной операции «бабочка ПЧФ», содержащей два сумматора и одно умножение на степень двойки (сдвиг) по модулю числа Ферма Данный пример иллюстрирует возможность конвейерной реализации даже тех алгоритмов, которые обладают сложной структурой связей

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

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

2 Для задач синтеза конвейерных схем на ПЛИС и полузаказных СБИС адаптированы элементы теории информационной структуры программ, которая изначально предназначались для оптимизации программ под суперкомпьютеры и вычислительные кластеры Использование новых предложенных преобразований позволяет формализовать проблему поиска различных аппаратных реализаций алгоритма, сведя ее к построению и решению систем линейных неравенств

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

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ

1 Анисимов И.Ю. Оценка качества выравнивания каналов тепловизионных приемников при использовании метода микросканирования /

И Ю Анисимов, В И Соловьев // Оптический журнал - 2005 - т 72, № 6 -С 47-50

2 Анисимов И.Ю. Методика синтеза специализированных параллельных вычислительных структур цифровой обработки изображений / И Ю.Анисимов, И А.Малышев//Оптический журнал -2006 -т73, №3 -С 35-39

3 Анисимов И.Ю. Использование сигнальных процессоров для автоматической обработки изображений в реальном времени / И Ю Анисимов // Оптический журнал -2005 -т72,№4 -С 44-47

Лицензия ЛР №020593 от 07 08 97

Подписано в печать 23 05 2008 Формат 60x84/16 Печать цифровая Уел печ л 1,0 Тираж 100 Заказ 3028Ь

Отпечатано с готового оригинал-макета, предоставленного автором, в Цифровом типографском центре Издательства Политехнического университета 195251, Санкт-Петербург, Политехническая ул , 29 Тел 550-40-14 Тел/факс 297-57-76

ВВЕДЕНИЕ.

1. ОБЗОР ПРИНЦИПОВ ОРГАНИЗАЦИИ И ПРОЕКТИРОВАНИЯ СХЕМ ДЛЯ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ.

1.1. Предварительная обработка изображений.

1.2. Способы записи алгоритмов в параллельной форме.

1.3. Процесс отображения программ с однократным присваиванием на матричные процессоры.

1.4. Граф зависимостей.

1.5. Метод построения графа зависимостей по последовательной форме алгоритма.

1.6. Анализ графа зависимостей и виды параллелизма.

1.7. Проектирование схем последовательного действия.

1.8. Выводы по главе.

2. МЕТОДИКА ПРОЕКТИРОВАНИЯ КОНВЕЙЕРНЫХ СХЕМ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ ПО ПРОГРАММЕ.

2.1. Общее содержание методики.

2.2. Оценка времени выполнения алгоритма на параллельном процессоре.

2.3. Построение графа зависимостей.

2.4. Нахождение допустимого множества разверток и максимальной развертки графа зависимостей.

2.5. Конвейерная развертка графа зависимостей, синтез конвейерной граф-машины.

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

2.7. Выводы по главе.

3. ИССЛЕДОВАНИЕ АЛГОРИТМОВ И СИНТЕЗ СТРУКТУР ДЛЯ

ТИПОВЫХ ВЫЧИСЛИТЕЛЬНЫХ ОПЕРАЦИЙ.

3.1. Алгоритм сложения.

3.1.1. Построение графа зависимостей.

3.1.2. Синтез структуры сумматора конвейерного типа.

3.2. Синтез структуры умножителя.

3.2.1. Построение графа зависимостей.

3.2.2. Систолическая структура.

3.2.3. Конвейерная структура.

3.2.4. Бит-последовательная структура.

3.3. Вычисление двумерной свертки.

3.3.1. Граф зависимостей.

3.3.2. Анализ графа зависимостей.

3.3.3. Синтез граф-машины.

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

3.5. Выводы по главе.

4. ПРИМЕНЕНИЕ МЕТОДИКИ СИНТЕЗА ДЛЯ ХАРАКТЕРНЫХ ЗАДАЧ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ.

4.1. Алгоритм вычисления поля градиентов изображения.

4.2. Построение графа зависимостей программы.

4.3. Построение развертки графа зависимостей.

4.4. Синтез граф-машины.

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

4.6. Выводы по главе.

Актуальность проблемы

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

• компенсацией погрешностей фотоприемного или отображающего устройства,

• улучшением качества визуального восприятия изображения,

• сжатием видеоданных,

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

В блоке цифровой обработки алгоритмы должны выполняться в реальном масштабе времени. Это требование строго задает необходимую пропускную способность используемых вычислительных схем. Например, поток изображений высокой четкости (HDTV), имеет интенсивность 110 Мбайт/с, такую же пропускную способность должен иметь вычислительный блок. Для современных универсальных процессоров это практически невыполнимые требования. Современный сигнальный процессор с производительностью 3 Млрд.оп./с способен выполнять около 30 операций на один отсчет изображения (пиксель). Это эквивалентно всего лишь реализации фильтра 5 на 5, а для перечисленных выше задач требуется гораздо больше операций. На современных вычислительных средствах для большинства алгоритмов предварительной обработки изображений достичь такой высокой пропускной способности можно только с помощью параллельной реализации алгоритмов, причем параллельной на уровне элементарных операций. Именно такой реализацией являются конвейерные схемы. В силу сказанного предварительную обработку обычно выносят в отдельный специализированный блок, имеющий конвейерную архитектуру.

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

Современной и перспективной элементной базой для специализированных конвейерных схем являются микросхемы ПЛИС (FPGA) и полузаказные СБИС (ASIC). Благодаря универсальности ПЛИС, они выпускаются большой серийностью, поэтому современной тенденцией является быстрое снижение цен на них при одновременном росте степени интеграции. ПЛИС являются матрицей конфигурируемых элементарных однобитовых процессоров объединенных между собой конфигурируемой системой связей. ПЛИС ориентированы на изделия малой серийности, тогда как полузаказные СБИС - на изделия средней серийности.

Еще одной актуальной областью применения конвейерных схем являются реконфигурируемые сопроцессоры. Идея состоит в том, что в компьютере, помимо центрального универсального процессора, можно иметь специализированный сопроцессор на базе ПЛИС, структура которого перестраивается пользователем под конкретную задачу. Любой алгоритм, выполняемый на компьютере, может иметь какую-то часть, реализуемую аппаратно, что существенно повышает скорость исполнения алгоритма. К примеру, при работе с видеоинформацией в сопроцессор может быть загружен кодек, сжимающий или разжимающий изображения и звуковые сигналы в реальном масштабе времени. Использование сопроцессора актуально при выполнении любых вычислительно сложных задач: научных расчетов, имитационного моделирования, архивирования файлов, играх, работе с трехмерной графикой и др. Необходимо только во время запуска очередного приложения менять конфигурацию сопроцессора, для ПЛИС время изменения конфигурации занимает несколько секунд. Самый технически простой путь интеграции сопроцессора в компьютер состоит в подключении его к шине периферийных устройств. До недавнего времени существовала проблема скорости обмена данными между периферийной шиной и оперативной памятью компьютера. Однако эта проблема стала менее актуальной с появлением высокоскоростных интерфейсов (например, шины PCI Express) и скоростной оперативной памяти. Наивысшая скорость обмена достигается путем подключения сопроцессора непосредственно на шину центрального процессора. Таким образом, реконфигурируемые сопроцессоры могут быть востребованы на массовом рынке компьютеров. Актуальность реконфигурируемых сопроцессоров подтверждают усилия в этом направлении многих известных фирм, в частности

• Cray Inc., широко известный производитель суперкомпьютеров с большой историей, выпустил суперкомпьютер Cray ХТ5™ Hybrid Computing Platform содержащий реконфигурируемые сопроцессоры на базе ПЛИС. [1]

• DRC Computer Corp. предлагает сопроцессорные модули (на базе ПЛИС Xilinx) для многопроцессорных серверов на базе AMD Opteron™, встраиваемые в слоты центральных процессоров, скорость обмена с памятью и соседними процессорами достигает 12.8 Гбит/с. [2]

• Altera совместно с XtremeData продемонстрировали сопроцессорные модули (на базе ПЛИС Altera) для многопроцессорных серверов на базе процессоров Intel Хеоп, подключаемые к межпроцессорной шине Intel FSB. [3]

• Nallatech продемонстрировала сопроцессорные модули (на базе ПЛИС Xilinx) для многопроцессорных серверов на базе Intel Хеоп, подключаемые к межпроцессорной шине Intel FSB. [4]

И в случае реконфигурируемых сопроцессоров, и в случае специализированных процессоров обработки видеоизображений остро стоит проблема проектирования. Это связано в основном с тем, что большинство изделий в этой предметной области выпускается малой серийностью, и вклад проектирования в стоимость одного изделия оказывается существенным. Проектирование конвейерных схем непростая задача, поскольку непосредственно связана с проблемой параллельной реализации алгоритмов. Современные САПР используют в качестве исходных данных только уже готовую конвейерную реализацию алгоритма, описанную на специальном языке (VHDL, Verilog, System С, Handle С и т.п.), и доведенную до уровня абстракции регистровых передач. То есть задача конвейерной реализации алгоритма возлагается на пользователя. Вместо этого хотелось бы задавать исходный алгоритм в последовательной форме (например, используя чистое поведенческое описание VHDL, System С, Handle С, или последовательные языки С++, MatLab, и др.), а по ней получать конвейерную схему автоматически. Это позволило бы значительно сократить срок проектирования и значительно снизить стоимость проектирования.

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

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

• Impulse Accelerated Technologies - программный продукт ImpulseC

• Mentor Graphics - программный продукт Catapult С

• Mitrionics Inc. - программный продукт Mitrion Software1 Development Kit

• Celoxica — программный продукт Agility Compiler

Все эти программные продукты претендуют на поведенческий синтез. Однако никто из них не берет на себя ответственность утверждать, что эта проблема полностью решена. Методы поведенческого синтеза являются коммерческой тайной данных фирм, поэтому нельзя оценить теоретически, насколько он эффективно реализован. Кампания Mentor Graphics, один из лидеров в области САПР, для своего продукта Catapult С приводит следующие данные. Размер автоматически сгенерированных схем оказывается на 20-50% больше, чем в случае ручного проектирования [6]. Таким образом, можно утверждать, что поведенческий синтез, то есть синтез схем по последовательной форме алгоритма, еще далек от совершенства, и 9 требует дальнейшего исследования и развития. Поведенческий синтез схем — обширная область, включающая синтез схем различного назначения. Данная работа ограничена исследованием методов синтеза только конвейерных схем, которые наиболее актуальны в предварительной обработке изображений.

Цель работы:

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

Основные задачи:

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

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

• Исследование и разработка методов представления алгоритма в конвейерной форме.

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

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

Научная новизна работы:

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

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

3. Предложен метод нахождения конвейерной развертки графа зависимостей программы.

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

Практическая значимость:

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

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

3. Исследованы алгоритмы, и получены конвейерные схемы для алгоритмов предварительной обработки изображений: двумерной свертки, вычисления градиентного поля, корреляционной функции, внедренные в сетевые камеры высокого разрешения ЗАО «Ареконт Вижн» (Акт внедрения прилагается к диссертации).

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

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

2. Метод нахождения конвейерного режима выполнения программы на основе нахождения специального вида разверток.

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

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

Реализация результатов работы:

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

Н264 кодера для камер высокого разрешения проводимой ЗАО «Ареконт

Вижн», в НИИ ВЦ «Карат» при проведении ОКР «Сфера», во ФГУП ВНЦ

ГОИ «Государственный оптический институт им. С.И. Вавилова» при проведении ОКР «Сатрап». Акты внедрения приложены к диссертации.

Апробация работы и публикации.

По основным результатам работы были сделаны следующие доклады:

1 Анисимов И.Ю. Методика отображения алгоритмов на параллельные вычислительные структуры. //VII Международная научно-техническая конференция «Распознавание-2005», 4-7 октября 2005 г., г.Курск.

2 Анисимов И.Ю., Мурсаев А.Х. Методика поведенческого синтеза конвейерных схем предварительной обработки изображений. // 61-я научно-техническая конференция профессорско-преподавательского состава СПбГЭТУ «ЛЭТИ», 29 января - 8 февраля 2008 г., г. Санкт-Петербург.

По материалам диссертации были опубликованы 3 научные работы:

1 Анисимов И.Ю. Использование сигнальных процессоров для автоматической обработки изображений в реальном времени. //Оптический журнал, Апрель 2005, т.72, № 4,. - сс.44-47.

2 Соловьев В.И., Анисимов И.Ю. Оценка качества выравнивания каналов тепловизионных приемников при использовании метода микросканирования. //Оптический журнал, Июнь 2005, т.72, № 6,. - сс.47-50.

3 Анисимов И.Ю., Малышев И.А. Методика синтеза специализированных параллельных вычислительных структур цифровой обработки изображений. //Оптический журнал, Март 2006, т.73, № 3,. - сс.35-39.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения и списка литературы. Она содержит 143 страницы машинописного текста (без приложений), 49 рисунков. Список литературы содержит 127 наименований. Нумерация формул и рисунков сквозная по всей диссертации.

4.6. Выводы по главе

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

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

127 синтез конвейерных схем по последовательной программной форме задания алгоритма.

3. На основе предложенной методики была получена новая эффективная конвейерная вычислительная структура для реализации алгоритма вычисления градиентного поля, ориентированная на реализацию на ПЛИС, и предназначенная для обработки видеоизображений формата HDTV в реальном масштабе времени.

4. Предложена оригинальная реализация алгоритма БПЧФ (БПФ в кольце вычетов по модулю чисел Ферма). На этом практическом примере была продемонстрирована универсальность принципа конвейерной обработки. Алгоритм БПЧФ имеет достаточно сложную нерегулярную структуру, тем не менее, даже для этого алгоритма существует конвейерная реализация.

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

ЗАКЛЮЧЕНИЕ

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

В ходе исследований были получены следующие результаты:

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

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

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

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

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

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

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

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

1. Cray Introduces Next-Generation Supercomputers Electronic resource.//Cray Inc. News release. - SEATTLE, WA: Cray Inc. - November 6, 2007. - Mode of access: http://investors.cray.com/phoenix.zhtml?c=98390&p=irolnewsArticle print&ID=1073071 &highlight=

2. А.Бухтеев. Средства ESL-проектирования компании Celoxica: программно ориентированный подход//Электроника: Наука, Технология, Бизнес. 2006. - №8. - С.106-111

3. Kevin Morris, Catapult С Mentor Announces Architectural Synthesis//FPGA and Programmable Logic Journal. 2004. - Vol.3, No.9.

4. Abbot L., Haralick R.M., Zhuang X. Pipeline Architectures for Morphologic Image Analysis//Machine Vision and Applications. 1988. - Vol.1. - P.23-40.

5. Sanz J.L.C., Dinstein I. Projection-Based Geometric Feature Extraction for

6. Computer Vision: Algorithms in Pipeline Architectures/ЛЕЕЕ Transactions on Pattern Analysis and Machine Intelligence. 1987. — Vol.9; No.l. — P.160-168.

7. Gennery D.B., Wilcox В., A Pipelined Processor for Low-Level Vision//IEEE Conference on Computer Vision and Pattern Recognition. 1985. - Vol.85. -P.608-613.

8. Jonker P.P., Komen E.R., Kraaijveld M.A., A Scalable Real-Time Image-Processing Pipeline/ZMachine Vision and Applications. 1995. - Vol.8; No.2.-P.l 10-121.

9. The Pipe-Group Architecture Real Time Active Vision/ P.F. McLauchlan, I.D. Reid, S.M. Fairley, D.W. Murray//Real-Time Imaging. 1997. - Vol.3; No.5.-P.319-330.

10. Fleury M., Downton A.C., Clark A.F., Pipelined parallelisation of automatic face inspection//Machine Vision and Applications. 2000. -Vol.12; No.4. -P.203-211.

11. Wu C.W., Bit-level pipelined 2-D digital filters for real-time image processing//IEEE Transactions on Circuits and Systems for Video Technology. 1991. - Vol.1; No.l. -P.22-34.

12. Lu Т., Azimi-Sadjadi M.R. Interleaved pipeline structures for two-dimensional recursive filtering//IEEE Transactions on Circuits and Systems for Video Technology. 1993. - Vol.3; No.l. - P.87-91.

13. Ferretti M., Boffadossi M., A parallel pipelined implementation of LOCO-I for JPEG-LS//International Conference on Pattern Recognition. 2004.1. P.769-772.

14. Abdelguerfi M., Sood A.K., Khalaf S., Parallel bit-level pipelined VLSI processing unit for the histogramming operation/ЛЕЕЕ Conference on Computer Vision and Pattern Recognition. 1988. - Vol.88. - P.945-950.

15. C.R. Dyer, A. Rosenfeld. Image Processing by Memory-Augmented Cellular Automata/ЯЕЕЕ Transactions on Pattern Analysis and Machine Intelligence. -1981. -Vol.3.-P.29-41.

16. A. Rosenfeld, A. Wu. Parallel computers for Region-Level Image Analysis//Pattern Recognition. 1982. - Vol.15. - P.41-50.

17. T. Dubitzki, A.Wu, A. Rosenfeld. Parallel Computations of Contour Properties/ЛЕЕЕ Transactions on Pattern Analysis and Machine Intelligence. -1981. -Vol.3.-P.331-337.

18. H. L. Groginsky, G. A. Works. A pipeline fast Fourier transform/ЛЕЕЕ Transactions on Computers. 1970. - Vol.19; No.ll. -P.1015-1019.

19. P. Pirsch. Architectures for Digital Signal Processing. New York: John Wiley & Sons Inc., 1998. - 419 p.

20. Pipeline architecture for 8x8 discrete cosine transform/ J. Takala, J. Nikara, D. Akopian et al.// Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing. Istanbul, Turkey: 2000. — P.3303-3306.

21. Array Architectures for Iterative Algorithms/ H.V Jagadish, S.K. Rao, T. Kailath//Proceedings of IEEE. 1987. - Vol.75. -P.1304-1321.

22. Kung, H.T., Ruane, L.M., Yen, D.W.L. Two-Level Pipelined Systolic Array for Multidimensional Convolution//Image and Vision Computing. 1983. -Vol.1; No.l.-P.30-36.

23. Fountain, T.J., Matthews, K.N., Duff, M.J.B., The CLIP7A Image Processor/ЯЕЕЕ Transactions on Pattern Analysis and Machine Intelligence. 1988. - Vol.10; No.3. -P.310-319.

24. Duff, M.J.B., Watson, D.M., Deutsch, E.S., A Parallel Computer for Array Processing//International Federation of Information Processing. 1974. — Vol.74.-P.94-97.

25. Gerritsen, F.A., A Comparison of the CLIP4, DAP and MPP Processor-Array Implementations//Computer Structures for Image Processing. 1983. -Vol.83.-P.15-30.

26. Ahuja, N., Swamy, S., Multiprocessor Pyramid Architectures for Bottom-Up Image Analysis//IEEE Transactions on Pattern Analysis and Machine Intelligence. 1984. - Vol.6; No.4, - P.463-475.134

27. VLSI Array Architecture for Pattern Analysis and Image Processing/ZHandbook of Pattern Recognition and Image Processing. New York: Academic press, 1986. -P.471-496.

28. Orthogonal Multiprocessor Sharing Memory with an Enhanced Mesh for Integrated Image Understanding/ K.Hwang, H.M.Alnuweiri, V.K.P.Kumar, D.Kim//Computer Vision Graphics and Image Processing. 1991. — Vol.53; No.l. -P.31-45.

29. Hierarchical Multiple-SIMD Architecture for Image Analysis/ G.R.Nudd, N.Francis, T.J.Atherton et al.//Machine Vision and Applications, — 1992. -Vol.5.-P.85-103.

30. Nudd, G.R., Atherton, TJ., Kerbyson, D.J., An heterogeneous M-SIMD architecture for Kalman filter controlled processing of image sequences/ZProceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. 1992. - P.842-845.

31. VLSI Implementation of Systolic and 3-D Cellular Architectures for Image Processing / J.G.Nash, R.D.Etchells, J. Grinberg et al. // Image Understanding Workshop. 1984. - P. 56-64.

32. Fujita, Y., Yamashita, N., Okazaki, S., A Real-Time Vision System Using an Integrated Memory Array Processor Prototype//Machine Vision and Applications. 1994. - Vol.7, No.4, P.220-228.

33. Yamashita, N., Fujita, Y., Okazaki, S., An Integrated Memory Array Processor with a Synchronous-DRAM Interface for Real-Time Vision Applications // International Conference on Pattern Recognition. 1996. -Vol. IV.-P. 575-580.

34. Pissaloux, E.E., An Adaptive Parallel System Dedicated to Projective Image Matching // International Conference on Image Processing. — 2000. — Vol. II. -P. 507-510.

35. Parallel Algorithm for a Very Fast 2D Velocity Field Estimation / F.LeCoat, E.E.Pissaloux, P.Bonnin // International Conference on Image Processing, — 1997.-Vol. II.-P. 179-184.

36. Design and Realisation of a Parallel Systolic Architecture Dedicated to Aerial Image Matching / F.LeCoat, E.E.Pissaloux, P.Bonnin // IAPR Workshop on Machine Vision Applications. 1998, - P. 402-405

37. Diamantaras, K.I., Kung, S.Y., A Linear Systolic Array for Real Time Morphological Image Processing // Journal of VLSI Signal Processing Systems for Signal Image and Video Technology. 1997. — Vol. 17; No. 1. -P. 43-55.

38. Guerra, C., 2D Object Recognition on a Reconfigurable Mesh // Pattern Recognition. 1998. - Vol. 31; No. 1. - P. 83-88.

39. Chung Y., Prasanna V.K., Parallelizing Image Feature Extraction on Coarse-Grain Machines // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1998. - Vol. 20; No. 12 - P. 1389-1394.

40. Chung, Y., Prasanna, V.K., Wang, C.L., Parallel Algorithms for Linear Approximation on Distributed Memory Machines // Proceedings of Image Understanding Workshop. 1996. - P. 1465-1472.

41. Meribout, M., Nakanishi, M., Ogura, Т., A Real-Time Image Segmentation on a Massively Parallel Architecture // Real-Time Imaging. — 1999. — Vol. 5; No. 4.-P. 279-291.

42. Kiryukhin, G., Celenk, M., Implementation of 2D-DCT on XC4000 Series FPGA Using DFT-based DSFG and DA Architectures // International Conference on Image Processing. 2000. - Vol. III. - P. 302-305.

43. Alnuweiri, H.M., Prasanna Kumar, V.K., Optimal Geometric Algorithms on Fixed-Size Linear Arrays and Scan Line Arrays. // IEEE Computer Vision and Pattern Recognition. 1988. - P. 931-936.136

44. Gealow, J.C., Love, N.S., Hall, G., Masaki, I., Sodini, C.G., Desktop Programmable Pixel-Parallel Accelerator for High Speed Image Processing // Proceedings of Image Understanding Workshop. 1997. — P. 1379-1384.

45. Вычислительные системы с массовым параллелизмом: Учеб. пособие. / А.И. Водяхо, А.Ф. Казак, Д.В. Пузанков, В.А Торгашев. СПб.: Издательство СПбГЭТУ «ЛЭТИ», 2000. - 64 с.

46. Спецпроцессоры в ЭВМ: Учеб. пособие / А.В. Анисимов, В.Д. Байков, А.А. Валов и др.; ЛЭТИ. Д., 1989.

47. Функционально-ориентированные процессоры / А.И. Водяхо, В.Б. Смолов, В.У. Плюснин и др. / Под ред. В.Б. Смолова. Л.: Машиностроение, 1988.

48. Байков В.Д., Смолов В.Б. Специализированные процессоры: итерационные алгоритмы и структуры. — М.: Радио и связь, 1985. — 288 с.

49. Кун С. Матричные процессоры на СБИС: Пер. с англ. М: Мир, 1991. — 672 с.

50. Сверхбольшие интегральные схемы и современная обработка сигналов: Пер. с англ./Под ред. С. Гунна, X. Уайтхауса, Т. Кайлата. -М.: Радио и связь, 1989.-472 с.

51. Супер ЭВМ. Аппаратная и программная организация / Под. ред. С. Фернбаха: Пер. с англ.- М.: Радио и связь, 1991. 320 е.: ил.

52. Мур У., Маккейб Э., Уркхарт Р. Систолические структуры. М.: Радио и связь. 1993г. - 416с.

53. Каневский Ю.С. Систолические процессоры. — Киев: Техника, 1991 г. -173 с.

54. Фрумкин М.А. Систолические вычисления. М.: Наука, 1990. - 191 с.

55. Варшавский В.И. и др. Однородные структуры. Анализ. Синтез. Поведение.- М.: Энергия, 1973.

56. Фет Я.И. Массовая обработка информации в специализированных однородных процессорах. Новосибирск: Наука. Сибирское отделение,1371976.

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

58. Однородные вычислительные среды и систолические структуры. 1-я Всесоюзная конференция, Львов, 1990.

59. Karp R.M., Miller R.E., Winograd S. The organization of computations for uniform recurrence equations // Journal of ACM. 1967. - Vol. 14(3). - P. 563-590.

60. Rao S.K. Regular Iterative Algorithms and Their Implementations on Processor Arrays: PhD thesis. Stanford University, Stanford, California, 1985.

61. Moldovan D.I. On the design of algorithms for VLSI systolic arrays // Proceedings of the IEEE. 1983. - Vol. 71(1). - P. 113-120.

62. Miranker W.L. Winkler A. Space-time representations of computational structures // Computing. 1984. - Vol. 32; No. 2. - P. 93-114.

63. Quinton P. Automatic synthesis of systolic arrays from Uniform Recurrentth

64. Equations // Proceedings of 11 Annual Symposium on Computer Architecture. 1984. - P. 208-214.

65. VLSI Signal Processing / Cappello P.R. et al. // NY: IEEE Press. 1984. - P. 229-238.

66. Краснов С.А. Транспьютеры, транспьютерные вычислительные системы и Оккам. В сб. Вычислительные процессы и системы / Под ред. Г.И. Марчука. Вып. 7 М.: Наука. Гл. ред. Физ.-мат. лит., 1990. - 352 с.

67. Б. А. Головкин. Параллельные вычислительные системы. М: Наука, 1980 г.,-520 стр.

68. Корнеев В. В. Параллельные вычислительные системы. М: Нолидж. 1999 г.,-320 стр.

69. B.C. Седов. Матрица одноразрядных процессоров. Львов: НТЦ "Интеграл", 1991.

70. Специализированные процессоры для высокопроизводительной обработки данных/ Под ред. В.Е. Котова, Н.Н. Миренкова. — Новосибирск: Наука. Сибирское отделение, 1988

71. Fortes, J.A.B., Wah, B.W., Special Issue: Systolic Arrays-From Concept To Implementation // IEEE Computer. 1987. - Vol. 20; No. 7. - P. 12-103.

72. Воеводин B.B., Воеводин Вл.В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2002. 608 с.

73. Воеводин В.В. информационная структура алгоритмов. — М: МГУ, 1997. 139 с.

74. Воеводин В.В. Математические модели и методы в параллельных процессах. М: Наука, 1986. - 296 с.

75. Воеводин В.В. Математические основы параллельных вычислений. М: МГУ, 1991.-345 с.

76. Воеводин В.В. Параллельные структуры алгоритмов и программ. М.: ОВМ АН СССР. 1987. - 148 с.

77. Воеводин В.В., Краснов С.А. Математические вопросы проектирования систолических массивов / Препринт ОВМ АН СССР. 1985. —N80. 26 с.

78. Feautrier P. Scalable and Structured Scheduling // International Journal of Parallel Programming. 2006. - Vol. 5. - P. 459-487.

79. Application Domain-Driven System Design for Pervasive Video Processing / Z. Chamski, M. Duranton, A. Cohen // Ambient Intelligence: Impact on Embedded System Design. 2003. - P. 251-270.

80. Feautrier P. Array Dataflow Analysis In Pande S. and Agrawal D., editors, Compiler Omptimizations for Scalable Parallel Systems. // Lecture Notes in Computer Science. 2001. - Vol. 1808; chapter 6. - P. 173-216.

81. Griebl M., Feautrier P., Lengauer C. Index Set Splitting // International139

82. Journal of Parallel Programming. 2000. - Vol. 28(6). - P. 607-631.

83. Collard J.-F., Feautrier P., Risset T. Construction of DO loops from systems of affine constraints // Parallel Processing Letters. 1995. - Vol. 5(3). - P. 421-436.

84. Feautrier P. Compiling for Massively Parallel Architectures: a Perspective. // Microprogramming and Microprocessors. 1995. - Vol. 41. - P. 425-439.

85. Feautrier P. Toward Automatic Distribution // Parallel Processing Letters. — 1994. Vol. 4(3). - P. 233-244.

86. Feautrier P. Some Efficient Solutions to the Affine Scheduling Problem, I, One Dimensional Time // International Journal of Parallel Programming. — 1992.-Vol. 21(5).-P. 313-348.

87. Feautrier P. Some Efficient Solutions to the Affine Scheduling Problem, II, Multidimensional Time. // International Journal of Parallel Programming. — 1992. Vol. 21(6). -P. 389-420.

88. Feautrier P. Dataflow Analysis of Scalar and Array References. // International Journal of Parallel Programming. 1991. - Vol. 20(1). - P. 2353.

89. Feautrier P. Parametric Integer Programming. // RAIRO Recherche Operationnelle. 1988. - Vol. 22. - P. 243-268.

90. Ершов А.П. Современное состояние теории схем программ // Проблемы кибернетики. 1973. - №27. - С. 87-110.

91. Мультипроцессорные системы и параллельные вычисления / Под ред. Ф.Г. Энслоу. М: Мир, 1976. - 384 с.

92. Гэри М. Джонсон Д. Вычислительные машины и труднорешаемые задачи. М: Мир. 1982ю - 416 с.

93. Программирование на параллельных вычислительных системах: Пер. с анг./Р. Бэбб, Дж. Мак-Гролу, Т. Акселрод и др.; под ред. Р. Бэбба И. -М.: Мир, 1991 -376 с.

94. Хоар Ч. Взаимодействующие последовательные процессы: Пер. с англ. -М.: Мир, 1989. 264 с.

95. Lamport L. The Parallel Execution of DO Loops // Communications of the ACM. 1974. - Vol. 17; No. 2. - P. 83-93.

96. Валысовский В.В. Распараллеливание алгоритмов и программ. Структурный подход. М.: Радио и связь, 1989. -176с.

97. С.Немнюгин, О.Стесик, Параллельное программирование для многопроцессорных вычислительных систем. СПб:, "БХВ-Петербург", 2002.

98. Шпаковский Г.И., Серикова Н.В. Программирование для многопроцессорных систем в стандарте MPI: Пособие Мн.: БГУ, 2002. -323 с

99. А.А. Букатов, В.Н. Дацюк, А.И. Жегуло. Программирование многопроцессорных вычислительных систем. Ростов-на-Дону. Издательство ООО "ЦВВР", 2003. - 208с

100. Антонов А.С. Параллельное программирование с использованием технологии MPI: Учебное пособие. М: Изд-во МГУ, 2004. - 71 с.

101. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. — Вильяме, 2003 512 стр.

102. Kanevski, J.S., Sergyienko, A.M., Piech H. A method for the structural synthesis of pipelined array processors // 1-st Int. Conf. Parallel Processing and Applied Mathematics, PPAM'94, Czestochowa (Poland), Sept. 14-16; 1994.-P. 100-109.

103. Майоров С.А., Новиков Г.И. Принципы организации цифровых машин. — JI.:, «Машиностроение», 1974. 432 с.

104. Глушков В.М. Синтез цифровых автоматов. -М.: Физматгиз, 1962.

105. Лазарев. В.Г., Пийль Е.И. Синтез управляющих автоматов. М.: «Энергия», 1970,-448 с.

106. Баранов С.И. Синтез микропрограммных автоматов. Л.: «Энергия», 1974.-216 с.

107. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах / В.И.Варшавский, М.А.Кишиневский,

108. В.Б.Мараховский и др. / Под ред. В.И.Варшавского. — М.: Наука, 1986. — 398 с.

109. Угрюмов Е.П. Цифровая схемотехника. СПб.: БХВ-Петербург, 2001. — 528 с.

110. Грушвицкий Р.И., Мурсаев А.Х., Угрюмов Е.П. Проектирование систем на микросхемах программируемой логики. СПб.: БХВ-Петербург, 2002. - 608 с.

111. Баранов С.Н., Ноздрунов Н.Р. Язык Форт и его реализация. Л.: Машиностроение, 1988.

112. Кострикин А.И. Введение в алгебру. Часть I. Основы алгебры: Учеб. для вузов. М.:Физматлит, 2004. - 272 с.

113. Кострикин А.И. Введение в алгебру. Часть И. Линейная алгебра: Учеб. для вузов. М.:Физматлит, 2001. — 368 с.

114. Методы компьютерной обработки изображений / Под ред. В.А. Сойфера. 2-е изд., испр. — М.: Физматлит, 2003. - 784 с.

115. А.С. Солодовников. Системы линейных неравенств. — 2-е изд. М.: Наука, 1977.-112 с.

116. Ларин P.M., Плясунов А.В., Пяткин А.В. Методы оптимизации. Примеры и задачи: Учеб. пособие. Новосиб. ун-т. Новосибирск. 2003. — 115 с.

117. Eyre J., Bier J. The Evolution of DSP Processor // IEEE Signal Processing magazine. 2000, March.

118. Куприянов M.C., Матюшкин Б.Д. Цифровая обработка сигналов: процессоры, алгоритмы, средства проектирования. — 2-е изд., перераб. и доп. СПб.: Политехника, 1999. - 592 с.

119. Солонина А.И., Улахович Д.А., Яковлев Л.А. Алгоритмы и процессоры цифровой обработки сигналов. СПб.: БХВ-Петербург, 2002. - 464 с.

120. С6000 DSPs : Benchmarks Electronic resource. // Texas Instruments inc. -Mode of access:http://dspvillage.ti.com/docs/catalog/generation/details.ihtml?templateId=5151424&path=templatedata/cm/dspdetail/data/c600Q benchmarks

121. TMS320C67x DSP Library Programmer's Reference Guide Electronic resource. // Texas Instruments inc. — Literature Number SPRU657. Dallas: Texas Instruments, February 2003. - Mode of access: http://focus.ti.com/docs/toolsw/folders/print/sprcl21.html

122. IEEE 1076-1993. Standard VHDL Language Reference Electronic resource.- 1994. Mode of access:http://ieeexplore.ieee.org/servlet/opac?punumber=3116

123. Virtex-4 Family Overview. // Xilinx. Literature Number DS112 (vl.6). -October 10, 2006

124. Маклеллан Дж.Х., Рейдер Ч.М. Применение теории чисел в цифровой обработке сигналов: Пер. с англ. М.: Радио и связь, 1983. - 264 с.