Содержание к диссертации
Стр.
ВВЕДЕНИЕ 6
1. СОСТОЯНИЕ ВОПРОСА ИССЛЕДОВАНИЯ И ПОСТАНОВКА ЗАДАЧИ . . 18 '
1.1. Особенности организации вычислительного процесса
на многомашинных ВЦ АСУП 18
Особенности задач АСЛІ . 19
Состав и структура многомашинного ВЦ . . . 21
Дисциплина обслуживания вычислительных
работ на многомашинном ВЦ АСУП 25
1.2. Обзор постановок; и методов решения задачи
планирования вычислительного процесса 30
1*3. Содержательная постановка задачи планирования . . 37
1.4. Формализация постановки задачи 44
Формальное описание вычислительного процесса 44
Формальное описание плана 52 «
Формализация ограничений задачи 54
Формализация критериев качества 56
1.5. Выводы 60
2. РЕШЕНИЕ ЗАДАЧИ ФОРМИРОВАНИЯ РАСПИСАНИЯ .' . . 62
Классификация задачи 62
Точные и эвристические методы дискретной оптимизации 63
Иерархическая модель задачи формирования расписания . 65
Методика обоснования метода решения задачи. 65
Классификация эвристических методов решения комбинаторных оптимизационных задач .... 67 '
Описание иерархической модели технологий составления статического расписания .... 69 |
2.3.4. Эвристический метод формирования расписания. 72
Технология формирования расписания. 73
Выбор задания ...... 75
Выбор позиции 78
Выбор альтернатив 79
Алгоритмы составления статического расписания ... 81
Выводы 91
3. ИССЛЕДОВАНИЕ' ЭФФЕКТИВНОСТИ АЛГОРИТМОВ ПЛАНИРОВАНИЯ ... 93
3.1. Общие вопросы исследования эффективности
эвристических алгоритмов . 93
3.I.I. Задачи исследования эффективности
эвристических алгоритмов 94
Исследование эффективности алгоритма планирования . 98
Автоматизация исследования эффективности алгоритма планирования 101
Методика исследования и результаты эксперимента . . 109
Выводы 117
4. АВТОМАТИЗИРОВАННАЯ СИСТЕМА УПРАВЛЕНИЯ ВЫЧИСЛИТЕЛЬНЫМ
ПРОЦЕССОМ (АСУ ВП) НА МНОГОМАШИННОМ ВЦ АСУП 119
Назначение и состав АСУ ВП 119
Подсистема планирования 121
Назначение и состав подсистемы 122
Суточное планирование 124
Формирование портфеля заданий ... 127
Составление статического расписания 134
4.2.3. Долгосрочное планирование 142
Постановка задачи . . . . 442
Метод решения задачи 445
Реализация долгосрочного планирования 4АЬ
Структура информационной базы данных (ИЩ) и подсистема ведения ДЦ 150
Подсистема исполнения 454
Подсистема сбора и обработки статистики ..... 45А
4.6. Выводы . 15^
ЗАКЛЮЧЕНИЕ . . . 15G
ЛИТЕРАТУРА 458
ПРИЛОЖЕНИЯ 471
Введение к работе
В настоящее время сложность управления производством и другими сферами деятельности человека достигла такого уровня, когда нормальное течение сложных производственных процессов, функционирование крупных предприятий возможно только при управлении с привлечением вычислительной техники, т.е. с использованием средств автоматизации управления [37,94,П9_|.
Решение этой задачи предполагает создание крупных вычислительных центров (ВЦ), которые обеспечивают функционирование автоматизированных систем управления производством. Постоянное развитие производства приводит к необходимости совершенствовать методы управления и, тем самым, ставит задачи создания новых, более совершенных АСУ, которые будут функционировать на более высоком уровне, решать задачи управления более крупного масштаба. Решение этой важной проблемы требует дальнейшего совершенствования технического и программного обеспечения ЭВМ, которое позволит повысить производительность ВЦ и благодаря этому удовлетворить возрастающие потребности в вычислениях fl7,96j.
Известны два пути, позволяющие достичь необходимой производительности ВЦ: экстенсивный и интенсивный [вв].
Экстенсивный путь, который получил широкое распространение, заключается в расширении и улучшении технической оснащенности ВЦ. Такой подход не всегда экономически оправдан, так как в конечном итоге приводит к значительному увеличению затрат на эксплуатацию и обслуживание оборудования, что снижает эффективность использования ЭВМ и увеличивает основной показатель функционирования ВЦ -себестоимость обработки информации.
Интенсивный путь предполагает увеличение производительности ВЦ за счет улучшения организации и управления процессом обработки
информации и включает целый комплекс мероприятий, направленных на совершенствование технологии обработки информации, использование средств автоматизации дои планирования процесса решения задач и исполнения полученного плана, развития средств сбора и обработки статистической информации о ходе вычислительного процесса, предоставление ее руководству для осуществления управления ВЦ ^1,2,88, 89,99J. Актуальность такого подхода определяется прежде всего быстрым ростом объемов обрабатываемой информации, усложнением технологии обработки информации и, как следствие, усложнением планирования и управления вычислительным процессом.
В плане управления руководство ВЦ решает целый комплекс задач, которые можно классифицировать следующим образом [88]:
Задачи оперативного управления.
Тактические задачи управления.
Задачи стратегического управления.
Задачи оперативного управления включают планирование вычислительного процесса, контроль за соблюдением технологии обработки информации и графика выполнения вычислений, диспетчирование загрузки ЭВМ работами, обработку нестандартных ситуаций, связанных со сбоями в вычислениях или отказом оборудования [17,46,54,84, 85,93].
При достаточно напряженном графике работы ВЦ решение этих задач без средств автоматизации становится трудновыполнимым, так как в этом случае многое зависит от качества планирования и быстроты реакции системы на любые отклонения от нормального хода вычислительного процесса.
Всслучае наличия жестких технологических требований, которые существуют для задач АСУП и устанавливают последовательность выполнения информационно связанных работ, периодичность и директивные сроки выполнения, значение вышеперечисленных требований еще более возрастает [42,55,62,63,64,65,88J.
Тактические задачи управления включают вопросы совершенствования методов планирования вычислительного процесса, которые обеспечивают наиболее точное соответствие ресурсов ВЦ и потребностей в ресурсах со стороны планируемого портфеля вычислительных работ [53,89].
Стратегическое управление осуществляет выбор направлений развития ВЦ в соответствии с основными целями, которые определяют назначение и требования функционирования ВЦ [*54,8o].
Решение тактических и стратегических задач управления возможно только при наличии детальной информации о вычислительном процессе, которая должна объективно отражать характер функционирования ВЦ, что можно обеспечить автоматизацией сбора, обработки и хранения интересующей информации [2,48,83,92,112].
Наметив основные направления по качественному улучшению организации и планирования вычислительного процесса, рассмотрим их более полно и с большей степенью детализации.
Рассмотрим два принципиально различных варианта управления
["88]:
программное,
позиционное.
Программное управление - статический план вычислительного процесса на произвольный интервал времени, который отражает всю картину выполнения заданий и, благодаря этому, дает возможность оценить предполагаемые сроки подготовки данных, увязать выполнение заданий с профилактическими работами, предусмотреть эффективную загрузку ЭВМ. Программное управление не рассчитано на отказы оборудования и новые заявки на вычисления.
Позиционное управление осуществляется непосредственно при реализации управляемого вычислительного процесса. Поэтому такое управление позволяет учесть отказы и случайные заявки, но, ввиду
отсутствия информации о развитии вычислительного процесса в будущем, не гарантирует, что задания выполнятся в установленные для них директивные сроки. Очевидно, что ни один из описанных способов управления в чистом виде не решает всех проблем управления функционированием ВЦ. Необходимо гибкое сочетание программных и позиционных принципов принятия решений. Поэтому планирование вычислительного процесса должно удовлетворять следующим требованиям:
Учет определяющих вычислительный процесс параметров заданий.
Учет параметров, определяющих возможности технических средств ВЦ (центральный процессор, каналы и устройства ввода-вывода, оперативная память).
Учет номенклатуры и параметров различных типов операционных систем, эксплуатируемых на ВЦ.
Диалоговое формирование портфеля вычислительных работ на плановый период с возможностью учета неформальных требований администратора ВЦ.
Автоматизированное составление статического расписания загрузки технических средств ВЦ.
Диспетчирование при выполнении статического расписания с целью учета случайных факторов.
Портфель вычислительных работ формируется, с одной стороны, исходя из потребностей в вычислениях, и, с другой стороны, в соответствии с возможностями ВЦ. Статическое расписание распределяет работы портфеля по ЭВМ и упорядочивает их выполнение во времени таким образом, чтобы обеспечить каждую работу всеми необходимыми ресурсами и соблюсти все технологические требования [88,89J Автоматизация диспетчирования вычислительных работ должна обеспечить надежный контроль за ходом вычислительного процесса и своевременную реакцию на отклонения от графика вычислений I,89J.
Автоматическое исполнение плана загрузки ЭВМ поможет оператору при выполнении таких функций, как стартирование заданий, контроль их нормального выполнения, контроль исправности ЭВМ [1.89].
Планирование оптимального размещения наборов данных на томах внешней памяти позволит сократить временные затраты на внешние обмены за счет минимизации непроизводительных временных задержек на подвод головок считывающего устройства к нужной записи [l,99J.
Для обеспечения алгоритмов планирования и исполнения необходимой информацией требуется организация автоматизированного сбора, обработки и хранения данных, которые содержат сведения о характеристиках ЭВМ и заданий, используемых томов и наборов данных, а также некоторую другую информацию для руководства ВЦ.
В известных автору разработках, посвященных организации и управлению вычислительным процессом, не решалась задача создания автоматизированной системы управления вычислительным процессом для многомашинного ВЦ, которая решала бы весь комплекс задач управления и учитывала особенности мультипрограммного режима работы ЭВМ. Главными особенностями такого режима являются, с одной 'стороны, большие возможности по эффективному использованию ресурсов ЭВМ и, с другой стороны, сложная организация вычислительного процесса, которая приводит к большим трудностям планирования работы ЭВМ [ 7,10,12,27,57_|. Видимо по этой причине до сих пор задача планирования вычислительного процесса с подбором хороших мультипрограммных смесей заданий, обеспечивающих полную загрузку устройств ЭВМ, не получила исчерпывающего решения.
Рассмотренные аспекты создания автоматизированной системы управления вычислительным процессом позволяют оценить степень сложности и важности решения возникающих здесь проблем. Очевидно, планирование вычислительного процесса должна быть отведена основ-
ная роль. Задача планирования может быть решена сочетанием двух указанных выше подходов к управлению, что сводится к конструирова- т нию алгоритмов составления статического расписания загрузки ЭВМ и оперативному управлению (диспетчирований) процессом выполнения заданий в соответствии с имеющимся расписанием. Предметом данной диссертационной работы является разработка и исследование алгоритмов составления статического расписания многомашинного ВЦ АСУП.
Рассматриваемый вычислительный процесс имеет ряд особенностей, природа которых обусловлена характеристиками ЭВМ и заданий, а также технологией обработки информации [43,I03j.
В общем случае ВЦ состоит из совокупности неоднородных ЭВМ, работающих в мультипрограммном режиме. Неоднородность ЭВМ обусловлена различной архитектурой (составом и конфигурацией связей устройств) и'неодинаковым быстродействием.
ВЦ решает задачи АСУП, которые состоят из непересекающихся подмножеств информационно связанных заданий. Такие задания будем называть плановыми. Каждое плановое задание характеризуется периодом и интервалом решения, а также ресурсами, которые необходимы для его выполнения (время центрального процессора, канала ввода-вывода, объем оперативной памяти, тома, наборы данных, операционная система). Интервал решения определяет диапазон времени, в течение которого задание должно быть выполнено, и может составлять несколько суток. Жесткость сроков выполнения диктуется потребностью в результатах решения задания, которые используются для управления производством. Правую границу интервала решения будем называть директивным сроком выполнения. Кроме того, для планового задания могут быть установлены часы в сутках, когда оно может выполняться. Это ограничение может быть связано, например, с необходимостью сопровождения выполнения задания со стороны программиста.
Кроме плановых заданий, которые полностью отлажены и находятся в промышленной эксплуатации, ВЦ решает отладочные задания (пакеты), выполнение которых не связано требованиями технологии решения задач АСУП. Поэтому для них отсутствуют периоды и интервалы решения, а заявки на выполнение пакетов появляются в случайные моменты времени.
Каждая ЭВМ центра может находиться в рабочем и нерабочем состоянии. Нерабочее состояние может быть обусловлено профилактическими работами, ограниченным ресурсом времени работы или неисправностью ЭВМ. Кроме того, в зависимости от потребностей в решении тех или иных задач на ЭВМ могут быть сгенерированы операционные системы разных типов.
В этих условиях требуется составить статическое расписание загрузки ЭВМ 'заданиями портфеля на планируемый интервал времени. Расписание должно установить для каждого задания позицию (номер ЭВМ и время старта), которая обеспечена всеми ресурсами и удовлетворяет требованиям технологии выполнения данного задания. К тому же, расписание должно обеспечить эффективную загрузку устройств за счет подбора хороших мультипрограммных смесей заданий, а также удовлетворять условиям выживаемости, необходимой для его успешной реализации.
Учет используемых томов приводит к необходимости параллельно с распределением заданий по ЭВМ планировать во времени размещение томов на внешних запоминающих устройствах (ВЗУ), и тем самым обеспечивать задание требуемыми томами. Так как установка и монти \ рование тома порождают достаточно большие дополнительные затраты времени и, кроме того, составляют большую долю труда оператора, целесообразно оценивать качество расписания и по количеству запланированных перестановок томов с одного устройства на другое [1,10
- ІЗ
Противоречивость сформулированных требований к расписанию затрудняет сведение рассматриваемой задачи к однокритериальной задаче дискретной оптимизации и вынуждает рассматривать многокритериальную задачу. Комбинаторность, нелинейность и большая размерность не позволяют воспользоваться точными методами решения, так как в данном случае сложность алгоритма является экспоненциальной [98,I08,II7J. Последнее недопустимо в условиях ограниченных ресурсов, отводимых на решение задачи планирования. Затраты на выполнение алгоритма планирования следует относить к непроизводительным расходам и поэтому существенным является вопрос об эксплуатационных характеристиках планирования. Их значение возрастает еще больше, если предусматривается возможность формирования нескольких расписаний на один и тот же интервал планирования до получения удовлетворительного решения. Качество такого расписания оценивает лицо, принимающее решение (ЛПР), которое с учетом своего опыта планировщика управляет процедурой составления расписания в рамках предоставленных ему возможностей [89,103J.
Из выше изложенного обоснованным выглядит использование для решения поставленной задачи метода, который в процессе конструирования плана позволит отсекать неперспективные направления развития вычислительного процесса с помощью решающих правил, которые формулируются на основе введенных эвристических соображений о "хорошем" и "плохом" решении [lOI,I03,II7j.
Использование эвристического метода для решения той или иной задачи связано с проблемой исследования его эффективности [_101, III, 117,120J, которое предполагает оценку трудоемкости алгоритма, а также качества получаемых решений. Наличие такой проблемы обусловлено тем, что эвристический метод способен обеспечить получение некоторого допустимого решения, оценить близость которого оптимальному решению нелегко, так как не существует регулярного
метода для такой оценки [іОі]. В этой ситуации для исследования алгоритма обычно используют следующие подходы:
Сравнение качества решений испытуемого алгоритма с решением, полученными точными методами. Естественно, что необходимым условием проведения такого сравнения является, во-первых, наличие точного метода решения поставленной задачи и, во-вторых, практическая его реализуемость, которая может отсутствовать в силу трудоемкости решения задачи точным методом или ограниченных ресурсов для исследования.
Сравнение качества решений испытуемого алгоритма с решениями, полученными общеизвестным эвристическим методом, который зарекомендовал себя. Испытуемый алгоритм может найти применение, если обеспечивает более высокую точность решений или обладает меньшей трудоемкостью.
Получение искусственным способом эталонного решения и сравнение с ним решений исследуемого алгоритма.
Для исследования алгоритма планирования использовался последний из рассмотренных подходов. Целью исследования было: оценить качество решений алгоритма планирования, исследовать зависимость качества решений от размерности задачи и устойчивость полученных оценок, а также исследовать зависимость качества решений от количества и номенклатуры учитываемых факторов, которые характеризуют вычислительный процесс. Исходя из целей исследования была разработана методика испытаний алгоритмов планирования.
Для уменьшения объема ручного труда на проведение испытаний был разработан программный комплекс, который позволил автоматизировать испытания.
Для рассматриваемой задачи составления статического расписания были разработаны алгоритмы, которые входят в подсистему планирования автоматизированной системы управления вычислительным
процессом (АСУ ВП). Сопоставление статического расписания выполняется в два этапа.
Во-первых, исходя из характеристик плановых и отладочных заданий, а также возможностей ВЦ формируется портфель заданий на плановый период. Вычислительные ресурсы ВЦ определяются на основе состояния суточного ресурса времени быстродействия и среднестатистического коэффициента мультипрограммирования каждой ЭВМ. Для учета случайных заявок на вычисления, корректировок, возникающих в технологии обработки информации, а также для обеспечения точного соответствия ресурсов ВЦ требуемым ресурсам портфеля заданий ЖР может уточнить состояние, характеристики ЭВМ центра и предварительный портфель заданий, используя средства диалога.
Во-вторых, составляется статическое расписание загрузки ЭВМ заданиями портфеля. Эвристический алгоритм формирует статическое расписание, которое отражает очередность выполнения заданий для каждой ЭВМ с указанием моментов старта и окончания каждого задания, а также номера логического раздела оперативной памяти, в которой данное задание будет загружаться. ЛПР управляет алгоритмом планирования посредством ранжирования локальных критериев по важности и назначением величины уступки, которые используются при выборе задания и позиции, организованных по методу уступки. Вся информация, необходимая для подсистемы планирования вводится из информационной базы данных АСУ ВП, туда же заносятся результаты планирования. ЛПР судит о качестве плана по оценкам, которые формируются в результате планирования и содержат информацию о временных запасах заданий до директивного срока, загрузке устройств каждой ЭВМ и запланированном количестве перестановок томов внешней памяти. В случае необходимости он может повторить процедуру планирования, изменив содержимое портфеля заданий или несколько изменив стратегию выбора. Использование такой обратной связи, ко-
торая позволяет привлечь предыдущий опыт принятия решений, способно существенно повысить эффективность решения поставленной задачи [74,101].
Рассмотренные алгоритмы объединены в суточное планирование (поскольку интервал планирования ограничен сутками). Помимо суточного предусмотрено выполнение месячного планирования, основная цель которого получить прогноз развития вычислительного процесса на более длительный период времени.
Учитывая необходимость регулярного выполнения алгоритмов планирования большое внимание при разработке уделено улучшению их эксплуатационных характеристик. Для этого используются средства, позволяющие управлять ресурсами, требуемыми для планирования [12,27,95, Пб].
Итак, данная диссертационная работа включает введение, четыре главы текста и заключение.
Первая глава посвящена рассмотрению состояния вопроса исследования. Она содержит подробное описание особенностей организации вычислительного процесса- на крупных ВЦ АСУП, характеристик задач АСУЇЇ, структуры и особенностей функционирования многомашинных ВЦ. Кроме того, в первой главе дан обзор постановок и методов решения задачи планирования вычислительного процесса. Далее излагается содержательная постановка задачи планирования и рассматривается ее формализованное описание, которое включает формализацию результатов планирования, ограничений и критериев задачи.
Вторая глава содержит классификацию поставленной задачи, затем рассматривается классификация методов решения комбинаторных оптимизационных задач и на ее основе проводится выбор и обоснование алгоритмов решения задачи формирования статического расписания на многомашинных ВЦ.
Третья глава посвящена вопросам исследования разработанных алгоритмов планирования. Она содержит постановку задачи исследования, описание известных подходов и исследование эффективности эвристических алгоритмов, обоснование выбранного метода исследования, а также описание методики и результатов исследования. Кроме того, здесь же представлено описание разработанной системы автоматизации испытаний, которая использовалась в процессе исследования алгоритмов планирования.
Заключительная глава посвящена описанию АСУ ВП, в котором центральное место занимает подсистема планирования.
Похожие диссертации на Разработка и исследование алгоритмов планирования вычислительного процесса многомашинного вычислительного центра
