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

Вид материала

Автореферат

Содержание Общая характеристика работы Целью исследования Методы исследования. Достоверность и обоснованность На защиту выносятся Научная новизна Практическая ценность Реализация и внедрение результатов работы. Апробация работы. Личный вклад автора. Структура и объем работы. Основное содержание работы Вторая глава S образована множеством сайтов , где — сайты, f N – число групп узлов; – число узлов в i U – скорость канала передачи данных; JV TN. Принимаем число групп узлов равным единице с производительностью тестового узла. Принимаем GN GN, для которого среднее значение f(GN) следующих за ним n X – это число GOP в одном задании плана. Шаг 6. В случае, если удалось улучшить значение f(GN,TN) Основные результаты диссертации опубликованы в работах ... ссылка скрыта

Подобный материал:

• Утверждаю, 111.69kb.
• Лабораторная работа №7 Технологии разработки распределенных информационных систем, 168.59kb.
• Метод повышения эффективности некаталитической очистки отработавших газов судовых дизелей, 266.03kb.
• ссылка скрыта, 169.51kb.
• Краткая история развития, 58.89kb.
• Лекция Архитектура распределенных приложений J2EE, 532.44kb.
• К автоматизации моделирования распределенных систем с помощью Марковских процессов, 133.26kb.
• Муниципальное общеобразовательное учреждение, 266.77kb.
• Реферат на тему «История развития вычислительной техники», 409.19kb.
• Контрольные вопросы и задания, 1518.03kb.

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


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


МЕТОД ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ОБРАБОТКИ

ВИДЕОИНФОРМАЦИИ С ИСПОЛЬЗОВАНИЕМ

РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ


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

информации (в технической отрасли)


АВТОРЕФЕРАТ

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

кандидата технических наук


Саратов 2011

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

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

Научный руководитель	- кандидат технических наук, доцент Долинина Ольга Николаевна
Официальные оппоненты	- доктор технических наук, профессор Большаков Александр Афанасьевич
	- доктор физико-математических наук, доцент Шульга Татьяна Эриковна
Ведущая организация	ФГОУ ВПО «Астраханский государственный технический университет»

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


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

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


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


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

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

В.В. Алешкин

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Среди существующих подходов можно выделить использование локальных вычислительных машин, специализированных аппаратных плат обработки, ресурсов локальных вычислительных сетей (ЛВС), вычислительных кластеров.

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

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

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

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

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

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

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

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

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

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

,

(1)

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

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

для ,

(2)

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

Значение характеризует количество заданий, выполненных j-м узлом за время, равное времени показанным тестовым узлом, и используется как базовая характеристика. Она позволяет определять скорость работы узлов относительно друг друга. Также для любого узла может быть получено время обработки им задания относительно другого узла, для которого оно известно: , где и , и – время обработки j-м узлом тестового задания и его производительность; время обработки искомым i-м узлом тестового задания и его производительность соответственно.

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

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

(3)

где – число групп узлов; – количество узлов в i-й группе.

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

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

,

(4)

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

(5)

где N – число групп узлов; – число узлов в i-й группе; t_{тест обр.}– время обработки одного задания тестовым узлом, а t_{j обр.}– время обработки i-м узлом; t_{тест пер.}– время передачи одного задания тестовым узлом, а t_j пер.– время передачи i-м узлом. При этом:

;

(6); (7)

где U – скорость канала передачи данных; JV – объем данных видеофайла; GN – число узлов; t_зп– время задержки при передаче данных; _ – производительность узла; tt– время обработки одного задания;

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

,

(8)

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

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

Полученная модель включает две управляемые переменные, первой из них является TN – число заданий в плане. Каждое задание может содержать один или более независимо сжатых изображений (GOP). Таким образом, один видеофайл может быть разбит на различное число заданий. Поэтому план содержит JK кадров с общим объемом данных JV. Задания представляют собой отрезок TK кадров, содержащих TV объем данных. При этом результат _ – целое число, где K – количество кадров в одном GOP. Отсюда

; .

(10); (11)

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

(12)

где NK – число GOP в одном задании.

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

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

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

Рассмотрим предлагаемый метод в виде пошаговой процедуры:

Шаг 1. Принимаем размер одного задания равным одному GOP и получаем TN. Принимаем число групп узлов равным единице с производительностью тестового узла. Принимаем GN равным числу узлов, имеющихся в системе.

Шаг 2. Определяем методом градиентного спуска число GN, для которого среднее значение f(GN) следующих за ним n точек не менее f(GN).

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

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

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

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

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

,

(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; GP₂= 1.64; GP₃= 1.27; GP₄= 1.

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

Результаты эксперимента проиллюстрированы на рис. 3, который демонстрирует снижающийся тренд, причем число узлов записывается как G₁/G₂/G₃/G₄, где G_i – число узлов i-й группы, причем их производительности P(G_i) соотносятся как P(G₁)> P(G₂)> P(G₃)> P(G₄). Это означает постепенное сокращение времени обработки видеоинформации при увеличении общей производительности вычислительных узлов.



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

при варьировании состава сайта

В рамках общего тренда можно выделить несколько участков графика, начало которых отмечено резким увеличением времени обработки с последующим постепенным возвращением к общему тренду. Анализ результатов эксперимента показывает, что постепенное изменение состава сайта с { G₁=1; G₂=1; G₃=1; G₄= 9} до { G₁=1; G₂ = 9; G₃= 1; G₄= 1} проходит без резких скачков, однако дальнейшее его изменение на { G₁=2; G₂ = 1; G₃= 1; G₄= 9} демонстрирует первый подъем. Остальные скачки также соответствуют подобным изменениям. Это позволяет сделать вывод о том, что увеличение числа более производительных узлов не компенсирует уменьшение числа узлов следующей по производительности группы. При этом различные составы вычислительного сайта могут демонстрировать одинаковую производительность. Как следствие, для однозначной трактовки отношения производительности одного состава сайта к другому необходимо применение математического моделирования для прогноза времени обработки видеофайлов. Как показано на рис. 3, график, отображающий экспериментальные данные, не противоречит графику, иллюстрирующему результаты применения предложенной математической модели. Эксперименты, проведенные для других значений параметров плана обработки и GRID-среды, также не выявили противоречий, что позволяет утверждать об экспериментально доказанной справедливости разработанной модели в определении зависимостей по исследуемому набору параметров.

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

Выбор критерия оценки адекватности основывается на типе распределения данных. Введем гипотезу H₀ о том, что данные, соответствующие выражению (15), распределены нормально. Разработанная модель содержит четыре величины (t_тест., t_зо., t_зп., t_сдв.), имеющие случайный характер, поэтому необходимо оценить их влияние на распределение. По эмпирическим выборкам значений случайных величин, полученным в ходе экспериментов, получим оценки их средних значений и оценки их дисперсий. Эти значения являются исходными данными для генерации независимых случайных равномерно распределенных чисел, выбранных из квазислучайной последовательности. Полученные значения позволяют рассчитать среднеквадратичное отклонение для каждой из величин и рассчитать среднеквадратичное отклонение для t_j. Воспользуемся методом переноса ошибок, согласно которому для малых дисперсий возможно разложение в ряд Тейлора с удержанием первых членов разложения, позволяющих оценить дисперсию. Если представить формулу (9) как

;

где , , , , , , , , ;

тогда:

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

Проведем эксперимент в условиях, аналогичных эксперименту, результаты которого приведены на рис. 3. Процедура оценки адекватности заключается в построение доверительных интервалов и оценке накрытия ими проверяемых значений. Введем гипотезу H₀ о нормальном распределении экспериментальных данных. Для этого выделим экспоненциальное среднее и вычислим абсолютную разницу между средней и всеми значениями эксперимента. Проверка полученных значений показывает, что остатки являются белым шумом, таким образом, нет оснований отклонить нулевую гипотезу. Для оценки адекватности используем критерий Стьюдента. Введем гипотезу где i=1,2 при альтернативной гипотезе где i=1,2, где — оценка математического ожидания экспериментальных данных и данных математического моделирования. Полученные на основе дисперсии значения с уровнем значимости удовлетворяют нулевой гипотезе. Таким образом, построенные доверительные интервалы для среднего накрывают ненаблюдаемую истину с вероятностью 95% (рис. 4), что позволяет судить об адекватности модели.



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

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

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

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

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



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

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

ЗАКЛЮЧЕНИЕ

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

1. Разработана математическая модель оценки времени обработки видеоинформации с использованием GRID-вычислений, которая позволяет моделировать обработку заданий, относящихся к классу задач с большим объемом обрабатываемой информации, где объем передаваемых и получаемых с вычислительного узла данных совпадает. Впервые проведен анализ влияния значений случайных величин на процесс обработки плана в GRID-среде. Для рассматриваемой модели доказана ее адекватность экспериментальным данным.
   
2. Предложен метод оценки производительности вычислительных узлов в GRID-среде. Его использование позволяет получить независимую оценку времени обработки одинаковых заданий разными узлами. Принцип объединения узлов в группы в зависимости от получаемого значения относительной производительности позволяет снизить влияние случайных колебаний на оценку производительности вычислительных узлов.
   
3. Создан метод повышения эффективности обработки видеоинформации с использованием GRID-вычислений, который базируется на предложенной в работе модели оценки времени обработки видеоинформации и позволяет повысить эффективность её обработки, основываясь на особенностях, которые отличают обработку видеофайлов от остальных задач с большим объемом обрабатываемых данных. Метод определяет значения управляемых переменных разработанной модели, для которых время обработки сокращается по сравнению с традиционно используемыми подходами. При этом число используемых вычислительных узлов не увеличивается. Метод может использоваться совместно с различными планировщиками GRID-среды.
   
4. Для всех предложенных в работе методов разработаны алгоритмы, реализованные затем в составе комплекса программ обработки видеоинформации в GRID-среде. Они позволили проверить работоспособность и достигаемое повышение эффективности предложенным методом. Применение разработанного комплекса программ позволило добиться снижения времени обработки для задачи совмещения нескольких видеоизображений.
   
5. Получены экспериментальные зависимости времени обработки видеофайлов от различных значений параметров GRID-среды и плана обработки.
   

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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


МЕТОД ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ОБРАБОТКИ

ВИДЕОИНФОРМАЦИИ С ИСПОЛЬЗОВАНИЕМ РАСПРЕДЕЛЕННЫХ

ВЫЧИСЛЕНИЙ


Автореферат


Ответственный за выпуск А.В.Бровко

Корректор Л.А. Скворцова

Подписано в печать	31.05.11	Формат 6084 1/16
Бум. тип	Усл.-печ.л. 1,0	Уч.-изд. л. 1,0
Тираж 100 экз.	Заказ	Бесплатно

Саратовский государственный технический университет

410054, г. Саратов, ул. Политехническая, 77

Отпечатано в издательстве СГТУ, 410054, г. Саратов, ул. Политехническая, 77