Перспективные топологии многопроцессорных вычислительных систем, основанные на графах Кэли, заданных группами периода 4
Автор: Кузнецов А.А., Кузнецова А.С.
Журнал: Сибирский аэрокосмический журнал @vestnik-sibsau
Рубрика: Математика, механика, информатика
Статья в выпуске: 3 т.17, 2016 года.
Бесплатный доступ
Определение графа Кэли было дано известным английским математиком Артуром Кэли в XIX веке для представления алгебраической группы, заданной фиксированным множеством порождающих элементов. В настоящее время графы Кэли нашли широкое применение как в математике, так и в прикладных задачах. В частности, указанные графы используются для представления компьютерных сетей, в том числе для моделирования топологий многопроцессорных вычислительных систем (МВС) - суперкомпьютеров. С тех пор данное направление активно развивается. Это связано с тем, что графы Кэли имеют много привлекательных свойств, из которых выделим их регулярность, вершинную транзитивность, малые диаметр и степень при достаточно большом количестве вершин в графе. Например, такие базовые топологии сети, как кольцо, гиперкуб и тор, являются графами Кэли. Одной из широко применяемых топологий МВС является k-мерный гиперкуб. Данный граф задается k-порожденной бернсайдовой группой периода 2, которую обозначают B ( k,2 ). Группа B ( k,2 ) имеет простую структуру и равна прямому произведению k экземпляров циклической группы порядка 2. Обобщением гиперкуба является n-мерный тор, который порождается прямым произведением n экземпляров циклических подгрупп, порядки которых могут не совпадать. Проведены исследования по определению структуры графов Кэли групп B ( k,4 ) - бернсайдовых k-порожденных групп периода 4 (а также их фактор-групп), для сравнения с гиперкубами и торами соответствующих размерностей. Анализ выявил, что графы B ( k,4 ) обладают лучшими характеристиками в сравнении c гиперкубами и торами, поэтому заслуживают внимания при проектировании перспективных топологий МВС.
Граф кэли, многопроцессорная вычислительная система
Короткий адрес: https://sciup.org/148177596
IDR: 148177596 | УДК: 519.6
Perspective topologies of multiprocessor computing systems based on the Cayley graphs of groups of period 4
The definition of the Cayley graph was given to the famous English mathematician Arthur Cayley in the XIX century to represent algebraic group defined by a fixed set of generating elements. At present, Cayley graphs are widely used both in mathematics and in applications. In particular, these graphs are used to represent computer networks, including the modeling of topologies of multiprocessor computer systems (MСS) - supercomputers. Since this direction is actively developed. This is due to the fact that Cayley graphs have many attractive properties such as regularity, vertex transitive, small diameter and degree at a sufficiently large number of vertices in the graph. For example, such a basic network topology as the “ring”, “hypercube” and “torus” are the Cayley graphs. One of the commonly used topologies MCS is a k-dimensional hypercube. This graph is given by k-generated Burnside groups of period 2, which is denoted B ( k,2 ). The group B ( k,2 ) has a simple structure and is equal to the direct product of k copies of the cyclic group of order 2. A generalization of the hypercube is a n-dimensional torus, which is generated by the direct product of n copies of the cyclic groups whose orders may be different. In this work, We researched the structure of the Cayley graphs of group B ( k,4 ) - Burnside k-generated groups of period 4 (and some their quotients). Then we compared these graphs with the corresponding toruses and hypercubes. The analysis is shown that the graphs B ( k,4 ) have better properties in comparison with hypercubes and toruses. Therefore, they deserve attention in the design of advanced topologies of MCS.
Список литературы Перспективные топологии многопроцессорных вычислительных систем, основанные на графах Кэли, заданных группами периода 4
- Akers S., Krishnamurthy B. A group theoretic model for symmetric interconnection networks//Proceedings of the Intern. Conf. on Parallel Processing. 1986. Рp. 216-223.
- Schibell S., Stafford R. Processor interconnection networks and Cayley graphs//Discrete Applied Mathematics. 1992. Vol. 40. P. 337-357.
- Cooperman G., Finkelstein L. New methods for using Cayley graphs in interconnection networks//Discrete Applied Mathematics. 1992. Vol. 37. P. 95-118.
- Lakshmivarahan S., Jho J., Dhall S. Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey//Parallel Computing. 1993. Vol. 19. P. 361-407.
- Heydemann M. Cayley graphs and interconnection networks, in Graph symmetry: algebraic methods and applications/Ed.: Hahnand Sabidussi. Dordrecht: Kluwer Academic Publishers, 1997. P. 167-226.
- Xu J. Topological Structure and Analysis of Interconnection Networks. Dordrecht: Kluwer Academic Publishers, 2001. 352 p.
- Parhami B. Swapped interconnection networks: Topological, performance, and robustness attributes//Journal of Parallel and Distributed Computing. 2005. Vol. 65. P. 1443-1452.
- Computing the diameter of 17-pancake graphs using a PC cluster/S. Asai //LNSC. 2006. Vol. 4128. P. 1114-1124.
- Chen B., Xiao W., Parhami B. Internode distance and optimal routing in a class of alternating group networks//IEEE Transactionson Computers. 2006. Vol. 55. P. 1645-1648.
- Wang L., Tang K. The Cayley Graph implementation in TinyOS for dense wireless sensor networks//Proc. of the 6th Wireless Telecommunications Symposium. 2007.
- Efficient Routing in Data Center with Underlying Cayley Graph/M. Camelo //Proceedings of the 5th Workshop on Complex Networks CompleNet. 2014. P. 189-197.
- Even S., Goldreich O. The Minimum Length Generator Sequence is NP-Hard//Journal of Algorithms. 1981. Vol. 2. P. 311-313.
- Vaughan-Lee M. The restricted Burnside problem. Oxford: Clarendon Press, 1990. 209 p.
- Кузнецов А. А. Графы Кэли бернсайдовых групп периода 3//Сибирские электронные математические известия. 2015. Т. 12. С. 248-254.
- Кузнецов А. А., Кузнецова А. С. Параллельный алгоритм для исследования графов Кэли групп подстановок//Вестник СибГАУ. 2014. № 1 (53). С. 34-39.
