ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 5, с. 84-94
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 65.012.122
ГРАФОВЫЙ ПОДХОД К НАЗНАЧЕНИЮ ЗАДАНИЙ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ
© 2014 г. А. М. Грузликов, Н. В. Колесов, Ю. М. Скородумов, М. В. Толмачева
Санкт-Петербург, ОАО "Концерн "ЦНИИ "Электроприбор"ГНЦРФ Поступила в редакцию 14.06.13 г., после доработки 07.03.14 г.
Предлагаются и исследуются два эвристических алгоритма назначения заданий на процессоры распределенной системы реального времени. При этом каждое из заданий описывается ориентированным графом достаточно общего вида. Основу первого алгоритма составляет принцип назначения на процессор смежных задач, а второго алгоритма — задач, обмены между которыми наиболее интенсивны. Исследуется эффективность этих алгоритмов в сопоставлении с оптимальным и с использованием случайной генерации примеров. Для каждого из алгоритмов установлена область эффективного применения, определяемая величиной отношения затрат "процессор/канал обмена".
DOI: 10.7868/S0002338814040088
Введение. В настоящей работе под назначением понимается процедура соотнесения с каждым процессором распределенной вычислительной системы некоторого списка решаемых на нем задач. Эта процедура предшествует любым вычислениям в многопроцессорных системах [1, 2]. Иногда в качестве формализации процедуры назначения рассматривается NP-полная (Nonde-terministic Polynomial) задача размещения предметов в контейнерах [1], когда множество предметов, каждый из которых характеризуется некоторым весом, необходимо упаковать в контейнеры ограниченной вместимости. Трактуя предметы как задачи, а контейнеры — как процессоры, приходим к задаче назначения. Обычно задачу о контейнерах интерпретируют как задачу о назначениях при известном числе процессоров и фиксированных директивных сроках [1]. Для решения задачи о контейнерах предложен целый ряд алгоритмов, которые могут быть интерпретированы как решения задачи назначения. Несмотря на привлекательность "контейнерной" формализации проблемы назначения, следует признать, что она не вполне адекватна в случаях, когда рассматриваются зависимые задачи, связанные некоторым отношением предшествования, и необходимо учитывать затраты на реализацию информационных обменов между процессорами. Кроме того, на практике ввиду высокой сложности оптимальных алгоритмов, как правило, отдают предпочтение простым эвристическим алгоритмам. Действительно, в достаточно типичной для практики ситуации, когда число размещаемых задач превышает сотню, применение оптимальных алгоритмов, предполагающих перебор вариантов, оказывается невозможным.
Обычно при разработке процедур назначения используется оптимизационная постановка с критериями, обеспечивающими, например, равномерность загрузки процессоров [3], минимальность необходимого числа процессоров или каналов обмена [2, 4], максимум надежности [5]. Алгоритмы назначения формулируются в рамках различных подходов, среди которых — генетический [6, 7], теория игр [3], графовый [8—10]. Последний подход представлен и в настоящей работе. В его рамках известны как оптимальные, так и эвристические алгоритмы, среди которых — метод бинарного деления, покоординатное деление, рекурсивный метод деления пополам, деление графов с учетом связности [9]. Качество эвристических алгоритмов обычно также оценивается с применением какого-либо выбранного критерия. Существенным классификационным признаком для процедур назначения является предположение (или отсутствие такового) об априорной известности числа используемых процессоров или каналов обмена. Только в этом случае, например, проблема достижения равномерности загрузки процессоров становится содержательной. Наконец, немаловажным свойством известных процедур является тип отношения предшествования для назначаемых задач. Обычно оно представляется в виде цепочки, иерархии или графа общего вида. Далее множество задач, связанных отношением предшествования, будем называть заданиями.
Для систем реального времени [11] при решении задачи назначения дополнительно должно учитываться ограничение, вызванное периодичностью входного потока данных. Это ограничение сказывается следующим образом. В момент появления очередной порции данных вычислительная система должна всегда иметь возможность взять их в обработку. В результате появляется ограничение по загруженности процессора, определяемое его производительностью на периоде Т поступления входной информации. Следует отметить, что широко применяемые при решении задачи назначения генетические алгоритмы [6, 7] в случае систем реального времени снижают свою эффективность из-за появления среди генерируемых вариантов нереализуемых.
Характеризуя в целом известные подходы к решению проблемы назначения, можно определить их как существенно комбинаторные. Под этим подразумевается тот факт, что преобладающее значение для их содержания имеют не математически строго обоснованные процедуры, а некоторые эвристические принципы, дополняемые в той или иной степени направленным перебором вариантов. Организация перебора может основываться на методологии генетического подхода [6, 7], динамического программирования [2], ветвей и границ [12, 13] и некоторых других. В качестве известных принципов можно назвать, например:
1) назначение на один процессор смежных задач, т.е. задач, непосредственно обменивающихся информацией;
2) назначение на один процессор в первую очередь пар задач, информационный обмен между которыми наиболее интенсивен (задачи, принадлежащие разным парам, могут быть не смежными).
Рассматривая решение задачи назначения в сложных системах, следует отметить, что все современные сложные вычислительные системы строятся по иерархическому принципу. В них можно выделить, по крайней мере, три уровня иерархии — процессоры, вычислительные модули, включающие эти процессоры, и сама система. По этой причине и процедуру назначения целесообразно организовывать как, например, двухэтапную — назначение на модули и назначение на процессоры (распределение задач, назначенных на каждый модуль, между его процессорами). Процедуры назначения, используемые на разных этапах, в общих чертах могут совпадать. Различие же этих процедур может определяться обычно имеющими место на практике ограничениями. Так, на первом этапе при назначении заданий на вычислительные модули, производительность которых существенно выше, чем у процессоров, целесообразно на первых шагах назначения на конкретный модуль оперировать целыми заданиями, а не задачами. На последующих же шагах, когда остаточной производительности модуля уже недостаточно для выполнения очередного назначаемого задания, уже оперировать задачами в соответствии с приводимым ниже алгоритмом. Кроме того, на первом этапе могут быть более жесткие ограничения по пропускной способности используемых каналов обмена, что делает целесообразным при оперировании задачами назначать на один и тот же модуль те из них, между которыми осуществляются наиболее интенсивные обмены.
К сожалению, в литературе алгоритмы назначения для систем реального времени представлены в основном переборными алгоритмами (динамическое программирование, метод ветвей и границ и т.п.), характеризующимися высокой вычислительной сложностью. Эти алгоритмы нельзя признать работоспособными как при статическом назначении (назначении на этапе разработки) в случае, когда число задач в рассматриваемых заданиях велико (например, 100 и более), так и при динамическом назначении, например, при восстановлении вычислительной системы после отказа. К существенным недостаткам многих представленных в литературе решений следует отнести отсутствие статистических оценок эффективности описываемых алгоритмов.
В настоящей работе рассматриваются алгоритмы назначения для систем реального времени, представляющие алгоритмическое выражение приведенных выше принципов, а также их комбинации с переборными алгоритмами. Для исследования эффективности алгоритмов предлагается подход, основанный на случайной генерации примеров, приводятся результаты этого исследования, указывающие на области эффективной применимости алгоритмов.
1. Постановка задачи. Будем предполагать, что рассматриваемое множество задач представлено ориентированным информационным графом 0(Л, В), где Л — множество ребер, В — множество вершин, причем вершины соответствуют задачам, а ребра отражают отношение предшествования, существующее между задачами. Граф 0(Л, В) можно охарактеризовать как граф достаточно общего вида. Он может содержать циклы и более одного пути между любыми двумя выделенными вершинами, т.е. не является древообразным. Каждой вершине и каждому ребру графа приписывается некоторый вес. Вес вершины отражает длительность решения соответствующей задачи, а вес ребра — длительность соответствующих информационных обменов.
В общем случае граф 0(Л, В) не является связным и состоит из т компонент связности g = |у = 1, т}, которые в дальнейшем будем называть заданиями, т.е. назначению на процессоры подлежат т независимых заданий т = {т.|у = 1, т}. Каждое задание состоит из задач {т.к\к = 1,т.} (ту- — число задач в у-м задании). Для всех задач известны длительности их исполнения на используемом типе процессора {е.к|у = 1,т, к = 1,т.}. Все процессоры имеют одинаковую производительность, а задачи и задания выполняются с одинаковым периодом Т. Причем за время Тлюбая задача может быть решена на одном процессоре, т.е. е.к < Т, однако все задачи из 0(Л, В) не могут быть решены на одном процессоре, т.е.
что вынуждает применять распределенные вычисления.
В предлагаемых алгоритмах назначения предполагается, что изначально число необходимых вычислительных модулей (процессоров) заранее неизвестно и определяется в процессе назначения. Далее проблема формулируется как поиск среди возможных такого варианта разделения графа на подграфы [8—10], который близок к оптимальному по критерию, представленному взвешенной суммой числа процессоров |Р| и числа каналов обмена |С|:
где а и Ь — весовые коэффициенты, Р — множество использованных процессоров, С — множество использо
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.