VII Международная студенческая научная конференция Студенческий научный форум - 2015

Применение моделей GERT для решения задач с использованием графов большой размерности.

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

• анализа систем профилактического обслуживания и резервирования на основе решетчатых многоразмерных стохастических случайных графов;

• исследования самоорганизующихся матричных сред отказоустойчивого мультимикроконтроллера с поиском ближайших резервных микроконтроллеров с учетом случайного времени перемещения программ между каждым микроконтроллером;

• проектирования отказоустойчивых цифровых систем с адаптивной многоярусной мажоритарной структурой, применяющихся в телекоммуникационных системах управления критическими техническими комплексами с различным временем активного применения (авиационными, космическими);

• расчета надежности ретрансляционной сети связи с аддитивной структурой и т.д.

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

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

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

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

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

Формулируется модель для отказоустойчивых цифровых систем с адаптивной многоярусной мажоритарной структурой (АММС), применяющихся в телекоммуникационных системах управления критическими техническими комплексами с различным временем активного применения (авиационными, космическими и др.). Это марковская модель с непрерывным временем. Более глубокий анализ может быть выполнен с использованием GERT-сетей. В частности, можно найти законы распределения времени работы алгоритмов реконфигурации АММС и оценить надежность различных вариантов ее структуры. Приведенная модель интересна тем, что она имеет большое число контуров, включающих в себя источник и сток сети (в терминологии GERT-сетей это — петли первого порядка). При использовании топологического уравнения Мейсона выражение для эквивалентной функции сети содержит экспоненциально большое число слагаемых с W-функциями петель первого порядка. Нахождение алгоритмов решения задач с большим числом петель первого порядка существенно расширило бы область применения системы GERT.

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

Можно сделать следующие выводы. Разработка новых стохастических GERT-моделей с большим числом циклов и/или петель первого порядка, ветви которых характеризуются распределениями произвольного вида, а^w также алгоритмов из расчета расширяет функциональные возможности системы GERT. В первую очередь это — решение задач нахождения временных и надежностных характеристик вычислительных систем, параллельных вычислительных структур, коммуникационных устройств и серверов телекоммуникаций.

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

Задача прогнозирования времени выполнения параллельных программных комплексов рассматривается как комплексы взаимосвязанных работ (КВР) — задач и/или их параллельно- последовательных фрагментов. При этом используется метод статистического прогнозирования времени выполнения сложных задач. Программные комплексы рассматриваются как КВР, задаваемые графовыми ориентированными моделями с одной начальной и одной конечной вершинами. Время выполнения каждой работы рассматривается как случайная величина, задаваемая экспоненциальным распределением. На уровне работ КВР не имеет логических ветвлений и циклов. Процесс выполнения КВР представляется математической моделью в виде однофазной СМО с двумя или более обслуживающими приборами, с буфером для готовых к выполнению работ. Структура модели является комбинированной и интересна тем, что состоит из двух компонент: сложного ориентированного графа КВР (фактически подсистемы PERT) и системы массового обслуживания.

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

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

Код для цитирования: Скопировать