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

• Автор: Ефимов, Александр Владимирович
• Шифр специальности: 05.13.15
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Новосибирск
• Количество страниц: 123 с. : ил.

СОДЕРЖАНИЕ
ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ
ВВЕДЕНИЕ
ГЛАВА 1 ОСНОВЫ ОРГАНИЗАЦИИ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЁННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
1.1 Понятие о распределённых вычислительных системах
1.1 Л Модель коллектива вычислителей
1.1.2 Классификация архитектур вычислительных систем
1.1.3 Функциональная организация распределённых ВС
1.2 Основные режимы функционирования ВС
1.2.1 Монопрограммный режим
1.2.2 Мультипрограммный режим
1.3 Классификация задач
1.4 Формирование расписания обработки наборов масштабируемых задач
на распределённых вычислительных системах
1.4.1 Задача формирования расписаний
1.4.2 Обзор методов и алгоритмов формирования расписаний
1.4.3 Методы кодирования расписаний
1.4.4 Обзор средств планирования
1.5 Выводы
ГЛАВА 2 АЛГОРИТМЫ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЁННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ В РЕЖИМЕ ОБРАБОТКИ НАБОРА МАСШТАБИРУЕМЫХ ЗАДАЧ
2.1 Методы решения
2.2 Выбор параметров масштабируемых задач
2.3 Формирование укрупненных задач с целью минимизации времени решения задач набора
2.3.1 Стохастический алгоритм
2.3.2 Генетический алгоритм
2.4 Многокритериальная оптимизация формирования укрупненных задач
2.4.1 Последовательный генетический алгоритм с кроссинговером перетасовки генов
2.4.2 Параллельный генетический алгоритм с кроссинговером перетасовки генов
2.5 Формирование последовательности решения укрупнённых задач с целью минимизации штрафа за задержку их решения
2.6 Формирование итогового расписания решения масштабируемых задач
на распределенных ВС
2.7 Моделирование алгоритмов формирования расписаний решения
задач на распределённых вычислительных системах
2.8 Выводы
ГЛАВА 3 ПРОСТРАНСТВЕННО РАСПРЕДЕЛЕННАЯ
ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
3.1 Архитектура пространственно-распределенной мультикластерной вычислительной системы
3.2 Программное обеспечение пространственно-распределённой мультикластерной вычислительной системы
3.2.1 Стандартные компоненты
3.2.2 Пакет МОГОБ поддержки мультипрограммных режимов обработки наборов масштабируемых задач
3.2.2 Интерфейс с системами пакетной обработки заданий
3.3 Выводы
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЯ
Приложение 1 Сводная таблица алгоритмов
Приложение 2 Структурная организация сегментов мультикластерной
вычислительной системы
Приложение 3 Исходные тексты программ

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ
АЛУ - арифметико-логическое устройство.
БИС - большая интегральная схема.
ВМ - вычислительный модуль.
ВС - вычислительная система.
ИФП СО РАН - Федеральное государственное бюджетное учреждение науки Институт физики полупроводников им. А.В. Ржанова Сибирского отделения Российской академии наук.
ЛК - локальный коммутатор.
ЛИ - локальная память.
МКМД - Множественный поток команд и множественный поток данных. МКОД - Множественный поток команд и одиночный поток данных.
НИР - Научно-Исследовательская работа.
ОКМД - Одиночный поток команд и множественный поток данных.
ОКОД - Одиночный поток команд и одиночный поток данных.
ОС - операционная система.
ПК - персональный компьютер.
ПО - программное обеспечение.
СО АН СССР - Сибирское отделение Академии наук Союза Советских Социалистических Республик.
СУ - системное устройство.
ФГОБУ ВПО “СибГУТИ” - Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования “Сибирский государственный университет телекоммуникаций и информатики”. ЦПВТ - Центр параллельных вычислительных технологий.
ЭВМ - электронная вычислительная машина.
ЭМ - элементарная машина.
ЭИ - элементарный процессор.
API - Application Programming Interface.

ных формах для формирования расписаний [149]. Данные методы привязаны к целевой функции и специфике ограничений на формирование расписания.
Метод ограниченного перебора осуществляет поиск в дереве возможных решений, составленном на основании зависимостей между задачами. Изменение ограничений в переборных методах требует модификации алгоритма, приводящего ветви дерева в согласованное состояние. К тому же, в крупных задачах дерево может приобрести слишком большой размер. Эвристические методы также широко используются при решении задач планирования [100]. В этом случае эвристики трактуются как правила планирования. В работе [153] приводится обзор ряда эвристик для задач планирования. В [124] сравниваются восемь эвристик на множестве однотипных задач формирования ресурсозависимых расписаний. Ресурсно зависимым является расписание, которое формируется для задач, решение которых невозможно на ресурсах отличных от заданных. В [125] сравниваются алгоритмы, основанные на эвристиках, с алгоритмами, основанными на методе ограниченного перебора. Результаты сравнения показали, что алгоритмы, основанные на эвристиках, плохо приспособлены для ситуаций, в которых ресурсы сильно ограничены. Применению эвристических правил в алгоритмах планирования посвящены публикации [140, 153]. Находят применение методы решения задач планирования, использующие экспертные оценки и основанные на знаниях (knowledge-based) системы [135, 141]. Каждый набор экспертных правил детально прорабатывается под ту или иную задачу, поэтому алгоритмы данной группы являются узкоспециализированными. Системы, основанные на знаниях, обычно делят задачу на подзадачи, решением которых занимаются подпрограммы-агенты. Вопросы динамического планирования, когда расписание может быть сформирование повторно уже после начала решения задачи, рассматриваются в работе [14]. Также ведутся