Некоторые вопросы параллельной реализации полного перебора
Аннотация
Рассматривается задача эффективного распараллеливания алгоритма полного перебора, применяемого при расчёте некоторых характеристик надёжности сетей с ненадёжными элементами, а также в задачах комбинаторной оптимизации. Описываются общие подходы и конкретные алгоритмы, позволяющие эффективно использовать вычислительные ресурсы при решении задач указанных классов.
Об авторах
А. С. Родионов
Институт вычислительной математики и математической геофизики СО РАН
Россия
Россия
А. В. Сакерин
Сибирский государственный университет телекоммуникаций и информатики
Россия
Россия
Д. А. Мигов
Институт вычислительной математики и математической геофизики СО РАН
Россия
Россия
Список литературы
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.
Рецензия
Для цитирования:
Родионов А.С., Сакерин А.В., Мигов Д.А. Некоторые вопросы параллельной реализации полного перебора. Вестник СибГУТИ. 2014;(4):80-85.
For citation:
Rodionov A..., Sakerin A..., Migov D... Some problems of exhaustive algorithm parallel realization (illustrated by network reliability analysis). The Herald of the Siberian State University of Telecommunications and Information Science. 2014;(4):80-85. (In Russ.)
Просмотров:
188
Послать статью по эл. почте 