Планирование вычислений. Синтез надежных планов. Оптимизация при планировании вычислений. Контрольная работа ОТА. Муромский институт (филиал)
 Скачать 94 Kb.
|
 Министерство образования и науки РФ Муромский институт (филиал) федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Владимирский Государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых» (МИ(филиал)ВлГУ) Факультет ИТ Кафедра ИС КОНТРОЛЬНАЯ РАБОТА по ОТА . Тема Планирование вычислений. Синтез надежных планов. Оптимизация при планировании вычислений. Руководитель Савичева С. В. (фамилия, инициалы) (подпись) (дата) Студент ИСз-111 (группа) Чернов А.О. (фамилия, инициалы) (подпись) (дата) Муром 2014 Оглавление 1. Введение 3 2. Задача совместного планирования вычислений и обменов 4 3. Известные алгоритмы, проблемы их применения и возможные подходы к решению задачи 6 4. Алгоритм совместного построения совместимых расписания выполнения работ передачи сообщений 9 5. Экспериментальное исследование 11 6. Заключение 12 7. Список литературы 13 Введение Одним из важнейших требований к функционированию информационно–управляющих систем реального времени (ИУС РВ) является соблюдение директивных сроков выполнения прикладных программ. При нарушении директивных сроков, ИУС РВ теряет свою работоспособность. При разработке и отладке прикладного программного обеспечения для каждой версии программного обеспечения ИУС РВ необходимо строить расписание выполнения прикладных программ и расписание обмена данными для проверки возможности выполнения ограничений реального времени. При построении расписаний необходимо учитывать технологические ограничения ИУС РВ, обусловленные особенностями используемых аппаратных и системных программных средств. Приведенная в работе задача совместного планирования вычислений и обменов возникает при модификации ИУС РВ (например, при добавлении новых подсистем), а также при разработке новых ИУС РВ на базе существующих. В данной статье задача совместного планирования вычислений и обменов рассматривается для ИУС РВ, в которой в качестве среды обмена используется канал с централизованным управлением. К основным особенностям задачи можно отнести: в качестве исходных данных задаются набор прикладных программ, подлежащих планированию, и набор сообщений, посредством которых прикладные программы взаимодействуют друг с другом и подсистемами, изменение которых недопустимо; время передачи сообщения зависит от расписания выполнения прикладных программ; присутствуют технологические ограничения на корректность расписания обменов, а не только ограничения на передачу каждого сообщения в рамках его директивного интервала. В работе приведена математическая постановка задачи, рассмотрены основные особенности задачи, отличающие её от других задач построения расписаний, проведен анализ возможных подходов к построению алгоритмов решения сформулированной задачи, предложен алгоритм, основанный на жадных стратегиях, и приведены результаты его численного исследования. Задача совместного планирования вычислений и обменов. В данной главе введем понятия расписания выполнения работ и расписания передачи сообщений, сформулируем условия корректности расписаний и условия их совместимости, приведем математическую постановку задачи совместного планирования вычислений и обменов. Исходными данными для задачи совместного планирования вычислений и обменов являются набор прикладных программ (работ) и набор сообщений, посредством передачи и приема которых работы взаимодействуют друг с другом и подсистемами. Для каждой работы задан директивный интервал, в рамках которого она должна быть выполнена, и набор вычислительных модулей, на которые работа может быть размещена. Для каждого сообщения задан директивный интервал, в рамках которого оно должно быть передано. Прерывание выполнения работ и передачи сообщений недопустимо. ИУС РВ рассматривается как система, состоящая из набора вычислительных модулей и подсистем, подключенных к единой среде передачи данных. Каждая подсистема может быть представлена как набор работ (в дальнейшем работы-подсистемы), исполняющихся на отдельном вычислительном модуле, на который недопустимо назначение работ из исходного набора. Для множества работ-подсистем известно расписание. Задача совместного планирования вычислений и обменов заключается в построении согласованных статических расписаний выполнения исходно заданных работ и обменов. Модель набора работ и сообщений, подлежащих планированию. Исходный набор работ и сообщений будем представлять ориентированным ациклическим графом (возможно, несвязным) с двумя типами вершин G=(WUM, p). Первый тип вершин соответствует работам (в том числе работам-подсистемам), второй – сообщениям. Дугами графа задаётся частичный порядок на множествах работ и сообщений. Пример графа приведен на рисунке. Квадратами отмечены вершины-работы, кругами –вершины-сообщения. Дополнительно вершины, соответствующие работам-подсистемам, отмечены пунктиром. Работы-подсистемы не подлежат планированию, но участвуют в передаче сообщений наряду с другими работами. Каждая вершина-сообщение передаёт данные от вершины-работы, являющейся её предшественником, вершинам-работам, являющимся её преемниками. Если у вершины-работы среди предшественников есть вершины-работы (как, например, вершины-работы 4 – 6), то все они вместе с исходной вершиной-работой должны быть запланированы на один и тот же вычислительный модуль, а обмен данными происходит через внутреннюю память этого модуля. При этом каждой вершине-сообщению инцидентны ровно одна входящая дуга и не менее одной исходящей дуги. Другими словами мы предполагаем, что данные, передаваемые в сообщении, формируются специальной работой, которая может брать слова данных от других работ, выполняющихся на этом же вычислительном модуле. Такой способ используется во многих ИУС РВ, в которых есть каналы с централизованным управлением. Обозначим через P={I,.....np} множество вычислительных модулей, W={I,....i....nw}– множество работ из исходно заданного набора, которые подлежат планированию, M={I,...i....nm}– множество всех сообщений. Для каждой вершины-работы из множества W известны: is – директивный срок начала выполнения работы (должно начаться не раньше этого срока); if – директивный срок завершения выполнения работы (должно завершиться до наступления этого срока); Pi⊆ – набор вычислительных модулей, на которые допустимо назначение этой работы для выполнения. Также известна функция dw:W*P→N, определяющая длительность выполнения заданной работы на заданном вычислительном модуле. Здесь и далее Ν обозначает множество натуральных чисел. Аналогично для каждой вершины-сообщения из множества M известны: js – директивный срок начала передачи сообщения; jf – директивный срок завершения передачи сообщения; Если среди предшественников или преемников вершины-сообщения есть работы из множества W , то длительность передачи сообщения зависит от того, на какие вычислительные модули эти работы будут назначены. Более того, если все предшественники и преемники вершины-сообщения будут запланированы на один вычислительный модуль, то сообщение вообще не требуется передавать по среде передачи данных. В состав исходных данных входит функция, позволяющая определить длительность передачи сообщения, однако формальное её представление будет введено ниже, так как требует введения понятия привязки работ к вычислительным модулям. Расписание выполнения работ. Расписание представляет собой множество троек вида <работа, номер вычислительного модуля на котором выполняется работы планируемое время старта работы. Промежуток времени будем называть интервалом выполнения работы i . Для простоты, когда известно (или не важно), о каком расписании работ идёт речь, будем обозначать длительность выполнения работы i в нём как dw. Известные алгоритмы, проблемы их применения и возможные подходы к решению задачи. В данном разделе обсуждаются две известные из литературы близкие задачи и алгоритмы их решения, а также четыре возможных подхода к построению алгоритмов решения рассматриваемой задачи. Под близкими задачами мы понимаем задачи, для которых набор работ, подлежащий планированию, содержит работы двух типов: работы-задачи и работы-сообщения. В [1] рассматривается следующая задача1. Заданы набор периодических заданий и набор вычислительных узлов системы. На размещение заданий на вычислительные узлы могут быть наложены такие ограничения, как: два задания должны быть размещены на один и тот же узел; два задания должны быть размещены на разные узлы; задание может быть размещено только на узлы из некоторого подмножества всех узлов системы. Каждое задание состоит из модулей, минимальных единиц планирования. На множестве модулей одного задания может быть определено отношение предшествования. Модули бывают двух типов: вычислительные и коммуникационные. Время выполнения вычислительного модуля зависит от узла, на который он назначен. Каждому коммуникационному модулю соответствует партнёр по коммуникации – коммуникационный модуль другого задания. Время выполнения коммуникационного модуля Mj зависит от того, на какой узел назначен. 1 Описание сходных задач будет вестись в терминах, принятых в статьях, описывающих эти задачи. партнёр, и равно local je, если партнёр выполняется на том же узле (локальная коммуникация), и remote je, если на другом (удаленная коммуникация), причем remote local. Временные задержки (например, на передачу служебных слов) при передаче сообщения между коммуникационными модулями Mi и Mj, выполняющимися на разных узлах системы, фиксированы и заданы. Отношение времени, которое прошло от директивного срока начала задания до завершения выполнения задания, к длительности директивного срока называется нормализованным временем отклика. В [1] ставится задача нахождения расписания, в котором минимизируется максимум нормализованного времени отклика, взятый по всем заданиям и зависящий от конкретного размещения модулей заданий по узлам системы. Напомним, что в понятие расписания также включается размещение заданий по вычислительным узлам. Алгоритм решения основан на методе ветвей и границ. Дерево поиска состоит из частичных или полных расписаний. У каждой вершины ровно столько потомков, сколько вычислительных узлов в системе. Если считать, что задано для планирования m заданий, то на уровне k дерева поиска запланировано ровно k заданий (корень считается вершиной уровня 0). Вершины уровня m представляет собой полные расписания – кандидаты в решения задачи. Вершины, в которых нарушены ограничения на размещение заданий по узлам, отбрасываются сразу же без вычисления значения критерия. В [1] предложен алгоритм оценки нижней границы значения критерия оптимальности расписания в вершине, имеющий сложность O(nM2), где n – количество вычислительных узлов, M – общее количество модулей. При использовании описанных выше результатов применительно к решению рассматриваемой в данной статье задачи логично отождествить вычислительные модули заданий из [1] с работами, а пары коммуникационных модулей – с сообщениями. Основные отличия задачи из [1], которые препятствуют её использованию, следующие: 1) у каждого сообщения может быть только один получатель; 2) нет ограничений на расписание сообщений в целом (технологических ограничений); 3) в среде передачи данных отсутствуют конфликты, два и более сообщения могут передаваться одновременно; 4) другой критерий оптимальности расписания. Учет этих различий будет означать построение нового алгоритма, основанного на методе ветвей и границ без использования результатов [1]. В [2] рассматривается набор периодических работ, который должен быть запланирован на набор вычислительных модулей. Работы взаимодействуют путем отправки сообщений. Каждое сообщение отправляется с минимальной частотой двух взаимодействующих работ. Для сообщений не вводится директивных сроков, но есть ограничение сверху на время между началом выполнения передающей работы и концом выполнения принимающей работы. В этот интервал должно передаться сообщение. Время на передачу каждого сообщения фиксировано. В каждый момент времени по среде может передаваться только одно сообщение. Допускаются циклические зависимости между работами. Например, экземпляр работы A шлет сообщение экземпляру работы B, который шлет сообщение следующему экземпляру работы A, и т.д. В [2] решается задача нахождения расписания, минимизирующего суммарные нарушения временных ограничений (в том числе нарушения директивных сроков). Алгоритм совместного построения совместимых расписания выполнения работ передачи сообщений. Предлагаемый алгоритм является жадным и относится к классу конструктивных алгоритмов, которые на каждом шаге достраивают частичное расписание, добавляя в него работы и сообщения. Главная проблема построения конструктивных алгоритмов – следующая особенность задачи: точная длительность передачи сообщения становится известной только после планирования (а точнее, привязки к вычислительным модулям) работ, получающих данное сообщение. Вместе с тем для любого неполного (и полного тоже) расписания можно вычислить минимальное и максимальное возможные значения времени передачи сообщения. Предлагаемый подход состоит в том, что длительность передачи сообщения считается равной максимально возможной (для данного сообщения при возможно неполной привязке работ на момент планирования). После размещения в расписание каждой работы просматриваются ранее запланированные сообщения на предмет изменения расчетной длительности передачи. На каждой итерации выбор очередной работы или сообщения для планирования происходит только среди тех, для которых уже запланированы все предшественники. В процессе работы алгоритма ведётся список работ и сообщений, которые алгоритм не может запланировать, а также упорядоченный список PL, хранящий порядок, в котором работы или сообщения добавлялись в расписание. Ниже приведена укрупненная схема одной итерации алгоритма, в которой отражены принцип построения и основные особенности алгоритма. Детальная схема алгоритма с выделением основных операций и описанием алгоритмов их выполнения приведена в Приложении. Перед началом каждой итерации известно текущее неполное расписание. В результате выполнения итерации получается расписание, содержащее дополнительную работу или сообщение, или становится известна точная длительность передачи ранее запланированного сообщения. Одна итерация алгоритма может быть представлена следующей схемой. 1. Вычисление с учетом текущего расписания минимально возможного времени размещения сообщения на канале и минимально возможных времен размещения работ на вычислительных модулях, вычисленные значения составляют список: одно значение для каждого модуля и одно значение для среды передачи данных. Критерий может быть многоуровневым. Если по одному из критериев работы и/или сообщения не различаются, то можно сравнить их по-другому. Среди этих критериев нет универсального или такого, который для общей задачи дает лучший результат, чем любой другой. Для каждого критерия есть своя область эффективного применения. Например, широкую область применения имеет критерий «минимальный директивный срок завершения». Но он неприменим для задач с единым директивным сроком для всех работ и сообщений. Следующий пример иллюстрирует случай, когда критерий «минимальное раннее время завершения» показывает лучше результат, чем критерий «минимальный директивный срок завершения». Характеристики пяти работ приведены в табл. 1, в системе два процессора. При использовании критерия «минимальный директивный срок завершения» запланированы будут только первые две работы (на разные процессоры), три другие не смогут быть выполнены в рамках своих директивных сроков. При использовании же критерия «минимальное раннее время завершения» запланированы будут третья, четвертая и пятая работы. Полное расписание все равно не будет построено, но с точки зрения критерия оптимальности расписания такое решение будет лучше. Экспериментальное исследование. Для исследования алгоритма было случайным образом составлено три комплекта наборов исходных данных, для которых возможно построение полного расписания. В состав всех наборов входит 300 работ, 100 сообщений и четыре процессора одинаковой производительности. Длительность выполнения каждой работы лежит на отрезке от 500 до 1500 мс. Количество слов данных в каждом сообщении лежит на отрезке от 1 до 32 (длительность передачи – от 104 до 724 мс). Длительность интервала планирования равна 500000 мс. Характеристики среды обмена следующие: 5000=mctr мс, 10=mccr и 500=mirмс. В первом комплекте исходных данных отношение длительности работы или сообщения к длительности директивного интервала равно 0.1, во втором – 0.5, в третьем – 0.8. Для каждого набора исходных данных осуществлялось два запуска алгоритма с разными жадными эвристиками – минимальный директивный срок завершения (колонка EDF) и минимальное раннее время завершения (колонка ETF). Результаты представлены в табл. 2, в которой w – количество запланированных работ; m – количество запланированных сообщений; t – время работы алгоритма (процессор – Core2Duo 3ГГц); r – количество выполнений пункта 6.3 схемы итерации алгоритма (количество «возвратов»); n – количество добавлений работ и сообщений в расписание, из-за наличия возвратов составления расписания это число может превосходить суммарное количество работ и сообщений. Величина n может являться мерой вычислительной сложности алгоритма на том или ином наборе исходных данных. Индексы min, max и avg указывают соответственно на минимальное, максимальное и среднее значение для комплекта наборов исходных данных. Проведенные исследования показывают, что из двух выбранных жадных критериев лучшие результаты показывает критерий «минимальный директивный срок завершения». При этом при уменьшении длительности директивных интервалов результаты применения каждого из критериев ухудшаются. Это связано с тем, что при применении этих эвристик не делается обоснованный выбор процессора, на который размещается очередная работа. Полученные данные позволяют утверждать, что критерий «минимальный директивный срок завершения» пригоден для частных задач со средним отношением времен выполнения к длительности директивных интервалов меньшим 0.1 и не пригоден для частных задач с большим значением отношения. Заключение. В данной работе была сформулирована задача совместного планирования вычислений и обменов, возникающая при проектировании информационно–управляющих распределенных систем реального времени. Описаны основные её особенности, отличающие её от других задач построения расписаний. Были рассмотрены две известные из литературы близкие постановки задач и методы их решения. Для первой алгоритм решения основывается на методе ветвей и границ, для второй – на методе имитации отжига. Показаны отличия от рассматриваемой задачи совместного планирования, препятствующие непосредственному применению алгоритмов из этих работ. Среди таких отличий для обеих работ можно назвать наличие у сообщений только одного получателя и отсутствие поддержки ограничений корректности на все расписание сообщений (технологических ограничений). Таким образом, показано, что требуется разработка новых алгоритмов для решения рассматриваемой задачи совместного планирования вычислений и обменов. Далее были рассмотрены возможные подходы к построению алгоритмов и проанализированы сложности, возникающие при их применении. Выделены два подхода, допускающие построение алгоритмов, которые принципиально не исключают возможность нахождения алгоритмом оптимального решения для любой индивидуальной задачи: 1)подход, основанный на рассмотрении сообщений как своеобразных работ, а среды передачи данных – как процессора с технологическими ограничениями, 2)подход, основанный на идеях метода критического пути. В последних двух разделах был описан разработанный в рамках первого подхода жадный алгоритм решения поставленной задачи и проведено его экспериментальное исследование. Список литературы. 1. Peng D.-T., Shin K. G., Abdelzaher T. F. Assignment and scheduling of communicating periodic tasks in distributed real-time systems // IEEE Trans. Software Engineering. 1997. V.23(12). P. 745–758. 2. Cheng S., Agrawala A. Allocation and scheduling of real-time periodic tasks with relative timing constraints // Proc. Second Intern. Workshop on Real-Time Computing Systems and Applications. Tokyo, Japan. 1995. 3. Теория расписаний и вычислительные машины / Под ред. Э.Г. Коффмана. М.: Наука, 1984. 334 с. 4. Liu C. L., Layland J. W. Scheduling algorithms for multiprogramming in a hard-real-time environment // J. ACM. 1973. V.20(1). P. 46–61. 5. Костенко В.А., Гурьянов Е.С. Алгоритм построения расписаний обменов по шине с централизованным управлением и исследование его эффективности // Программирование. 2005. №6. С. 340-346. |