USING HIGH-PERFORMANCE COMPUTATIONS FOR STUDYING MODIFIED BUBBLE-SORT GRAPHS

Full Text

Введение. Определение графа Кэли было дано известным английским математиком Артуром Кэли в XIX веке для представления алгебраической груп- пы, заданной фиксированным множеством порож- дающих элементов. В последние десятилетия теория графов Кэли раз- вивается как отдельная большая ветвь теории графов. Графы Кэли находят применение как в математике, так и за ее пределами. Эффективное применение гра- фы Кэли нашли в информационных технологиях после пионерской работы 1986 года С. Эйкерса и Б. Кришнамурти [1], которые впервые предложили применять указанные графы для представления ком- пьютерных сетей, в том числе для моделирования топологий многопроцессорных вычислительных сис- тем (МВС) - суперкомпьютеров. С тех пор данное направление активно развивается [2-11]. Это связано с тем, что графы Кэли имеют много привлекательных свойств, из которых стоит отметить их регулярность, вершинную транзитивность, малые диаметр и степень при достаточно большом количестве вершин в графе. Например, такие базовые топологии сети, как «коль- цо», «гиперкуб» и «тор», являются графами Кэли. Напомним определения основных терминов, используемых в работе. Пусть X - порождающее множество группы G, т. е. большое количество вершин, необходимо применять G = X . Графом Кэли G = Cay (G, X ) = (V , E ) назы- вают ориентированный граф, обладающий следую- МВС. Пусть Sn = Xn щими свойствами: a) множество вершин V(Г) соответствуют элемен- там группы G; б) множество ребер E(Г) состоит из всех упорядо- ченных пар (g, xg), где g Î G и x Î X . симметрическая группа, порожденная множеством транспозиций Xn . Граф Кэли BSn = Cay(Sn , Xn ) называют графом пузырьковой сортировки (bubble- sort graph) [5]. Свойства данного графа хорошо известны [5] , в частности, В дальнейшем будем считать порождающее мно- жество X симметричным и свободным от единичного элемента группы, т. е. x Î X Þ x-1 Î X и e Ï X . (S ) = n(n -1) D n X n 2 и DXn D S (S ) = X ( n ) . n n 2 Поскольку X является свободным от единичного эле- Пусть теперь Sn = Xˆ n , где Xˆ n = Xn È{(1, n)} . мента, то граф Г не содержит петель. Симметричность порождающего множества означает, что граф будет Граф Кэли MBSn = Cay (Sn , Xˆ n ) называют графом неориентированным и без кратных ребер, т. е. если в графе имеется ребро из g в xg, то оно совпадает с ребром из xg в x-1 ( xg ) = g . модифицированной пузырьковой сортировки (modified bubble-sort graph) [5]. На сегодняшний день известны характеристики данного графа только для n £ 13 . В работе [14] получено, что Таким образом, Г = Cay(G, X ) = (V , E) , где V = G ê n2 ú n2 - n +1 и E = {{g, xg} g Î G, x Î X } . Количество вершин | V | равно порядку группы G. Граф Кэли является регулярным, и его степень s, т. е. количество ребер, выходящее из каждой вершины, рав- но числу порождающих элементов группы: s = | X | . Шаром Ks радиуса s группы G будем называть множество всех ее элементов, которые могут быть представлены в виде групповых слов в алфавите X DXˆn (Sn ) = ê 4 ú и DXˆn (Sn ) = 6 при n £ 13 . ë û В настоящей работе представлена модифициро- ванная версия алгоритма A-I из [15], на основе кото- рого при помощи суперкомпьютерных вычислений получены ранее неизвестные характеристики MBSn- графов для n = 14 и 15. Алгоритм A-I Вход: конечная группа длиною, не превышающей s. Для каждого целого неотрицательного s можно определить функцию роста группы F(s), которая будет равна числу элементов = {x1, x2,..., xm} - порождающее множество G. Выход: диаметр DX (G) , средний диаметр группы G относительно X, представимых в виде несографа Кэли G = Cay(G, X ) , а также функция роста кратимых групповых слов длиною s. Таким образом, F(s) группы G, где 0 £ s £ DX (G) . F (0) = | K0 | = 1, F (s) = | Ks | - | Ks -1 | при s Î N . 1. s = 0, K0 = {e} , F (0) = 1 , P = K0 . Как правило, функцию роста конечной группы представляют в виде таблицы, в которую записывают ненулевые значения F(s). Отметим также, что при вычислении функции рос- та группы мы параллельно выясняем характеристики соответствующего графа Кэли, например, такие как диаметр и средний диаметр [12]. Пусть F (s0 ) > 0 , но F (s0 +1) = 0 , тогда s0 будет являться диаметром графа Кэли группы G в алфавите порождающих X, который мы будем обозначать DX (G) . Соответственно, сред- ний диаметр DX (G ) равен средней длине минималь- 2. s = s +1 . 3. Ks = Ks-1 . 4. "x Î X и "p Î P : 4.1. g = x o p ; 4.2. если g Î Ks , то K 5. P = Ks - Ks-1 . 6. F (s) = | P | . 7. 1 0 Если F (s) > 0 , то переход п. 2; иначе переход п. 8. 8. DX (G) ных (несократимых) групповых слов. Вычисление диаметра графа Кэли большой конечной 9. Выход. s=0 группы является хотя и разрешимой, но весьма слож- ной проблемой. Это связано с тем, что в общем случае задача по определению минимального слова в группе, как показали С. Ивен и О. Голдрейх в 1981 году [13], является NP-трудной (nondeterministic polynomial). Таким образом, в наихудшем случае количество эле- ментарных операций, которые необходимо выполнить для решения указанной задачи, представляет собой экспоненциальную функцию от |X|. Поэтому для эф- фективного решения задач на графах Кэли, имеющих В [15] доказана корректность алгоритма A-I, а также получено, что T (| G |) ÎQ(| G |2 ) при | X |=| G | , где T (| G |) - вычислительная сложность алгоритма A-I и Q - одновременно верхняя и нижняя асимпто- тическая оценка сложности. Для снижения вычислительной сложности требуется способ для нумерации элементов [15]. Пусть g = (a1, a2 , K, an ) - произвольная перестановка из Sn. Используя факториальную систему счисления можно однозначно определить номер перестановки (при этом нумерация будет начинаться с нуля). Определим биективное отображение j следующего вида: Подпись: n g ¾j® ng = åbkk ! k =1 сток алгоритма можно легко распараллелить. В этом случае сначала параллельно вычисляются все произ- ведения g, а затем для каждого элемента получивше- гося массива последовательно выполняется п. 4.2. Исследование MBS-графов. Модифицированный алгоритм A-I был реализован на языке С++ и апроби- рован на 96-ядерном сервере суперкомпьютера СФУ, Здесь ng представляет собой целое неотрицательпри этом было задействовано 512 Гб оперативной памяти и 8 Тб дискового пространства. В результате ное число, записанное в факториальной системе счисления, при этом коэффициент bk при множителе k ! были вычислены функции роста групп S14 = Xˆ14 будет обозначать число инверсий для элемента ak +1 и S15 = Xˆ15 . Затраченное на расчеты время равно в том множестве, в котором производятся перестановки (количество элементов, меньших ak +1 , но стоящих правее его в рассматриваемой перестановке). Легко примерно 2,5 часа для n = 14 и 46 часов для n = 15. В табл. 1, 2 приведены функции роста групп S14 и S15 , а на рис. 1, 2 - их графики. Из табл. 1, 2 следует, что увидеть, что ng пробегает все значения от 0 до n!-1 . 142 142 -14 +1 Модифицируем алгоритм A-I следующим обра- зом. В п. 1 добавим булев вектор V, размерностью n!, DXˆ14 (S14 ) = 49 = , 4 DXˆ14 (S14 ) = 30 1 = , 2 6 все элементы которого первоначально равны 0. Для удобства индексация элементов V начинается с 0. DXˆ15 (S15) ê152 ú = = 56 ê 4 ú , Ввиду того, что K0 = {e} и j(e) = 0 , запишем V0 = 1 . Заменим п. 4.2 алгоритма A-I на следующий: 4.2. если Vng = 0 , то Vng = 1 и Ks = Ks È{g} . DXˆ15 (S15 ) = 35 1 = ë û 152 -15 +1 . 6 6 Поскольку сложность процедуры перевода пере- Таким образом мы можем расширить результат из [14]: становки в число и обратно равна Q(1) , то согласно Теорема. Пусть Sn = Xˆ n и n £ 15 . Тогда верно, [15] сложность модифицированного алгоритма A-I будет равна Q(| G |) . Также отметим, что в п. 4.1 все элементы g вычисчто ë û ê n2 ú n2 - n +1 ляются независимо друг от друга, поэтому этот уча- DXˆn (Sn ) = ê 4 ú и DXˆn (Sn ) = 6 . Функция роста группы S14 в алфавите Xˆ14 Таблица 1 s F(s) s F(s) s F(s) s F(s) s F(s) 0 1 10 1144066 20 523576508 30 7875671024 40 439630193 1 14 11 2496144 21 807898884 31 8184285564 41 177894717 2 105 12 5200300 22 1206399194 32 8059876006 42 59073300 3 560 13 10399573 23 1741769068 33 7486458696 43 15497794 4 2380 14 20044817 24 2428791549 34 6521589932 44 3095274 5 8568 15 37346764 25 3266926299 35 5291298298 45 457459 6 27132 16 67385500 26 4232447674 36 3964966720 46 46501 7 77520 17 117857285 27 5272211438 37 2715665810 47 2912 8 203490 18 199872075 28 6301765938 38 1678335828 48 93 9 497420 19 328616470 29 7210522410 39 920955932 49 1 |S14|=14!=87178291200 Функция роста группы S15 в алфавите Xˆ15 Таблица 2 s F(s) s F(s) s F(s) s F(s) s F(s) 0 1 12 9657700 24 8330511890 36 111514773216 48 723446997 1 15 13 20058300 25 12267072742 37 108665304904 49 217500207 2 120 14 40115312 26 17570631028 38 100844738930 50 52359036 Окончание табл. 2 s F(s) s F(s) s F(s) s F(s) s F(s) 3 680 15 77540544 27 24463138336 39 88757487936 51 9748102 4 3060 16 145284325 28 33079985068 40 73721997284 52 1343342 5 11628 17 264439921 29 43405123242 41 57447140400 53 126700 6 38760 18 468283120 30 55204143800 42 41700857614 54 7282 7 116280 19 807550010 31 67970322498 43 27958028594 55 210 8 319770 20 1356808058 32 80902850743 44 17132134736 56 2 9 817190 21 2221351570 33 92936928305 45 9472716396 10 1961256 22 3543440716 34 102839910030 46 4651580804 11 4457400 23 5505931806 35 109374995290 47 1989274794 |S15|=15!=1307674368000 Рис. 1. График функции роста группы S14 Fig. 1. Graph of group growth function Рис. 2. График функции роста группы S15 Fig. 2. Graph of group growth function Заключение. Применение высокопроизводитель- ных вычислений позволило продвинуться в изучении свойств MBSn-графов. Несмотря на это, представить аналитическое решение для произвольного n на сего- дняшний день не представляется возможным.

About the authors

A. A. Kuznetsov

Reshetnev Siberian State University of Science and Technology

Email: kuznetsov@sibsau.ru
31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

V. V. Kishkan

Reshetnev Siberian State University of Science and Technology

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

References

Supplementary files