Параллельная реализация и имитационное моделирование оценки надёжности сети методом Монте-Карло | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 47. DOI: 10.17223/19988605/47/8

Параллельная реализация и имитационное моделирование оценки надёжности сети методом Монте-Карло

Рассматривается NP-трудная задача расчета надежности сети, элементы которой подвержены случайным отказам. Для оценки надежности сети используется метод Монте-Карло, улучшенный при помощи проверки связности реализации графа одновременно с генерацией этой реализации. Имитационное моделирование позволило оптимально настроить параметры параллельной версии алгоритма для повышения масштабируемости, сделав возможным его применение для приближенного расчета надежности сетей на суперЭВМ большой производительности (пета- и экзафлопсные).

Parallel implementation and simulation of network reliability calculation by Monte Carlo method.pdf Универсальным методом для оценки различных показателей надежности сетей является метод Монте-Карло [1-4], в том числе и в параллельной реализации [5-7]. Несмотря на принадлежность задачи точного расчета надежности сети к классу NP-трудных [8], для сетей небольшой размерности (до сотни ребер) возможно, как правило, осуществлять точный расчет надежности. Для этого используются метод факторизации (ветвления, Мура-Шеннона) и различные методы ускорения, в первую очередь методы редукции, декомпозиции, стратегия выбора элемента для факторизации, точные формулы для графов малой размерности и др. Однако подобные техники разработаны далеко не для всех показателей сетевой надежности. Больше всего таких приемов существует для классического показателя надежности - вероятности связности случайного графа. Некоторые методы ускорения расчета известны для надежности с ограничением на диаметр и для математического ожидания числа связных пар узлов сети. Отсутствие подобных методов сильно затрудняет расчет исследуемого показателя, делая его сложность близкой к экспоненциальной по числу ненадежных элементов (каналов связи и / или узлов). Для анализа надежности сетей средней и большой размерности (сотни, тысячи элементов) точные методы неприменимы, вследствие чего используются различные приближенные методы. Большинство методов основывается на структурных и других особенностях сетей, что делает эти методы эффективными для определенных типов сетей. Наиболее известны методы на основе рассмотрения циклов, разрезов, остовных деревьев. Метод Монте-Карло является среди приближенных методов наиболее универсальным, способным за приемлемое время дать ответ. Другим универсальным методом является метод, основанный на кумулятивном уточнении границ надежности [9-10]. При расчете надежности сети методом Монте-Карло необходимо случайным образом сгенерировать определенное число реализаций сети и усреднить по полученной выборке интересующий нас показатель (связность, число связных пар и т.д.), что и будет оценкой показателя надежности. Исходя из дисперсии выборки можно сделать заключение о погрешности полученного решения. Для некоторых показателей возможно оценить дисперсию в зависимости от размера выборки еще перед началом расчета и, соответственно, определить необходимое количество итераций алгоритма для достижения требуемой погрешности решения. Для других показателей необходимо динамически вычислять дисперсию текущей выборки и принимать решение либо о продолжении расчета, либо о его окончании. Для сокращения дисперсии при расчете надежности сети методом Монте-Карло применяются различные подходы; отметим расслоенную выборку Ван Слайка [1] и рекурсивный метод RVR [2]. В данной работе в качестве показателя надежности рассматривается вероятность связности случайного графа с ненадежными ребрами. Для этого показателя мы предлагаем при генерации реализации графа делать заключение о связности реализации без дополнительного обхода графа. Также для вероятности связности возможно оценить дисперсию в зависимости от размера выборки еще перед началом расчета и определить необходимое количество итераций алгоритма для достижения требуемой погрешности решения. Такой подход также значительно упрощает параллельную реализацию, избавляя от необходимости периодически всем процессам приостанавливать расчет и ждать, пока процесс-сборщик проведет оценку дисперсии. Для исследования эффективности данного параллельного алгоритма при его исполнении на высокопроизводительном суперкомпьютере (в том числе и на потенциальном экзафлопсном суперкомпьютере) применяется имитационное моделирование на основе мультиагентного подхода. При имитационном моделировании с использованием платформы мультиагентного моделирования AGNES предполагалось, что архитектура экзафлопсного суперкомпьютера не отличается от архитектуры кластера НКС-30Т ССКЦ СО РАН. В результате выявлено, что параллельный алгоритм идеально масштабируется до 512 000 вычислительных ядер, далее наблюдается уменьшение эффекта ускорения от количества ядер. Решением в данном случае могут быть увеличение количества агентов-«сборщиков» и их иерархическая организация. Отметим, что предложенная модель позволяет осуществлять моделирование расчета методом Монте-Карло и для других показателей сетевой надежности, для которых возможно оценить дисперсию перед началом расчета. 1. Случайный граф как модель сети с ненадежными элементами Для анализа надежности сетей различного назначения используют, как правило, аппарат случайных графов. Рассмотрим произвольный неориентированный граф G = (V, E), где V - это множество вершин, а E - множество ребер графа G. Пусть для каждого ребра e задана вероятность его присутствия в графе ре, при этом предполагается, что вершины абсолютно надежны. Элементарным событием будем называть частную реализацию графа, определяемую исправностью или отказом каждого ребра. Элементарное событие удобно представлять как список длины |E|, в котором i-й элемент равен 1, если i-е ребро присутствует в реализации, и равен 0 в противном случае. Вероятность элементарного события равна произведению вероятностей присутствия исправных ребер, умноженному на произведение вероятностей отсутствия отказавших ребер. Произвольное событие (событие есть объединение некоторых элементарных событий) будем называть успешным, если в каждом элементарном событии, входящем в это событие, все вершины могут быть связаны исправными ребрами. Вероятность связности графа G, R(G), есть вероятность того, что эти вершины связаны исправными ребрами, т.е. вероятность события, состоящего из всех успешных событий, и только из них. 2. Оценка надежности сети методом Монте-Карло Опишем общую схему применения методов Монте-Карло к рассматриваемым задачам. Как уже упоминалось, для оценки надежности сети методом Монте-Карло нам нужно случайным образом сгенерировать определенное число реализаций сети, усреднить по полученной выборке интересующий нас показатель и получить таким образом оценку показателя надежности. Для оценки вероятности связности графа показателем будет индикаторная функция связности x(E), заданная как случайная величина на пространстве элементарных событий. Эта функция равна 1, если событие успешно, и 0 в противном случае. Факт успешности E определяется возможностью соответствующей сети успешно функционировать, исходя из практических соображений. В данном случае это связность сети. Математическое ожидание случайной величины и будет точным значением надежности. Среднее значение по выборке будет приближенным значением надежности, сходящимся к точному с ростом размера выборки L по закону больших чисел: 1 L R = M(х) к -£х, = Rl . (1) L i=1 Согласно ЦПТ, с ростом L вычисляемое приближение R становится все ближе к точному значению. Таким образом, по правилу трех сигм получаем следующую оценку: р (IR - L t х, Дисперсия случайной величины равна D(X) = M(х2) -M2(х) = R -R2. Соответственно, дисперсия оценки надежности (среднего значения по выборке) составит D( R)=LiDpl=R), L L2 L а утроенное среднеквадратичное отклонение, которое мы используем для оценки погрешности s (2), оценивается сверху как: .=з0=з.R1-R)

Ключевые слова

надежность сети, случайный граф, связность, обход в ширину, параллельный алгоритм, методы Монте-Карло, имитационное моделирование, network reliability, random graph, connectivity, Monte Carlo methods, simulation

Авторы

ФИООрганизацияДополнительноE-mail
Мигов Денис АлександровичИнститут вычислительной математики и математической геофизики СО РАНкандидат физико-математических наук, старший научный сотрудник лаборатории системного моделирования и оптимизацииmdinka@rav.sscc.ru
Винс Дмитрий ВладимировичИнститут вычислительной математики и математической геофизики СО РАНкандидат технических наук, научный сотрудник лаборатории системного моделирования и оптимизацииvins@sscc.ru
Всего: 2

Ссылки

Slyke R.V, Frank H. Network reliability analysis. Part I // Networks. 1972. V. 1. P. 279-290.
Cancela H., Urquhart M.E. Adapting RVR simulation techniques for residual connectedness network reliability models // IEEE Trans. Computers. 2002. V. 51, No. 4. P. 439-443.
Botev Z.I., Kroese D.P. Efficient Monte Carlo simulation via the generalized splitting method // Statistics and Computing. 2012. V. 22, No. 1. P. 1-16.
Cancela H., Murray L., Rubino G. Highly reliable stochastic flow network reliability estimation // Proc. XLII IEEE Latin Ameri can Computing Conference. CLEI'16. IEEE Press, 2016.
Khadiri M.E., Marie R., Rubino G. Parallel estimation of 2-terminal network reliability by a crude Monte Carlo technique // Proc. of the 6th Int. Symposium on Computer and Information Sciences. 1991. Elsevier, 1991. P. 559-570.
Martinez S.P., Calvino B.O., Rocco S.C.M. All-terminal reliability evaluation through a Monte Carlo simulation based on an MPI implementation // Proc. European Safety and Reliability Conference: Advances in Safety, Reliability and Risk Management. PSAM 2011/ESREL. Helsinki, 2012. P. 1-6.
Мигов Д.А. Параллельные методы точного и приближенного расчета надежности сетей // Молодежь. Наука. Технологии (МНТК-2017) : труды Междунар. конф. Новосибирск : Изд-во НГТУ, 2017. Ч. 3. С. 67-69.
Colbourn Ch.J. The combinatorics of network reliability. New York : Oxford University Press, 1987. 160 p.
Won J.-M., Karray F. Cumulative update of all-terminal reliability for faster feasibility decision // IEEE Trans. on Reliability. 2010. V. 59, No. 3. P. 551-562.
Rodionov A.S., Migov D.A., Rodionova O.K. Improvements in the efficiency of cumulative updating of all-terminal network reliability // IEEE Trans. on Reliability. 2012. Vol. 61, No 2. P. 460-465.
Podkorytov D., Rodionov A., Choo H. Agent-based simulation system agnes for networks modeling: review and researching // Proc. 6th Int. Conf. on Ubiquitous Information Management and Communication. ACM ICUIMC 2012. ACM New York, USA. Article No. 115.
Glinsky B., Rodionov A., Marchenko M., Podkorytov D., Weins D. Scaling the distributed stochastic simulation to exaflop supercomputers // Proc. 14th IEEE Int. Conf. on High Performance Computing and Communications. HPCC'2012. IEEE Press, 2012. P. 1131-1136.
 Параллельная реализация и имитационное моделирование оценки надёжности сети методом Монте-Карло | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 47. DOI: 10.17223/19988605/47/8

Параллельная реализация и имитационное моделирование оценки надёжности сети методом Монте-Карло | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 47. DOI: 10.17223/19988605/47/8