Программные продукты и системы

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

Разработанная авторами методика [1] использует иной подход к созданию параллельного ПО. Разработчик параллельного программно-аппарат­ного комплекса уходит от наукоемкой разработки параллельного алгоритма, проблемы выбора метода распараллеливания, от написания параллельного исходного кода и сложной последующей отладки. Согласно данной методике разработка параллельного ПО включает следующие этапы.

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

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

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

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

5.     Автоматическая генерация параллельного кода функций.

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

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

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

Одним из преимуществ предложенной методики является возможность объединения всех этапов разработки в одной интегрированной програм- мной среде. В качестве такой системы была реализована среда визуального программирования, использующая набор заменяемых модулей. Разработка среды проводилась на языке C# с использованием библиотеки отображения WPF в MS Visual Studio. Основные модули системы и их взаимосвязь представлены на рисунке 1.

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

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

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

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

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

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

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

Аналитическое моделирование проводится по полученным авторами формулам коэффициента ускорения, эффективности и масштабируемости в соответствии со схемой аппаратной платформы и типом ПАС, выбранных для функций обработки изображений или сигналов [2]. Имитационное моделирование программно-аппаратного комплекса параллельной обработки реализовано в соответствии с разработанной моделью при помощи системы сетевого моделирования OMNET++ [3]. Модель планируемого программно-аппаратного комплекса формируется из набора моделей отдельных компонент. Компонентам аппаратной схемы сопоставляются разработанные модели соответ- ствующих устройств: вычислительного узла, концентратора, коммутатора, маршрутизатора, хранилища данных и сетевого соединения. Для имитации обработки и передачи данных в соответствии с выбранной алгоритмической структурой используются модели клиентского и серверного сетевого приложения. Модель, состоящая из компонент, сопоставленных аппаратной и функциональной схемам, генерируется автоматически. После генерации файлов среды OMNET++ запускается моделирование с получением статистических данных, в результате которого определяются следующие характеристики для оценки производительности программно-аппаратной связки: время параллельной обработки данных, использующееся для расчета коэффициентов ускорения и эффективности, и загрузка вычислительных узлов многопроцессорной системы.

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

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

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

После декомпозиции разработчик производит генерацию параллельного ПО, выполняющего обработку данных по заданной цепочке функций. Инкрементальное распараллеливание последовательного кода функций реализовано следующим образом: на первом шаге проводятся верификация модели, лексический и синтаксический анализ исходного кода при помощи нисходящего LL(k) анализатора ANTLR. Далее проблемно-ориенти­рованная среда визуального программирования генерирует код в соответствии с ПАС согласно следующим принципам:

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

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

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

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

Реализация подсистемы планирования выполнения цепочки операций на многопроцессорной системе

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

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

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

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

Реализованная среда визуального программирования позволила ускорить и повысить эффективность разработки параллельного ПО для обработки изображений и сигналов [4] в ряде крупных проектов. В проекте для Концерна «Системпром» представленная среда разработки использовалась при создании комплекса верификации изображений печатных плат на многоядерных процессорах. Узким местом верификации являлось большое время сравнения рентгенограмм с изображением закладочных устройств. Для проверки изображений был выбран метод SIFT, алгоритм компьютерного зрения, предназначенный для нахождения и описания локальных характеристик изображения. Поскольку основной этап метода можно проводить для его отдельных фрагментов, которые должны быть перекрывающимися на область, необходимую для нахождения дескрипторов, алгоритму SIFT была сопоставлена ПАС – локальный алгоритм.

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

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

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

Литература

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

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

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

4.     Gertsenberger K.V., Chepin E.V., Implementation parallel processing of digital signals on cluster system, Proc. Intern. Workshop on Computer Science and Inform. Technologies (CSIT'2007), Bashkortostan, 2007, Vol. 1, Ufa State Aviation Technic. Univ., 2007, pp. 152–155.

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

6.     Гладцын В.А., Яновский В.В. Средства моделирования вычислительных сетей. СПб: Изд-во СПбГЭТУ «ЛЭТИ», 2001. 128 с.

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

8.     Varga A., OMNeT++ Discrete Event Simulation System Version 4.0, User Manual, 2004, 342 p.

References

1.  Gertsenberger K.V., Chepin E.V.,  Trudy 53 nauch.  konf.MFTI «Sovremennye problemy fundamentalnykh i prikladnykh na-uk»  [Proc. 53 Sc. Conf. MFTY «Modern problems of fundamental and applied sciences»], Moscow, MFTI, 2010, Iss. XI, pp. 54–55.

2.  Gertsenberger K.V., Chepin E.V.,  The Business Informat-ics, 2011, no. 4, pp. 24–30.

3.  Gertsenberger K.V., Chepin E.V.,  Programmye produkty i sistemy [Software and Systems], 2012, no. 2, pp. 117–120.

4.  Gertsenberger K.V., Chepin E.V.,  Proc. of CSIT'2007, Bashkortostan, 2007, Vol. 1, Ufa State Aviation Technic. Univ.,
2007, pp. 152–155.

5.  Voevodin V.V., Voevodin Vl.V.,  Parallelnye vychisleniya (Parallel computing), St. Petersburg, BHV-Peterburg, 2002, 608 p.

6.  Gladtsyn V.A., Yanovsky V.V.,  Sredstva modelirovaniya vychislitelnykh setey  (Modeling aids of computing nets),  St. Peters-burg, SPbGETU «LETI», 2001, 128 p.

7.  Andrews G.R.,  Foundations of Multithreaded, Parallel, and Distributed Programming, Addison Wesley, 2000.

8.  Varga A.,  OMNeT++ Discrete Event Simulation System Version 4.0, User Manual, 2004, 342 p.