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

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

005533793 I 1,

ЧЖО МЬЮ ХТУН

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

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

3 ОКТ 2013

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

Москва 2013

005533793

Работа выполнена на кафедре Вычислительной техники в Национальном исследовательском университете "МИЭТ".

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

Лупин Сергей Андреевич.

Официальные оппоненты

Заведующий кафедрой информатики и программного обеспечения вычислительных систем НИУ «МИЭТ», доктор технических наук, профессор

Гагарина Лариса Геннадьевна кандидат физ.-мат. наук, доцент МАИ

Шебеко Юрий Александрович

Ведущее предприятие

ОАО «НИИ Компонент»

Защита состоится "29_" 40_ 2013 года на заседании

диссертационного совета Д212.134.02 в Национальном исследовательском университете "МИЭТ".

124498, Москва, Зеленоград, проезд 4806, МИЭТ.

С диссертацией можно ознакомиться в библиотеке МИЭТ. Автореферат разослан "?3 " 09_2013 года.

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

д.т.н., доцент Гуреев А.В.

Общая характеристика работы

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

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

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

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

важно повысить эффективность работы PCO и качество обслуживания заявок.

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

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

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

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

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

Для достижения поставленной цели в работе решаются следующие основные задачи:

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

2. Формализация задачи диспетчеризации, как оптимизационной задачи.

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

4. Анализ методов реализации оптимизационных алгоритмов на параллельных платформах.

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

6. Проведение вычислительных экспериментов и анализ эффективности разработанных алгоритмов.

Объект и предмет исследования. Объектом исследования являются процессы управления распределенными системами обслуживания.

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

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

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

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

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

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

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

4. Параллельная реализация случайных алгоритмов оптимизации.

5. Результаты экспериментальных исследований, испытаний и анализ эффективности предложенных алгоритмов.

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

Внедрение результатов. Результаты диссертационной работы используются на кафедре вычислительной техники НИУ «МИЭТ» при чтении лекций по курсам «Высокопроизводительные вычислительные системы» и «Применение высокопроизводительных вычислительных систем в научных исследованиях».

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Всероссийских межвузовских научно-технических конференциях студентов и аспирантов "Микроэлектроника и информатика - 2009, 2010, 2012", МИЭТ; Международной телекоммуникационной конференции молодых ученых и студентов «МОЛОДЕЖЬ И НАУКА». НИЯУ МИФИ, 2012; Всероссийской межвузовской научно-практической конференции молодых ученых, специалистов, преподавателей, аспирантов и студентов "Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем - 2008, 2011", МИЭТ; международных научно-практических конференциях "Информационные технологии, электронные приборы и системы", Минск, 2010; "Современные информационные технологии и ИТ-образование", МГУ, 2010, 2012; "Современные вопросы науки - XXI век", Тамбов, 2011.

Публикации. По материалам диссертации опубликовано 10 тезисов докладов и 15 статей, в том числе 4 в журналах, входящем в перечень ВАК.

Структура и объём диссертационной работы. Рукопись диссертационной работы объемом 141 страница состоит из введения, четырех глав, заключения, приложения и списка литературы.

Содержание работы

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

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

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

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

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

Рис. 1 Диаграмма работы диспетчерской службы

Рис. 2 Диаграмма процедуры приема вызова Формализация процесса диспетчеризации (табл.1) позволяет использовать для синтеза систем управления процессно-ориентированные

модели.

__Таблица 1. Субъекты процесса диспетчеризации

Субъект и события Действие Описание

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

Инцидент Фиксация Любой инцидент фиксируется в ДС

Сигнал тревоги Ввод в систему Данные от системы сигнализации через специальный интерфейс поступают в ДС.

Внешние ДС Вызов Внешние ДС могут передавать информацию в рамках договоров о совместной работе.

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

Внешние службы Перевод вызова Оператор может перевести вызов в специализированную службу.

Группа отчетности Передача вызова Формирует отчет обо всех поступивших вызовах

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

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

Во второй главе рассмотрены алгоритмические подходы к решению задачи диспетчеризации.

Если рассматривать PCO, как замкнутую систему обслуживания без переопределения, то с математической точки зрения задача

диспетчеризации сводится к задаче назначения на узкие места, которую Можно представить в следующем виде:

пусть N — число заявок, поступивших от множества обслуживаемых объектов {¡2};

М - число обслуживающих объектов, составляющих множество {s}', ja. - целевая переменная, равная 1, если j -ый объект используется для обслуживания i -ого вызова и равная 0 в противном случае; r-j - время следования j -ого объекта к источнику i -ой заявки.

Тогда целевая функция системы (1), минимизирующая время реакции, имеет вид:

Trtac, = max(W, V/ = TJwj = Ü?) min (1)

При этом:

¿.у,< l,j = ÜM (2)

Ы1

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

В качестве критериев эффективности PCO может использоваться и некоторый набор временных характеристик:

tdday, время задержки заявки в коммуникационной сети;

tmov, время следования объекта к источнику заявки;

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

При этом интегральная функция, минимизирующая указанные параметры, будет иметь вид (2.3):

(К, хtJehy + Кгхtmov + ts!n) ^min (3)

Коэффициенты КиКг,К3 позволяют варьировать важность отдельных критериев. В случае, невозможности воздействия системы управления на один из них, соответствующий коэффициент будет равен 0. Так, если мы не можем влиять на время прохождения заявки от источника к диспетчеру, то Kt = 0, а элементы матрицы R будут соответствовать (4) и, кроме времени движения обработчика к объекту, характеризуют и возможность выполнения объектом своей функции по отношению к источнику заявки:

r = (K2xt„10V + K,xtxn) (4)

В этом случае минимизируя Тпас1 (1), мы оптимизируем не только

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

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

Точные алгоритмы: метод ветвей и границ; перебор всех возможных вариантов решений.

Детерминированные алгоритмы: последовательные алгоритмы; итерационные алгоритмы.

Случайные алгоритмы: метод случайного поиска; итерационные алгоритмы.

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

количество одновременно обслуживаемых заявок в реальных системах обычно не превышает 100;

время анализа ситуации и принятия решения не должно превышать интервала между поступлением заявок*

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

В качестве исходных данных итерационные алгоритмы используют заданное начальное распределение в виде матрицы Р(лй .

Рассмотрим два варианта стратегий, основанные на градиенте целевой функции.

Вариант, реализующий стратегию плавного спуска (рис.3), определяет направление минимума градиента целевой функции 7 . На

каждом шаге работы алгоритма определяется пара элементов р, и р]

матрицы РШ1, перестановка которых даст минимальное улучшение целевой функции.

Вариант, реализующий стратегию наискорейшего спуска, определяет направление максимума градиента целевой функции Тгеас1. На каждом

шаге работы алгоритма определяется пара элементов р,- и р) матрицы

Р,',„у . перестановка которых даст максимальное улучшение целевой функции.

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

Рассмотрим последовательность шагов алгоритма, реализующего подобную стратегию (рис.4):

1. Пусть задано начальное распределение в виде матрицы Р/га,. Найдем

2.

/,„,, для этого распределения. Получим пару случайных чисел

^ и ГГ2,

местами элементы рщ и Рщ в векторе Р;т, и получим вектор

Найдем значение функционала Т Т < Т.., то Ты. = Т" и Р,„, = Р".

IV, * Я/2. Поменяем Р".

для распределения Р . Если

/п/7 ' ~ тп * " Л :п11

3. Повторим шаг 2 заданное число раз.

Решением задачи будет последний вариант, запомненный на шаге 2.

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

Рис. 4 Итерационный случайный алгоритм

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

Последовательность шагов алгоритма, реализующего случайный поиск:

1. Пусть задано начальное распределение в виде матрицы РШ1. Найдем

Тм, для этого распределения.

2. С помощью генератора случайных чисел получим новую матрицу Р" с неповторяющимися элементами. Найдем значение функционала Т" для распределения Р". Если Т < Тш, то Тш, = Т и Р,Я|7 = Р .

3. Повторим шаг 2 заданное число раз.

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

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

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

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

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

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

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

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

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

С помощью Intel Parallel Studio проведен анализ переносимости ресурсоемких алгоритмов дискретной оптимизации, используемых для решения задачи распределения заявок, который подтвердил, что они обладают хорошей масштабируемостью и могут быть реализованы как многопоточные приложения (рис. 6 и 7).

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

I Locks and Wails

Jl •[ • : ;; sris««.'.!-*.: -шщ^в/шшт.

Pi -юл«*«*!.» ._ _ _

¡1 <|№ |pw |oi|t«: |on |

listtraMiilif^vMtf-E'-? . |

' I—' " '' " '

IMSSKWlMM iff 9s

Sj^...................."i_____________________;_______

затопкам «ж

.SteraMiiajl Is ||||?ам!пМ1|г^й Os

Gowi j

¡¡isstitnOTifcg '¡I flows

'!..........................L.

¡¡ШийЧзН.к! ils

MTlTetiHii!ion;S*iOSfi( '

]и|р:1|л|а„|йг м-

0! MJ'j

0000 s j i -ОКО:

Os 1 OKOs

0000s ) i Ш-

[ -jja-; жч

Щни'сг

0000s 0s

- (f ftv

: ■ям!

'.■ж®: м» на ч:» vanisch- ";;,: г;:;3! Silt I .izOJi LK 1.Й _

- • лг: :: f. : .

fiiti i.'tiL^:

isp

Рис. 6 Эффективность параллельной реализации случайного итерационного алгоритма

:! t|to::|p-«iOi8ll11:|Dl|lt[B.1,n»B<'lRo«

:.....................■ ' ' /ч-fal ' \шКч> Щ.

- I • 02Г<г8 ' I

;ia=it'£=rrD; ;issafdrK t.1i&*

■jffiSliip Or*

ООЭ7Ш5 0.1*1«

5:5977ГА

ьшг

MVjre 0} Ш&спММегспсв

Hit Р:а» ft «и O.H

jwirs tits ore ere

-З.ОКгз У-$ O^s Ore Cms

JOnTS 0-5 Ore 0ms

CfS -OKl-fc -22S0:*5: Ore

■аз'зг« ore are

te tos Ons

у X r:lil- ' 7 >•'

SiilCsut .. i: :1J-; l

IsgtSOttlifed:. tSC:'"-19i tKBtiOUTae: ХЗНг ¿3»i

CwCwt ThjwC'ei

=r=

Рис. 7 Эффективность параллельной реализации алгоритма случайного поиска

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

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

В качестве тестовых с помощью генератора случайных чисел были созданы различные задачи с размерностью N = 5 + 24 . Обслуживающие элементы {s} и заявки {q} распределены по Полю размером 500*300 дискрет.

Точное решение для тестовых задач с размерностью N < 15 было найдено с помощью алгоритма перебора, а для большей размерности с помощью алгоритма линейного назначения, описанного выше. Для задачи размерностью N = 18 оно составило 141, а для N=24 равно 151.

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

Таблица 2. Точность алгоритма при N = 24

rp mit * read »r» rezuh read Число результативных итераций Точность решения (%)

стратегия плавного спуска

478 151 46 100

441 151 45 100

429 151 59 100

470 151 61 100

429 151 40 100

стратегия наискорейшего спуска

446 151 18 J 100

473 151 19 100

474 151 18 100

498 151 14 100

450 151 16 100

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

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

Таблица 3. Зависимость точности решения от числа итераций Л' = 18

Число итераций Время реакции системы

Эксперименты Среднее Последовательная реализация

1 2 3 4 5 значение

104 189 178 176 155 177 175 185.4

5* 104 155 170 177 146 166 162.8 171.8

105 167 166 150 141 162 157.2 167.2

5*105 152 148 141 146 144 146.2 164.6

10б 141 150 146 146 141 144.8 151.8

5*106 141 141 141 141 141 141 141

107 141 141 141 141 141 141 141

Таблица 4. Быстродействие алгоритма N = 18

Число итераций Время решения задачи (сек)

Эксперименты Среднее значение Последовательная реализация

1 2 3 4 5

1о< 0.06 0.07 0.06 0.06 0.07 0.064 0.12

5*104 0.09 0.09 0.09 0.09 0.08 0.088 0.214

105 0.11 0.12 0.12 0.11 0.12 0.116 0.351

5*105 0.31 0.32 0.33 0.36 0.32 0.328 1.378

106 0.56 0.59 0.59 0.58 0.58 0.58 2.688

5 * 106 2.61 2.65 2.71 2.75 2.84 2.712 12.97

107 6.13 5.41 5.54 5.83 5.15 5.612 25.85

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

Алгоритм случайного поиска был также реализован в последовательной и параллельной версиях. Сравнительные результаты приведены в табл. 5 и 6.

Таблица 5. Зависимость точности решения от числа итераций N = 18

Время реакции системы

Число итераций Эксперименты Среднее значение Последовательн

1 2 3 4 5 реализация

104 189 177 178 180 176 180 191

5*10" 167 155 170 167 162 164 173.4

105 146 162 169 153 142 154 161

5*105 141 146 143 146 141 143 149.8

106 141 143 143 143 143 142 152.4

5 * 106 143 143 141 141 141 141 142

107 141 141 143 141 143 141 141

Таблица 6. Быстродействие алгоритма// = 18

Число итераций Время решения задачи (сек)

Эксперименты Среднее значение Последователи

1 2 3 4 5 реализация

104 0.11 0.13 0.11 0.13 0.12 0.12 0.56

5*104 0.44 0.36 0.37 0.38 0.43 0.40 2.42

105 0.67 0.69 0.73 0.68 0.75 0.70 4.79

5* 105 3.21 3.21 3.13 3.17 3.17 3.18 24.26

106 6.22 6.24 9.18 6.93 9.21 7.56 49.93

5*106 31.4 31.02 31.9 31.3 33.2 31.76 239.34

107 64.1 65.4 64.1 63.9 64.4 64.38 477.63

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

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

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

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

В заключении приведены основные результаты работы.

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

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

2. С математической точки зрения задача диспетчеризации сводится к задаче назначения на узкие места, для решения которой используются методы дискретной оптимизации. Метод ветвей и

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

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

ограниченное время.

4. Эффективное использование многоядерных процессоров и ускорителей возможно только в случае реализации на них многопоточных приложений. Среди различных инструментов разработки параллельных приложений для МЯВС следует отметить Intel Parallel Studio, который позволяет автоматизировать процесс перевода последовательных реализаций приложений на параллельную платформу. Проведенный с помощью IPS анализ переносимости ресурсоемких алгоритмов дискретной оптимизации, используемых для решения задачи распределения заявок, подтвердил, что они обладают хорошей масштабируемостью и могут быть реализованы как многопоточные приложения.

5. Результаты проведенных вычислительных экспериментов позволили оценить практическую эффективность различных алгоритмов оптимизации при решении задачи диспетчеризации в PCO. Точные переборные алгоритмы могут быть использованы для оценки свойств других алгоритмов, а также при невысокой размерности задачи (N < 8 ). Детерминированные градиентные алгоритмы оптимизации можно использовать в СППР без ограничения размерности задачи в том случае, когда точность решения не является критическим требованием к системе управления. Параллельные реализации итерационных алгоритмов, использующих рандомизацию при поиске решения, способны обеспечить высокую точность ответа за ограниченное время и могут служить основой для СППР.

Публикации автора по теме диссертации:

1. Чжо Мью Хтун. Оценка состояния распределенной системы обслуживания. //Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем. Вторая всероссийская межвузовская научно-практическая конференция: Материалы конференции. -М.: МИЭТ, 2008. - 188с., С. 155.

2. Чжо Мью Хтун. Приближенный алгоритм решения задачи распределения заявок. //Микроэлектроника и информатика - 2009. 16-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. - М.: МИЭТ, 2009. - 372с„ С. 226.

3. Чжо Мью Хтун. Использование метода ветвей и границ для решения задачи распределения нагрузки. //Микроэлектроника и информатика - 2010. 17-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. - М.: МИЭТ, 2010. - 352с., С. 228.

4. Лупин С.А., Мью Мьинт Ту, Чжо Мью Хтун. К вопросу о реализуемости методов динамической структурной оптимизации распределенных систем облуживания на параллельных вычислителях. //Информационные технологии, электронные приборы и системы: Материалы Международной научно-практической конференции. Минск, 6-7 апреля 2010 г. В 3-х частях. Ч. 1 -Минск: БГУ, 2010. - 161с., С. 84-87.'

5. Тан Шейн, Тхан Зо У, Чжо Мью Хтун, Лупин С.А. Динамическая структурная оптимизация распределенных систем обслуживания на многопроцессорных системах. //V Международная научно-практическая конференция «Современные информационные технологии и ИТ-образавание». Сборник избранных трудов МГУ, 2010. - 640с., С. 621-625.

6. Чжо Мью Хтун. Количественная оценка состояния распределенных систем обслуживания. //Международная научная школа «Микроэлектронные информационно-управляющие системы и комплексы». Материалы научной школы. -М.: МИЭТ, 2010. С. 114.

7. Чжо Мью Хтун. Параллельная реализация алгоритма случайного поиска при решении задачи назначения на узкие места. //Актуальные вопросы современной техники и технологии. Сборник докладов Ш-й Международной научной заочной конференции (Липецк, 29 января 2011 г.). В 2-х ч. Ч. I. / Под ред. A.B. Горбенко, C.B. Довженко. - Липецк: Издательский центр «Гравис», 2011. - 112 е., С.67-69.

8. Чжо Мью Хтун. Исследование эффективности алгоритмов решения задачи диспетчеризации. //Современная техника и технологии: исследования и разработки. Сборник докладов Международной научной заочной конференции (Липецк, 23 июля 2011 г.). / Отв. ред. A.B.

Горбенко. - Липецк: Издательский центр «Гравис», 2011. - 136 е., С 4042.

9. Чжо Мью Хтун. Итерационный алгоритм для распределения заявок в системах обслуживания. //Современные вопросы науки - XXI век: сб. науч. тр. по материалам Междунар. науч.-практ. конф. 27 июня 2011 г.: в 2 частях. Часть 2; М-во обр. и науки РФ. Тамбов: Изд-во ТРОО «Бизнес-Наука-Общество», 2011.-143 е., С. 135-136.

10. Чжо Мью Хтун, Сай Вин Мо. Итерационный алгоритм решения задачи назначения на узкие места при низком значении градиента целевой функции. //Актуальные проблемы информатизации в науке, образовании и экономике - 2011г. 4-я Всероссийская межвузовская научно-практическая конференция. М.: М: МИЭТ, 2011. - 196 е., С. 112.

11. Чжо Мью Хтун, Сое Мое Аунг. Эффективность итерационного алгоритма решения задачи назначения на узкие места при высоком значении градиента целевой функции. //Актуальные проблемы информатизации в науке, образовании и экономике - 2011г 4-я Всероссийская межвузовская научно-практическая конференция. М.: М:

МИЭТ, 2011.-196 е., С. 113.

12. Чжо Мью Хтун, Сай Вин Мо, Сое Мое Аунг. Эффективность итерационных алгоритмов при решении задачи назначения на узкие места XV Международная телекоммуникационная конференция молодых ученых и студентов «МОЛОДЕЖЬ И НАУКА». Тезисы докладов. В 3-х частях. Ч. 3. М.: НИЯУ МИФИ, 2012. - 204с„ С. 129-130.

13. Лупин С.А., Сай Вин Мо, Чжо Мью Хтун. Параллельная реализация итерационного алгоритма решения задачи назначения на узкие места. //Актуальные научные вопросы: реальность и перспективы: Сборник научных трудов по материалам Международной заочной научно-практической конференции 26 декабря 2011 г.: в 7 частях. Часть 1; М-во образования и науки Рос. Федерации. Тамбов: Изд-во ТРОО «Бизнес-Наука-Общество», 2012. - 163 е., С. 96-98.

14. Лупин С.А., Чжо Мью Хтун, Сое Мое Аунг. Сравнительный анализ последовательной и параллельной реализаций алгоритма случайного поиска. //Актуальные научные вопросы: реальность и перспективы: Сборник научных трудов по материалам Международной заочной научно-практической конференции 26 декабря 2011 г.: в 7 частях. Часть 1; М-во образования и науки Рос. Федерации. Тамбов: Изд-во ТРОО «Бизнес-Наука-Общество», 2012. - 163с., С. 98-100.

15. Чжо Мью Хтун. Параллельная реализация алгоритма случайного поиска. //Проблемы разработки информационных технологий и подготовки ИТ-кадров: Сборник научных трудов /Под ред. Л.Г.Гагариной. -М.: МИЭТ, 2012. - 168 е., С. 148-153.

16. Сай Вин Mo, Сое Мое Аунг, Чжо Мью Хтун. Анализ эффективности параллельной реализации случайных алгоритмов. //Теоретические и прикладные проблемы науки и образования в 21 веке: Сборник научных трудов по материалам Международной заочной научно-практической конференции 31 января 2012 г.: в 10 частях. Часть 1; Мин. образования и науки Рос. Федерации. Тамбов: Изд-во ТРОО «Бизнес-Наука-Общество», 2012. - 163с., С. 118-119.

17. Чжо Мью Хтун, Сай Вин Мо, Сое Мое Аунг. Многопоточная реализация итерационных алгоритмов оптимизации. //Современные вопросы науки и образования -XXI век: Сборник научных трудов по материалам Международной заочной научно-практической конференции 29 февраля 2012 г.: в 7 частях. Часть 1; Мин. образования и науки Рос. Федерации. Тамбов: Изд-во ТРОО «Бизнес-Наука-Общество», 2012 -164с., С.159-160.

18. Чжо Мью Хтун, Сай Вин Мо. Учебная многопоточная программа для вычисления числа п. //Микроэлектроника и информатика -2012. 19-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. - М.: МИЭТ, 2012. - 324с., С. 193.

19. Лупин С.А, Тхан Зо У, Чжо Мью Хтун. Применение алгоритмов случайного поиска для решения задачи диспетчеризации в распределенных системах обслуживания. //Известия ВУЗов: Электроника. - М.: МИЭТ, 2012, №3, 100с., С. 40-46. (перечень ВАК)

20. Лупин С.А, Тан Шейн, Тхан Зо У, Чжо Мью Хтун. К вопросу оценки точности алгоритмов дискретной оптимизации. // Проблемы разработки перспективных микро- и наноэлектронных систем - 2012. Сборник трудов / под общ. Ред. академика РАН А.Л. Стемпковского - М • ИППМ РАН, 2012. - 735 е., С. 553-556. (перечень ВАК)

21. Лупин С.А, Тхан Зо У, Чжо Мью Хтун. Методы отображения данных при управлении распределенными системами обслуживания. //Информационные системы и технологии. №4(72), 2012, С.92-96. (перечень ВАК)

22. Лупин С.А, Чжо Мью Хтун. О применимости итерационного алгоритма для распределения нагрузки в системах обслуживания. //Информационные системы и технологии. №5(73), 2012, С. 114-119. (перечень ВАК)

23. Чжо Мью Хтун, Чжо Чжо Лин. Точность итерационного алгоритма решения задачи распределения нагрузки в системах обслуживания. // Сборник избранных трудов VII Международной научно-практической конференции. Под ред. проф. В.А. Сухомлина. - М • ИНТУИТ.РУ, 2012. - 1050с. -ISBN 978-5-9556-0140-3, С.958-962.

24. Лупин С.А., Чжо Мью Хтун, Тан Шейн. Параллельная реализация алгоритмов дискретной оптимизации. // Сборник избранных трудов VII Международной научно-практической конференции. Под ред. проф. В.А. Сухомлина. - М.: ИНТУИТ.РУ, 2012. - 1050с. -ISBN 978-5-9556-0140-3, С.912-918.

Формат 60x84 1/16. Уч.-изд. л. *,2.Тираж ¿Оэкз. Заказ №-S4

Отпечатано в типографии ИПК МИЭТ.

124498, Москва, Зеленоград, проезд 4806, д.5, МИЭТ

Министерство образования и науки Российской Федерации Национальный исследовательский университет «МИЭТ»

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

04201362465

ЧЖО МЬЮ ХТУН

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

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

(в приборостроении)

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

Научный руководитель: к.т.н., профессор Лупин Сергей Андреевич

у

Москва-2013

Обозначения и сокращения...............................................................................................................5

Введение..............................................................................................................................................6

ГЛАВА 1. ДИСПЕТЧЕРИЗАЦИЯ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ ОБСЛУЖИВАНИЯ..........................................................................................................................12

1.1 Структура и функции распределенных систем обслуживания...................................12

1.2 Представление PCO как системы массового обслуживания.......................................13

1.3 Диспетчеризация заявок в системах обслуживания.....................................................14

1.4 Задачи диспетчеризации в коммунальном хозяйстве...................................................16

1.5 Диспетчеризация на транспорте.....................................................................................18

1.6 Централизация управления PCO.....................................................................................19

1.7 Распределение функций управления в иерархических PCO........................................23

1.8 Автоматизированные диспетчерские системы..............................................................25

1.8.1 Диспетчерское управление в системе AwareNess..............................................28

1.9 Выводы....................................................................................................................................29

ГЛАВА 2. АЛГОРИТМИЧЕСКИЕ ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧИ ДИСПЕТЧЕРИЗАЦИИ....................................................................................................................31

2.1 Постановка задачи диспетчеризации.............................................................................32

2.2 Точные алгоритмы...........................................................................................................34

2.2.1 Метод ветвей и границ.........................................................................................34

2.2.2 Метод полного перебора вариантов решений....................................................36

2.2.3 Линейное назначение............................................................................................36

2.3 Детерминированные алгоритмы......................................................................................37

2.3.1 Последовательные алгоритмы.............................................................................37

2.3.2 Детерминированные итерационные алгоритмы................................................39

2.4 Случайные алгоритмы......................................................................................................41

2.4.1 Случайные итерационные алгоритмы................................................................41

2.4.2 Алгоритм случайного поиска..............................................................................42

2.5 Параллельная реализация алгоритмов...........................................................................44

2.5.1 Параллельные итерации.......................................................................................44

2.6 Выводы..............................................................................................................................49

ГЛАВА 3. ОСОБЕННОСТИ ПОСТРОЕНИЯ ПРОГРАММНО-АППАРАТНЫХ КОМПЛЕКСОВ ДЛЯ ДИСПЕТЧЕРСКИХ СИСТЕМ..................................................................50

3.1 Особенности многоядерных архитектур.......................................................................50

3.1.1 Технология гиперпоточности..............................................................................53

3.1.2 Перспективные многоядерные ускорители........................................................55

3.2 Методы создания параллельных программ...................................................................61

3.2.1 Ручное распараллеливание...................................................................................62

3.2.2 Полуавтоматическое распараллеливание...........................................................65

3.2.3 Автоматическое распараллеливание...................................................................65

3.2.4 Многопоточное программирование....................................................................66

3.2.5 Библиотека ОрепМР.............................................................................................67

3.2.6 Библиотека MPI.....................................................................................................70

3.3 Среда Intel Parallel Studio и ее функциональный состав..............................................71

3.3.1 Утилита Intel Parallel Advisor...............................................................................73

3.3.2 Утилита Intel Parallel Composer...........................................................................74

3.3.3 Утилита Intel Parallel Inspector.............................................................................75

3.3.4 Утилита Intel Parallel Amplifier............................................................................75

3.4 Оценка реализуемости алгоритмов в параллельной среде..........................................76

3.4.1 Анализ случайного итерационного алгоритма..................................................76

3.4.2 Анализ алгоритма случайного поиска................................................................82

3.5 Выводы....................................................................................................................................86

ГЛАВА 4. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ И

ИСПЫТАНИЙ..................................................................................................................................88

4.1 Последовательные реализации алгоритмов..................................................................88

4.1.1 Тестовые задачи....................................................................................................88

4.1.2 Последовательный алгоритм...............................................................................88

4.1.3 Детерминированные итерационные алгоритмы................................................90

4.1.4 Случайные алгоритмы........................................................................................103

4.1.4.1 Итерационный случайный алгоритм..................................................103

4.1.4.2 Алгоритм случайного поиска...............................................................108

4.2 Параллельные реализации алгоритмов........................................................................113

4.2.1 Итерационный случайный алгоритм.................................................................113

4.2.2 Алгоритм случайного поиска............................................................................118

4.3 Выводы............................................................................................................................123

Заключение..................................................................................................................................124

Публикации автора по теме диссертации....................................................................................126

Список литературы.........................................................................................................................131

Приложения. Условия тестовых задач.........................................................................................135

Обозначения и сокращения

ЛИР Лицо, принимающее решение

мяв с Многоядерные вычислительные системы

ОУ Объект управления

по Программное обеспечение

PCO Распределенная система обслуживания

СП11Р Система поддержки принятия решений

СУ Система управления

чс Чрезвычайная ситуация

GPU Graphic Processor Unit

IPS Intel Parallel Studio

MIC Many Integrated Cores

Введение

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

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

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

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

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

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

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

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

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

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

Для достижения поставленной цели в работе решаются следующие основные задачи:

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

2. Формализация задачи диспетчеризации, как оптимизационной задачи.

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

4. Анализ методов реализации оптимизационных алгоритмов на параллельных платформах.

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

6. Проведение вычислительных экспериментов и анализ эффективности разработанных алгоритмов.

Объект и предмет исследования. Объектом исследования являются процессы управления распределенными системами обслуживания.

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

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

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

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

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

Внедрение результатов. Результаты диссертационной работы используются на кафедре вычислительной техники МИЭТ при проведении лабораторных работ по курсу «Высокопроизводительные вычислительные системы».

На защиту выносятся следующие положения:

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

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

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

4. Параллельная реализация случайных алгоритмов оптимизации.

5. Результаты экспериментальных исследований, испытаний и анализ эффективности предложенных алгоритмов.

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

1. Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем. Вторая всероссийская межвузовская научно-практическая конференция. МИЭТ, 2008

2. Микроэлектроника и информатика - 2009. 16-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИЭТ

3. Микроэлектроника и информатика - 2010. 17-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИЭТ

4. Информационные технологии, электронные приборы и системы. Международная научно-практическая конференция. Минск, 2010.

5. V Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование». МГУ, 2010.

6. Современные вопросы науки - XXI век. Международная научно-практическая конференция. Тамбов, 2011.

7. Актуальные проблемы информатизации в науке, образовании и экономике. 4-я Всероссийская межвузовская научно-практическая конференция. МИЭТ, 2011.

8. XV Международная телекоммуникационная конференция молодых ученых и студентов «МОЛОДЕЖЬ И НАУКА». НИЯУ МИФИ, 2012.

9. Микроэлектроника и информатика - 2012. 19-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИЭТ, 2012.

10. VII Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование». МГУ, 2012.

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

Структура и объём диссертационной работы. Рукопись диссертационной работы, общим объемом 141 страница, состоит из введения, четырех глав, заключения, списка литературы и приложения.

ГЛАВА 1. ДИСПЕТЧЕРИЗАЦИЯ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ ОБСЛУЖИВАНИЯ

1.1 Структура и функции распределенных систем обслуживания

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

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

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

- служба скорой помощи,

- служба пожарной безопасности,

- служба охраны общественного порядка,

- Министерства по чрезвычайным ситуациям (МЧС).

Для достижения основной цели своего существования - выполнения поступающих заявок — распределенная система должна удовлетворять некоторым необходимым требованиям [1.1]:

Открытость - взаимодействие элементов внутри распределенной системы должны быть основаны на общедоступных стандартах.

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

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

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

Безопасность - данные, перед�