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

• Автор: Ярчук, Владимир Федорович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Свердловск
• Количество страниц: 202 c. : ил

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

1. СОСТОЯНИЕ ВОПРОСА ИССЛЕДОВАНИЯ И ПОСТАНОВКА ЗАДАЧИ . .

1.1. Особенности организации вычислительного процесса

на многомашинных ВЦ АСУП

1.1.1. Особенности задач АСУП

1.1.2. Состав и структура многомашинного ВЦ . . .

1.1.3. Дисциплина обслуживания вычислительных

работ на многомашинном ВЦ АСУП.

1.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.3.3. Описание иерархической модели технологий составления статического расписания
2.3.4. Эвристический метод формирования расписания.
2.3.4.1. Технология формирования расписания.
2.3.4.2. Выбор задания .
2.3.4.3. Выбор позиции
2.3.4.4. Выбор альтернатив
2.4. Алгоритмы составления статического расписания .
2.5. Выводы
3. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ ПЛАНИРОВАНИЯ .
3.1. Общие вопросы исследования эффективности эвристических алгоритмов .
3.1.1. Задачи исследования эффективности эвристических алгоритмов .
3.2. Исследование эффективности алгоритма планирования .
3.3. Автоматизация исследования эффективности алгоритма планирования
3.4. Методика исследования и результаты эксперимента . .
3.5. Выводы.
4. АВТОМАТИЗИРОВАННАЯ СИСТЕМА УПРАВЛЕНИЯ ВЫЧИСЛИТЕЛЬНЫМ ПРОЦЕССОМ АСУ ВП НА МНОГОМАШИННОМ ВЦ АСУП.
4.1. Назначение и состав АСУ ВП .
4.2. Подсистема планирования.
4.2.1. Назначение и состав подсистемы
4.2.2. Суточное планирование . А
4.2.2.1. Формирование портфеля заданий .
4.2.2.2. Составление статического расписания А
4.2.3. Долгосрочное планирование 1А
4.2.3.1. Постановка задачи 1А
4.2.3.2. Метод решения задачи . 1А
4.2.3.3. Реализация долгосрочного планирования .
4.3. Структура информационной базы данных ИВД и подсистема ведения ДЦ .
4.4. Подсистема исполнения.
4.5. Подсистема сбора и обработки статистики А
4.6. Выводы А
ЗАКЛЮЧЕНИЕ . . . . Ь
ЛИТЕРАТУРА


ЛПР управляет алгоритмом планирования посредством ранжирования локальных критериев по важности и назначением величины уступки, которые используются при выборе задания и позиции, организованных по методу уступки. Вся информация, необходимая для подсистемы планирования вводится из информационной базы данных АСУ ВП, туда же заносятся результаты планирования. ЛПР судит о качестве плана по оценкам, которые формируются в результате планирования и содержат информацию о временных запасах заданий до директивного срока, загрузке устройств каждой ЭВМ и запланированном количестве перестановок томов внешней памяти. В случае необходимости он может повторить процедуру планирования, изменив содержимое портфеля заданий или несколько изменив стратегию выбора. Рассмотренные алгоритмы объединены в суточное планирование (поскольку интервал планирования ограничен сутками). Помимо суточного предусмотрено выполнение месячного планирования, основная цель которого получить прогноз развития вычислительного процесса на более длительный период времени. Учитывая необходимость регулярного выполнения алгоритмов планирования большое внимание при разработке уделено улучшению их эксплуатационных характеристик. Для этого используются средства, позволяющие управлять ресурсами, требуемыми для планирования [,,, Пб]. Итак, данная диссертационная работа включает введение, четыре главы текста и заключение. Первая глава посвящена рассмотрению состояния вопроса исследования. Она содержит подробное описание особенностей организации вычислительного процесса-на крупных ВЦ АСУП, характеристик задач АСУП, структуры и особенностей функционирования многомашинных ВЦ. Кроме того, в первой главе дан обзор постановок и методов решения задачи планирования вычислительного процесса. Далее излагается содержательная постановка задачи планирования и рассматривается ее формализованное описание, которое включает формализацию результатов планирования, ограничений и критериев задачи. Вторая глава содержит классификацию поставленной задачи, затем рассматривается классификация методов решения комбинаторных оптимизационных задач и на ее основе проводится выбор и обоснование алгоритмов решения задачи формирования статического расписания на многомашинных ВЦ. Третья глава посвящена вопросам исследования разработанных алгоритмов планирования. Она содержит постановку задачи исследования, описание известных подходов и исследование эффективности эвристических алгоритмов, обоснование выбранного метода исследования, а также описание методики и результатов исследования. Кроме того, здесь же представлено описание разработанной системы автоматизации испытаний, которая использовалась в процессе исследования алгоритмов планирования. Заключительная глава посвящена описанию АСУ ВП, в котором центральное место занимает подсистема планирования. Функционирование крупного многомашинного ВЦ представляет собой сложный разносторонний процесс, управление которым связано, в силу сказанного, с большими трудностями. Сложность управления работой ВЦ во многом определяется сложностью организации вычислительного процесса на современных вычислительных машинах [^,, 9,Пб]. С одной стороны, - наличие огромных возможностей по эффективному использованию вычислительных ресурсов, которые обеспечиваются мультипрограммным режимом работы машин третьего поколения, большими объемами оперативной памяти и фактически неограниченной внешней памятью на сменных томах и т. С другой стороны, - сложная организация вычислительного процесса вносит в него дополнительные неопределенности, которые затрудняют выполнение вычислений строго в соответствии с графиком. Сложность управления вычислительным процессом возрастает еще больше, если необходимо реализовать жесткую технологию обработки информации, которая характерна для крупных ВЦ АСУП. Задачами, которые решаются на ВЦ. Составом и структурой технических средств центра. Технологией обработки информации. Поэтому рассмотрим особенности организации вычислительного процесса на многомашинном ВЦ АСУП в указанном порядке.