Исследование и разработка методов поведенческого синтеза конвейерных схем для цифровой обработки видеоизображений тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат технических наук Анисимов, Игорь Юрьевич

• Анисимов, Игорь Юрьевич
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Анисимов, Игорь Юрьевич

ВВЕДЕНИЕ.

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. Исследование параллельной структуры алгоритма, являющееся основой предложенной методики, позволяет значительно повысить качество проектируемых схем. Применяемые методы анализа программ и синтеза схем позволяют исследовать все возможные параллельные реализации алгоритма и выбирать из них оптимальные в соответствии с заданным критерием, зависящим от целевой элементной базы.

Список литературы диссертационного исследования кандидат технических наук Анисимов, Игорь Юрьевич, 2008 год

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 с.