Статья: Выполнение заданий в вычислительных системах реального времени

ОАО «Концерн «Центральный научно-исследовательский институт «Электроприбор»

Выполнение заданий в вычислительных системах реального времени

Ю.М. Скородумов

В настоящей работе вводится понятие задания как совокупности задач, связанных отношением предшествования, и проблема формулируется как назначение на процессоры распределенной системы множества независимых заданий. Фактически проблема сводится к оптимальному (рациональному) размещению набора заданий с учетом их отношений предшествования и периодичности потока входных данных на достаточном количестве процессоров. Предложен алгоритм назначения для распределенной системы реального времени. Исследована эффективность этого алгоритма с использованием случайной генерации примеров.

вычислительный алгоритм реальный поток

Введение

В настоящей работе под назначением понимается процедура соотнесения с каждым процессором некоторого списка решаемых на нем задач. Эта процедура предшествует любым вычислениям в многопроцессорных системах. Обычно при разработке таких процедур используется оптимизационная постановка с критериями, обеспечивающими, например, равномерность загрузки процессоров или минимальность необходимого числа процессоров или каналов обмена [1 - 5]. Для систем реального времени при решении задачи назначения дополнительно должно учитываться ограничение, вызванное периодичностью входного потока данных. Это ограничение сказывается следующим образом. В момент появления очередной порции данных вычислительная система должна всегда иметь возможность взять их в обработку. В настоящей работе предлагаются: алгоритм назначения для систем реального времени, подход к исследованию эффективности алгоритма назначения, а также приводятся результаты этого исследования.

Обычно в качестве формализации процедуры назначения рассматривается NP-полная (Nondeterministic Polynomial) задача размещения предметов в контейнерах [1], когда множество предметов, каждый из которых характеризуется некоторым весом, необходимо упаковать в контейнеры ограниченной вместимости. Трактуя предметы как задачи, а контейнеры как процессоры, приходим к задаче назначения. Обычно задачу о контейнерах интерпретируют как задачу о назначениях при известном числе процессоров и фиксированных директивных сроках. Для решения задачи о контейнерах предложен целый ряд алгоритмов, которые могут быть интерпретированы как решения задачи назначения. Причем на практике ввиду высокой сложности оптимальных алгоритмов зачастую отдают предпочтение простым эвристическим алгоритмам [1], среди которых, например, назначение на первый подходящий процессор (процессор, при назначении на который директивный срок не нарушается) или на первый подходящий при предварительном упорядочивании задач по невозрастанию их длительностей, или на лучший из подходящих процессоров с точки зрения минимума неиспользованного времени после назначения, в том числе и с учетом предварительного упорядочивания задач. Этот ряд можно продолжить алгоритмом, ориентированным на достижение загрузки процессоров, близкой к равномерной, когда назначение производится на процессор с максимальным неиспользованным временем.

Несмотря на привлекательность «контейнерной» формализации проблемы назначения, следует признать, что она не вполне адекватна при рассмотрении систем реального времени. Это наиболее очевидно в случаях, когда рассматриваются зависимые задачи, связанные некоторым отношением предшествования, и необходимо учитывать затраты на реализацию информационных обменов между процессорами. Именно эта ситуация будет рассматриваться далее.

Постановка задачи

Предположим, что рассматриваемое множество задач разбито на независимые группы связанных между собой задач (далее задания).

Итак, назначению на процессоры подлежат m независимых заданий , обрабатывающих входные данные, поступающие с периодом T. Все процессоры имеют одинаковую производительность. Для рассматриваемого алгоритма важным условием является наличие ограничения по производительности для используемых процессоров, выражающееся неравенствами: ( - время решения j-го задания на одном процессоре). В результате любое задание не может быть реализовано на одном процессоре за время T, что вынуждает использовать распределенные вычисления. При этом возможны два варианта организации вычислительного процесса, которые условно назовем «конвейерным» и «неконвейерным».

Конвейерная организация. Каждый из процессоров, исполняющих задание, исполняет не всё задание, а только некоторую его часть. На диаграмме вычислительного процесса при конвейерной организации, представленной на рис. 1 а, показан один из наиболее простых вариантов, когда используются три процессора p1, p2, p3, образующие конвейер, и каждый из процессоров реализует лишь одну из трех задач, составляющих задание. Процессоры обмениваются результатами решения задач. Причем длительность решения задачи должна быть не больше периода поступления

входных данных . В противном случае процесс решения задачи выходит по времени за пределы периода T, т.е. система начинает работать не в реальном времени. Можно представить ситуацию, когда на конвейере решается не одно задание, а больше. При этом суммарное время решения всех задач одной стадии не должно превышать Т.

Неконвейерная организация - процессор решает всё задание от начала до конца. На рис. 1, б показано использование трех процессоров с одинаковым программным обеспечением (программным обеспечением всех стадий). В этом случае нет обменов между процессорами. Через период для обработки очередной порции входных данных включается второй процессор. Еще через период - третий, потом опять первый и т.д. Таким образом, предполагается, что все процессоры имеют доступ к входным данным. При этом выходные данные выдаются с разных процессоров.

Примем для дальнейшего рассмотрения конвейерный вариант как более удобный в реализации. Это, конечно, не означает, что все анализируемые ниже системы имеют идеализированную структуру примера на рис. 1, а. Для них лишь характерно, что выполняемое задание разбивается на части, реализуемые на разных процессорах. При этом будем предполагать, что задачи любого задания связаны иерархическим отношением предшествования, что характерно для систем реального времени. В результате задания можно представить ориентированными древообразными графами, где вершины - это задачи, а ребра - отражают отношение предшествования. При этом проблему назначения удобно формализовать как проблему разрезания графа на подграфы. В этом случае каждой вершине и каждому ребру приписывается некоторый вес. Вес вершины отражает длительность решения соответствующей задачи, а вес ребра - длительность соответствующих информационных обменов. Задача может быть сформулирована как разделение графа на минимальное число подграфов, суммарный вес вершин каждого из которых не превосходит заданной величины (допустимой загруженности процессора), либо как разделение графа на заданное число подграфов, для которых суммарный вес соединяющих ребер минимален. Для решения подобных задач известны как оптимальные, так и эвристические алгоритмы, среди которых метод бинарного деления, покоординатное деление, рекурсивный метод деления пополам, деление графов с учетом связности [5].

Опишем алгоритм назначения, который по существу соответствует распространенному на практике упрощенному подходу к назначению задач, основанному на принципе: «каждой задаче - свой процессор». В данном случае формула несколько меняется: «каждому заданию - свои процессоры». Фактически проблема сводится к оптимальному (рациональному) размещению одного задания с учетом отношения предшествования и периодичности потока входных данных на достаточном количестве процессоров.

Итак, будем предполагать, что каждое задание предварительно надлежащим образом разбито на задачи ( - число задач в j-м задании). Для всех задач известны длительности их исполнения на используемом типе процессора . При разбиении задания на задачи обычно руководствуются двумя соображениями - ограничением по производительности процессора и минимизацией обменной

информацией в точках разрыва задания.

В общем случае результаты процедуры назначения могут характеризоваться различными затратами. На рис. 2 представлены примеры трех вариантов назначения на процессоры состоящего из шести задач иерархического задания. Напомним, что вершина, у которой нет выходящих ребер, называется корнем, а вершина, у которой нет входящих ребер - листом. Корень в данном случае - это выходная задача, выдающая информацию во вне, а листья - входные задачи, принимающие внешнюю информацию. Для каждого примера рядом с графом задания с намеченным штриховой линией размещением задач по процессорам (рис. 2, а, в, д) представлен соответствующий граф межпроцессорных связей (рис. 2, б, г, е), где прямоугольниками обозначены процессоры, а стрелками - межпроцессорные связи информационного обмена. Видно, что во втором случае (рис. 2, в, г) требуется три процессора вместо двух, затребованных в первом и третьем случаях. Если сравнивать случаи, показанные на рис. 2, а, б и д, г, то они различаются сложностью информационных обменов. Считая все информационные связи, представленные стрелками, равной сложности (оценим ее единицей), приходим к выводу, что в первом случае - сложность

связи равна 4 (четыре стрелки), а в третьем - 1.

Алгоритм назначения

В основу используемого представления иерархических заданий в машине положен известный способ представления произвольного дерева в виде бинарного дерева. Этот способ был модифицирован в соответствии с требованиями предлагаемого алгоритма. На рис. 3 приведено машинное представление для дерева, рассмотренного выше (см. рис. 2). Здесь каждая вершина соответствует некоторой задаче и имеет четыре адресных поля и четыре информационных. Крайнее левое адресное поле L указывает на крайнего левого «сына», крайнее правое поле R - на следующего «брата», второе слева поле B указывает на «предка» в машинном представлении, поле g - на предка вершины в исходном графе. В информационном поле p сохраняется номер процессора, на который назначается задача, соответствующая данной строке, в поле e располагается длительность задачи, в поле d - длительность обмена информацией задачи с ее предком в исходном графе. Стрелки в представлении задания указывают на существующую между соответствующими вершинами связь по адресам, хранящимся в их представлении. Табличное описание машинного представления, показанного на рис. 3, приведено в табл. 1, где к семи описанным выше столбцам добавлен еще один - номер вершины.

1. Пример машинного представления задания (рис. 2)

Приведем эвристический алгоритм назначения, стремящийся к ситуации на рис. 2, д, е, когда на одном процессоре оказываются вершины, принадлежащие одному поддереву. В конкретных примерах эта ситуация реализуется не всегда. Алгоритм работает с табличным описанием графа задания. Введем обозначения: i - номер в таблице для рассматриваемой на данном шаге задачи; j - номер рассматриваемого процессора; - временной ресурс процессора ; - текущая загрузка рассматриваемого процессора; - текущая загрузка рассматриваемого канала обмена. Обращение к конкретной клетке таблицы, например, к левому адресу L для i-й задачи будем обозначать .

Алгоритм назначения.

Положим i = 1, j = 0.

Определить адрес левого поддерева i-й вершины .

Если , то

обнулить левый адрес i-й вершины ,

перейти на следующий ярус по левому адресу ,

перейти к п. 1,

иначе определить адрес правого брата .

Если , то

обнулить правый адрес i-й вершины ,

перейти к следующему брату по правому адресу ,

перейти к п. 1,

иначе назначить рассматриваемую задачу (последнего «брата») на текущий процессор:

определить текущую загрузку процессора .

сравнить ее с допустимой,

если , то перейти к п. 2,

иначе , j = j + 1, .

Определить адрес «предка» в машинном представлении .

Если , то

обнулить адрес возврата из i-й вершины ,

перейти к «предку» по адресу возврата ,

перейти к п. 1,

иначе конец алгоритма.

По результатам применения приведенного алгоритма заполняется столбец p таблицы 1 и исходя из заданного значения производительности используемых каналов обмена производится определение их требуемого числа.

Пример. Применим описанный алгоритм к заданию, представленному на рис. 3 и в табл. 1, в предположении, что допустимая загрузка процессора на периоде равна 10. В результате последовательность посещений вершин графа будет следующей: 1, 2, 3, 4, 5, (6, 5, 4, 3), (2, 1). Таким образом, сначала осуществляется переход из корня 1 в вершину 6, а затем из вершины 6 в корень 1. При обратном переходе, начиная с задачи 6, происходит назначение задач на процессоры. При этом задачи 6, 5, 4, 3 оказываются на первом процессоре, а задачи 2 и 1 - на втором. Это назначение в последовательности посещений отражено скобками.

Нетрудно видеть, что алгоритм предполагает посещение каждой вершины графа не более двух раз. При этом каждый раз выполняются операции сравнения с константами для адресов и текущей загрузки процессоров. Измеряя временную сложность алгоритма числом операций сравнения, можно говорить для него о линейной сложности в отличие от оптимального алгоритма, характеризующегося экспоненциальной сложностью.

Представляется полезным обсудить вопрос о влиянии выбираемого варианта назначения на возможность построения в дальнейшем корректного плана, когда система реального времени без пропусков обрабатывает все порции входной информации. Всё ясно, когда процедура назначения приводит к конвейеру. Тогда возможный корректный план очевиден: задачи первого яруса графа предшествования решаются на первом процессоре, задачи второго яруса - на втором процессоре и т.д. Ситуация менее очевидна, если назначение задач производится произвольным образом.