Параллельная реализация алгоритма расчета надежности сети

Назначение - программа предназначена для точного расчета надежности сети с использованием ресурсов кластера НКС-30Т ССКЦ КП СО РАН.
Область применения - анализ надёжности и живучести сетей различного назначения.

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

Данная программа позволяет осуществлять параллельный точный расчёт надёжности сетей с ненадёжными каналами связи (под надёжностью понимается вероятность связности всех узлов сети). Распараллеливание расчёта основано на известном методе факторизации (ветвления, Мура-Шеннона), использованный алгоритм опубликован в [1].

Входные данные программы – структура сети в виде графа, значения надёжности каналов связи (т.е. вероятности их присутствия).

Выходные данные программы – значение надёжности сети, время расчёта.

Программа работает с представлением графов при помощи полного файла предшественников (списки KAO,FO). Текстовый файл, содержащий информацию о графе, должен иметь имя «graph.txt» и располагаться в той же директории, что и файл программы. Информация в файле должна располагаться следующим образом: первая строка – количество вершин, вторая строка – количество рёбер, третья и четвёртая строка – списки представления графа (элементы списка разделяются запятыми).

[1] Мигов Д.А. Параллельный метод для расчета структурной надежности сети // Тезисы докладов XIV Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям, Томск, ТНЦ СО РАН, 2013. Новосибирск, ИВТ СО РАН, 2013, с. 42.

Функциональные возможности - расчёт надёжности сетей с количеством элементов в несколько сотен.

Инструментальные средства создания - C++, MPI.