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

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

Герценбергер Константин Викторович

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

05.13.11- Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

005549681

5 и:0!! 2014

Москва-2014

005549681

Работа выполнена в Национальном исследовательском ядерном университете «МИФИ»

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

ЧЕПИН Евгений Валентинович

Официальные оппоненты: доктор технических наук, профессор

КАЛЯНОВ Георгий Николаевич Институт проблем управления им. В. А. Трапезникова РАН, заведующий лабораторией

кандидат физико-математических наук ЭЙСЫМОНТ Леонид Константинович ФГУП "НИИ "Квант", научный консультант

Ведущая организация: ЗАО «Московский центр ЗРАЯС-

технологий» (МЦСТ)

Защита диссертации состоится 30 июня 2014 года в 15 часов на заседании диссертационного совета Д 212.130.08 при Национальном исследовательском ядерном университете «МИФИ» по адресу: 115409, г. Москва, Каширское шоссе, дом 31. Тел. для справок: +7 (499) 324-84-98.

С диссертацией можно ознакомиться в библиотеке Национального исследовательского ядерного университета «МИФИ» и на сайте НИЯУ МИФИ http://ods.mephi.ru.

Отзывы в двух экземплярах, заверенные печатью, просьба направлять по адресу: 115409, г. Москва, Каширское ш., д. 31, диссертационные советы НИЯУ МИФИ, тел.: +7 (499) 324-84-98.

Автореферат разослан 2-"/ мая 2014 г.

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

диссертационного совета Горбатов В. С.

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

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

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

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

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

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

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

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

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

Для достижения поставленной цели в ходе диссертационной работы были решены следующие задачи.

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

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

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

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

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

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

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

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

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

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

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

Научная новизна.

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

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

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

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

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

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

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

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

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

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

Внедрение результатов работы. Теоретические и практические результаты работы использовались при выполнении НИР по направлению "Разработка архитектуры, системы управления и программного обеспечения кластерной вычислительной системы" для компании ЗАО "ACT" и в работах по теме Объединенного института ядерных исследований №02-0-1065-2007/2014 "Развитие экспериментальной базы ОИЯИ для получения интенсивных пучков тяжелых ионов и поляризованных ядер". Получены соответствующие акты о внедрении результатов диссертационной работы в ЗАО "ACT" и ОИЯИ. Отдельные результаты и методы использовались при разработке комплекса обработки изображений печатных плат в ФГУП "Концерн "Системпром" и гранте РФФИ №09-07-00459-а.

Апробация. Основные результаты диссертационной работы докладывались на следующих конференциях: научных сессиях МИФИ в 2004-2008 годах (г. Москва), на 9-ой и 10-ой международной конференции по компьютерным наукам и информационным технологиям CSIT (Башкортостан в 2007 г., г. Анталия в 2008 г.), на 7-ой международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности" (г. Санкт-Петербург, 2009 г.), на 53-ей научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук" (г. Москва, 2010 г.), на международной научной конференции "Математическое моделирование и вычислительная физика" ММСР (г. Дубна, 2013 г.).

Публикация результатов. По основным положениям диссертационной работы опубликовано 17 печатных работ, из них 3 -в изданиях, рекомендованных ВАК, и 1 работа в журнале, входящем в базу цитирования Scopus.

Основные положения работы, выносимые иа защиту:

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

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

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

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

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

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

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

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

Личный вклад автора. Основные научные результаты получены автором лично.

Структура и объем работы. Диссертационная работа включает введение, четыре главы, заключение, список литературы и пять приложений. Общий объем работы 138 страниц машинописного текста (без учета приложений). Работа содержит 60 рисунков, 3 таблицы и 84 наименования библиографии.

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

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

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

целом. Для каждого класса определены алгоритмы распараллеливания обработки данных, которые в дальнейшем объединены в новом подходе диссертационной работы.

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

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

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

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

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

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

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

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

Для описания схемы планируемой аппаратной платформы сформирован список основных аппаратных компонент с атрибутами:

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

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

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

3. Коммутатор, концентратор, маршрутизатор: имя, тип сети, реальная пропускная способность, количество портов вход/выход.

4. Соединительная связь: тип сети, реальная пропускная способность.

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

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

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

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

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

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

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

При разработке аналитической модели для каждой параллельной алгоритмической структуры и типа параллельной архитектуры проведен вывод характеристик производительности параллельной обработки. Ниже приведены формулы только для многопроцессорной системы с распределенной памятью. Вводятся следующие обозначения: количество узлов - P„ode, средняя скорость линейного чтения/записи носителя данных - W, реальная пропускная способность сети с характерной для задачи длиной сообщений - Вы, объем обрабатываемых данных — п, Ti - время последовательной обработки, а Вп выбирается как min(i?.v, W). Для точечного алгоритма распараллеливания ускорение вычисляется как:

2 * — + Ti BD * pnode

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

стремится к величине Вп * + Эффективность независимо от повышения общей размерности задачи падает с ростом числа процессоров. Для локального алгоритма выведена следующая формула:

5 (п) =_Вр.Р^.^ + ъ)_

Р Рпойе * П * (1 + (РП0£ге-1) * сМ(+Мг)) + Во* Тг* (1 + РпоЛе* (М,+Мг)) + пЛ }

где М{ = ^ и Мг = ^ - коэффициенты перекрытия, а X/ и 1Г - длины перекрытия слева и справа соответственно.

Ускорение алгоритма параллельной редукции вычисляется как:

V") - —. о)

т + Г 2 'Г п+Г Г

п-г в0 вы

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

к «Во + к

где / - длина конвейера, п0, т,..., П1 - объем данных, поступающих на ступени конвейера, к = п/п0, а 7д - время обработки и передачи на самой медленной ступени конвейера.

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

Бр ^ =-;—т-Л, т-1-—-, (5)

Во Вы

где дерево рекурсий имеет глубину I и арность т, время обработки в узлах - Т, размер результата — г, к- число распараллеленных уровней. Число уровней для максимального ускорения при фиксированной п:

/ Ш-1 , \

/71 * ——:--V ЛГ \

-В =-- + Т (171-1)

от Т*\пт 4 '

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

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

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

Имитационная модель программно-аппаратной платформы формируется из набора моделей отдельных компонент: вычислительного узла, коммуникационной среды и устройств, хранилища данных, моделей передачи данных по сети и обработки на узлах. Модель вычислительного узла и хранилища данных построена на основе существующей в OMNeT-н- модели сетевого хоста StandartHost, дополненной разработанной моделью аппаратных ресурсов, отвечающей за занятие времени в узле для имитации обработки. В качестве модели сетевого коммутатора и концентратора выбран готовый модуль EtherSwitch, модели маршрутизатора - модуль Router. Модель сетевого соединения определяется существующим классом Channel. Для моделирования передачи и обработки данных в соответствии с выбранной параллельной алгоритмической структурой используются модели сетевого приложения TCPBasicClientApp и TCPGenericSrvApp пакета INET Framework. Описание и состав компонент приведены в диссертационной работе и руководстве пользователя OMNeT++.

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

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

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

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

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

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

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

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

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

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

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

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

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

Следующий этап — автоматизированная генерация параллельного кода для цепочки функций обработки изображений или сигналов. Разработана подсистема декомпозиции последовательного исходного кода распараллеливаемой функции по составляющим блокам выбранной ПАС. Реализован модуль генерации параллельного кода, который проводит верификацию, лексический и синтаксический анализ исходного кода функции при помощи программного анализатора ANTLR. Далее генерируется параллельный код в соответствии с алгоритмами инкрементного расширения, разработанными во второй главе. Для каждой ПАС реализован свой алгоритм автоматической генерации параллельного кода функции для исходного кода на языке программирования С++. Возможно добавление модулей других языков программирования.

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

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

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

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

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

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

Для запуска в параллельном режиме на системе с разделяемой памятью в библиотеку был добавлен разработанный класс CIPImage_Thread. Таймирование многопоточного выполнения функций проводилось на 4-х процессорном компьютере Intel Pentium Xeon 3. Результаты приведены на рис. 1. Погрешность определения

ускорения в аналитической модели для функций, выполняющихся более 2 секунд, составило до 14%, в имитационной модели - до 8%.

5000-----------------------------------------------------------------—........—----*

----------------

4000—.............................. - .............-......... . ....... . -;

3500................... ................... ..... ....—------

| ЗООО------------------------------------------- -----------------

с. Многопоточный режим о 2Ь00———-----—— - ---——-———. • —— - ■ • .1

5! • а Однопо точный режим

| 2000- —-----—---—---? ™ —• ~~~--г---

: I! I 111, 11

МИШ

Операции

Рис. 1. Сравнение времен последовательного и параллельного режима Для систем с распределенной памятью был разработан класс параллельной обработки изображений CIPImage_MPI. Погрешность определения ускорения для функций, выполняющихся более 2 секунд, на "кластере" из двух машин составила до 12% в аналитической модели, в имитационной - до 7%.

Разработанные методы и среда визуального программирования были применены для распараллеливания цифровых фильтров сигналов на кластерной системе для компании "ACT". В ходе данной работы разработан программный комплекс цифровой фильтрации сигналов. Реализованы пять алгоритмов на языке С++: одномерный цифровой КИХ-фильтр, БИХ-фильтр, КИХ-фильтр сигнала по столбцам, подстраиваемый компенсационный фильтр и фильтр высоких частот.

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

При помощи генератора параллельного кода в интегрированной среде распараллелены фильтры сигналов, которым соответствовали

шШШ

it

1

iffllisni. мнрвдиишш

■i i ilmn mif ¡ip ■ ¡ПИ il IIII i № is iliiii ti r i; si it ii BitII i! r s1 ii I; I! i! II nflT

7i

зм

BO,

и

ПАС: локальный алгоритм, параллельная конвейеризация и точечный алгоритм. На рисунке 2 приведена зависимость времени обработки сигнала от числа процессоров для КИХ-фильтра и представлены

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

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

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

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

Поставленная цель диссертационной работы была достигнута.

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

В изданиях, рекомендованных ВАК Минобрнауки России

1. Герценбергер, К. В. Аналитическая модель оценки производительности многопроцессорной обработки данных для набора параллельных алгоритмических структур / К. В. Герценбергер, Е. В. Чепин // Бизнес-информатика : междисциплинарный научно-практический журнал. - 2011. - № 4 (18). - С. 24—30.

2. Герценбергер, К. В. Имитационная модель оценки эффективности многопроцессорной обработки данных для параллельных алгоритмических структур / К. В. Герценбергер, Е. В. Чепин // Программные продукты и системы : международный журнал.-2012,-№2.-С. 117-120.

3. Герценбергер, К. В. Среда визуального программирования для разработки параллельного программного обеспечения обработки изображений и сигналов / К. В. Герценбергер, А. А. Дюмин, П. С. Сорокоумов // Программные продукты и системы : международный журнал. - 2013. - № 2. - С. 208-213.

4. Герценбергер, К. В. Визуализация событий эксперимента MPD коллайдера NICA для системы мониторинга / К. В. Герценбергер, С. П. Мерц, Е. В. Чепин // Научная визуализация. - 2014. - Том 6, № 1. - С. 1-19. - Режим доступа к журн.: http://sv-joumal.com/2014-l/. (SCOPUS)

Публикации в других изданиях

5. Бирюков, П. Ю. Разработка системы автоматической обработки печатных плат / П. Ю. Бирюков, И. В. Богин, К. В. Герценбергер, А. И. Фирсов, Е. В. Чепин // Науч. сессия МИФИ-2004 : сб. науч. тр. -М.: МИФИ, 2004.-Т. 12.-С. 184-186.

6. Бирюков, П. Ю. Сопоставление образов с шаблоном в системе автоматической обработки изображения печатных плат / П. Ю. Бирюков, И. В. Богин, К. В. Герценбергер, А. И. Фирсов, Е. В. Чепин // Науч. сессия МИФИ-2005 : сб. науч. тр. - М. : МИФИ, 2005. - Т. 12. -С. 157-158.

7. Богин, И. В. Реализация параллельной обработки цифровых изображений для библиотеки IPPLab MSCo / И. В. Богин, К. В. Герценбергер, Е. В. Чепин // Науч. сессия МИФИ-2006 : сб. науч. тр. - М.: МИФИ, 2006. - Т. 12. - С. 139-140.

8. Gertsenberger, К. V. Implementation parallel processing of digital signals on cluster system / К. V. Gertsenberger, E. V. Chepin // Proc. of the International Workshop on Computer Science and information technologies : CSIT2007 : Bashkortostan, 2007. - Ufa State Aviation Technical University, 2007.-Vol. l.-P. 152-155.

9. Гайдученко, А. Б. Библиотека цифровой фильтрации сигналов для реализации на вычислительном кластере / А. Б. Гайдученко, К. В. Герценбергер, И. И. Егоров, А. В. Прохоров, Е. В. Тестов, Е. В. Чепин // Науч. сессия МИФИ-2007 : сб. науч. тр. - М. : МИФИ, 2007. - Т. 12. -С. 150-151.

10. Герценбергер, К. В. Реализация параллельной фильтрации цифровых сигналов на кластерной системе / К. В. Герценбергер,

Е. В. Чепин // Науч. сессия МИФИ-2007 : сб. науч. тр. - М. : МИФИ, 2007.-Т. 12.-С. 148-149.

11. Gertsenberger, К. V. Using a CASE-oriented approach for parallel software development / К. V. Gertsenberger, E. V. Chepin // Proc. of the International Workshop on Computer Science and information technologies : CSIT'2008 : Antalya, Turkey, 2008. - Ufa State Aviation Technical University, 2008. - Vol. 1. - P. 63-68.

12. Герценбергер, К. В. Эффективность распараллеливания глобальных операций на кластерной системе / К. В. Герценбергер // Науч. сессия МИФИ-2008. -М.: МИФИ, 2008. - Т. 12. - С. 155-156.

13. Герценбергер, К. В. Разработка программного комплекса параллельной обработки сигналов на кластерной системе / К. В. Герценбергер, С. Д. Горев, Е. В. Чепин // Науч. сессия МИФИ-2008 : сб. науч. тр.-М.: МИФИ, 2008. - Т. 12.-С. 125-126.

14. Герценбергер, К. В. Методы параллельной обработки изображений и сигналов в зависимости от локальности вычислений / К. В. Герценбергер // Сб. тр. Седьмой международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности". - СПб. : Изд-во Политехи, ун-та, 2009. - Т. 2. - С. 49-50.

15. Герценбергер, К. В. Использование параллельных алгоритмических структур для автоматизации процесса разработки параллельного программного обеспечения / К. В. Герценбергер, Е.В. Чепин // Труды 53-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». - М.: МФТИ, 2010. - Часть XI: Информационные бизнес системы. - С. 54-55.

16. Герценбергер, К. В. Об аппаратно-программном комплексе для определения характеристик электромагнитных полей / К. В. Герценбергер, П. С. Сорокоумов, Е. В. Чепин // Труды 53-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». - М. : МФТИ, 2010. - Часть XI: Информационные бизнес системы. - С. 56-57.

17. Герценбергер, К. В. Проектирование распределенного вычислительного комплекса для эксперимента MPD коллайдера NICA / К. В. Герценбергер // XVII Научная конференции молодых учёных и специалистов к 100-летию В. П. Джелепова. Труды конференции. -Дубна : ОИЯИ, 2013.-С. 188-192.

Подписано в печать:

28.04.2014

Заказ № 10014 Тираж -100 зкз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Национальный исследовательский ядерный университет "МИФИ"

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

Л/ 1 ГН /. С

Герценбергер Константин Викторович

МЕТОДЫ И СРЕДСТВА РАЗРАБОТКИ ПАРАЛЛЕЛЬНОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ОБРАБОТКИ

ИЗОБРАЖЕНИЙ И СИГНАЛОВ

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

Научный руководитель: кандидат технических наук, доцент Чепин Е. В.

Москва-2014

Оглавление

Введение......................................................................................................................5

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

1.1. Классификация функций обработки изображений и сигналов с точки

зрения параллельного исполнения.......................................................... 14

1.1.1. Точечные операции.......................................................................16

1.1.2. Локальные операции.....................................................................17

1.1.3. Глобальные операции....................................................................18

1.2. Выбор парадигмы программирования в зависимости от типа

параллельной вычислительной системы...............................................18

1.3. Обзор традиционных методов распараллеливания обработки изображений и сигналов............................................................................23

1.3.1. Использование библиотек работы с потоками...........................25

1.3.2. Коммуникационные средства.......................................................26

1.3.3. Параллельные конструкции высокоуровневых языков программирования..................................................................................27

1.3.4. Параллельные языки программирования....................................30

1.3.5. Распараллеливающие компиляторы............................................31

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

1.5. Выводы.........................................................................................................38

2. Разработка метода автоматизированного создания параллельного программного обеспечения для обработки изображений и сигналов..........40

2.1. Формализация нового метода разработки............................................40

2.2. Проектирование аппаратной и программной части целевой платформы....................................................................................................43

2.3. Разработка набора параллельных алгоритмических структур.........46

2.4. Разработка моделей предсказания производительности

параллельных программно-аппаратных платформ.............................51

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

2.4.2. Разработка аналитической модели исполнения параллельных алгоритмов для разных типов параллельных систем..........................54

2.4.3. Разработка имитационной модели исполнения параллельных алгоритмов для распределённых систем..............................................65

2.5. Разработка алгоритмов автоматизированного получения

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

2.6. Требования к системе планирования при обработке изображений и сигналов на параллельной архитектуре.................................................72

2.7. Выводы.........................................................................................................73

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

3.1. Реализация интерфейса системы, задание аппаратной и функциональной схемы.............................................................................75

3.2. Реализация подсистемы моделирования параллельной обработки данных на заданной аппаратной платформе........................................82

3.3. Реализация подсистемы автоматизированной генерации параллельного программного обеспечения..........................................86

3.4. Реализация подсистемы запуска обработки изображений и сигналов на многопроцессорной системе..............................................................90

3.5. Преимущества и ограничения разработанной проблемно-ориентированной среды визуального программирования.................92

3.6. Выводы.........................................................................................................95

4. Использование нового метода и разработанной системы для параллельной обработки изображений и сигналов.........................................97

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

на многоядерных процессорах.................................................................97

4.2. Распараллеливание функций библиотеки обработки изображений IPPLab MSCo...............................................................................................101

4.3. Использование нового метода для распараллеливания цифровых фильтров сигналов на кластерной системе для ЗАО "ACT".............108

4.4. Выводы.......................................................................................................124

Заключение.............................................................................................................126

Литература..............................................................................................................129

Приложения............................................................................................................139

Приложение 1. Акты о внедрении.................................................................139

Приложение 2. Графики зависимости ускорения от числа

вычислительных элементов для аналитической модели.................142

Приложение 3. Алгоритмы инкрементного распараллеливания при

генерации параллельного кода для набора ПАС................................146

Приложение 4. Грамматика ANTLR для разбора языка С++...................148

Приложение 5. Сгенерированный параллельный исходный код функции FFT................................................................................................................158

Введение

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

Цифровая обработка сигналов зародилась в 1950-х годах и к настоящему времени стала неотъемлемой частью жизни. Бурное развитие цифровых технологий привело к тому, что эти задачи являются крайне актуальными на сегодняшний день. Сюда относят развитие обработки данных на процессорных системах, обработку звука, решения в телекоммуникационной сфере, и даже методы шифрования. Изображения, по сути, являются сигналами со специфичными характеристиками. В этих областях большой набор задач требует решения в режиме реального времени, другие - обработки больших объёмов данных за короткий срок.

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

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

граммирование, наследуя все сложности последовательного, добавляет немало новых: организация параллельной структуры программы и обмена данными между параллельными процессами, синхронизация вычислений и доступа к ресурсам, сложности отладки параллельных программ [63]. Объектом исследования диссертационной работы является процесс распараллеливания обработки и анализа изображений и сигналов для различных типов многопроцессорных систем.

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

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

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

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

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

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

Таким образом, автоматизировать деятельность разработчика для многопроцессорных систем возможно за счёт использования высокоуровневых алгоритмических абстракций, таких как представление алгоритма в виде графа [68] или использование готовых параллельных блоков и типовых алгоритмических структур. Именно это направление (а также направление автоматизированного распараллеливания за счёт анализа исходных кодов) является на сегодняшний день одним из наиболее перспективных в сфере автоматизации программирования для параллельных архитектур.

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

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

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

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

Для достижения поставленной цели в ходе диссертационной работы были решены следующие задачи.

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

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

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

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

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

6. Сформулирован набор характеристик и разработаны аналитическа