BC/NW 2010; №2 (17):7.1

 

МЕТОДИКА ПОСТРОЕНИЯ ПРОГРАММНОГО КОНСТРУКТОРА ИМИТАЦИОННЫХ МОДЕЛЕЙ ФУНКЦИОНИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ ДЛЯ ИСПЫТАНИЯ РЕАЛИЗАЦИЙ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ

Филатов А.В.

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

 

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

1)       задавать вычислительной системе любые структурные и функциональные параметры;

2)        видеть и исследовать любые, в том числе и скрытые в реальной системе, глубинные процессы и состояния;

3)        воздействовать на функционирование вычислительной системы, имитируя отказы, изменения в конфигурации, коллизии вычислительных процессов и т. п. 

В данной работе представлена методика построения программного конструктора имитационных моделей вычислительных систем. Основными параметрами, моделируемыми с помощью представляемой методики, являются: порядок смены состояний аппаратных компонентов вычислительной системы и времена  пребывания этих аппаратных компонентов в тех или иных состояниях.

Данной методикой для создания собственных программных конструкторов могут воспользоваться студенты, аспиранты, другие исследователи и разработчики параллельных программ.

Для формализованного представления составляющих, с которыми оперирует методика, введём следующие определения.

Функционирование вычислительной системы определяется четырьмя составляющими:

1)       аппаратными компонентами вычислительной системы представляющие собой кортеж SA={E, L, A}, где: E – множество аппаратных компонентов {e0, e1, … ei, …}; L – множество связей между компонентами {l0, l1, … li, …}; A – множество алгоритмов функционирования аппаратных компонентов {a0, a1, … ai, …};

2)       системными программными компонентами SS;

3)       пользовательской программой P, выполнение которой и следует исследовать;

4)       множество воздействий, к которым относятся как внешние, так и внутренние, например: отказ оборудования, подключение/отключение устройств и т.д.

При функционировании системы, в каждый момент времени t, каждый
i-й аппаратный компонент ei вычислительной системы из множества E, может находиться в одном из допустимых для него состояний. Определим каждый i-й аппаратный компонент как кортеж ei={SE_i, TE_i, PE_i, AE_i}, где:

SE_i={se0_i, se1_i, … sej_i, …} – множество состояний, в которых может находится аппаратный компонент;

TE_i={te0_i, te1_i, … tej_i, …} – множество известных времен выполнения аппаратным компонентом каждого j-го действия, из тех, которые может выполнять данный компонент;

PE_i={pe0_i, pe1_i, … pej_i, …} – множество логических портов аппаратного компонента, которые коммутируются (на основе множества связей L (см. далее)) с портами других аппаратных компонентов, и в итоге с помощью этих портов организуется взаимодействие аппаратных компонентов между собой;

AE_i={ae0_i, ae1_i, … aej_i, …} – множество алгоритмов функционирования аппаратного компонента, которые определяют:

1)       порядок перехода компонента из состояния в состояние;

2)       порядок взаимодействия компонента ei с другими аппаратными компонентами системы с помощью логических портов из множества PE;

3)       определение времени пребывания компонента в каждом состоянии на основе множества TE_i или на основе анализа портов из множества PE_i.

Последнее положение необходимо пояснить.

Каждое состояние аппаратного компонента соответствует своему действию или набору действий. В соответствии с этим каждое состояние  аппаратного компонента из множества SE_i, можно отнести к двум типам:

активные состояния аппаратного компонента SE_Ai – это состояния, время пребывания в которых определяется самим компонентом, на основе  известных времен из множества TEi, поскольку компонент в этих состояниях выполняет действия, время которых определяет он сам;

пассивные состояния аппаратного компонента SE_Pi – это состояния, время пребывания в которых определяется другими аппаратными компонентами, взаимодействующие с данным через логические порты из множества PEi.

На рис. 1 представлен пример структуры вычислительной системы состоящей из пяти аппаратных компонентов.

 

Рис. 1. Пример структуры вычислительной системы из пяти аппаратных компонентов

 

Логические порты аппаратных компонентов соединены связями составляющими множество L.

Множество аппаратных компонентов вычислительной системы E можно разбить на несколько подмножеств по числу типов аппаратных компонентов. Тогда E={M0, M1, … Mk, …}. Компоненты могут быть признаны однотипными и включены в некоторое подмножество Mk только в том случае, если для всех установлена полная идентичность их кортежей {SE, TE, PE, AE}. В дальнейшем при построении программной модели в стиле объектно-ориентированного программирования для программных объектов, описывающих аппаратные компоненты одного подмножества Mk, будет создаваться только один класс.

Представим процесс функционирования вычислительной системы как развёрнутую в модельном времени совокупность последовательностей смены состояний каждым компонентом множества E. Отобразим времена пребывания аппаратных компонентов в разных состояниях вычислительной системы в виде временной диаграммы Ганта (рис. 2). Все активные состояния аппаратных компонентов вычислительной системы заштрихованы. Ниже на этом же рисунке представлена шкала событий происходящих в моделируемой системе. Все события, так или иначе, связаны со сменой состояний аппаратных компонентов и в совокупности своей составляют множество событий V={v0, v1, … vi, …}.

Рис. 2. Пример временной диаграммы функционирования вычислительной системы и шкала событий

 

Множество событий V является ключевой составной частью процесса моделирования функционирования вычислительной системы. Оно формируется в процессе моделирования и является его основным результатом.

Теперь рассмотрим методику построения программного конструктора, состоящую из  пяти этапов.

Первый этап.

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

Второй этап.

Для каждого k-го типа аппаратных компонентов определяются параметры элементов кортежа {SE_k, TE_k, PE_k, AE_k}.

Множество PE_k описывается как массив элементов, в которые будут заноситься параметры запросов к аппаратному компоненту данного типа от других аппаратных компонентов.

Множество TE_k описывается как простой одномерный массив, куда заносятся задаваемые времена выполнения действий присущих данному типу компонентов.

Чтобы определить множества SE_k и AE_k необходимо составить автоматный граф интересующего аппаратного компонента, например, как на рис. 3. Состояния компонента изображаются вершинами графа, а дуги, соответствующие переходам из одного состояния в другое, взвешиваются условием этого перехода, то есть элементами множества AE_k, и идентифицируются значением флага flag. В дальнейшее, при программировании этот флаг поможет определить, откуда был осуществлён переход в подпрограмму обработчик (метод-обработчик)  состояния.

 

Рис. 3. Пример автоматного графа некоторого аппаратного компонента

 

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

Третий этап.

Каждый тип аппаратных компонентов описывается как отдельный программный класс (в терминах ООП). Предлагаемая структура класса показана на рис. 4 (здесь и далее используется синтаксис языка C++).
В каждом классе в начале описываются переменные-состояния программного объекта данного класса. На рис. 4. отмечены три важные переменные-состояния. Переменная number будет хранить уникальный номер каждого программного объекта, что эквивалентно номеру аппаратного компонента в системе. Переменная status будет хранить текущее состояние аппаратного компонента. Публичный массив структур логических портов PE будет использоваться для того, что в него могли сохранять «послания» другие аппаратные компоненты.

Метод-конструктор класса будет вызываться каждый раз при создании нового объекта данного класса и через него в частности будет этому объекту присваиваться его уникальный  номер.

Метод-активизатор activate служит для того, чтобы через него к данному объекту обращалась моделирующая программа (её описание см. далее). Этот метод-активизатор определяет текущее состояние аппаратного компонента и вызывает соответствующий метод-обработчик состояния. Важно отметить, что при вызове этого метода-обработчика, activate передаёт ему параметр flag. Этот параметр сообщает методу-обработчику состояния причину обращения к нему. Предлагается установить следующую идентификацию:

1)  flag=0 – означает, что наступило (в модельном времени) ожидаемое событие «запланированное» самим аппаратным компонентом. Например, событие – время окончания выполнения какого-либо действия в активном состоянии;

 

Рис. 4. Предлагаемая структура класса аппаратного компонента

 

2)  flag=1 – означает, что к данному программному компоненту в текущий момент модельного времени к данному аппаратному компоненту  обратился другой аппаратный компонент и сделал соответствующую запись в массиве PE;

3)  flag³2 – означает переход компонента из другого состояния (см. рис. 3).

SEj – метод-обработчик некоторого j-го состояния «определяет» по параметру flag причину обращения к нему и вызывает соответствующий алгоритм обработки (элемент множества AE_k). Эти алгоритмы можно свести к пяти группам:

1)  выполнение аппаратным компонентом некоторого действия. В этом случае из множества TE_k выбирается время выполнения этого действия, которое суммируется с текущим модельным временем, после чего планируется событие (с флагом 0) для текущего аппаратного компонента (окончание выполнения действия) которое фиксируется в массиве событий модельного времени EVENTS (описание см. ниже) после чего осуществляется выход из метода-обработчика;

2)  воздействие другого аппаратного компонента. В этом случае считывается содержимое соответствующей ячейки массива PE и дальше действия по логике, например, переход в другое состояние;

3)  завершение некоторого действия. Как правило, это переход аппаратного компонента в другое состояние;

4)  обращение к другому аппаратному компоненту. В этом случае по матрице смежности LL (см. ниже) определяется, к какому порту какого аппаратного компонента будет осуществлено обращение, в соответствующую ячейку массива PE заносится идентификатор обращения, после чего в массив EVENTS заносится событие с флагом 1 (обращение к другому компоненту) и текущем модельным временем;

5)  взаимодействие с моделью пользовательской программы P и системным программным обеспечением SS. Модель программы представляет собой множество одномерных массивов PROCESS по числу параллельных процессов, в которые последовательно включаются команды программы и команды системного программного обеспечения. Цель взаимодействия – согласно логике выбрать код текущей команды и в соответствии с ним  перевести аппаратный компонент в нужное состояние или запланировать событие с заданным временем.

Четвёртый этап.

Описание основных программных структур. К этим структурам относятся матрица смежности LL и  массив событий модельного времени EVENTS.

Матрица смежности определяет, какой логический порт k-го аппаратного компонента соединён с какими логическими портами других аппаратных компонентов. Фактически, в матрице смежности в момент моделирования отображаются элементы множества связей L.

Массив событий модельного времени EVENTS состоит из структур описывающих события, происходящие в моделируемой системе. Поля структуры следующие:

1)  n_e – номер аппаратного компонента, событие которого записано в данной ячейке (т.е. объект какого аппаратного компонента надо будет активировать);

2)  r_e – флаг реализованности события. Если r_e=0, то событие запланировано, но ещё не реализовано, если r_e=1, то событие уже произошло (т.е. реализовано);

3)  t_e – модельное время, когда должно произойти (или уже произошло) событие;

4)  f_e – флаг события, т.е. какое значение параметру flag надо присваивать при активизации объекта аппаратного компонента;

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

 

Рис. 5. Структура моделирующего программного модуля

 

Пятый этап

Создание моделирующего программного модуля. Структура модуля  приведена на рис. 5.

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

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