НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o283.Pdf (948.12Кб)

УДК 519.87+519.6+681.324

Россия,  Институт вычислительной математики и математической геофизики СО РАН

В работе исследуется решение оптимизационной проблемы построения оптимальных по диаметру регулярных сетей (графов). Регулярные сети обеспечивают практический интерес как графо-теоретические модели надежных сетей связи параллельных суперкомпьютерных систем, как основа структуры в модели малого мира, в нейронных и оптических сетях. Вводится новый класс параметрически описываемых регулярных сетей - гиперциркулянтные сети (графы). Разработан подход, использующий эволюционные алгоритмы для автоматического порождения параметрических описаний оптимальных гиперциркулянтных сетей. Синтез оптимальных гиперциркулянтных сетей производится на основе оптимальных циркулянтных сетей с меньшей степенью вершин. Для построения оптимальной гиперциркулянтной сети применяется темплейт, описывающий циркулянтную сеть из известных оптимальных семейств циркулянтных сетей с требуемым числом вершин и с меньшей степенью вершин. При этом множество образующих циркулянтной сети используется как подмножество образующих гиперциркулянтной сети, а недостающие образующие синтезируются с помощью эволюционного алгоритма, осуществляющего минимизацию диаметра (среднего диаметра) сети. Проведен сравнительный анализ структурных характеристик гиперциркулянтных, тороидальных и циркулянтных сетей. Показано преимущество гиперциркулянтных сетей по таким структурным характеристикам, как диаметр, средний диаметр и ширина бисекции, при соизмеримых затратах на число узлов и число связей системы. Отмечено преимущество гиперциркулянтных сетей размерности три перед торами большей размерности, равной четырем. Таким образом, показано, что оптимизация гиперциркулянтных сетей размерности три является более эффективной, чем введение дополнительной размерности для соответствующих тороидальных структур. Отмечены также лучшие структурные показатели у гиперциркулянтных сетей по сравнению с предложенными ранее другими авторами iBT-сетями.

1. Монахов О.Г., Монахова Э.А. Параллельные системы с распределенной памятью: структуры и организация взаимодействий. Новосибирск: Изд-во СО РАН, 2000. 242 с.
2. Монахова Э.А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011. № 3 (13). С . 92-115.
3. Bermond J.C., Comellas F., Hsu D.F. Distributed loop computer networks: a survey // Journal of Parallel and Distributed Computing. 1995. Vol. 24, iss. 1. P. 2-10. DOI: 10.1006/jpdc.1995.1002
4. Hwang F.K. A survey on multi-loop networks // Theoretical Computer Science. 2003. Vol. 299, iss. 1-3. P. 107-121. DOI: 10.1016/S0304-3975(01)00341-3
5. Martinez C., Beivide R., Gabidulin E.M. Perfect codes from Cayley graphs over Lipschitz integers // IEEE Transactions on Information Theory. 2009. Vol . 55, no. 8. P . 3552-3562. DOI: 10.1109/TIT.2009.2023733
6. Нестеренко Б.Б., Новотарский М.А. Клеточные нейронные сети на циркулянтных графах // Искусственный интеллект. 2009. № 3. С . 1 32-138.
7. Muga II F.P., Saldana R.P., Yu W.E.S. Building Graph-Based Symmetric Cluster // NECTEC Technical Journal. 2001. Vol. 2, no. 9. P. 195-199.
8. Monakhov O.G., Monakhova E.A. A Class of Parametric Regular Networks for Multicomputer Architectures // Intern. Scientific Journal "Computing and Systems". 2000. Vol. 4, no. 2. P. 85-93.
9. Монахова Э.А., Монахов О.Г. Эволюционный синтез семейств оптимальных двумерных циркулянтных сетей // Вестник СибГУТИ. 2014. № 2 . С . 72-82 .
10. Jha P.K. Dense bipartite circulants and their routing via rectangular twisted torus // Discrete Applied Mathematics. 2014. Vol. 166. P. 141 - 158. DOI: 10.1016/j.dam.2013.09.021
11. Watts D.J., Strogatz S.H. Collective dynamics of "small-world" networks // Nature.1998. Vol. 393. P. 440-442. DOI:10.1038/30918
12. Монахова Э.А., Монахов О.Г. О некоторых характеристиках циркулянтных и тороидальных структур // Вестник СибГУТИ. 2013. № 3. С. 63-69 .
13. Aroca J.A., Anta A.F. Bisection (Band)Width of Product Networks with Application to Data Centers // In: Theory and Applications of Models of Computation. Springer Berlin Heidelberg , 2012. P. 461- 472. (Ser. Lecture Notes in Computer Science; vol. 7287). DOI: 10.1007/978-3-642-29952-0_44
14. Zhang P., Powell R., DengY. Interlacing Bypass Rings to Torus Networks for More Efficient Networks // IEEE Transactions on Parallel and Distributed Systems. 2011. Vol. 22, no. 2. P. 287-295. DOI:10.1109/TPDS.2010.89