Просмотр статьи


Номер журнала: 2014.4

Заголовок статьи: Некоторые вопросы параллельной реализации алгоритма полного перебора (на примере задач надёжности сетей)

Резюме

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

Авторы

А.С. Родионов, А.В. Сакерин, Д.А. Мигов

Библиография

1. Мигов Д.А. Параллельный метод для расчёта структурной надёжности сети // Тезисы 14-й Всероссийской конференции молодых учёных по математическому моделированию и информационным технологиям (Томск, 2013). Новосибирск, ИВТ СО РАН, 2013. С. 42.
2. Каневский В.И., Мигов Д.А., Родионов А.С. Параллельный алгоритм расчёта математического ожидания числа несвязных пар вершин в графе // Труды Х Международной Азаитской школы-семинара «Проблемы оптимизации сложных систем», Часть 1, 2014, – Новосибирск: ИВМиМГ СО РАН, – С. 346-351.
3. Migov D., Rodionov A. Parallel Implementation of the Factoring Method for Network Reliability Calculation // ICCSA 2014. Springer Lecture Notes in Computer Science. Vol. 8584, issue 6, Heidelberg: Springer, – 2014, P. 654-664.
4. Migov D.A. A parallel method for network probabilistic connectivity calculation // Abstracts of the Int. conf. «Advanced mathematics, computations and applications – 2014». ICM&MG SB RAS, 2014, p. 103.
5. Colbourn Ch. J. The combinatorics of network reliability. N.Y.: Oxford Univ. press, 1987. 160 p.
6. Satyanarayana A., Chang M.K. Network reliability and the factoring theorem // Networks. 1983. V. 13. P. 107-120.
7. Rodionov, A.S, Rodionova, O.K., Choo, H. On the Expected Value of a Number of Disconnected Pairs of Nodes in Unreliable Network. In: ICCSA 2007. LNCS, vol. 4707, Heidelberg: Springer, – 2007, P. 534–543.
8. Chen Y., Li J., Chen J. A new algorithm for network probabilistic connectivity // Military Communications Conference Proceedings, 1999, MILCOM 1999. IEEE. – 1999. – Vol. 2. –
P. 920–923.
9. Мигов Д.А. Формулы для быстрого расчёта вероятности связности подмножества вершин в графах небольшой размерности // Проблемы информатики, № 2(6), 2010. – С.10-17.
10. Rodionova, O.K., Rodionov, A.S., and Choo, H. Network Probabilistic Connectivity: Exact Calculation with Use of Chains. ICCSA-2004, Springer LNCS. Vol. 3046 (2004) P. 315–324.
11. Glinsky, B., Rodionov, A., Marchenko, M., Podkorytov, D., and Weins, D. Scaling the Distributed Stochastic Simulation to Exaf{l}op Supercomputers. High Performance Computing and Communication & 2012 IEEE 9th International Conference on Embedded Software and Systems (HPCC-ICESS), 2012 IEEE 14th International Conference on, Proceedings, P. 1131–1136.

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

надёжность сети, случайный граф, параллельный алгоритм.


Скачать полный текст