Мигов Д.А.
Параллельный метод для расчета структурной надежности сети
В докладе рассматривается задача расчета вероятности связности случайного графа с ненадежными ребрами и абсолютно надежными вершинами. Эта характеристика является одним из основных показателей структурной надежности сетей, в которых надежность узлов на порядки превосходит надежность каналов связи. Расчет данного показателя - NP-трудная задача [1], что делает его затруднительным для сетей реальной размерности. Впервые задача расчета этого показателя была рассмотрена Е.Ф. Муром и К.Э. Шенноном в 1956 году [2], ими же был предложен метод ветвления, являющийся наиболее известным методом расчета вероятности связности графа. С тех пор было введено в рассмотрение и изучено достаточное количество других показателей надежности сетей, также описываемых в рамках теории случайных графов. Однако почти для каждого показателя задача его расчета является NP-трудной, соответственно точный расчет потребует экспоненциальной трудоемкости. Поэтому исследовались преимущественно приближенные методы [1,3].
С применением разработанных к настоящему времени точных алгоритмов реально рассчитывать надежность сетей средней размерности (сотни элементов). При этом параллельные методы расчета и оптимизации ранее практически не изучались, тогда как их использование должно обеспечить вычисление на современных суперЭВМ за приемлемое время надежности сетей практически интересной размерности (сотни и тысячи элементов).
В данной работе предлагается параллельная реализация уже упомянутого метода ветвления. Разработанный алгоритм был реализован на языке C++ c использованием MPI. Были проведены численные эксперименты на кластере ССКЦ. Результаты экспериментов подтвердили эффективность разработанного метода.
Работа поддержана РФФИ. Гранты № 11-07-00183, № 13-07-00589.
Литература
[1] Charles J. Colbourn. The Combinatorics of Network Reliability. Oxford University Press, New York. 1987.
[2] Moore E.F., Shannon C.E. Reliable circuits using less reliable relays // J. Franclin Inst. – 1956. – Vol. 262, N4b. – P. 191-208.
[3] Rodionov A.S, Migov D.A., Rodionova O.K. Improvements in the Efficiency of Cumulative Updating of All-Terminal Network Reliability // IEEE Transactions on Reliability. June 2012. Vol. 61, N 2. P. 460-465.
| Тезисы доклада: | abstracts_176045_ru.pdf |
К списку докладов
