ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 2, с. 101-108
== КОМПЬЮТЕРНЫЕ МЕТОДЫ =
УДК 65.012.122
ПЛАНИРОВАНИЕ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА В ИЕРАРХИЧЕСКИХ СИСТЕМАХ
© 2007 г. Н. В. Колесов, М. В. Толмачева
Санкт-Петербург, ГНЦ РФ-ЦНИИ "Электроприбор" Поступила в редакцию 28.02.06 г., после доработки 05.09.06 г.
Рассматривается субоптимальный алгоритм составления расписаний в иерархических вычислительных системах, практически не требующий перебора вариантов. Приводятся результаты исследования его эффективности на основе случайного генерирования примеров.
Введение. Проблеме планирования процесса обработки данных при распределенных вычислениях всегда уделялось достаточно большое внимание [1, 2]. В настоящей работе под планированием вычислений понимается распределение вычислительных ресурсов (времени) между исполняемыми программами [3]. Целый ряд решений, связанных с данной проблемой, предлагается в рамках теории расписаний [4-6]. При этом, как правило, исследуются системы канонического вида - параллельные, последовательные, параллельно-последовательные, последовательно-параллельные. Среди указанных моделей одной из наиболее популярных является конвейерная (последовательная). Известные процедуры поиска оптимальных расписаний для распределенных вычислительных систем характеризуются высокой алгоритмической сложностью, в связи с чем на практике обычно используют приближенные локально-оптимальные алгоритмы или алгоритмы, основанные на эвристиках [7-10].
Авторам работы представляется целесообразным рассмотрение, кроме выше перечисленных, также и класса иерархических систем. Основанием для таких исследований является не только покрытие этим классом семейства конвейерных систем, но и возможность, например, описания в рамках данного класса вычислительных систем, входящих в состав различных информационно-управляющих комплексов специального назначения. Примерами могут служить навигационные комплексы, устанавливаемые на подвижных объектах. Структура таких вычислительных систем может быть весьма разнообразной и характеризоваться связями не всегда иерархического вида (как правило, эти системы строятся на основе магистрального принципа). Однако функциональные связи между программами, реализуемыми на разных ЭВМ системы, по нашему мнению, с достаточной степенью приближения могут быть приняты иерархическими. Необходимо отметить, что для подобных систем рассматриваемые ниже
вопросы упорядочивания исполняемых задач являются лишь частью общей проблемы планирования. Последняя предполагает, в частности, жесткую временную привязку интервалов исполнения этих задач. Дополнительная особенность таких систем - применение статических циклических расписаний, в связи с чем используемое далее в тексте понятие "очередь" имеет определенную долю условности, поскольку в этом случае ожидающие решения задачи не накапливаются в буфере, а резидентно присутствуют в памяти ЭВМ и запускаются в моменты, устанавливаемые неизменным расписанием.
Итак, в статье рассматривается проблема составления расписаний применительно к иерархической вычислительной системе, которая решает некоторую последовательность задач. При этом каждая задача разбита на фрагменты по числу ЭВМ в системе. Предполагаются известными времена исполнения для всех фрагментов каждой из задач. Ниже описывается субоптимальный алгоритм построения расписаний, практически не требующий перебора вариантов.
1. Основные понятия и определения. Обсудим предварительно понятие иерархической системы. На рис. 1, а приведен пример четырехъярусной иерархической системы из восьми ЭВМ. На рисун-
Рис. 1. Примеры иерархических систем: а - иерархическая система общего вида; б - конвейерная система.
ке прямоугольники обозначают ЭВМ, а стрелки -связи между ними. Система на рис. 1, а не имеет циклов и разветвлений, включает четыре входные ЭВМ (1, 3, 4 и 6) и одну выходную (8). Отметим, что конвейерная система является частным случаем иерархической системы, когда любой ярус содержит лишь одну ЭВМ (рис. 1, •).
Каждая входная ЭВМ Ц связана с выходной Ь0 некоторым вычислительным путем (последовательностью ЭВМ) рк = Ц, Ц, ..., Ь0. Назовем величину ррк) временем выполнения вычислительного пути рк на р-й задаче. Определим ее как сумму времен т;, р выполнения фрагментов р-й задачи ЭВМ, принадлежащими этому пути, что с использованием введенной нумерации вдоль пути рк можно записать как
t] (Pk) = Хя j'
г = 1
где тк - число ЭВМ, принадлежащих пути рк.
Заметим, что в общем случае реальное время вычислений на этом пути будет больше из-за необходимости ожидания готовности исходных данных для ЭВМ, входящих в рк, подготавливаемых ЭВМ, которые не принадлежат этому пути.
Назовем вычислительный путь р* критическим для р-й задачи, если время его выполнения максимально среди всех остальных путей системы. Очевидно, что для разных задач, решаемых в одной и той же системе, критические вычислительные пути могут быть различными.
Для любой иерархической системы время ¿н ] начала обработки информации в некоторой ЭВМ Ц определяется временем подготовки для нее всех исходных данных, которые в свою очередь складываются из ряда частных данных, формируемых предшествующими ЭВМ Ьг по каждому г-му информационному входу Ц (так, в примере на рис. 1, а ЭВМ 8 предшествуют ЭВМ 5, 6 и 7). В результате время получения данных для ЭВМ Ь1 является максимальным среди времен, характеризующих конец подготовки частных данных, т.е.
tu j = max {t
r, ]
}.
В свою очередь время ^ подготовки частных данных по некоторому вычислительному пути определяется не только продолжительностью обработки данных в ЭВМ этого пути, но также периодом ожидания данных и временем начала вычислений во входной ЭВМ на рассматриваемом вычислительном пути. Последняя величина имеет в общем случае отличающиеся значения для разных вычислительных путей для любой задачи, кроме первой.
В дальнейшем удобно трактовать понятие "иерархическая система" или просто "система" (обозначим ее через С) как состоящее из двух объектов - иерархии ЭВМ L = {L1, L2, ..., Lm} и множества J = (J1, J2, ..., Jn} решаемых задач, т.е. С = {L, J}. Это связано с вводимым ниже отношением доминирования и основанной на нем классификацией иерархических систем, в которой переплетаются свойства структуры и решаемых задач. Таким образом, будем считать различными две иерархические системы, имеющие одинаковую структуру, но различающиеся множеством решаемых задач.
Выделим три базовых класса иерархических систем, предполагая, что в дальнейшем этот список может быть расширен. Особенность всех рассматриваемых классов - существование характерных упорядоченностей на множестве ЭВМ по определяемому ниже отношению доминирования. Первый класс связан с наличием убывающей упорядоченности, второй - возрастающей, третий - с наличием двух упорядоченностей (возрастающей и убывающей). Введем на множестве ЭВМ отношение доминирования ">".
Определение. ЭВМ Lq доминирует над ЭВМ Lr (Lq > Lr) если
minTq j > maxTr j.
jj
Конкретизируем три базовых класса иерархических систем, предполагая, что для всех классов характерно следующее общее свойство. Если в каждом ярусе системы выделить ЭВМ, максимальную по отношению доминирования, то эти ЭВМ образуют критический путь для любой из решаемых задач.
Класс 1. Множество ЭВМ представляет собой последовательность L1 > L2 > ... > Lm, убывающую по отношению доминирования.
Класс 2. Множество ЭВМ образует последовательность L1 < L2 < ... < Lm, возрастающую по отношению доминирования.
Класс 3. Множество ЭВМ представляет собой пару соединенных последовательностей L1< < L2 < ... < Lh > ... > Lm _ 1 > Lm, 1 < h < m, первая из которых возрастает, а вторая убывает по отношению доминирования.
На рис. 2 приведена иерархическая система, соответствующая классу 3. Отношение доминирования на рисунке показано штриховой линией, а ЭВМ с номерами 1, 2, 5 и 8, являющиеся максимальными элементами ярусов, выделены жирными линиями. Видно, что эти ЭВМ образуют путь, причем он критичен для всех задач системы.
2. Постановка задачи и основная идея предлагаемого алгоритма. Пусть рассматриваемая система С = {L, J} характеризуется иерархией L = {L1, L2, ..., Lm} из m ЭВМ и множеством J = (J1, J2, ..., Jn} из n
m
k
решаемых задач. Каждая задача разбивается на т фрагментов (по числу ЭВМ). При этом ¡-й фрагмент j-й задачи выполняется на г-й ЭВМ за
• 1 • 1 *к ,н ,н
время т¡ j г = 1, т, ] = 1, п и т¡ j = ^ - ^, где ^ и
К . о
- времена начала и конца решения ]-й задачи на ¡-й ЭВМ. Проблема состоит в определении расписания решения задач, которое не существенно проигрывает минимальному расписанию по суммарному времени исполнения всех задач. Заметим, что под минимальным расписанием понимается расписание, характеризующееся минимальным временем решения всех задач.
Для построения интересующего нас расписания предлагается субоптимальный рекурсивный алгоритм (рис. 3), на каждом шаге которого в формируемое расписание включаются одна или две задачи из числа принадлежащих исходному множеству J и не введенных на предыдущих шагах. Эти действия повторяются до исчерпания исходного множества задач. Для размещения задач в расписании на каждом шаге рекурсии используется один из трех частных беспереборных алгоритмов. Каждый из них оптимален по отношению к системам одного из определенных выше базовых классов. В предложенном субоптимальном алгоритме на конкретном шаге рекурсии применяется алгоритм размещения, соответствующий тому из упомянутых классов, к которому наиболее близка рассматриваемая на данном шаге система С = {Ь, У}, где J' - множество неразмещенных задач (У' с У). Ясно, что реальная система, как правило, не принадлежит ни к одному из этих трех классов, а значит, все упомянутые алгоритмы для нее не являются оптимальными.
3. Построение оптимальных расписаний для базовых классов. Покажем теперь, как сконструировать оптимальное расписание в системе из первого класса. При этом характеристики критического пути будем отмечать звездочкой (*).
Алгоритм 1.
Шаг 1. Выделим задачу которая удовлетворяет условию
I-
г = 2
= тл
1г
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.