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

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

ЕРМАКОВ Александр Вадимович

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

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в технической отрасли)

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

Саратов 2011

2 3 ИЮН 2011

4851154

Работа выполнена в ГОУ ВПО «Саратовский государственный технический университет»

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

Долинина Ольга Николаевна

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

Большаков Александр Афанасьевич

- доктор физико-математических наук, доцент Шульга Татьяна Эриковна

Ведущая организация ФГОУ ВПО «Астраханский государственный

технический университет»

Защита состоится «5» июля 2011 г. в 14.00 часов на заседании диссертационного совета Д 212.242.04 при ГОУ ВПО «Саратовский государственный технический университет» по адресу: 410054, г. Саратов, ул. Политехническая, 77, Саратовский государственный технический университет, ауд.1/319

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

Отзыв на автореферат (в двух, экз.), заверенный печатью, просим выслать по адресу: 410054, г. Саратов, ул. Политехническая, 77, каф. ПИТ.

Автореферат разослан «3» июня 2011 года

Автореферат размещен на сайте СГТУ www.sstu.ru. «3» июня 2011 г.

Ученый секретарь диссертационного совета

В.В. Алешкин

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

Актуальность исследования. Для обработки видеоинформации с высоким качеством большие ее объемы создаются и хранятся в цифровой форме. Концепции цифрового представления видеоинформации разрабатываются экспертной группой по кинематографии (MPEG - Moving Picture Expert Group) и отражены в работах Джона Уоткинса, Сакаэ Окубы, Элойса Бока, Леонардо Чиэйрлогна и др. Обычно цифровая видеопоследовательность является набором межкадрово-и внутрикадрово-сжатых цифровых изображений. Такая форма представления позволяет решать широкий круг задач по обработке видеоинформации, имеющих различную природу и широкое научно-практическое применение. К ним относятся, например, анализ видеоизображений для поиска объектов, применение фильтрующих алгоритмов, совмещение видеоизображений с компьютерно-сгенерированными объектами.

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

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

Одним из актуальных направлений эффективного развития параллельных и распределенных вычислений для обработки видеоинформации является применение GRID-технологий, разрабатываемых такими зарубежными учеными как Ян Фостер, Карл Кассельман, Стив Тыоки, Райкумар Буйя и др. Среди отечественных организаций, занимающихся проблемами GRID-вычислений, следует выделить НИИЯФ МГУ, Институт Теоретической и Экспериментальной Физики, Институт физики высоких энергий, Институт математических проблем биологии РАН. Этот подход активно используется для решения задач с большими объемами вычислений, например, в ядерной физике. Его достоинством является возможность решения проблем, связанных с реализацией безопасной, надежной и эффективной обработки данных, использующей ресурсы не только доступные в локальной вычислительной сети, но и предоставляемые пользователями сети Интернет для совместных вычислений. Однако для задачи обработки видеоинформации с использованием GRID-вычислений также недостаточно развиты модели и методы, которые могут определить эффективность обработки видеоинформации.

Целью исследования является повышение эффективности обработки видеоинформации в вЯЮ-среде.

Задачами исследования являются: 1) обоснование вычислительной архитектуры, необходимой для осуществления распределенной обработки видеоинформации для больших вычислительных сетей; 2) разработка метода определения производительности вычислительных узлов СЯГО-среды; 3) создание математической модели для оценки времени обработки видеофайла с использованием СЯГО-вычислений; 4) разработка метода повышения эффективности обработки видеоинформации в вычислительных сетях; 5) создание программного комплекса практически реализующего предложенный метод; 6) определение эксплуатационных характеристик разработанного метода.

Методы исследования. В работе использованы методы обработки видеоинформации и распределения заданий в СИГО-среде, статистического анализа, имитационное моделирование, численные методы оптимизации.

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

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

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

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

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

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

1) Предложена математическая модель обработки видеоинформации в вЯЮ-среде, которая позволяет оценить время обработки видеоинформации для вЯГО-среды и задачи обработки с известными характеристиками.

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

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

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

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

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

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

3) Разработанная и внедренная система позволяет осуществлять кодирование и декодирование видеоотрезков в формате MPEG-2 и их обработку.

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

Реализация и внедрение результатов работы. Разработанные модели и методы реализованы в комплексе программ, внедренном в Саратовском государственном техническом университете в рамках проекта Hewlett Packard Adaptive-Enterprise Grid for University Teaching and Learning, а также на Нижневолжской студии кинохроники, что подтверждено соответствующими актами.

Апробация работы. Результаты работы докладывались на международных конференциях «Математические методы в технике и технологиях XXI» (Саратов, 2008), «Математические методы в технике и технологиях XXII» (Иваново,

2009) и «Математические методы в технике и технологиях XXIII» (Саратов,

2010); на Всероссийской конференции «Практические вопросы информационного обеспечения инновационной деятельности» (Саратов, 2008); на Всероссийской научно-практической конференции «Инновации и актуальные проблемы техники и технологий» (Саратов, 2009); на XVII Всероссийской научно-практической конференции «Телематика -2010» (Санкт-Петербург, 2010); на научных семинарах кафедры «Прикладные информационные технологии» Саратовского государственного технического университета в 2008 - 2011 годах. Работа получила поддержку программы «У.М.Н.И.К.-2011».

Публикации. Основные положения диссертации отражены в 10 публикациях, в т.ч. в 3 журналах, рекомендованных ВАК РФ. Без соавторов опубликовано 2 работы.

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

Структура и объем работы. Диссертационная работа изложена на 144 страницах и состоит из введения, трех глав, и заключения; список использованной литературы включает 104 наименования; диссертационная работа содержит 3 приложения, 28 таблиц;. 32 рисунка.

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

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

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

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

отрезок видеопоследовательности

кадр

8 пикселей

• Задачи любого объема, не гребобагелыыею времени обработки

■ Задачи с он-лайн обработкой и небольшим с&1>е|»ом аадач обработки

Программная обработка на ..: локальном

вычислительном ;

>

Обработка на специалязи-. роранных. аппаратных платах .

Спсгсиы-збра&лкп

• Задачи со средний объемом V

обрабатываемых данных,

требовательные ко времени обработки

Обработка на

основа параллельных .... вычислений в . сугаркомпьютерах

? ..'• •■■■у

\ . . .. ;,......; -

/ /

■ Задачи, тр«боват< времени обработки и сверхбольшими объемами исходныхданных

Рис. 1. Схема кодирования МРЕв-2 Рис. 2. Методы обработки видеоинформации

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

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

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

вЯГО-среда 5 образована множеством сайтов = у гДе

—сайты,/—число сайтов в СШБ-среде 51 Каждый сайт ^ явля-

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

Обработка видеофайла представляет собой совокупность распределенно выполняемых заданий (tasks) по обработке видеоинформации, объединенных в один план (job). Задание г, является неделимым блоком операций, выполняемых на одном вычислительном узле. План J — это множество заданий, которые должны быть выполнены для получения результата обработки: J = г2,...,г7).

Выполнение плана в GRID-среде означает, что любой сайт gj, при обработке плана J может использовать ресурсы любого gsK е S, к = 1 .

Таким образом, план отождествляет один видеофайл, а для формирования заданий выбран метод, в котором минимальной единицей обработки (одним заданием) является независимо сжатая группа изображений (GOP — Group of Pictures). Этот метод позволяет максимально по сравнению с остальными существующими методами, сократить объем передаваемых данных, увеличением вычислительной нагрузки на конечные узлы. Его использование обусловлено тем, что наиболее узким местом распределенной обработки видеофайлов является время передачи данных ввиду их большого объема.

Технологически базовым механизмом обработки является система OurGrid, функционирующая на базе Р2Р сетей. Для распределения заданий в GRID-среде выбран метод сходства памяти (Storage Affinity(SA)), который минимизирует объем передаваемых данных поиском таких блоков ранее переданных данных, которые совпадают с текущими. В том случае, если повторно используемые данные отсутствуют, применяется метод WQR (Working Query Replication), который распределяет данные между всеми узлами, отслеживая ошибки в обработке данных и исключая из списка доступных узлы, регулярно отказывающие в обработке.

В диссертации приведено описание GRID-системы и разработана модель задачи обработки видеоинформации в ней. В общем виде время обработки видеоинформации tj представляется

{/ Твыч +Ттр, (1)

где Тшч ,Тпер - время обработки и передачи данных всего плана соответственно.

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

GP) = Г;/Г„,„,„для 7=1.....GN, (2)

где tj - время, затраченное на обработку тестового задания j-м узлом; GN- число доступных вычислительных узлов.

Значение GPj характеризует количество заданий, выполненных j-м узлом за время, равное времени показанным тестовым узлом, и используется как базовая

характеристика. Она позволяет определять скорость работы узлов относительно друг друга. Также для любого узла может быть получено время обработки им задания относительно другого узла, для которого оно известно: 1] = * СР1 / С/> , где ^ и GPj, ¿,и - время обработки узлом тестового задания и его производительность; время обработки искомым 1-м узлом тестового задания и его производительность соответственно.

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

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

ъ о)

1=1 М

где №гр- число групп узлов; А^ - количество узлов в /-й группе.

Для вновь добавленных в систему внешних узлов, первое обработанное задание присылается из расчета ОР = 1 и становится тестовым. В дальнейшем производительность определяется исходя из полученного значения времени работы тестового узла.

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

Т =77У *СР */ +ГЛГ*г (4)

выч. п тест '¡пест. 1 'т •

где СРтсст- производительность тестового узла локального вычислительного сайта; ?„,,,„„. - время обработки одного задания тестовым узлом; ТИ- число заданий в плане; Гдо. - время задержки при обработке на вычислительном узле; Т1ЧП - число задач, выполняемых группой узлов с производительностью СРШд , которое вычисляется как

" / +1

Г^У„ - 77У / ^ С.У, * "'""'0бр' """""''• 7 (5)

^} обр. ^\ пер.

где N - число групп узлов; - число узлов в ;-й группе; Ьгестобр- время обработки одного задания тестовым узлом, а Ц обр- время обработки /-м узлом; ^тестпер - время передачи одного задания тестовым узлом, а Ц „ер- время передачи 1-м узлом. При этом:

1ШС„,„р = /V *GNШ +ТАГ * (,„. (6); (7)

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

Время передачи данных вычисляется согласно выражению

Т„ер=2*М*СМ/и+Т^(3„+1ав, (8)

где 1сдвига - время сдвига окончания обработки, определяемое числом задержек.

Таким образом, время обработки видеоинформации в СГ£Ш-среде описывается математической моделью:

2* 1У*С,Ы

ь =ТК *С/?ест%т„+77УЧ1,+/ ^ ип+т+и +и (9)

Полученная модель включает две управляемые переменные, первой из них является ТЫ - число заданий в плане. Каждое задание может содержать один или более независимо сжатых изображений (СОР). Таким образом, один видеофайл может быть разбит на различное число заданий. Поэтому план содержит Л( кадров с общим объемом данных .IV. Задания представляют собой отрезок ТК кадров, содержащих ТУ объем данных. При этом результат ТК / К - целое число, где К - количество кадров в одном вОР. Отсюда

ТК=Ж!ТИ; ТУ = ЗУПЫ. (10); (11)

Таким образом, ТЫ определяется как

77У = ЛС/ЫК*К, (12)

где А'К - число вОР в одном задании.

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

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

Учитывая описанные выше особенности, разработан метод повышения эффективности обработки видеоинформации, который основывается на том, что существует число заданий в плане, которое минимизирует время, затрачиваемое на передачу данных, на основе уменьшения числа задержек при получении максимальной загрузки вычислительных узлов. Таким образом, идея метода заключается в поиске минимального значения I], причем глобальный минимум определяется на основе априорных знаний о его нахождении, а локальный минимум определяется методом покоординатного градиентного спуска с дроблением шага. Рассмотрим предлагаемый метод в виде пошаговой процедуры: Шаг 1. Принимаем размер одного задания равным одному вОР и получаем ТМ. Принимаем число групп узлов равным единице с производительностью тестового узла. Принимаем О//равным числу узлов, имеющихся в системе. Шаг 2, Определяем методом градиентного спуска число С/У, для которого среднее значение 1'(ОМ) следующих за ним п точек не менее/(СЫ). Шаг 3. Заменяем найденное значение числа узлов на те узлы, которые доступны в вычислительной среде, в порядке снижения их производительности.

Шаг 4. Определяем методом градиентного спуска минимальное f(GN) для существующих узлов.

Шаг 5. Определяем методом градиентного спуска минимальное f(TN), при этом основным условием является существование числа X, для которого результат операции TN -JK1NK*X является целым числом. Таким образом, X- это число GOP в одном задании плана.

Шаг 6. В случае, если удалось улучшить значение/(GN.TN), возвращаемся к шагу 4, иначе принимаем, что достигнуто минимальное значение.

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

f,GNt<GN. (13)

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

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

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

Эксперименты проведены с испрльзованием разработанного программного комплекса, основанного на системе OurGrid. Он состоит из трех частей: MyGrid, Peer и Gum - служб, управляющих заданиями, ресурсами и запуском заданий на вычислительных узлах, соответственно.

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

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

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

Представленный программный комплекс использован для проверки адекватности предложенной в работе математической модели оценки времени обработки видеофайлов, а также повышения ее эффективности при использовании созданного метода. Его разработка осуществлена с использованием платформы программирования JAVA Standart Edition 6, которая позволяет использовать

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

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

Проведем эксперимент по выявлению зависимости времени обработки видеофайла от производительности вычислительных узлов в составе GRID-среды. Для этого сформирована вычислительная среда из трех подсетей, содержащих компьютеры одной группы производительности, число заданий в плане TN=10.....180; объем данных TV=1500 КБ; число узлов GN=12; производительность GP,=2.54; GP2= 1.64; GP3= 1.27; GP4= 1.

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

Результаты эксперимента проиллюстрированы на рис. 3, который демонстрирует снижающийся тренд, причем число узлов записывается как G1/G2/G3/G4, где Gj - число узлов i-й группы, причем их производительности P(G,) соотносятся как P(Gi)> P(G2)> P(G3)> P(G4). Это означает постепенное сокращение времени обработки видеоинформации при увеличении общей производительности вычислительных узлов.

Число узлов

—■—данные, полученные с использованием GRID-среды

—|—данные, полученные в результате математического моделирования

Рис. 3. Сравнительный график изменения и оценки времени обработки плана при варьировании состава сайта

В рамках общего тренда можно выделить несколько участков графика, начало которых отмечено резким увеличением времени обработки с последующим постепенным возвращением к общему тренду. Анализ результатов эксперимента показывает, что постепенное изменение состава сайта с { С|=1; С2=1; Оз=1; й4= 9} до { С|=1; й2 = 9; С3= 1; С4= 1} проходит без резких скачков, однако дальнейшее его изменение на { 01=2; С2 = 1; Сз= 1; й4= 9} демонстрирует первый подъем. Остальные скачки также соответствуют подобным изменениям. Это позволяет сде-

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

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

Выбор критерия оценки адекватности основывается на типе распределения данных. Введем гипотезу Н0 о том, что данные, соответствующие выражению (15), распределены нормально. Разработанная модель содержит четыре величины ((тест., 11а, ^п., 1СДВ )г имеющие случайный характер, поэтому необходимо оценить их влияние на распределение. По эмпирическим выборкам значений случайных величин, полученным в ходе экспериментов, получим оценки их средних значений и оценки их дисперсий. Эти значения являются исходными данными для генерации независимых случайных равномерно распределенных чисел, выбранных из квазислучайной последовательности. Полученные значения позволяют рассчитать среднеквадратичное отклонение для каждой из величин и рассчитать среднеквадратичное отклонение для Воспользуемся методом переноса ошибок, согласно которому для малых дисперсий возможно разложение в ряд Тейлора с удержанием первых членов разложения, позволяющих оценить дисперсию. Если представить формулу (9) как

г, =щ +а2 *х2 + а3 *х3 +а, * хА ; (14)

2* ./V

где а, = ТЫ*ОР„„ш, а2=ТЫ, я2=д3, а4=1, Ь =---=',„«„,, хг=1„,

ХЪ = 'м « ХЬ~ Кдв.'<

тогда

4=и- - (£)' • < + (£)' • * ♦ (£)' • <♦•

< ~ о-Х * < + «1 * °1г + * < + +«4 * = а\ * агн + а\ * + аД) +

< О5)

Проведенное компьютерное моделирование позволило построить гистограмму, форма которой соответствует нормальному распределению, со значением эксцесса, равным 0.04; и значением асимметрии, равным -0.005. Таким образом, нет оснований отклонить нулевую гипотезу.

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

построение доверительных интервалов и оценке накрытия ими проверяемых значений. Введем гипотезу Но о нормальном распределении экспериментальных данных. Для этого выделим экспоненциальное среднее и вычислим абсолютную разницу между средней и всеми значениями эксперимента. Проверка полученных значений показывает, что остатки являются белым шумом, таким образом, нет оснований отклонить нулевую гипотезу. Для оценки адекватности используем критерий Стьюдента. Введем гипотезу Н0 :сг, где ¡=1,2 при альтернативной гипотез'е Н, : о"/ Ф а, где ¡=1,2, где а1 - оценка математического ожидания экспериментальных данных и данных математического моделирования. Полученные на основе дисперсии значения с уровнем значимости а = 0.05 удовлетворяют нулевой гипотезе. Таким образом, построенные доверительные интервалы для среднего накрывают ненаблюдаемую истину с вероятностью 95% (рис. 4), что позволяет судить об адекватности модели.

1550 ---:------------

Число узлов

■—а.— модель нижний доверительный интервал ■■ 1 верхний доверительный интервал

Рис. 4. Взаиморасположение доверительных интервалов и данных модели

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

Для оценки степени повышения эффективности обработки видеоинформации при применении разработанного метода сравнивается время, полученное при его использовании с полученным при использовании традиционно применяющегося метода Storage Affinity (SA).

Проведем эксперимент, где входными данными являются: JK =30,...,3600 секунд; NK = 10 кадров; время обработки одного NK, NKK = 30 мс*10"2' объем данных одного NK, NKV = 0.5 МБ; N = 1; GN = 9; GPj = 1; GF = 0. На рис.5 показаны зависимости времени обработки видеоотрезка от его длины, полученные с помощью метода SA (линия «1 GOP») и разработанного метода (линия «X GOP»).

Анализ этих зависимостей позволяет сделать вывод о том, что их характер остается линейным, однако соотношение времени обработки видеофайла методом SA ко времени обработки разработанным методом увеличивается с увеличением длины видеоотрезка. Так, для рассмотренного случая максимальное сокращение времени обработки составило 25%. Проведенная серия экспериментов

показала, что сокращение времени обработки зависит от соотношения времени передачи видеоотрезка ко времени его обработки. Максимально полученное сокращение времени обработки составило 50%.

длина видеоотрезка (сек)

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

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

ЗАКЛЮЧЕНИЕ

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

1. Разработана математическая модель оценки времени обработки видеоинформации с использованием вЯГО-вычислений, которая позволяет моделировать обработку заданий, относящихся к классу задач с большим объемом обрабатываемой информации, где объем передаваемых и получаемых с вычислительного узла данных совпадает. Впервые проведен анализ влияния значений случайных величин на процесс обработки плана в вЯЮ-среде. Для рассматриваемой модели доказана ее адекватность экспериментальным данным.

2. Предложен метод оценки производительности вычислительных узлов в СИЮ-среде. Его использование позволяет получить независимую оценку времени обработки одинаковых заданий разными узлами. Принцип объединения узлов в группы в зависимости от получаемого значения относительной производительности позволяет снизить влияние случайных колебаний на оценку производительности вычислительных узлов.

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

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

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

5. Получены экспериментальные зависимости времени обработки видеофайлов от различных значений параметров GRID-среды и плана обработки.

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

Основные результаты диссертации опубликованы в работах:

Публикации в изданиях, рекомендованных ВАК РФ

1. Оуграбко А.В (Ермаков A.B.). Повышение эффективности обработки видеоинформации с использованием GRID-вычислений [Текст] / О.Н. Долинина, A.B. Оуграбко // Вестник Саратовского государственного технического университета.

2009. №1 (42). С. 101-106.

2. Ермаков A.B. Метод повышения эффективности обработки видеоинформации с использованием GRID -ресурсов [Текст] / О.Н. Долинина, A.B. Ермаков II Вестник Саратовского государственного технического университета. 2010. №4 (50). Вып. 2. С. 131-133.

3. Ермаков A.B. Разработка и анализ метода повышения эффективности обработки видеоинформации с использованием GRID-вычислений [Текст] / A.B. Ермаков // Вестник Саратовского государственного технического университета.

2010. №4 (51). Вып. 3. С. 184-188.

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

4. Оуграбко А.В (Ермаков A.B.). Обработка видеоинформации при помощи грид-вычислений. [Текст] / О.Н. Долинина, A.B. Оуграбко II Математические методы в технике и технологиях-21. сб. статей по материалам конференции: Саратов: СГТУ, 2008. С. 136-138.

5. Оуграбко А.В (Ермаков A.B.). Маркированные потоковые графы как метод обеспечения грид-вычислений [Текст] / A.B. Оуграбко // Практические вопросы информационного обеспечения инновационной деятельности: сб. статей по материалам конференции. Саратов: СГТУ, 2008. С. 371-374.

6. Оуграбко А.В (Ермаков A.B.). Повышение эффективности обработки видеоинформации при помощи грид-вычислений [Текст] / A.B. Оуграбко // Технологии интернет - на службу обществу: актуальные проблемы использования ин-тернет/интранет технологий: сб. статей по материалам конференции. Саратов: СГТУ: 2008. С. 33-35.

7. Оуграбко А.В (Ермаков A.B.). Построение масштабируемых расписаний для обработки видеоинформации в GRID-среде [Текст] / О.Н. Долинина, A.B. Оуграбко // Математические методы в технике и технологиях-22: сб. статей по материалам конференции. Псков, 2009. С. 87-92.

8. Оуграбко А.В (Ермаков A.B.). Использование GRID-технологий для обработки видеоинформации [Текст] / О.Н. Долинина, A.B. Оуграбко // Инновации и актуальные проблемы техники и технологий: сб. статей по материалам всероссийской научно-практической конференции. Саратов: СГТУ, 2009. С. 72-75.

9. Ермаков A.B. Метод обработки видеоинформации с использованием GRID-ресурсов [Текст] / О.Н. Долинина, A.B. Ермаков, Д.М Верескун // Математические методы в технике и технологиях-23: сб. статей по материалам конференции. Саратов: СГТУ, 2010. С. 178 - 181.

10. Ермаков A.B. Обработка видеоинформации с использованием GRID-вычислений [Текст] / О.Н. Долинина, A.B. Ермаков // Телематика'2010: телекоммуникации, веб-технологии, суперкомпьютинг: сб. статей участников Всероссийского конкурса научных работ студентов и аспирантов. СПб: СПбГУ ИТМО, 2010. С. 197-203.

ЕРМАКОВ Александр Вадимович

МЕТОД ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ОБРАБОТКИ ВИДЕОИНФОРМАЦИИ С ИСПОЛЬЗОВАНИЕМ РАСПРЕДЕЛЕННЫХ

ВЫЧИСЛЕНИЙ

Автореферат

Ответственный за выпуск A.B. Бровко Корректор Л.А. Скворцова

Подписано в печать 31.05.11 Формат 60x84 1/16

Бум. тип Усл.-печ.л. 1,0 Уч.-изд. л. 1,0

Тираж 100 экз. Заказ 107 Бесплатно Саратовский государственный технический университет 410054, г. Саратов, ул. Политехническая, 77

Отпечатано в Издательстве СГТУ, 410054, г. Саратов, ул. Политехническая, 77 Тел.: 24-95-70; 99-87-39, e-mail: izdat@sstu.ru

Введение.

1. Обзор методов обработки видеоинформации.

1.1 Методы представления видеоинформации.

1.2 Методы обработки видеоинформации.

1.2.1 Локальная обработка видеоинформации.

1.2.2 Распределенная обработка видеоинформации.

1.3 Основные'понятия GRID-вычислений.

1.4 Методы обработки данных с использованием GRID-вычислений.

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

1.4.2 Планирование вычислений на основании прогноза времени обработки.

1.4.3 Планирование вычислений на основании вероятности завершения обработки в расчетный отрезок времени.

1.5 Постановка задачи диссертационного исследования.

1.6 Выводы по главе 1.

2.Метод обработки видеоинформации с использованием GRID-вычислений.

2.1. Выбор метода распределения заданий в GRID-среде.

2.2. Постановка задачи обработки видеоинформации.

2.3.Параметрическая модель обработки видеоинформации в GRID-среде.

2.4. Метод обработки видеоинформации с использованием GRID-вычислений.

2.5.Реализация метода обработки видеоинформации в GRID-среде.

2.6. Выводы по главе 2.

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

3.1 Описание программно-аппаратного комплекса.

3.2 Постановка эксперимента.

3.3 Анализ результатов обработки видеоинформации с использованием

GRID вычислений.

3.4 Оценка непротиворечивости модели.

3.5 Статистическое исследование разработанной модели.

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

3.7 Выводы по главе 3.

Обработка видеоинформации в настоящее; время- имеет широкое распространение в различных областях человеческой деятельности. Мировой: рынок, аппаратногпрограммногообеспе'гения'дляразличныхзадачповидеообработке в!2009угоду оценивалсяш; 10-1?5 млрд:.долларов; [ЭД Видеообработкашожет быть применена для- получения! новых видеоданных на основе имеющихся« или для проведения; их анализа [2]. Видеообработку используют для решения различных задач, например, сбора статистики событий на базе архивного видеоматериала^ совмещения; нескольких видеопоотоков для анализа характеристик трехмерных объектов, восстановления видеоизображения по известной его части, выделениягобъектов и их;повёденйя;из видеопоследовательности:(таК'называемое матирование), создания; кинофильмов и многих других задач: Подавляющая часть мировой кинопродукции проходит этан цифровой видеообработки, а многие страны; например США, полностью переходят нащифровое; телевещание. Общий доход от обработанных цифровым образом -кинофильмов за ; 2009 год составил 29;9 млрд. долларов [3];

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

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

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

Создание цифровых видеоотрезков, которые демонстрируются конечному пользователю, требует прохождения последовательности операций, включая следующие этапы: 1) съемка видеоизображения; 2) запись в хранилище данных; 3) монтаж видеоотрезков; 4) обработка видеоинформации; 5) кодирование видеоинформации.

На этапе съемки видеоизображения происходит формирование исходной видеопоследовательности. Для выполнения этой функции используются^ различные цифровые видеокамеры [6]. Съемка видеопоследовательности, пригодной для дальнейшей обработки, происходит в одном из форматов, которые сохраняют данные без потери информации, например, DV [7].

На этапе записи исходного видеоматериала в хранилище данных производится передача данных с устройства записи на устройство, с которого будет производиться обработка. Для этого используют различные аппаратные средства, например, такие как fireware [8]. При этом формируется окончательная форма видеопоследовательности.

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

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

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

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

Создание видеопоследовательностей до сих пор является весьма длительным, трудоемким и дорогостоящим процессом. Для* создания видеопоследовательности крупной кинокартины, может потребоваться от одного года до четырех лет, а стоимость может составить до 300 млн. долларов [10].

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

Для ускорения процесса обработки используют параллельные или распределенные алгоритмы обработки видеоотрезков [11,12]. Так, использование распределенных вычислений для обработки видеоинформации в фильме "Avatar" (2009 г.) потребовало круглосуточного использования вычислительного центра Weta digital, состоящего из 100 кластерных узлов по 40000 процессорных ядер каждый и имеющего 104 ТБ оперативной памяти [13]. В работе [14] отмечено, что до создания этого вычислительного центра, осуществившего обработку видеоинформации, съемка такого фильма была невозможна.

Таким образом; время, затрачиваемое на обработку видеоинформации, зависит от следующих факторов:

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

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

• качества каналов связи и степени развития методов управления данными.

Важность рассмотренных факторов подтверждается производителями программного обеспечения, реализующими эти функции в»своих продуктах, таких как Adobe Premier[15] и Virtual Dub [16]. Дальнейшие разработки в этой области призваны повысить эффективность обработки путем использования новых подходов в организации вычислительных архитектур. Разработанное компанией NetApps [17] программное обеспечение для управления планами обработки в высокопроизводительных кластерах позволило компании WetaDigital на 95 % сократить расходы на управление данными и на 40 % повысить соотношение между производительностью и затратами. Полученные результаты достигнуты- использованием специфики кластерных архитектур при формировании последовательности исполнения большого числа различных обработок [18]. Однако использование такой системы ограничено кластерной архитектурой, и для вычислительных сетей необходима разработка других методов повышения эффективности.

Для видеофайлов небольшого объема возможна обработка на локальном вычислительном узле. Некоторые наиболее общие функции могут быть реализованы на аппаратном уровне [19]. Однако для файлов большого размера или файлов со сложными алгоритмами обработки такие решения не позволяют добиться существенного сокращения времени обработки. Установлено, что основным показателем для обработки является соотношение между временем передачи видеофайла между вычислительными узлами и временем обработки на локальном узле. Причем время обработки должно быть не менее чем вдвое больше времени передачи этого видеофайла [20].

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

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

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

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

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

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

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

Целью исследования является повышение эффективности обработки видеоинформации при помощи вЯГО-вычислений.

Задачами исследования; являются: 1) определение вычислительной архитектуры, необходимой' для осуществления! распределенной обработки, для- больших вычислительных сетей; 2) разработка метода определения-производительности вычислительных узлов ОЯГО-среды; 3) создание модели для оценки времени обработки видеофайла с использованием. ОШБ-вычислений;.4) разработка метода повышения эффективности обработки; видеоинформации в вычислительных сетях; 5)практическая(программная);реализация'предложенного метода; 6) определение эксплуатационных характеристик разработанного метода:

Методы исследования. В работе использованы-методы, обработки; видеоинформации и распределения ч заданий в СШБ-среде, статистического анализа, имитационное моделирование, численные методы оптимизации;

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

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

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

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

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

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

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

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

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

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

6. Построен модифицированный метод обработки видеоинформации, отличающийся использованием ОЯТО-вычислений и сочетанием методов обработки информации в вИГО-среде с разработанным методом, повышающим эффективность обработки видеоинформации.

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

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

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

3. Разработанный и внедренный программный продукт, основанный на предложенных моделях и методах, позволяет осуществлять кодирование и декодирование видеоотрезков в формате МРЕО-2 и их обработку различными алгоритмами.

Реализация и внедрение результатов работы. Разработанные модели и методы реализованы в комплексе программ, внедренном на Нижневолжской студии кинохроники и в Саратовском Государственном Техническом Университете.

Апробация работы. Результаты работы докладывались на Международных конференциях «Математические методы в технике и технологиях XXI» (Саратов, 2008), «Математические методы в технике и технологиях XXII» (Иваново, 2009) и «Математические методы в технике и технологиях XXIII» (Саратов, 2010); на Всероссийской конференции «Практические вопросы информационного обеспечения инновационной деятельности» (Саратов, 2008); на Всероссийской научно-практической конференции «Инновации и актуальные проблемы техники и технологий» (Саратов, 2009); на XVII Всероссийской научно-практической конференции «Телематика -2010» (Санкт-Петербург, 2010); на научных семинарах кафедры «Прикладные информационные технологии» Саратовского государственного технического университета в 2008 - 2011 годах.

Публикации. Основные положения диссертации отражены в 10 публикациях, в т.ч. в 3 журналах, рекомендованных ВАК. Без соавторов опубликовано 2 работы.

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

Структура и объем работы. Диссертационная работа изложена на 144 страницах и состоит из введения, трех глав, и заключения; список использованной литературы включает 104 наименования; диссертационная работа содержит 3 приложения, 28 таблиц, 32 рисунка.

3.7 Выводы по главе 3

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

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

Во-вторых, предложенный в работе метод, основанный на модели (55), позволяет повысить эффективность обработки видеоинформации с использованием ОЯГО-вычислений. Использование этого метода в проведенных экспериментах позволило получить максимальное снижение времени обработки до 50 %. При этом, исследования показали, что для данного метода существуют границы эффективности, определяемые конкретным соотношением значений параметров вычислительного объема задачи к объему передачи данных.

Заключение

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

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

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

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

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

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

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

1. Бурсак, А. Пионер модернизации Электронный ресурс. / А. Бурсак, А.

2. Дементьев, В. Петлевой. Режим доступа:http://www.rbcdaily.ru/2010/02/25/media/460754

3. Burger, Wilhelm. Digital Image Processing: An Algorithmic Approach Using Java* Текст. / Wilhelm Burger, Mark J. Burge. Springer, 2007. - ISBN 1846283795.

4. Бондаренко, Д. Кинематограф не заметил кризиса Электронный ресурс. / Д. Бондаренко Режим доступа: http://eizvestia.com/world/full/4193269

5. Коупланд, Ли. Цифровое видео Электронный ресурс. / Ли Коупланд. -Режим доступа: http://www.osp.ru/cw/2000/21/5194/

6. Fisher, R. Dictionary of Computer Vision and Image Processing Текст. / R. Fisher, К Dawson-Howe, A. Fitzgibbon, C. Robertson, E. Trucco. John Wiley, 2005. ISBN 0-470-01526-8.

7. Zettl, H. Television Production Handbook Текст./ H. Zettl. Thomson Wadsworth, 2006. - ISBN 0-534-64727-8

8. ISO/IEC 61834. Стандарт DV Текст. — Сентябрь 1999.

9. Anderson, Don. FireWire System Architecture Текст. / Don. Anderson. -MindShare, Inc. 1999. - ISBN 0-201-48535-4.

10. Watkinson, John. The MPEG Handbook Текст./ John. Watkinson. 2-е изд., перераб. и доп. - Focal Press, 2004. - 470 е.- ISBN-10: 024080578X - ISBN-13: 978-0240805788

11. Epstein, Edward Jay. The Hollywood Economist: The Hidden Financial Reality Behind the Movies Текст./ Edward Jay Epstein. Melville House - 2010. - 240 c. - ISBN-10: 1933633840 - ISBN-13: 978-1933633848

12. Shahriar, M. A Data-Parallel Approach for Real-time MPEG-2 Video Encoding Текст./ M. Shahriar, Akramullah, Ahmad Ishfaq, L. Liou Ming. Springer

13. Yung, H. C. Spatial and Temporal Data Parallelization of the H.261 Video Coding Algorithm Текст. / H. C. Yung // IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY. 2001- том 11. - № 1.

14. Блог компании HP. Немного о том, как создавался «Аватар» Электронный ресурс. / Блог компании HP Режим доступа: http ://habrahabr.ru/company/hp/b log/805 81 /#habracut

15. Hoffman; J. Cameron's Twenty-Year Journey to Pandora Электронный ресурс.'/ ] J.* Hoffman. Режим доступа: http://www.ugo.com/movies/camerons-twenty-year-journey-to-pandora

16. Rosenberg, Jacob. Adobe Premiere Pro 2.0 Studio Techniques Текст./ Jacob Rosenberg. Adobe Press. - 2006. - 624 c.- ISBN-10: 0-321-38547-0

17. Beuchler, John. Learning VirtualDub: The complete guide to capturing, processing and encoding digital video/ Текст. / John Beuchler. Packt Publishing - 2005. - 212 c. - ISBN-10: 1904811353 - ISBN-13: 978-1904811350

18. News@NetApp. NetApp Announces Results for Fourth Quarter and Fiscal Year 2010 Электронный ресурс. / News@NetApp. Режим доступа: http://www.netapp.com/us/company/news/news-rel-20100526-results.html

19. Woods, John W Multidimensional Signal, Image, and Video Processing and Coding Текст./ John W. Woods. Academic Press, 2006. - 512 c. -ISBN-10: 0120885166 - ISBN-13: 978-0120885169

20. O.H. Долинина, A.B. Оуграбко. Использование GRID-технологий для обработки видеоинформации \\ Сб.статей по материалам всероссийской научно-практической конференции "Инновации и актуальные проблемы техники и технологий" , Саратов, СГТУ, 2009.

21. Гуле, А. Оцифровываем видео при помощи ТВ-тюнера Электронный ресурс. / А. Гуле. Режим доступа: http://ixbt.com/divideo/capture-with-tv-tuner.shtml#VDubAdvancedCluster.

22. Список серверных решений компании HP Электронный ресурс. / Режимдоступа: http://welcome.hp.com/country/ru/ru/smb/servers.html136

23. ISO/IEC 11172. MPEG-1: Coding of moving pictures and associated audio for digital storage media at up to about 1.5 Mbit/s. Текст. —93.

24. ITU-T Recommendation H.261. Video Codec for Audiovisual Services at px64 kbit/s. Текст. —, Версия 1: Ноябрь 1990; Версия 2: Март 1993

25. IS0/IEC 13818-2. Generic coding of moving pictures and associated audio information Part 2: Video. Текст. — ITU-T Recommendation H.262- Ноябрь 1994.

26. ITUT Recommendation H.263. Video coding for low bit rate communication Текст. —; версия 1, Ноябрь1995; версия 2, Январь 1998; версия 3, Ноябрь 2000.

27. JTC1/SC29/WG11 N3908. Coding of Moving Pictures and? Audio: MPEG-4 Video Verification Model version 18.0 Текст. — ISO/IEC ITC1/SC29/WG11-Январь 2001.

28. ITU-T Rec. H.264 ; ISO/IEC 14496-10 AVC. Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification Текст. — Joint Video Team (JVT) of ISO/IEC MPEG и ITU-T VCEG, JVT-G050 Март 2003.

29. Sony. DVCAM format overview Текст. — Sony Corporation, Japan 2000

30. SMPTE 314M. Data Structure for DV-Based Audio, Data and Compressed Video — 25 and 50 Mb/s Текст. —1999

31. SMPTE 316M. Television Digital Recording — 12.65-mm Type D-9 Component Format — Video Compression — 525/60 and 625/50 Текст. —1999

32. ISO/IEC 14 496-2. Coding of Moving Pictures and Associated Audio Текст. — MPEG-4 FDIS ISO/IEC JTC1/SC29/WG11- Март 1999

33. ATSC спецификация. ATSC Digital Television Standard. Advanced Television Standard Committee - 1995.

34. Torres, L. Video Coding: The Second Generation Approach Текст. / M. L. Torres, M. Kunt. Norwell, MA: Kluwer, 1996.

35. RECOMMENDATION ITU-R ВТ.709-5. Текст. -1990-2002

36. ISO/IEC International Standard 13 818-2. Information Technology—Generic Coding of Moving Pictures and Associated Audio Information—Part 2: Video Текст. —1994.

37. Cho, N. I. Fast Algorithm and Implementation of 2-D Discrete Cosine Transform Текст. / N. I. Cho, S. U. Lee. // IEEE Transactions on Circuits and Systems. 1991. -том 38- № 3. - C. 297-305.

38. Bovik, Alan С. The Essential Guide to Video Processing Текст. / Alan C. Bovik. -Academic Press, 2009. 778 c. - ISBN-10:0123744563 - ISBN-13:978-0123744562

39. Bryant, Steve. Basic Camcorder Guide Текст./ Steve Bryant. Amherst Media,U.S., 1991. - 96 c.- ISBN-10: 0936262125 - ISBN-13: 978-0936262123

40. Browne, Steven E. High Definition'Postproduction: Editing and Delivering HD Video Текст./ Steven E. Browne. Focal Press, 2006. - 248 c. - ISBN-10: 0240808398 -ISBN-13: 978-0240808390

41. All-in one editorial finishing Электронный ресурс. / Autodesk Режим доступа: http://images.autodesk.com/adsk/files/smoke2011brochureus.pdf

42. Francis, Т. Mission: An integrated Asset Managementsolution for Quantel sQ servers Электронный ресурс. / Т. Francis. Режим доступа: http://www.quantel.com/repository/files/whitepapersmissionapril2010.pdf

43. Work Faster the Way You Want, with What You Want Электронный ресурс. / AVID Режим доступа: http://www.avid.com/us/pressroom/ACE-honors-Media-Composer-as-preferred-choice-for-editors.aspx

44. An Overview of Parallel Processing Approaches to Image and Video Compression Текст.: Technical report Ke Shen, Cook Gregory W., Jamieson Leah H., Delp Edward J.— Purdue University West Lafayette, Indiana 47907-1285, 1994

45. Apple Qmaster Help Электронный ресурс. / Apple Режим доступа: http://documentation.apple.com/en/appleqmaster/

46. Сайт CineSoft. What is Duma ? Электронный ресурс. / Сайт CineSoft. -Режим доступа: http://www.cinesoft.ru/duma

47. Foster, I. The Grid: Blueprint for a Future Computing Infrastructure. Текст. / I. Foster, C. Kesselman. Morgan Kaufmann: San Francisco, CA, 1998.

48. Foster, I. Enterprise Distributed Computing Текст. / I. Foster, S. Tuecke // ACM Queue. 2005. -том 3 - № 6.

49. What Is the GRID? A Three Point Checklist Текст.: Techical notes : I. Foster — National Laboratory and University of Chicago, 2002, Argonne National Laboratory.

50. Rittinghouse, John. Cloud Computing: Implementation, Management, and Security Текст./ John Rittinghouse, James Ransome. Springer-2009.

51. O.H. Долинина, A.B. Оуграбко. Построение масштабируемых расписаний для обработки видеоинформации в ОЫГО-среде.\\Сб.статей по материалам конференции "Математические методы в технике и технологиях-22", Иваново, 2009.

52. Cirne, W. Running Bag-of-Tasks Applications on Computational Grids: The MyGrid Approach Текст. / W. Cirne и др // ICCP'2003, 2003.

53. Xgrid and Cross Platform Grid Computing Текст. : Project Report: Bowness

54. Stuart. —University College of the Fraser Valley, Апрель, 2005139

55. Litzkow, M. Condor—a hunter of idle workstations Текст. / M. Litzkow, M. Livny, M.Mutka // In: Proceedings of the 8th international conference of distributed computing systems, 1998.

56. Zhou, S. Utopia: a load sharing facility for large, heterogeneous distributed1 computer systems Текст. /S. Zhou, X. Zheng, J. Wang, P. Delisle // Softweare1 Practice Expirience. 1993'. - № 23:1305-1336

57. Henderson, R.L. Job scheduling under the portable batch system Текст. / R.L. Henderson // In: IPPS '95: proceedings of the workshop on job scheduling strategies for parallel processing. Springer, London, 1995- pp 279-294

58. Abramson, D. A computational economy for grid computing and its implementationin the nimrod-g resource broker Текст. / D. Abramson, R. Buyya, J. Giddy // Future Generation Computer Systems. 2002. -№ 18:1061-1074

59. Mateescu, G. Quality of service on the grid via metascheduling with resource co-scheduling and co-reservation Текст. / G. Mateescu //Int Journal of High Performance Computer Applications. 2003. - №17:209-218

60. Using performance prediction to allocate grid resources Текст. : Technical report : Jang S.H., Wu X., Taylor V. —2004, GriPhyN

61. Elizeu, S. N. Exploiting replication and data reuse to efficiently schedule dataintensive applications on grids Текст. / S. N. Elizeu, W. Cirne, F. Brasileiro, A. Lima // Springer том 3277

62. Maheswaran, M. Dynamic mapping of a class of independent tasks onto heterogeneous computing systems Текст. / M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, R. F. Freund // Journal of Parallel and Distribute Computing 1999. - № 59. - С. 107-13.

63. Derbal, Y. A probabilistic scheduling heuristic for computational grids. Текст. / Y. Derbal // Multiagent Grid Systems. 2006. - № 2:45-59

64. Yang, L. Homeostatic and tendency-based cpu load predictions. Текст. / L. Yang, I. Foster, J.M. Schopf// IPDPS '03: proceedings of the 17th international symposium on parallel and distributed processing. IEEE Computer Society, Washington 2003.

65. Gibbons, R. A historical application profiler for use by parallel schedulers. Текст. / R. Gibbons // IPPS '97: proceedings of the job scheduling strategies for parallel processing. London, 1997 - pp 58-77

66. Downey, A. B. Predicting queue times on space-sharing parallel computers. Текст. / A. B. Downey // In: IPPS '97: proceedings of the 11th international symposium on parallel processing.- IEEE Computer Society Washington, 1997 -pp 209-218

67. Iverson, M.A. Statistical prediction of task execution times through analytic benchmarking for scheduling in a heterogeneous environment Текст. / M. A. Iverson, F. Ozguner, L. Potter // IEEE Transanction Compututing. 1999. - № 48. - C. 1374-1379

68. Imran, Rao. A probabilistic and adaptive scheduling algorithm using systemi generated predictions for inter-grid resource sharing Текст. / Rao Imran, Huh Euij

69. Nam // Journal of Supercomputing 2008. - № 45. - C. 185-204'

70. Andrade, N. Our- Grid: An Approach to Easily Assemble Grids with Equitable1. J!

71. Resource Sharing Текст. / N. Andrade, W. Cirne, F. Brasileiro, P. Roisenberg //9th JSSPP, 2003.

72. Paranhos, D. Trading Cycles for Information: Using Replication to Schedule Bag-of-Tasks Applications on Computational Grids- Текст. / D. Paranhos, W.

73. Cirne, F. Brasileiro // Europar'2003, 2003.

74. Santos-Neto, E. Exploiting Replication and Data Reuse to Efficiently Schedule Dataintensive Applications on Grids Текст. / E. Santos-Neto, W. Cirne, F. Brasileiro, A. Lima // 10th JSSPP, 2004.

75. Casanova, H. Heuristics for Scheduling Parameter Sweep Applications in Grid

76. Environments Текст. / H. Casanova и др. // Heterogeneous Computing Workshop -2000. -№9. c. 349-363.

77. Cirne, Walfredo. Labs of the World Unite!! Электронный ресурс. / Walfredor

78. Cirne, Francisco Brasileiro, Nazareno Andrade, Robson Santos, Alisson Andrade. -Режим доступа: http://copin.ufcg.edu.br/twikipublic/pub/OG/OurPublications/LabsoftheWorldUnitev 19.pdf

79. Resource Selection Using Execution and Queue Wait Time Predictions Текст. : Technical Report: Warren Smith, Parkson Wong —2002. —NASA Ames Research Center Moffett Field, CA 94035, NAS Technical Report Number: NAS-02-003

80. Atkeson, C. Locally Weighted Learning Текст. / С. Atkeson, A. Moore, S. Schaal // Artificial Intelligence Review. 1997. - № 11. - С. 11-73.

81. A Locally Weighted Learning Tutorial using Vizier 1.0 Текст. Technical Report : Schneider J., Moore A. —2000. Robitics Institute, Carnegie Mellon University, CMU-RI-TR-00-18.

82. Wilson, D. R. Improved Heterogeneous Distance Functions Текст. / D. R. Wilson, T. R. Martinez // Journal of Artificial Intelligence Research. -1997. № 6. - C. 1-34.

83. Goldberg, D. Algorithms in Search, Optimization, and Machine Learning Текст./D. Goldberg.-Addison-Wesley, 1989.

84. Messing, F. Predicting scheduling success Текст. / F. Messing // SpaceOps symposium, Germany, 1996:

85. Ямпольский, А. Двухпроходное перекодирование Электронный ресурс. / А'. Ямпольский. Режим доступа: http://wvm.gotview.ru/obzor/printfaq/faq004p.html

86. Polychronopoulos, С. D. Guided self-scheduling: A practical scheduling scheme for parallel supercomputers Текст. / Polychronopoulos, C. D., Kuck, D. J. // IEEE Transactions on Computers. 2007. -том 36- № 12. - С. 1425-1439.

87. MONARC Project Phase2 Report Текст. Technical Report :* Aderholz, M. [и др.] —2000, CERN.

88. Lichun, Ji. Coordination and P2P Computing. Текст. : Master Thesis, Department of Computer Science, University of Saskatchewan Saskatoon, Canada, 2004.

89. Dutcher, Bill. The NAT Handbook: Implementing and Managing Network Address Translation Текст. / Bill Dutcher. John, Wiley & Sons, 2001. - 322 c. -ISBN-10: 0471390895 - ISBN-13: 978-0471390893

90. Anderson, D. P. SETI@home: an experiment in public-resource computing Текст. / D. P. Anderson, J. Cobb, E. Korpela, M. Lebofsky, D. Werthimer. // . Communications of the ACM. 2002. - том 45-№ 11. - C. 56-61.

91. Foster, I. The Grid2: Blueprint for a New Computing Infrastructure, Morgan Kaufmann Текст. /1. Foster and C. Kesselman. Morgan Kaufmann, 2003.

92. Долинина, О. H. Повышение эффективности обработки видеоинформации с использованием GRID-вычислений Текст. / О.Н. Долинина, A.B. Оуграбко- Вестник Саратовского государственного технического университета. -2009.-№42.-с 101-106.

93. Stärk, Robert F. Java and the Java Virtual Machine: Definition, Verification, Validation Текст. / Robert F. Stärk, Joachim Schmid . Springer, 2001. - 392 c.- ISBN-10: 3540420886 ISBN-13: 978-3540420880

94. Zukowski , John. Java 6 Platform Revealed Текст. / John Zukowski . 1-е изд. - Apress, 2006. - 240 c. - ISBN-10: 1590596609 - ISBN-13: 978-1590596609

95. О.Н. Долинина, A.B. Ермаков, Д.М. Верескун. Метод обработки видеоинформации с использованием GRID-pecypcoB\\ XXIII Международная научная конференция Математические Методы в Технике и Технологиях -ММТТ- 23 22-24 июня 2010 года, СГТУ, Саратов, Россия.

96. Д. Худсон. Статистика для физиков Текст.//Москва 1970.

97. Правообладатель(ли): Государственное образовательное учреждение высшего профессионального образования «Саратовский государственный технический университет» (ГОУВПО СГТУ) (№)

98. Автор(ы): Ермаков Александр Вадимович, Верескун Дмитрий Михайлович (К11)1. Заявка № 2010617860

99. Дата поступления 13 декабря 2010 Г.

100. Зарегистрировано в Реестре программ для ЭВМ7 февраля 2011 г.

101. Руководитель Федеральной службы по интеллектуальной собственности, патентам и товарным знакам1. Б.П. Симонов1. Ж Ж