BC/NW 2007, №2, (11) :2.2

СИСТЕМЫ ИЕРАРХИЧЕСКОЙ ОБРАБОТКИ ДАННЫХ
И ЗАДАЧА АНАЛИЗА ИХ ВРЕМЕННЫХ ХАРАКТЕРИСТИК

Ю.Е. Мороховец

(Москва, Московский энергетический институт (ТУ), Россия)

Системы иерархической обработки данных (СИОД) рассматриваемого класса имеют древовидную структуру, в узлах которой размещаются специализированные устройства обработки данных (УОД). УОД иерархически связаны между собой каналами передачи данных (КПД). Передача информации в каналах однонаправленная – от подчиненных устройств нижних уровней иерархии к головным устройствам верхних уровней. Передача информации осуществляется блоками данных фиксированного формата, формируемыми нижестоящими УОД. Размеры блоков различны и зависят от того, какими устройствами они формируются.

На рисунке 1 представлен пример простой четырехуровневой СИОД.

 

 

 

 

 

 

 

 

 

 

Рисунок 1 – Пример системы иерархической обработки данных

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

Для идентификации устройств в системе применяются квалифицированные номера. Полный идентификатор УОД состоит из латинской буквы D, за которой в квадратных скобках следует квалифицированный номер устройства.

Номер корневого устройства системы, единственного УОД верхнего нулевого уровня иерархии, равен 1. Номера устройств нижележащего первого уровня, подчиненных устройству D[1], имеют вид 1.1, …, 1.i₁, …, 1.n(1), где n( ) – число устройств, подчиненных УОД с номером указанным в скобках.

Если D[1..i_k] – произвольное устройство обработки данных k-го уровня иерархии, то подчиненные ему УОД (k+1)-го уровня будут иметь номера 1..i_k.1, …, 1..i_k.i_k+1, …, 1..i_k.n(1..i_k), где n(1..i_k), как уже было сказано, – число устройств подчиненных устройству D[1..i_k].

На рисунке 2 показан базовый фрагмент системы – куст устройств, головным УОД которого является устройство D[1..i_k].

 

 

 

 

 

 

 

Рисунок 2 – Нумерация устройств на k-м и (k+1)-м уровнях иерархии

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

Рабочий цикл узлового УОД состоит их трех фаз – фазы приема блоков данных от подчиненных устройств, фазы обработки данных и фазы выдачи блока данных с результатами обработки «наверх», вышестоящему устройству системы (рисунок 3).

 

 

 

 

 

 

Рисунок 3 – Диаграмма рабочего цикла устройства D[1..i_k]

Функционирование устройства D[1..i_k] на фазе приема данных может быть представлено как многократный опрос сигналов готовности, поступающих в его систему прерывания от подчиненных УОД. Если в результате опроса обнаруживается один или несколько готовых к выдаче УОД, устройство D[1..i_k] инициализирует прием блока данных, причем в случае готовности нескольких УОД, выбирается устройство с наименьшим значением i_k+1.

На прием блока данных от подчиненного УОД D[1..i_k.i_k+1] устройство D[1..i_k] затрачивает время t_п(1..i_k.i_k+1). Выполнение фазы приема данных завершается, если получены блоки данных от всех подчиненных устройств. Будем считать, что время обнаружения готового устройства и инициализации приема данных от него пренебрежимо мало по сравнению с временем t_п. Кроме того, будем считать, что после окончания приема очередного блока данных устройство незамедлительно приступает к опросу сигналов готовности, если он необходим, или к выполнению обработки данных, если все исходные данные получены.

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

На выдачу блока данных вышестоящему устройству устройство D[1..i_k] затрачивает время t_п(1..i_k). По окончанию выдачи устройство незамедлительно начинает выполнять фазу приема данных, относящуюся к следующему рабочему циклу.

Корневое и листовые устройства обработки данных имеют более простые рабочие циклы.

Цикл корневого УОД имеет две фазы – фазу приема и фазу обработки данных. По окончании обработки корневое устройство незамедлительно начинает выполнять фазу приема данных, относящуюся к следующему рабочему циклу.

Цикл листового УОД также имеет две фазы – фазу обработки  и фазу выдачи данных. По окончании выдачи листовое устройство незамедлительно начинает выполнять фазу обработки данных, относящуюся к следующему рабочему циклу.

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

В настоящей работе рассматриваются СИОД с естественной синхронизацией рабочих циклов устройств.

В процессе функционирования таких систем можно выделить два режима – переходный и установившийся режим. Для исследования интерес представляет установившейся режим функционирования системы. В этом режиме процессы, протекающие в системе, носят периодический характер. Времена выполнения рабочих циклов устройств одинаковы и равны времени периода работы системы T.

Таким образом, произвольная система иерархической обработки данных S может быть задана множеством квалифицированных номеров ее устройств и двумя множествами параметров, одно из которых относится к устройствам обработки данных, а другое – к каналам передачи данных.

Устройство обработки данных с номером 1..i_k характеризуется параметром t_о(1..i_k), а канал передачи данных с номером 1..i_k, обеспечивающий выдачу блоков данных «наверх» устройством с тем же номером, – параметром t_п(1..i_k).

Задача анализа временных характеристик систем иерархической обработки данных может быть сформулирована следующим образом.

Пусть S – произвольная система, заданная так, как было сказано выше. Необходимо:

–  определить время периода работы системы T;

– вычислить коэффициенты загрузки h входящих в систему устройств;

– построить расписание (временную диаграмму) работы входящих в систему устройств в установившемся режиме функционирования.

Для вычисления коэффициента загрузки узлового устройства следует использовать формулу:

h(1..i_k) = (+ t_о(1..i_k) + t_п(1..i_k)) / T.

Коэффициенты загрузки корневого и листовых устройств вычисляются по формулам:

h(1) = (+ t_о(1)) / T  и

h(1..i_k) = (t_о(1..i_k) + t_п(1..i_k)) / T,

соответственно.

Решение поставленной задачи содержится в [1].

 

ЛИТЕРАТУРА

 

1. Калинина Г.А., Мороховец Ю.Е. Об одном методе анализа временных характеристик систем иерархической обработки данных. В настоящем сборнике докладов.