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

• Автор: Чжо Мью Хтун
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 142 с. : ил.

Обозначения и сокращения
Введение
ГЛАВА 1. ДИСПЕТЧЕРИЗАЦИЯ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ ОБСЛУЖИВАНИЯ
1.1 Структура и функции распределенных систем обслуживания
1.2 Представление РСО как системы массового обслуживания
1.3 Диспетчеризация заявок в системах обслуживания
1.4 Задачи диспетчеризации в коммунальном хозяйстве
1.5 Диспетчеризация на транспорте
1.6 Централизация управления РСО
1.7 Распределение функций управления в иерархических РСО
1.8 Автоматизированные диспетчерские системы
1.8.1 Диспетчерское управление в системе AwareNess
1.9 Выводы
ГЛАВА 2. АЛГОРИТМИЧЕСКИЕ ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧИ ДИСПЕТЧЕРИЗАЦИИ
2.1 Постановка задачи диспетчеризации
2.2 Точные алгоритмы
2.2.1 Метод ветвей и границ
2.2.2 Метод полного перебора вариантов решений
2.2.3 Линейное назначение
2.3 Детерминированные алгоритмы
2.3.1 Последовательные алгоритмы
2.3.2 Детерминированные итерационные алгоритмы
2.4 Случайные алгоритмы
2.4.1 Случайные итерационные алгоритмы

2.4.2 Алгоритм случайного поиска
2.5 Параллельная реализация алгоритмов
2.5.1 Параллельные итерации
2.6 Выводы
ГЛАВА 3. ОСОБЕННОСТИ ПОСТРОЕНИЯ ПРОГРАММНО-АППАРАТНЫХ КОМПЛЕКСОВ ДЛЯ ДИСПЕТЧЕРСКИХ СИСТЕМ
3.1 Особенности многоядерных архитектур
3.1.1 Т ехнология гиперпоточности
3.1.2 Перспективные многоядерные ускорители
3.2 Методы создания параллельных программ
3.2.1 Ручное распараллеливание
3.2.2 Полуавтоматическое распараллеливание
3.2.3 Автоматическое распараллеливание
3.2.4 Многопоточное программирование
3.2.5 Библиотека ОрепМР
3.2.6 Библиотека MPI
3.3 Среда Intel Parallel Studio и ее функциональный состав
3.3.1 Утилита Intel Parallel Advisor
3.3.2 Утилита Intel Parallel Composer
3.3.3 Утилита Intel Parallel Inspector
3.3.4 Утилита Intel Parallel Amplifier
3.4 Оценка реализуемости алгоритмов в параллельной среде
3.4.1 Анализ случайного итерационного алгоритма
3.4.2 Анализ алгоритма случайного поиска
3.5 Выводы

ГЛАВА 4. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ И ИСПЫТАНИЙ
4.1 Последовательные реализации алгоритмов
4.1 Л Тестовые задачи
4Л .2 Последовательный алгоритм
4.1.3 Детерминированные итерационные алгоритмы
4.1.4 Случайные алгоритмы
4.1.4.1 Итерационный случайный алгоритм
4.1.4.2 Алгоритм случайного поиска
4.2 Параллельные реализации алгоритмов
4.2.1 Итерационный случайный алгоритм
4.2.2 Алгоритм случайного поиска
4.3 Выводы
Заключение
Публикации автора по теме диссертации
Список литературы
Приложения. Условия тестовых задач

Если задана матрица II, то в качестве оптимистической оценки Оор1 для выражения (2.1) при М=Л^используем:
основе порождающей оценки верхнего уровня О следующим образом: заменим в матрице К элемент г] на00 ;
Оценка Ог включения элемента ги в решение формируется на основе

порождающей оценки верхнего уровня Оир следующим образом: заменим в матрице К строку I и столбец /на ;
Оценки 2.5-2.7 позволяют использовать метод ветвей и границ для решения задачи диспетчеризации. С точки зрения практического использования в системах управления РСО этот метод не представляет интереса, поскольку обладает низким быстродействием, которое невозможно повысить распараллеливанием.
Оор1 = max(min( гу, V/ = 1, N), V/ = 1, N)
(2.5)
Оценка 0Г] не включения элемента /т в решение формируется на
найдем
ML - min(/^., V/ = 1, N) MC = min(^., Vz = ,N) .

Oup, если Oup > max(WC, Ml) max(MCME), если Oup (2.6)
найдем
°,est = max(inin(r,;, V/ = 1,N), V/ = 1,N) .
(2.7)