РЕШЕНИЕ ЗАДАЧИ АНАЛИЗА НАДЕЖНОСТИ НА ПАРАЛЛЕЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ

 

 

Ладыгин И.И., Яньков С.Г.

 

 

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

 

 

 

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

Для решения задачи анализа надежности систем с применением программного моделирования обычно используют два метода [1]:

-         метод статистических испытаний;

-         моделирование поведения системы по интервалам времени.

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

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

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

Рассмотрим особенности реализации метода моделирования по интервалам времени на параллельной вычислительной системе (ПВС).

 

В основе метода расчета надежности по интервалам времени лежит анализ всех работоспособных состояний системы и возможных переходов системы из одного состояния в другое, рассматриваемое как событие наступаемое с определенной вероятностью. Все возможные работоспособные состояния определяются так называемым массивом кратчайших путей успешного функционирования системы (КПУФ) [1], который задается как исходные данные. КПУФ системы представляет собой массив таких конъюнкций элементов системы, ни одну из компонентов которых нельзя изъять, не нарушив функционирование системы. Расчет производится в соответствии с графом переходов системы из одного работоспособного состояния в другое, который в свою очередь строится на основании КПУФ системы. Граф переходов является основой для представления процесса моделирования системы в ярусно-параллельной форме. При расчете надежности по интервалам времени время расчета и его сложность напрямую зависит от нескольких параметров:

–       количества работоспособных состояний системы;

–       количества интервалов времени исследования надежности;

–       количества связей между узлами графа переходов системы;

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

Для достижения результата за более короткий промежуток времени при расчете надежности на ПВС необходимо минимизировать время передач и их количество за счет более удачного распараллеливания узлов задачи по процессорам системы. Удачное распараллеливание подразумевает под собой такое распределение узлов по процессорам, которое обеспечивало бы наиболее равные времена расчета каждого яруса графа. Это приведет к более равномерной и рациональной загрузке процессоров и линий передач вычислительной системы и, соответственно, уменьшению времени расчета. При распараллеливании необходимо учесть структуру вычислительной системы, наиболее важными параметрами которой, являются количество процессоров и линий передачи данных между ними и характер организации ее памяти [2].

Также на сложность распараллеливания влияют и исходные данные расчета. Далее, на примере графов переходов простых вариантов типовых отказоустойчивых вычислительных систем, рассматривается возможность определения на основании значений входных данных основных принципов дальнейшего распараллеливания задачи. На рис. 1 приведены КПУФ систем и соответствующие им графы переходов: а – вычислительная система с резервированием 3 из 5, б – вычислительная система с несколькими, обязательно работоспособными, элементами.

Рис.1. КПУФ систем и графы переходов

 

Проанализировав графы переходов системы, нетрудно заметить, что они обладают асимметрией узлов по количеству входов и выходов.  Очевидно, что асимметричность графа напрямую зависит от характера заданных КПУФ (т.е. от симметричности расположения 0 в них относительно исходного состояния (все единицы). Асимметричность графа является основной трудностью решения задачи с точки зрения равномерной загрузки процессоров и линий передачи данных при распараллеливании задачи.

Сложность и длительность расчета напрямую зависит также  и от количества 0 в КПУФ системы, которые определяют количество всех работоспособных состояний. А чем больше состояний, тем больше передач, что приводят к значительному усложнению расчета и увеличению его времени. Таким образом, основным критерием распараллеливания задач данного класса является такое размещение узлов графа по процессорам, при котором общее число связей между ними минимально.

 

Рассмотренные примеры наглядно демонстрируют, что принципы распараллеливания задачи по процессорам вычислительной системы и их сложность напрямую зависят от заданных КПУФ, так как КПУФ дает четкое представление о графе переходов, на основе анализа которого и происходит выбор той или иной стратегии распараллеливания. Другими словами, проанализировав только входные данные о системе можно довольно четко представить себе дальнейшие принципы стратегии распараллеливания задачи. Это дает широкие возможности по созданию систем распараллеливания задач рассматриваемого класса для параллельных вычислительных систем.

 

ЛИТЕРАТУРА

 

1.        Ладыгин И.И., Калинина Г.А. Исследование надежности вычислительных систем. Описание лабораторных работ по курсу «Основы теории надежности».–М.: Издательство МЭИ,1999.–32с.

2.        Ладыгин И.И., Калинина Г.А. Лабораторные работы по курсу «Вычислительные системы».–М.: Издательство МЭИ,1999.–32с.

3.        Интернет-сайт http://www.citforum.ru/koi/hardware/svk