РЕЦЕНЗИРОВАНИЕ РАБОТ

Просмотров

Web Counters

МІНІСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Лемесев Кирилл Анатольевич

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

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

Автореферат

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

МОСКВА – 2012


Актуальность темы исследования

 

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

Инфраструктура Интернета изначально была разработана для использования человеком, а не компьютерными программами. Подавляющее большинство данных в Интернете доступны в формате HTML (Hypertext Markup Language, язык разметки гипертекста). Это формат создан для визуализации данных в интернет-браузерах, но он не предоставляет какой-либо семантической информации о данных, которые записаны с помощью этого языка. Это способ представления данных не подходит для автоматических систем обработки и управления данными. По этой причине использование данных из Интернета в первоначальном виде для решения каких-либо задач является проблемой.

 

Существует несколько способов для решения этой проблемы. В частности, для того чтобы собрать данные из нескольких источников в едином формате, необходимо разрабатывать специальные программы – “обертки” (wrappers). «Оборачивать» в этом смысле означает скрывать детали внутренней работы с неструктурированными данными, предоставляя пользователю простой интерфейс работы с уже структурированными данными. Пользователем таких программ обычно выступает программист, создающий программы для конечных пользователей.

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

 

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

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

В техническом плане подобные требования может удовлетворить горизонтальное масштабирование ресурсов – увеличение совокупной вычислительной мощности системы путем добавления новых компьютеров. Такой подход увеличения ресурсов потенциально не имеет ограничений. При этом горизонтальное масштабирование технически может осуществляться различными техническими и аппаратными способами. Важным критерием здесь является способность системы относительно быстро и «дешево» изменять объем ресурсов (то есть количество компьютеров) для решения задачи.

Обеспечить такого рода масштабирование с гибким выделением ресурсов на сегодняшний день может особый способ организации вычислений – так называемые облачные вычисления. В настоящей работе будем понимать под этим термином следующее: программная система работает в дата-центрах поставщиков платформ облачных вычислений («в облаке»), пользователю детально не известны ресурсы, которые использует система; при необходимости объем этих ресурсов может быть оперативно, «на ходу», увеличен или уменьшен. Подобная модель носит название SaaS (software as a service, программное обеспечение как сервис), когда пользователь оплачивает только использование какого-либо продукта, его не интересует внутренняя инфраструктура, лицензии на экземпляры ПО и т.д.

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

Цель и задачи диссертационной работы

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

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

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

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

4. Используя критерий, определить лучшие алгоритмы. Для оценки каждого алгоритма, использовать вычислительный эксперимент.

5. Проверить результаты на практике.

Объектом исследования является задача извлечения структурированной информации из сети Интернет.

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

Методы исследования

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

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

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

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

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

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

Положения, выносимые на защиту

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

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

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

Достоверность результатов работы

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

Проверка адекватности (валидация) имитационной модели проводилась на основе теста по прогнозу поведения реальной системы на основании модели.

Программный комплекс для извлечения структурированной информации из сети Интернет, использующего облачную инфраструктуру, построен по описанным принципам. Система - общедоступный веб-сайт (частично доступен по адресу rss-farm.ru). Основное назначение системы - получение структурированной информации различной тематики из открытых источников сети Интернет. Структура данных, получаемых от системы, специфицирована форматом RSS (feed2.w3.org/docs/rss2.html).

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

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

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

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

• Интернет-сервис «RSS-farm», реализованный на базе разработанных принципов и компонент, который на протяжении нескольких лет активно используется для получения статей, новостей и прочего содержимого периодических интернет-изданий на мобильные устройства.

Апробация работы

Основные результаты работы доложены на следующих конференциях:

• Восьмой конкурс молодежных инновационных проектов Технопарка МИФИ (Москва, 2009);

• XII московская международная телекоммуникационная конференция студентов и молодых ученых «Молодежь и наука» (Москва, 2009);

• 6th RuSSIR Young Scientists Conference (Ярославль, 2012);

• Ежегодная научно-техническая конференция МГУЛ (Москва, 2013);

Объем и структура работы

Диссертация состоит из введения, трех глав с выводами, заключения, перечня литературы (44 наименования) и 1 приложений, включающих исходные данные и промежуточные результаты апробации разработанных методов и алгоритмов. Работа изложена на 80 страницах машинописного текста, из них 1 страниц - основной текст и 1 страниц – приложения, содержит 1 рисунка и 1 таблиц (1 – в основном тексте и 1 в приложениях).

Основное содержание работы

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

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

Существует несколько определений процесса извлечения структурированных данных из сети Интернет. В частности, в [Laender, Ribeiro-Neto, 2002] извлечение структурированных данных определяется как «последовательность процедур, извлекающая информацию из информационных источников сети Интернет». В [Baumgartner, Gatterbauer, 2009] задача определяется как «программная система, автоматически и регулярно извлекающая информацию из страниц сети Интернет, содержащие данные, и поставляющие эти данные базе данных или третьей программе». Из этих определений можно выделить следующий список:

• Взаимодействие с веб-страницами;

• Создание алгоритма для преобразования данных (wrapper, обертка);

• Автоматизация и планирование процесса извлечения информации;

• Преобразование данных;

• Использование преобразованных данных.

Рассмотрим подробнее каждый из этих аспектов

Взаимодействие с веб-страницами. Первая фаза процесса извлечения структурированных данных – взаимодействие с сетью Интернет [Wang, Hawk, 2000]. Источники информации сети Интернет обычно представлены с помощью веб-страниц, RSS- или ATOM-лент и так далее. Пользователь может перемещаться по этим источникам с помощью Интернет-браузера. Современные системы извлечения структурированных данных поддерживают извлечения данных из динамических страниц, которые были созданы в момент запроса пользователей страницы по определенным параметрам. Также поддерживается другой тип страниц – статический, для страниц с неизменным содержанием.

Создание алгоритма для преобразования данных (wrapper, обертка).

Предназначение программ-оберток – извлекать неструктурированную информацию из источника данных и преобразовывать эту неструктурированную информацию в структурированные данные [Zhao, 2007; Irmak, Suel, 2006]. Система извлечения информации должна поддерживать создание и выполнение программ-оберток.

Автоматизация и планирование процесса извлечения информации. Автоматизация процесса получения веб-страниц, определение положения искомой информации и ее извлечение – ключевые возможности систем извлечения структурированных данных [Phan, Horiguchi, 2005]. Планирование расписания извлечения информации необходимо в случае извлечения информации из регулярно обновляемых веб-сайтов (например, новостных).

Преобразование данных. Информация может быть извлечена из разных источников («обернута» с помощью программ-оберток). После работы программ-оберток данные будут представлены в известном формате. Стадии между извлечением и поставкой данных называются преобразованием данных: на этих этапах, среди которых может быть очистка данных [Rahm, Do, 2000] и разрешение конфликтов данных [Monge, 2000], достигается получение однородных непротиворечивых данных.

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

Масштабируемость системы – способность системы обрабатывать растущие объемы данных, путем увеличения используемых системой вычислительных ресурсов. Как можно обеспечить такое требование? Как обеспечить автоматическое масштабирование системы, при котором системе автоматически выделяется больше компьютеров для работы при возрастании нагрузки (числа данных, которые нужно обработать) и меньше – при снижении нагрузки?

Масштабируемость подразумевает использование системой нескольких компьютеров. Как в таком случае распределить составные части системы по разным компьютерам? Количество каких компьютеров нужно увеличивать (или уменьшать) в зависимости от нагрузки?

В литературе (например, в [Lee, 2004]) широко распространена схема системы извлечения структурированных данных «медиатор - обертки». Суть заключается в том, что обертки сами по себе не представляют большой ценности, так как каждая обертка способна получить данные только из одного ресурса. В задачах реального мира, при использовании систем извлечения структурированных данных, необходимо получать структурированные данные из разных источников. В дополнение к этому, полученные данные из разных источников необходимо «согласовывать» (например, заменять разные значения в словарях, обозначающие одно и то же) и объединять в единый массив данных для дальнейшей обработки. Для этих целей вводят специальный компонент – медиатор.

Схема «медиатор – обертки»

Рис. 1. Схема «медиатор – обертки»

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

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

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

Для краткости, будем называть компьютер, на котором запущен компонент медиатора – медиатором. Компьютер, на котором запускается обработка оберток – процессором (оберток или заданий).

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

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

• Какой процессор должен обработать поступившее задание.

Такие задачи возникают не только в системах извлечения структурированных данных из сети Интернет.

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

Множество алгоритмов, подходящих для решаемой задачи управления вычислительными ресурсами:

I. Равновероятностное распределение нагрузки (чего?) и Принятие решения об изменении числа компьютеров на основе показателей загрузки;

II. Последовательное распределение и Принятие решения об изменении числа компьютеров на основе показателей загрузки;

III. Распределение на основе показателей загрузки и Принятие решения об изменении числа компьютеров на основе показателей загрузки.

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

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

• Хотелось бы уменьшить затраты на машинное время (и прочие накладные расходы), которое было использовано при обработке заданий пользователя. Чем меньше значение этого параметра, тем «дешевле» обойдется пользователю обработка заданий.

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

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

Критерий эффективности

Будем считать затратами на машинное время стоимость аренды компьютеров на время, необходимое для обработки заданий. Затраты на машинное время будем учитывать следующим образом. Предположим, что для обработки заданий возможно использование компьютеров, различающихся по производительности (и по цене за аренду в единицу времени). Цена более производительных компьютеров может быть выше, менее производительных – ниже. Для того, чтобы не учитывать абсолютные значения стоимости аренды оборудования, будем использовать относительную цену аренды. Относительная цена аренды компьютера – безразмерная величина, показывающая, во сколько раз дешевле стоит арендовать данный компьютер относительно самого дешевого компьютера (на одно и тоже время). Умножив относительную цену компьютера на интервал времени в секундах, необходимый для обработки заданий, получим затраты для аренды данного компьютера. Просуммировав такие затраты по всему множеству использованных в обработке компьютеров, получим суммарные затраты на машинное время. Полученное значение будет измеряться в секундах.

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

Более формально, существует некоторая функция φ (лучше, чтобы обозначения функций были как в формалах в тексте) от входного потока заданий A:

φ(А) =k*α+p*β (2.1)

Где:

α - суммарные затраты на все компьютеры, использованные в ходе выполнения заданий:

Cуммарные затраты на все компьютеры, использованные в ходе выполнения заданий (2.2)

ci – относительная стоимость i-го компьютера в единицу времени,

ti – время существования i-го компьютера.

β – суммарное время, затраченное на выполнение всех заданий:

Cуммарное время, затраченное на выполнение всех заданий (2.3)

tj' – время начала обработки задания j,

tj'' – время окончания обработки задания j.

k и p – весовые коэффициенты (k + p = 1). Для того чтобы функция была безразмерна, примем размерность k – с-1, p – с-1.

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

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

Описание модели

На вход модели поступают задания для обработки – обертки, на основании которых должны быть извлечены структурированные данные из сети Интернет. Модель имитирует обработку заданий на переменном числе компьютеров. В зависимости от частоты и «сложности» поступающих заданий, модель может увеличивать или уменьшать число компьютеров для обработки заданий.

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

Модель предлагаемой системы (структуры) реализована в среде MATLAB Simulink. Данная среда позволяет моделировать, в том числе, системы массового обслуживания. Основные объекты таких моделей – задания (заявки), блоки, и маршруты между блоками. Поток заданий проходит «сквозь» систему, от момента создания до момента попадания в блок коллектора заданий. Пути следования заданий соединяют блоки. Задания, проходя через систему, взаимодействуют с блоками, через которые они проходят. Блоки могут задерживать в себе задания, имитируя работу, могут модифицировать атрибуты заданий и изменять пути следования заданий. Так же блоки могут быть соединены дополнительными связями для передачи сигналов. Кроме блоков, взаимодействующих с заданиями, существуют служебные блоки, такие как таймер, генератор случайных чисел, коллектор данных и прочие служебные блоки.

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

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

В реальной системе заранее определить время, которое уйдет на обработку какого-либо задания сложно. Более того, для одного задания это время может изменяться (случайные задержки сети, разная производительность оборудования источников данных и т.д.). Таким образом, определить «сложность» задания можно только после окончания обработки этого задания. В модели вычислительная сложность каждого задания определяется заранее, с помощью случайной величины Ψ, равномерно распределенной на отрезке [tmin; tmax].

В модели Задания (нужна ли заглавная буква?) обрабатываются одновременно на нескольких компьютерах. На одном компьютере может обрабатываться несколько заданий параллельно. В модели на одном компьютере может обрабатываться до двух задач параллельно. Это обосновано двумя факторами:

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

• Согласно допущению модели, время обработки задания – неизменная величина. При параллельной обработке двух заданий, время обработки задания не меняется.

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

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

Максимально возможное число компьютеров в системе равно N минимальное – M. M < N.

Параметры алгоритмов

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

Критериями для алгоритма масштабирования служат следующие два:

• Верхний порог (T) - максимальное число заданий в одной очереди, при превышении которого необходимо подключить новый компьютер. Если очередей несколько, учитывается среднее значение по всем очередям.

• Нижний порог – минимальное число заданий в очереди. Если длина очереди меньше чем нижний порог, число компьютеров необходимо уменьшить. Так же как и верхний порог, этот показатель рассчитывается по всем очередям. Будем обозначать нижний порог, как долю верхнего порога (Tm).

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

Добавление компьютеров в систему занимает определенное время. С момента принятия решения о включении еще одного компьютера до момента начала обработки заданий этим компьютеров проходит некоторое время, за которое подготавливается виртуальная машина, происходит загрузка операционной системы и т.д. Эта особенность учитывается в модели следующим образом. В момент принятия решения о необходимости добавить в систему еще один компьютер, создается фиктивное задание (точнее, два задания, т.к. модель предполагает до двух параллельно обрабатываемых заданий), цель которого – заблокировать «новый» компьютер на некоторое время. Это задание поступает на компьютер в числе первых. Компьютер, обрабатывая фиктивное задание, остается занятым для «настоящих» заданий. Вычислительная сложность такого задания равна времени подготовки нового компьютера. Время, которое потребуется для создания нового компьютера, невозможно задать. Это время определяется параметрами облачной среды. Обозначим эту величину как Tnewc.

Общая структура модели выглядит следующим образом:

Общая структура модели (Сплошные линии – направления движения заданий; курсивная линия – движение информации о загруженности компьютеров)

Рис. 2. Общая структура модели (Сплошные линии – направления движения заданий; курсивная линия – движение информации о загруженности компьютеров)

Анализ проведенных экспериментов

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

Определяя коэффициенты k и p (то есть, определяя приоритеты в работе системы) по-разному, оптимальными становились разные наборы параметров (Mt, Tm, T).

Отметим следующие особенности:

• Алгоритм 3 (распределение на основе показателей загрузки) всегда не хуже или лучше чем все остальные алгоритмы. Основываясь на проведенных экспериментах, можно сказать, что этот алгоритм в некоторых случаях может быть до 16% эффективнее, чем все остальные алгоритмы, представленные в работе.

• С помощью коэффициентов k и p (или верхнего порога T) возможно задавать поведение системы: либо экономить на скорости обработки задач, либо на вычислительных ресурсах.

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

• При создании и эксплуатации реальных систем, такие параметры как верхний порог (T), время среднего (Mt) и множитель порога (Tm) должны быть уточнены исходя из опыта работы реальной системы.

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

В настоящей работе для проведения экспериментов, помимо модели, использовалась реальная программная система извлечения структурированных данных. Данная система была создана в рамках работы над диссертацией. Эта система является общедоступным Интернет-сервисом, позволяющим всем желающим формировать собственные RSS-каналы [RDF Site Summary (RSS) 1.0].

С помощью Системы пользователи могут определить, какую информацию необходимо взять из источников сети Интернет и представить в виде документа, имеющего определенную структуру (RSS). Поле подобного определения, Система регулярно будет опрашивать источники с целью обновления данных RSS-канала.

Более подробно узнать о Системе и попробовать её в действии можно по адресу [RSS-farm.ru: полные версии RSS-каналов].

В рамках данной работы обработчик оберток был адаптирован для работы в облачной инфраструктуре вычислений (Windows Azure):

• Добавлена возможность работы на нескольких компьютерах одновременно;

• Выделены алгоритмы Медиатора и Процессора оберток;

• Добавлен алгоритм масштабирования ресурсов.

Медиатор поддерживает несколько режимов распределения нагрузки между процессорами, а именно (из таблицы 2.1.):

1. Равновероятностное распределение нагрузки;

2. Последовательное распределение;

3. Распределение на основе показателей загрузки.

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

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

Анализ работы на реальной системе

• Как и в экспериментах на модели, компонент α значительно меньше β. Как и прежде, актуальны как минимум две оценки целевой функции φ – для k=p=0,5 и k=0.99, p=0,01.

• Алгоритм 3 (Распределение на основе показателей нагрузки) имеет минимальные значения целевой функции φ во всех проведённых экспериментах.

Основные результаты работы

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

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

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

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

• С помощью вычислительного эксперимента выявлен наилучший способ управления вычислительными ресурсами в облачной инфраструктуре.

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

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

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

Нет ответа на вопрос, когда облачная структура не нужна!

Публикации

По теме диссертации опубликовано 8 научных работ, в том числе 2 статьи в сборниках научных трудов, 2 свидетельства о государственной регистрации программы для ЭВМ.

1. * Лемесев К.А. Модели и методы извлечения структурированной информации из сети Интернет. Лесной вестник, Москва 2012, с.113-115.

2. Лемесев К.А. Программный комплекс для преобразования содержимого интернет-сайтов. Материалы XII московской международной телекоммуникационной конференции студентов и молодых ученых «Молодежь и наука», Москва 2009, с.50.

3. Лемесев К.А., Несвижский А.И. Принципы построения портала вуза. Материалы научной сессии МИФИ – 2006. Сборник научных трудов. Москва 2006, с. 39.

4. Лемесев К.А. Современные способы построения информационных интернет-ресурсов образовательных учреждений. Материалы научной сессии МИФИ – 2007. Сборник научных трудов. Москва 2007, с. 43.

5. Свидетельство о регистрации электронного ресурса №17448 «Программный комплекс для исполнения вычислительных потоков в изолированных доменах приложения» от 23 сентября 2011.

6. Свидетельство о регистрации электронного ресурса №17449 «Программный комплекс для извлечения структурированной информации из сети Интернет» от 23 сентября 2011.

7. Крутенев Д.В., Лемесев К.А., Несвижский А.И. Проектирование и реализация Интернет-портала вуза. XV Международный научно-технический семинар "Современные технологии в задачах управления, автоматики и обработки информации". Сборник трудов. М.: изд. МИФИ. 2006, с. 78

8. Крутенев Д.В., Лемесев К.А., Мельникова Н.А. Проектирование и разработка инструмента для создания Интернет-порталов. XVI Международный научно-технический семинар "Современные технологии в задачах управления, автоматики и обработки информации". Сборник трудов. Тула: изд. ТулГУ. 2007, с. 62-63.