Университет Украины «Киевский Политехнический Институт»

Вид материала

Документы

Подобный материал:

• Программа конференции предусматривает: пленарные доклады ведущих научных работников, 88.12kb.
• Университет Украины "Киевский Политехнический Институт", 1479.05kb.
• Программа конференции 18 20 мая 2010 г. Киев, Украина, 944.72kb.
• Влияние постоянного магнитного поля на диффузионные процессы и структуру, 33.27kb.
• Уважаемые коллеги!, 89.84kb.
• Уважаемые коллеги!, 92.7kb.
• Уважаемые коллеги!, 94.31kb.
• 04–08 июня 2012 г, 92.72kb.
• Уважаемые коллеги!, 91.05kb.
• А. М. Степанчук Национальный технический университет Украины "Киевский политехнический, 245.12kb.

Дерево иерархии ребер GL-модели

А.М. Романкевич, В.А. Романкевич, Бахтари Хедаятоллах

Национальный Технический Университет Украины

«Киевский Политехнический Институт», Киев, Украина


В докладе рассматриваются циклические графо-логические модели (GL-модели) поведения отказоустойчивых реконфигурируемых многопроцессорных систем (ОМС) в потоке отказов [1]. Подобные модели используются при расчете надежности ОМС. GL-модель представляет собой граф, каждому ребру которого приписана булева функция. Переменные функций суть состояния процессоров (1 – работоспособен, 0 - отказ), значение функции определяет состояние ребра графа (0 – исчезает, 1 - присутствует). Состоянию ОМС соответствует связность графа (отсутствие связности отражает потерю работоспособности системы). ОМС, включающую n процессоров и теряющую работоспособность при появлении не менее, чем m+1 отказов своих процессоров, мы будем называть базовой.

Основой GL-модели базовой ОМС является циклический (хотя это не обязательно) граф, связность которого при появлении того или иного вектора состояния системы определить несложно. Сложности начинаются при преобразовании модели базовой ОМС к модели небазовой [2], то есть системы, которая может вести себя в потоке отказов иначе, чем базовая, например, оказаться работоспособной при появлении некоторого множества векторов состояния ОМС с m+1 нулевых компонент.

Один из путей преобразования моделей – введение дополнительных ребер, которые способны блокировать потерю связности при появлении того или иного вектора состояния. Эти ребра вместе со своими реберными функциями могут усложнить модель. Поэтому за основу выбирается модель, которая при появлении вектора с m+1 нулевых компонент теряет всего 2 ребра: с одной стороны это – минимум для потери связности, а с другой – для блокирования достаточно одного дополнительного ребра.

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


Литература

1. 
   Романкевич А.М., Карачун Л.Ф., Романкевич В.А. Графо-логические модели для анализа сложных отказоустойчивых вычислительных систем // Электронное моделирование.- 2001.-т.23, №1.- С.102-111.
   
2. Романкевич А.М., Иванов В.В., Романкевич В.А. Анализ отказоустойчивых многомодульных систем со сложным распределением отказов на основе циклических GL-моделей // Электронное моделирование.-№5, т.26, 2004, с.67-81