СОДЕРЖАНИЕ РАБОТЫ
Во введении обсуждается актуальность и практическая значимость темы, сформулированы цели и предмет исследования, изложено краткое содержание работы.
Первая глава посвящена исследованию и анализу существующих алгоритмов и средств распределённой обработки потоковой информации.
В начале главы раскрывается понятие задач обработки потоковой информации и рассматриваются общие особенности решения данных задач на распределённых вычислительных комплексах.
Далее рассматриваются характерные особенности задач обработки мультимедийной информации, среди которых отмечаются высокая гранулярность при распараллеливании и высокие требования к возможностям модернизации получаемых решений.
Производится обзор классов систем распределённой обработки информации (суперкомпьютеры, кластерные системы на базе компьютеров среднего уровня, GRID системы) и производится их сравнительный анализ по ряду параметров.
Рассматриваются основные статистические характеристики потоков мультимедийной информации и отмечается близость этой области к классическим моделям, пришедшим в теорию массового обслуживания из анализа телекоммуникационного трафика.
Производится обзор современных моделей и технологий, связанных с областью распределенной потоковой обработки мультимедийных данных. Рассматриваются основные проблемы и пути их решения.
Рассмотрены принципы построения распределённых систем, что позволило сделать вывод о том, что при решении задач потоковой обработки информации на гетерогенных комплексах целесообразно построение подсистемы обмена данными между вычислительными узлами с использованием существующих средств создания распределённых приложений типа MPI, DCOM или CORBA. Это обеспечивает разумный компромисс между требованием гибкости получаемого решения и степенью использования готовых решений.
Далее проведён краткий обзор теории массового обслуживания, суть которой состоит в применении методов теории вероятностей и математической статистики для моделирования работы распределённых систем обработки информации. Исходя из этого, сделан вывод о том, что функционирование гетерогенного распределённого комплекса может быть естественным образом описано в рамках этой теории.
В заключении главы сформулированы основные задачи исследования.
Вторая глава посвящена моделированию функционирования распределённых гетерогенных комплексов обработки потоковой информации в рамках теории массового обслуживания.
Постановка задачи включает разомкнутую сеть массового обслуживания (СеМО), состоящую из  перенумерованных одноканальных узлов. На вход сети поступает пуассоновский поток требований интенсивности  . Поступившее требование с вероятностью  поступает на обслуживание в  -й узел,  . Каждый узел представляет собой аппарат с интенсивностью обслуживания  , то есть время обслуживания требования на -м аппарате является случайной величиной, распределенной по экспоненциальному закону с плотностью распределения  .
Норма обслуживания характеризуется следующим правилом: если требование, поступившее на -й аппарат, застает его занятым, то оно становится в очередь ожидания этого аппарата. После окончания обработки на аппарате требование моментально покидает сеть.
Введем случайный процесс:  , где  - число требований в -м узле, ввиду известных свойств распределения Лапласа и экспоненциального распределения («отсутствие последствия») этот процесс является Марковским.
Рассмотрим вероятность обнаружения системы в момент времени  в состоянии  :
 .
Определим далее предельное распределение вероятностей в виде:
 .
Данное распределение существует в виду марковости процесса  .
Далее формулируются следующие основные задачи, связанные с исследованием рассматриваемой модели:
определение стационарного распределение вероятностей  этой системы обслуживания;
определение среднего времени пребывания требования в системе;
минимизация среднего времени пребывания требования в системе, путем управления делением входного потока  . То есть требуется выбрать такое распределение , при котором среднее время пребывания требований в системе будет минимальным относительно любого другого распределения.
В рамках решения первой задачи полученные уравнения нестационарного режима рассматриваемой модели имеют вид:
 ,
где  .
При переходе в стационарный режим производные по времени стремятся к нулю,  , и система линейных уравнений стационарного режима приводится к следующему виду:
 ,
где 
Далее в работе показано, что решение уравнений стационарного режима имеет вид:
Отметим важный вывод: узлы сети функционируют независимо друг от друга, что выражается в независимости стационарных вероятностей каждой из подсистем. Последнее характерно для большого множества разомкнутых сетей, в том числе и сети Джексона. Каждый узел при этом представляет собой одноканальную систему массового обслуживания с ожиданием. При этом входной поток для каждой из подсистем, выражается в виде
и обладает таким же пуассоновским свойством, как и общий поток  .
Среднее время пребывания в системе обслуживания складывается из среднего времени ожидания и среднего времени обслуживания. Так как система разделена на независимые составляющие, то среднее время пребывания можно выразить так:
 ,
где  – вероятность того, что требование будет обслуживаться на i-м аппарате,  – среднее время пребывания на аппарате.
Для одноканальной СМО с ожиданием, каковой является каждая из подсистем, среднее время ожидания просто выражается через среднюю длину очереди:
 ,
где  – среднее время ожидания начала обслуживания на i-м аппарате и  – среднее время обслуживания на нем же.
Показано, что для среднего времени пребывания требования в системе, в конечном итоге, имеет место выражение:
Оптимальное деление входного потока (вероятности ) было найдено путём построения и решения соответствующих систем уравнений, соответствующих экстремуму значения среднего времени пребывания  . В результате, для оптимальных значений вероятностей получено следующее выражение:
 ,
где  – средняя производительность аппаратов,  .
Соответственно, для минимального среднего времени пребывания требования в системе имеем выражение:
 .
Показано, что существует такое значение мощности обработчика  :
 , при которой оптимальная вероятность направления задания на данный обработчик не зависит от интенсивности входного потока.
Для проведения качественного анализа результата положим количество обработчиков достаточно большим, их производительности равномерно распределенными в интервале [0,3; 0,5] и рассмотрим функцию  как функцию двух аргументов  . Величины  и  при этих условиях можно считать постоянными. Для относительной интенсивности входного потока  можно построить набор графиков функции , показанный на рисунке 1.
  
Рисунок 1. Зависимость вероятности распределения заданий от производительности обработчика для разных значений относительной интенсивности входного потока
Качественный анализ полученного результата показывает, что зависимость  от , такова, что при росте , минимальные вероятности направления заданий на обработчик растут, а максимальные, наоборот, – падают.
Другими словами, при уменьшении интенсивности входного потока, вероятности направления заданий на обработчики со значением мощности, меньше чем , уменьшаются вплоть до выхода за пределы области определения вероятности. То есть, минимум среднего времени пребывания задания в системе, находится вне области определения параметров (вероятности направления заданий). При этом допустимое минимальное значение среднего времени пребывания заданий в системе находится на границе области определения его параметров. Показано, что решение этой проблемы состоит в исключении данных обработчиков из модели и пересчёте оптимальных вероятностей для получившейся модели.
Третья глава посвящена имитационному моделированию функционирования распределённых гетерогенных комплексов обработки потоковой информации.
Для проведения имитационного моделирования в среде системы компьютерной алгебры SAGE (http://sagemath.org) была разработана специальная программа, позволяющая оценивать основные характеристики СМО, подобных рассмотренной выше: с обработчиками различной мощности; без обмена данными между обработчиками; с временем обслуживания, удовлетворяющим различным распределениям вероятностей; с различными распределениями входного потока; с определённым набором стратегий распределения заданий.
Рисунок 2. Зависимость  от параметра функции управления
С помощью данной программы было проведена проверка полученного оптимального деления в описанной выше сети массового обслуживания. На рисунке 2 показан результат экспериментальной проверки формулы (1) для системы с двумя аппаратами следующей конфигурации:  ,  ,  .
Сплошной линией показана зависимость среднего времени пребывания требования в системе от значения параметра функции управления  (при этом  ). Точками показаны полученные экспериментальные значения, а вертикальными штрихами – оцененные дисперсии этих значений (производилось несколько независимых запусков системы с набором из 10000 заданий). Пунктирной линией показано среднее время пребывания требования в системе при другом алгоритме распределении заданий, учитывающем информацию о состоянии системы: очередное задание направляется на свободный обработчик, а если оба обработчика заняты – на более мощный из них.
Модель, рассмотренная во второй главе, на практике в чистом виде не встречается. В связи с этим, в третьей главе была предложена расширенная модель, имеющая по сравнению с рассматриваемой ранее, следующие особенности:
время обработки заданий в узлах описывается не экспоненциальным распределением, а гамма-распределением с малой дисперсией (т.е. в окрестности математического ожидания распределение близко к нормальному закону);
модулю управления заданий доступна актуальная информация о состоянии системы (длины очередей и состояния обработчиков).
Первое предположение соответствует довольно широкому классу задач обработки потоковой информации. Например, к нему относятся задачи обработки файлов, распределение длин которых хорошо описывается нормальным законом, а время обработки линейно коррелирует с длиной файла.
В реальных распределённых системах, как правило, присутствуют механизмы контроля ресурсов системы в реальном времени. Это оправдывает сделанное предположение о доступности актуальной информации о состоянии системы. Соответственно, логично предположить, что методы распределения заданий для новой модели будут использовать данную информацию.
Для введённой модели были рассмотрены три метода распределения заданий:
Метод с асинхронными обработчиками. Суть этого метода заключается в том, что задания сначала поступают в общую очередь системы, а освободившиеся обработчики забирают из неё очередное задание для обработки. Требование к организации общей очереди, вообще говоря, изменяет модель. Но поскольку это требование не затрагивает аппаратных ресурсов, то в контексте конечной цели – получения максимальной выгоды от имеющихся вычислительных ресурсов – рассмотрение данного метода наряду с другими можно считать корректным.
Метод минимизации времени пребывания в системе очередного задания. В этом методе при поступлении очередного задания для каждого обработчика оценивается предполагаемое время выхода данного задания из системы, и задание направляется на обработчик, «обещающий» минимальное время выхода.
Метод на основе поддержания фиксированного распределения загрузки обработчиков. Данный метод был разработан в рамках диссертационного исследования специально для расширенной модели. Он опирается на предположение о том, что, несмотря на изменение модели, в оптимальном режиме работы статистически оцениваемые вероятности отправки заданий на обработчики должны быть близки к полученным во второй главе оптимальным значениям. При этом принимается компромиссное решение с критерием, используемым предыдущим методом (минимизация времени пребывания в системе очередного задания).
Сравнение указанных моделей проводилось для различных моделей систем, и наиболее полно был рассмотрен случай системы с двумя обработчиками различной мощности. На рисунке 3 показана зависимость среднего времени пребывания задания в системе в зависимости от интенсивности входного потока . Производительность аппаратов составляла:  , 
Эксперименты показывают, что первый метод даёт наилучшие результаты при большой интенсивности входного потока и проигрывает другим методам при малой. Второй метод, в противоположность первому, даёт наилучшие результаты при малой интенсивности входного потока и заметно проигрывает другим методам при большой. Неоптимальный режим работы возникает в связи с тем, что при достаточно большой входной нагрузке на мощном обработчике образуется очередь, в то время, как слабый простаивает. То есть стремление к локальному оптимуму – минимизации времени пребывания в системе очередного задания – приводит к отдалению от оптимума глобального.
Рисунок 3. Среднее время пребывания заданий в системе для различных методов
Третий метод сочетает в себе лучшие черты первых двух при крайних значениях интенсивности входного потока и заметно опережает их в довольно широкой области средних значений. Кроме того, анализ гистограмм распределения времени пребывания задания в системе показывает, что у третьего метода наиболее короткий «хвост»: начиная с некоторого значения времени, вероятность того, что задание будет пребывать в системе дольше данного времени убывает быстрее, чем у других методов.
Результаты экспериментов с моделями систем с большим количеством обработчиков различной мощности подтверждают все качественные выводы, сделанные для системы с двумя обработчиками.
Четвертая глава посвящена описанию практической реализации распределённых комплексов потоковой обработки речевой информации. А именно, рассмотрена реализация комплекса обработки потока речевых сообщений.
В начале главы перечисляются требования, предъявляемые к комплексу, включающие отказоустойчивость, контроль модулей обработки, требования параллельности доставки заданий на обработчики, возможность учёта приоритета заданий, поддержка различных схем обработки, возможность обновления программных модулей обработки речи.
Далее приводится обзор модулей обработки речи, использовавшихся в реализованных комплексах: транскодер – для декодирования аудиосигнала из различных форматов; модуль детекции и определения качества речи; модуль сегментации диалога на монологи; модуль идентификации дикторов; модуль идентификации языка; модуль выделения ключевых слов.
В разделе кратко описаны общие алгоритмы и особенности функционирования данных модулей. Приведены сравнительные данные по их входным и выходным данным, требованиям по объёму оперативной и дисковой памяти.
Между данными модулями имеется ряд зависимостей, связанных с тем, что некоторые из них используют результаты работы других. Эти зависимости учитывались в схемах обработки.
При решении задачи организации взаимодействия узлов обработки с центральным управляющим сервером были рассмотрены различные подходы (с использованием технологий MPI, CORBA, DCOM). В результате было принято решение об использовании технологии DCOM.
Для реализации взаимодействия прикладных модулей обработки речи с управляющей подсистемой вычислительного узла был использован механизм динамических подключаемых библиотек (DLL). Проведённый анализ особенностей модулей обработки речи показывает, что их входные и выходные данные могут значительно различаться, поэтому интерфейс их подключения должен обладать достаточной общностью. В описываемом решении это достигнуто за счёт применения технологии XML.
Открытость архитектуры достигается за счет унификации интерфейсов всех модулей, хранения промежуточных результатов в XML формате, а также независимой настройки входных и выходных параметров модулей. То есть, под открытостью архитектуры понимается не только заменяемость модулей на аналогичные, но и возможность добавления принципиально новых модулей обработки. Унификация интерфейсов модулей состоит в том, что все модули имеют одинаковые объявления процедур в секции экспорта библиотеки и одинаковые для всех модулей типы формальных параметров этих процедур.
В рамках данного комплекса также был спроектирован и реализован интерфейс пользователя, позволяющий эффективно осуществлять контроль и управление комплексом распределенной обработки. На рисунке 4 показан интерфейс окна «Компьютеры обработчики», которое содержит информацию о подключенных к вычислительному комплексу компьютерах и позволяет удалённо управлять ими.
В заключении четвертой главы приводятся результаты экспериментальных измерений параметров работы комплекса и производится их сравнение с результатами имитационного моделирования.
Рисунок 4 – Общий вид окна «Компьютеры обработчики»
Аппаратная конфигурация комплекса, с которой проводились эксперименты, включала 14 четырёхъядерных промышленных компьютеров и 6 двухпроцессорных BLADE-серверов. По экспериментальным запускам процесса обработки на компьютерах различных типов был сделан вывод о том, что процессорное ядро BLADE-сервера в 1,7 раз менее производительнее ядра 4 х ядерного компьютера. Два компьютера первого типа использовались для управления и обслуживания комплекса, и на них модули обработки речи не запускались. Таким образом, конфигурация системы включала 12 узлов обработки с относительной производительностью 1 и 48 узлов с относительной производительностью 1,7.
Для тестирования работы комплекса использовался набор из порядка 800 файлов, на которых запускались все задачи обработки речи. Схема распределения заданий была реализована в соответствии с методом для расширенной модели, описанным в третьей главе.
В рамках проведения экспериментов, данный пакет файлов подавался на вход в случайном порядке, причём так, чтобы количество заданий в единицу времени соответствовало распределению Пуассона (интервалы между поступлениями заданий соответственно распределены по экспоненциальному закону). Выбирая различные параметры интенсивности входного потока, была получена экспериментальная кривая среднего времени пребывания задания в системе, которая оказалась близка к кривой, полученной путём имитационного моделирования – относительная погрешность не превысила 3%.
Исходя из полученных результатов, в диссертации сделан вывод о том, что разработанный метод распределения заданий является сбалансированным для данной конфигурации в достаточно широких значениях входной нагрузки.
В заключении обобщены итоги и результаты проведенных исследований. Сделан вывод о том, что поставленная научная задача была успешно решена и имеет практическую значимость.
При выполнении диссертационной работы лично автором была предложена модель функционирования гетерогенного распределённого комплекса обработки потоковой информации и в рамках ее исследования разработан для неё метод распределения заданий по обработчикам, минимизирующий среднее время пребывания задания в системе [5, 6, 9-11]; разработана расширенная модель гетерогенного комплекса и соответствующая модификация метода минимизации среднего времени пребывания задания в системе, а также проведено сравнительное имитационное моделирование работы различных методов распределения заданий (глава 3). В рамках реализации программных средств распределённого комплекса обработки мультимедийной информации (глава 4) лично автором была разработана подсистема распределения заданий по обработчикам, интерфейс подключаемых модулей обработки речи, а также пользовательский интерфейс управления и контроля работы комплекса.
|
