ПЕРСПЕКТИВНЫЕ ТОПОЛОГИИ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ, ОСНОВАННЫЕ НА ГРАФАХ КЭЛИ, ЗАДАННЫХ ГРУППАМИ ПЕРИОДА 4


Цитировать

Полный текст

Аннотация

Определение графа Кэли было дано известным английским математиком Артуром Кэли в XIX веке для представления алгебраической группы, заданной фиксированным множеством порождающих элементов. В настоящее время графы Кэли нашли широкое применение как в математике, так и в прикладных задачах. В частности, указанные графы используются для представления компьютерных сетей, в том числе для моделирования топологий многопроцессорных вычислительных систем (МВС) - суперкомпьютеров. С тех пор данное направление активно развивается. Это связано с тем, что графы Кэли имеют много привлекательных свойств, из которых выделим их регулярность, вершинную транзитивность, малые диаметр и степень при достаточно большом количестве вершин в графе. Например, такие базовые топологии сети, как кольцо, гиперкуб и тор, являются графами Кэли. Одной из широко применяемых топологий МВС является k-мерный гиперкуб. Данный граф задается k-порожденной бернсайдовой группой периода 2, которую обозначают B ( k,2 ) . Группа B ( k,2 ) имеет простую структуру и равна прямому произведению k экземпляров циклической группы порядка 2. Обобщением гиперкуба является n-мерный тор, который порождается прямым произведением n экземпляров циклических подгрупп, порядки которых могут не совпадать. Проведены исследования по определению структуры графов Кэли групп B ( k,4 ) - бернсайдовых k-порожденных групп периода 4 (а также их фактор-групп), для сравнения с гиперкубами и торами соответствующих размерностей. Анализ выявил, что графы B ( k,4 ) обладают лучшими характеристиками в сравнении c гиперкубами и торами, поэтому заслуживают внимания при проектировании перспективных топологий МВС.

Полный текст

Введение. Определение графа Кэли было дано известным английским математиком Артуром Кэли в XIX веке для представления алгебраической группы, заданной фиксированным множеством порождающих элементов. В последние десятилетия теория графов Кэли развивается как отдельная большая ветвь теории графов. Графы Кэли находят применение как в математике, так и за ее пределами. Заметим, что известная задача по определению так называемого числа Бога кубика Рубика , т. е. минимального количества поворотов граней кубика, за которое его можно «собрать» из любого начального положения, сводится к исследованию соответствующего графа Кэли. Неожиданное применение графы Кэли нашли в информационных технологиях после пионерской работы 1986 г. С. Эйкерса и Б. Кришнамурти [1], которые впервые предложили применять указанные графы для представления компьютерных сетей, в том числе для моделирования топологий многопроцессорных вычислительных систем (МВС) - суперкомпьютеров. С тех пор данное направление активно развивается [2-11]. Это связано с тем, что графы Кэли имеют много привлекательных свойств, из которых выделим их регулярность, вершинную транзитивность, малые диаметр и степень при достаточно большом количестве вершин в графе. Например, такие базовые топологии сети, как кольцо, гиперкуб и тор, являются графами Кэли. Вычисление диаметра графа Кэли большой конечной группы является хотя и разрешимой, но весьма сложной проблемой. Это связано с тем, что в общем случае задача по определению минимального слова в группе, как показали С. Ивен и О. Голдрейх в 1981 г. [12], является NP-трудной. Так, при вычислении в 2010 г. упомянутого выше числа Бога, которое равно диаметру соответствующего графа Кэли, Т. Рокики, Г. Коцемба, М. Дэвидсон и Д. Детридж доказали, что любая конфигурация кубика Рубика может быть решена не более чем в 20 ходов. Для установления данного факта потребовалось около 35 «процессоро-лет» распределенных вычислений. Поэтому для эффективного решения задач на графах Кэли, имеющих большое количество вершин, необходимо применять МВС. Как было сказано, одной из широко применяемых топологий МВС является k-мерный гиперкуб. Данный граф задается k-порожденной бернсайдовой группой периода 2, которую обозначают B(k,2). Группа B(k,2) имеет простую структуру и равна прямому произведению k экземпляров циклической группы порядка 2. Обобщением гиперкуба является n-мерный тор, который порождается прямым произведением n экземпляров циклических подгрупп, порядки которых могут не совпадать. В настоящей работе проведены исследования по определению структуры графов Кэли групп B(k,4) - бернсайдовых k-порожденных групп периода 4 (а также их фактор-групп), для сравнения с гиперкубами и торами соответствующих размерностей. Строение групп B(k,4) известно [13], однако характеристики графов Кэли указанных групп до настоящего времени изучены не были. Отметим также, что в работе [14] были исследованы графы Кэли групп B(k,3), т. е. групп периода 3, а также проведен сравнительный анализ данных графов с гиперкубами. Определение. Пусть X - порождающее множество группы G, т. е. . Графом Кэли Г = Cay(G,X) = = (V,E) называют ориентированный граф, обладающий следующими свойствами: - множество вершин V(Г) соответствуют элементам группы G; - множество ребер E(Г) состоит из всех упорядоченных пар (g, xg), где и . В дальнейшем будем считать порождающее множество X симметричным и свободным от единичного элемента группы, т. е. и . Поскольку X является свободным от единичного элемента, то граф Г не содержит петель. Симметричность порождающего множества означает, что граф будет неориентированным и без кратных ребер, т. е. если в графе имеется ребро из g в xg, то оно совпадает с ребром из xg в . Таким образом, , где V = G и . Количество вершин равно порядку группы G. Граф Кэли является регулярным, и его степень s, т. е. количество ребер, выходящее из каждой вершины, равно числу порождающих элементов группы: . Диаметр графа Кэли D (средний диметр d), т. е. максимальное (среднее) кратчайшее расстояние от произвольной фиксированной вершины до других вершин графа, равен максимальной (средней) длине минимальных слов группы, записанных через порождающие элементы [15]. Ниже представлен алгоритм для исследования графов Кэли конечных групп [15]. Алгоритм A-I: Вход: конечная группа , где X = {х1, х2, …, хm} - порождающее множество G. Выход: диаметр , средний диаметр графа Кэли , а также функция роста группы F(r) группы G, где . 1. s = 0, - шар группы G, . 2. , , . 3. , . 4. Если , то и . 5. Если 6. Если 7. , для 1 ≤ r ≤ s - 1 и F(0) = 1, . 8. Выход. Характеристики графов Кэли групп В(k,4) и некоторых их фактор-групп |V| s D d |V| s D d |V| s D d |V| s D d 24 4 4 2 29 4 10 5,9 213 6 10 6,8 217 8 12 7,9 25 4 4 2,5 29 6 6 4,2 214 6 11 7,4 218 8 12 8,5 26 4 6 3,4 210 6 8 4,9 214 8 8 6,0 219 8 12 8,8 27 4 8 4,1 211 6 10 5,6 215 8 10 6,6 220 8 14 9,3 28 4 8 5,2 212 6 10 6,3 216 8 12 7,3 220 10 10 7,9 Теорема [15]. Алгоритм A-I корректен, т. е. для любой конечной группы он за конечное число шагов находит характеристики соответствующего графа Кэли. Исследование графов Кэли групп B(k,4). В таблице приведены указанные характеристики для графов Кэли групп B(k,4) и некоторых их факторов при , полученные при помощи компьютерных вычислений по алгоритму A-I. Порождающие множества были взяты симметричными, поскольку в этом случае графы будут неориентированными. Именно неориентированные графы, как правило, используют при проектировании топологий МВС. При рассмотрении графа в качестве топологии МВС берут во внимание следующие характеристики графа: количество вершин, степень (для регулярного графа), диаметр и средний диаметр. Теперь сравним полученные характеристики графов Кэли групп B(k,4) c соответствующими характеристиками гиперкубов и торов. Будем считать, что топология Γ1 предпочтительнее Γ2, если , но , и , при этом по крайней мере одно неравенство должно быть строгим. Граф k-мерного гиперкуба имеет вершин, его степень и диаметр равны k, средний диаметр равен . Легко заметить, что графы B(k,4) обладают более предпочтительными характеристиками при сравнении с гиперкубами. Также нетрудно увидеть, что графы B(k,4) будут иметь лучшие значения указанных параметров в сравнении с n-мерными торами. Напомним, что топология n-мерный тор является графом Кэли, который порождается прямым произведением n экземпляров циклических подгрупп Данный граф имеет следующие характеристики: где где где Заключение. Анализ выявил, что графы B(k,4) обладают лучшими характеристиками в сравнении c гиперкубами и торами соответствующих размерностей, поэтому заслуживают внимания при проектировании перспективных топологий МВС. Также представляется актуальной задача по исследованию графов Кэли конечных бернсайдовых групп других периодов. Благодарности. Работа поддержана грантом Президента РФ (проект МД-3952.2015.9). Acknowledgments. This work was supported by a grant from the President of the Russian Federation (MD-3952.2015.9 Project).
×

Об авторах

А. А. Кузнецов

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Email: kuznetsov@sibsau.ru
Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

А. С. Кузнецова

Красноярский государственный аграрный университет

Российская Федерация, 660049, г. Красноярск, просп. Мира, 90

Список литературы

  1. Akers S., Krishnamurthy B. A group theoretic model for symmetric interconnection networks // Proceedings of the Intern. Conf. on Parallel Processing. 1986. Рp. 216-223.
  2. Schibell S., Stafford R. Processor interconnection networks and Cayley graphs // Discrete Applied Mathematics. 1992. Vol. 40. P. 337-357.
  3. Cooperman G., Finkelstein L. New methods for using Cayley graphs in interconnection networks // Discrete Applied Mathematics. 1992. Vol. 37. P. 95-118.
  4. 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.
  5. 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.
  6. Xu J. Topological Structure and Analysis of Interconnection Networks. Dordrecht : Kluwer Academic Publishers, 2001. 352 p.
  7. Parhami B. Swapped interconnection networks: Topological, performance, and robustness attributes // Journal of Parallel and Distributed Computing. 2005. Vol. 65. P. 1443-1452.
  8. Computing the diameter of 17-pancake graphs using a PC cluster / S. Asai [et al.] // LNSC. 2006. Vol. 4128. P. 1114-1124.
  9. 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.
  10. Wang L., Tang K. The Cayley Graph implementation in TinyOS for dense wireless sensor networks // Proc. of the 6th Wireless Telecommunications Symposium. 2007.
  11. Efficient Routing in Data Center with Underlying Cayley Graph / M. Camelo [et al.] // Proceedings of the 5th Workshop on Complex Networks CompleNet. 2014. P. 189-197.
  12. Even S., Goldreich O. The Minimum Length Generator Sequence is NP-Hard // Journal of Algorithms. 1981. Vol. 2. P. 311-313.
  13. Vaughan-Lee M. The restricted Burnside problem. Oxford : Clarendon Press, 1990. 209 p.
  14. Кузнецов А. А. Графы Кэли бернсайдовых групп периода 3 // Сибирские электронные математические известия. 2015. Т. 12. С. 248-254.
  15. Кузнецов А. А., Кузнецова А. С. Параллельный алгоритм для исследования графов Кэли групп подстановок // Вестник СибГАУ. 2014. № 1 (53). С. 34-39.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML

© Кузнецов А.А., Кузнецова А.С., 2016

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.

Данный сайт использует cookie-файлы

Продолжая использовать наш сайт, вы даете согласие на обработку файлов cookie, которые обеспечивают правильную работу сайта.

О куки-файлах