Новые семейства мультипликативных циркулянтных сетей | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/8

Новые семейства мультипликативных циркулянтных сетей

Рассматривается задача оптимизации циркулянтных сетей, состоящая в максимизации числа вершин при заданных степени и диаметре графа. На основе изучения мультипликативных циркулянтов с образующими, представленными в виде степеней нечётных чисел t ^ 5, построены два новых семейства мультипликативных циркулянтов нечётных размерностей k ^ 3 и диаметров d = 0 mod k и чётных размерностей k ^ 4 и диаметров d = 0 mod k и d = 0 mod k/2, графы которых превосходят по числу вершин при тех же размерностях и диаметрах известные семейства мультипликативных циркулянтов.

New families of multiplicative circulant networks.pdf 1. Введение и основные определения Пусть s1, s2,..., sk, n - целые числа, такие, что 1 ^ s1 < s2 < ... < sk < n. Граф C с множеством вершин V = {0,1,... ,n - 1} и множеством рёбер E = {(i, j) : i - j = = sj mod n, / = 1,..., k}, называется циржулянтным, числа S = (s1, s2,..., sk) -образующими, (n; S) -его параметрическим описанием, k - размерностью, n - порядком Исследование выполнено в рамках проекта № 0315-2016-0006. графа. Циркулянтные графы являются вершинно-транзитивными. Степень циркулянта равна 2k, если Sk = n/2. При чётном n и Sk = n/2 циркулянт имеет степень 2k - 1. В данной работе рассматриваются только связные циркулянтные графы чётных степеней. Известно, что циркулянтный граф C(n; s1, s2,... , Sk) является связным, если и только если наибольший общий делитель чисел s1, s2, ..., Sk, n равен 1. Циркулянтные сети (графы) широко изучаются при проектировании и анализе вычислительных систем, в теории графов и дискретной математике, в качестве топологии мультипроцессорных систем и компьютерных сетей и для других применений [1-3]. Интересным представляется новое направление использования циркулянтных сетей в центрах обработки информации больших баз данных [4]. Циркулянтные сети C(n; 1,t,t2,... ,tk-!) с образующими, представленными в виде степеней натурального числа t ^ 2, называются мультипликативными циркулянтами. Следует отметить, что мультипликативные циркулянтные сети имеют простые коммуникационные алгоритмы, эффективны относительно трассировки интегральных схем, живучести и отказоустойчивости и поэтому могут использоваться в качестве структур сетей связи суперкомпьютерных систем. Диаметром графа C называется d(C) = maxd(i,j), где d(i,j) -длина кратчайi,jev шего пути из вершины i в вершину j графа C. Для любых натуральных d и k пусть M(d, k) обозначает максимально возможное (достижимое) натуральное n, такое, что существует множество образующих S = (1,s2,...,sk), при котором d(C (n; S)) ^ d. В [1, 2] можно найти обзоры результатов по оценкам диаметра и достижимого порядка k-мерных, k ^ 2, циркулянтных сетей. Приведём известные результаты, касающиеся оценок диаметра и достижимого порядка k-мерных, k ^ 2, циркулянтных сетей. k-1 В [5] показано, что M(d, k) ^ 1+ Cjki2k-i, получена нижняя граница диаметра i=0 для любых n и k порядка -(k!)1/kn1/k и доказана Теорема 1. Циркулянтные сети вида C(n; 1, t, t2,... ,tk-1), где n = tk и t ^ 3 - нечётное число, имеют диаметр d = k|_t/2_|. Для k = 2 задача построения семейств двумерных циркулянтов с единичной образующей и максимально возможным порядком при любом диаметре d решена (см., например, обзор в [1]). Найдена [6, 7] функция M(d, k) для k = 3 и любого диаметра d и аналитически построены семейства трёхмерных циркулянтов с порядком, совпадающим с M(d, 3). Для k = 4 наилучшие известные оценки функции M(d, 4) аналитически найдены с помощью компьютерного поиска в [8]. В [9, 10] авторы представили таблицу, содержащую свод самых больших известных циркулянтных сетей, найденных в литературе для ряда значений степеней и диаметров. Таблица рекордных циркулянтов включает в том числе ряд значений порядков графов, полученных на основании перечисленных аналитических результатов для размерностей 2, 3 и 4, а также результаты для нечётных степеней, найденные в [7, 8, 10]. В настоящее время таблица рекордных циркулянтных сетей для k ^ 8 и d ^ 10 представлена в Интернете [11] и постоянно обновляется. Изучение мультипликативных циркулянтов, начатое в работе [5], продолжалось в последующие годы. Результаты теоремы 1 улучшены в [12]: Теорема 2. Пусть d и k - натуральные числа, d ^ k ^ 3 и p = L(d - k + 3)/kJ. Тогда k-1 1 / 4\ k M(d, k) ^ n = 2pE (4p)^ = - у dk + O(dk-1). i=0 2 V k / На основе теоремы 2 в [12] построены семейства мультипликативных циркулянтов с большим числом вершин, чем в [5], при тех же размерностях и диаметрах. В [13, 14] рассмотрены свойства мультипликативных циркулянтных сетей вида C(n; 1, t,... , tk-1) с нечётным t ^ 3 и 2tk-1 < n ^ tk и получена общая формула для верхней оценки диаметра: d(n; 1, t, t2,..., tk-1) ^ (k - 1) Lt/2J + [(n - tk-1)/(2tk-1)]. В [15] исследованы свойства мультипликативных циркулянтов вида C(n; 1,t,... ,tk-1) с n = tk и чётным t ^ 2 и получен их диаметр: d(tk ;1,t,t2,...,tk-1) = kt/2 - Lk/2J. Показано также, что мультипликативные циркулянтные сети как графы с образующими, представленными в виде степеней целого числа, имеют простые алгоритмы парного [13, 15] и трансляционного обменов [15], эффективны относительно трассировки интегральных схем, живучести и отказоустойчивости [13, 14]. В [16] получены новые улучшенные оценки для M(d, k): d - Lk/4J k M(d,k) ^ n = < где d и k > 4 - целые числа, такие, что Теорема 3. Пусть p d ^ k + Lk/4J. Тогда k-1 2p Е (4p)\ если kp + Lk/4J ^ d < kp + Lk/2J, i=0 k-1 (2p + 1) E (4p + 1)\ если kp + Lk/2J ^ d < k(p +1), i=0 k1 (2p + 2) E (4p + 3)\ если k(p +1) ^ d < k(p + 1) + Lk/4J. i=0 В настоящей работе продолжено исследование нижних оценок экстремальной функции M(d, k) и получение их аналитических выражений при любых размерностях k > 4. На основе изучения циркулянтов с образующими, представленными в виде степеней нечётных чисел t ^ 5, получены аналитически новые нижние оценки достижимого числа вершин циркулянтных сетей размерностей k > 4 и построены соответствующие семейства мультипликативных циркулянтов, реализующих эти оценки. 2. Новые семейства мультипликативных циркулянтных сетей Для мультипликативных циркулянтов размерностей k = 4 и 5 проведены дальнейшие исследования сетей, рассмотренных в работах [5, 15, 16]. С помощью компьютерного поиска исследованы диапазоны их существования и определено максимальное значение порядка графа, при котором значения диаметров и образующих совпадают с найденными в [5, 15, 16]. Полученный результат позволил улучшить порядки графов по сравнению с известными результатами [5, 12, 15, 16]. Анализ значений подмножеств найденных максимально возможных порядков графов мультипликативных циркулянтов размерности 5 (табл. 1) послужил основой теоретического обобщения полученных результатов для любых размерностей. В табл. 1 использованы следующие обозначения: d - диаметры найденных мультипликативных циркулянтов; n - их порядки; t - параметр, порождающий соответствующие множества образующих графа S = (1,t,t2,t3 ,t4). Таблица 1 Новые циркулянтные графы размерности 5 k = 5 d n t d n t d n t 6 682 4 15 111271 11 24 1245289 19 7 2343 5 16 137598 12 25 1505931 19 8 4399 7 17 216587 13 26 1692610 20 9 8803 7 18 282053 15 27 2246255 21 10 13605 7 19 383303 15 28 2671209 23 11 22820 8 20 484553 15 29 3230891 23 12 36905 9 21 563592 16 30 3790573 23 13 52707 11 22 798669 17 31 4168812 24 14 81989 11 23 984647 19 32 5289713 25 Рассмотрим множество мультипликативных циркулянтных сетей вида C(n; 1, t, t2, ... ,tk-1), k ^ 3, с нечётным t ^ 5. В теореме 4 представлены два новых бесконечных семейства рассматриваемых сетей, которые улучшают известные оценки достижимого порядка циркулянтных графов. Далее D(x), 0 ^ x < n, обозначает длину кратчайшего пути из вершины 0 в вершину x. Теорема 4. Пусть k ^ 3, t ^ 5 - нечётное число, S = (1, t, t2,..., tk-1). Если k-1 n = ft/21 £ t + tk-1, (1) i=0 то d(n; S) = M^p) (2) при следующих условиях: k ^ 3 - нечётное число и t = 3 mod 4 (3) или k ^ 4 - чётное число. (4) Доказательство. Рассмотрим циркулянтный граф C(n; 1, t, t2,..., tk-1), где t ^ 5 - нечётное число и значение n удовлетворяет (1). Заметим, что все вершины графа образуют замкнутый цикл 0,1,... , n - 1, 0. Возьмём любую вершину 0 ^ x < n рассматриваемого графа. Определим c0, такое, что c0 = x mod t и |c0| ^ ft/2 J. Для любых i = 1,... , k - 1 определим q, такие, что Вычисленные таким образом коэффициенты c, i = 0,... , k-1, являются координатами пути из вершины 0 в x, а именно: |q| определяет, сколько раз в пути из вершины 0 в x использовалась соответствующая образующая, а знак (+ или -) у c указывает направление движения по соответствующей образующей. Обозначим длину этого пути k-1 через D+(x). Имеем D+(x) = £ |q|. i=0 Второй возможный путь из 0 в x определим, взяв разность x - n. Учитывая (1), fc-1 имеем x - n = £ c^, где ci = c - |~t/2] для i = 0,..., k - 2 и c'fc_ 1 = ck-1 - |~t/2] - 1. i=0 В дальнейшем с помощью алгоритма 1 преобразуем коэффициенты ci в ci' таким образом, чтобы выполнялось условие |ci'| ^ |_t/2J, i = 0,... , k - 2. Преобразованные коэффициенты ci', i = 0,... , k - 1, являются координатами второго возможного пути из k-1 вершины 0 в x. Обозначим длину этого пути через D-(x). Она равна D-(x) = £ |ci' |. i=0 4 Для любой вершины 0 ^ x < n длина кратчайшего пути D(x) ^ min{D+(x),D-(x)}. Пусть значение выполнено (1). Покажем, что диаметр d графа C(n; 1, t, t2,... , tk-1) удовлетворяет (2). Для этого докажем, что для любой вершины 0 ^ x < n при выполнении как условия (3), так и условия (4) D+(x) + D-(x) ^ k|"t/2] + 1 = 2d +1. Далее последовательно для i = 0, 1, . . . , k - 1 выполняем преобразование коэффициентов ci в ci' и подсчитываем суммы |ci| + | ci' | (алгоритм 1). На рис. 1 приведена граф-схема алгоритма 1, где T = |~t/2]. Суммируя результаты выполнения алгоритма 1 и анализируя все возможности k обходов по данной граф-схеме (соответственно k образующим), получаем для любой вершины 0 ^ x < n £(Ы + |ci'|) ^ k|~t/2] + 1 = kT + 1 = 2d + 1. i=0 Следовательно, или D+(x) ^ d, или D-(x) ^ d. Покажем, что в данном графе существует хотя бы одна такая вершина x, что D(x) = d. Рассмотрим два возможных варианта. Случай (3). Пусть k ^ 3 - нечётное число и t = 3 mod 4. В качестве искомой t + 1 k-1 . t + 1 fc-2 . t + 5 вершины возьмём x0 = -£ ti. Имеем x0 - n =--£ ti--tk-1. Таким 4 i=0 4 i=0 4 образом, k-1 |ci| = + k = d и Y1 |ci'| = + (k - 1) +-+5 = + k + 1 = d + 1. i=0 i 4 i=0 i 4 4 4 Рассмотрение длин альтернативных путей из 0 в x0 показывает, что они не меньше d. Следовательно, D(x0) = d. Алгоритм 1. Алгоритм преобразования коэффициентов Вход: параметр t; коэффициенты c и ci для i = 0,... ,k - 1. Выход: суммы |ci| + |c£'|, i = 0,... , k - 1. 1: i = -1. 2: Увеличить i на 1. Положить ci' = ci. 3: Если i < k - 1 и c ^ 0, то заменяем С на ci' = ci' + t. Очевидно, при такой замене сумма |ci'| + |ci'+1| не увеличивается по сравнению с суммой |ci| + |ci+1| (соответственно в последующем будет замена c'i+1 на ci'+1 = ci+1 - 1). При этом 0 ^ ci' ^ _t/2j и |ci| + |ci'| = ft/2] -1, перейти в п. 8. 4: Если i = k - 1, то 5: из условия 0 ^ ck-1 ^ ft/2] + 1 следует - ft/2] - 1 ^ c'k_ 1 = c'k_ 1 ^ 0 и |ck-1| + + |ck_ 1| = ft/2] + 1, перейти в п. 15. 6: Если i < k - 1 и ci > 0, то 7: |ci| = |ci - ft/2]| ^ Lt/2j. Тогда |ci| + |c£'| = \t/2], перейти в п. 2. 8: Увеличим i на 1 и положим ci = ci - 1. 9: Если i = k - 1, то 10: |ck-1| + |ck-1| = ft/2] + 2, перейти в п.15. 11: Если ci > 1 , то 12: |ci| + |ci'| = ft/2] + 1, перейти в п. 2. 13: Если ci ^ 1, то 14: заменяем ci' на новое значение ci' = ci' +1 (соответственно в последующем будет замена ci+1 на d(+1 = di+1 - 1). При этом -1 ^ ci' ^ |_t/2J и ft/2] - 2, если - ft/2] +2 ^ ci ^ 0, ft/2], если ci е {-ft/2] +1,1}, перейти в п.8. 15: Конец алгоритма. Рис. 1 Случай (4). Пусть k ^ 4 - чётное число и t = 1 mod 4. В качестве искомой вершины возьмём Х0 = ^ + t + ^ t2 + t3 + ... + ^ tk-2 + tk-1. Имеем xo - n = -1 - - t - t2 - -t3 - ... - tk-2 - - tk-1. 0 2 2 2 k-1 k-1 Таким образом, E Ы = k/2((t - 1)/2 + 1) = d и £ |c£'| = k/2((t - 1)/2 + 1) + 1 = d +1. i=0 i=0 Длины всех других возможных путей из 0 в x0 не меньше d. Следовательно, D(x0) = d. Случай, когда k ^ 4 - чётное число и t = 3 mod 4, доказывается аналогично случаю (3). ■ В табл. 2 показан результат сравнения известных семейств мультипликативных циркулянтов с полученными в работе. Здесь n1, n2 и n - порядки графов, найденных соответственно посредством теорем 2 [12], 3 [16] и 4. Таблица 2 Сравнение семейств мультипликативных циркулянтов k = 5 k = 6 d ni n2 n t d ni n2 n t 10 682 11204 13 605 7 9 2 730 11718 14 843 5 15 18 724 96 630 111271 11 12 2 730 78 432 95 239 7 20 135 726 433 928 484 553 15 15 149 796 332 150 391199 9 25 559 240 1375 610 1505 931 19 18 149 796 1 062 936 1223 987 11 30 244 210 3 510 732 3 790 573 23 21 1628 718 2 815 638 3186 931 13 Поясним на примерах результат сравнения двух новых семейств с известными семействами мультипликативных циркулянтов. 1. Пусть k = 5 и d =25. Тогда в силу теоремы 2 имеем M(d, 5) ^ n = 559 240. Теорема 3 даёт следующую оценку: M(d, 5) ^ n = 1375 610. Новое семейство при том же диаметре даёт оценку M(d, 5) ^ n = 1505 931. Данный порядок циркулянта достигается при образующих S = (1, t, t2, t3, t4), где t = 19. 2. Пусть k = 6 и d =18. Тогда в силу теоремы 2 M(d, 5) ^ n = 149 796. Теорема 3 даёт следующую оценку: M(d, 5) ^ n = 1 062 936. Новое семейство при диаметре d =18 даёт оценку M(d, 5) ^ n = 1 223 987. Данный порядок циркулянта достигается при образующих S = (1,t,t2,t3,t4,t5), где t = 11. С помощью специально разработанной компьютерной программы показано, что порядки графов новых семейств мультипликативных циркулянтов являются максимально возможными для исследуемых типов образующих при диаметрах d ^ 22 и 20 и размерностях соответственно k = 4 и 5. Для дальнейшей работы представляет интерес возможность доказательства обобщения данного результата для любых размерностей и диаметров. Таким образом, полученная в настоящей работе оценка функции M(d, k), подтверждённая конструктивно построением семейств мультипликативных циркулянтных сетей, для размерностей k ^ 5 (чётных степеней 10 и более) остается пока лучшей известной оценкой.

Ключевые слова

мультипликативные циркулянтные сети, диаметр, максимальный порядок графа, multiplicative circulant networks, diameter, maximum order of a graph

Авторы

ФИООрганизацияДополнительноE-mail
Монахова Эмилия АнатольевнаИнститут вычислительной математики и математической геофизики СО РАНкандидат технических наук, доцент, старший научный сотрудникemilia@rav.sscc.ru
Всего: 1

Ссылки

Монахова Э. А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011. №3. С. 92-115.
Monakhova E. A. A survey on undirected circulant graphs // Discr. Math., Algorithms and Appl. 2012. No.4(1). P. 17-47.
Perez-Roses H. Algebraic and computer-based methods in the undirected degree/diameter problem - a bief survey // Electronic J. Graph Theory and Appl. 2014. No. 2(2). P. 166-190.
Erickson A., Stewart I. A., Navaridas J., and Kiasari A. E. The stellar transformation: From interconnection networks to datacenter networks // Comput. Networks. 2017. No. 113. P. 29-45.
Wong C. K. and Coppersmith D. A combinatorial problem related to multimodule memory organizations // J. Assoc. Comput. Mach. 1974. No. 21. P. 392-402.
Monakhova E. Optimal triple loop networks with given transmission delay: Topological design and routing // Intern. Network Optimization Conf. (IN0C'2003), Evry/Paris, France, 2003. P. 410-415.
Dougherty R. and Faber V. The degree-diameter problem for several varieties of Cayley graphs, 1: The Abelian case // SIAM J. Discrete Math. 2004. No. 17(3). P. 478-519.
Lewis R. The degree-diameter problem for circulant graphs of degree 8 and 9 // arXiv:1404.3948v1, 2014.
Feria-Puron R., Ryan J., and Perez-Roses H. Searching for large multi-loop networks // Elec. Notes Disc. Math. 2014. No. 46. P. 233-240.
Feria-Puron R., Perez-Roses H., and Ryan J. Searching for large circulant graphs // arXiv:1503.07357v1 [math.CO] (25 Mar 2015). P. 31.
The Degree/Diameter Problem For Circulant Graphs. http://combinatoricswiki.org/ wiki/The_Degree_Diameter_Problem_for_Circulant_Graphs.
Chen S. and Jia X. -D. Undirected loop networks // Networks. 1993. No. 23. P. 257-260.
Parhami B. Chordal rings based on symmetric odd-radix number systems // Proc. Intern. Conf. on Communications in Computing (Las Vegas, NV, June 27-30). Los Alamitos: IEEE Press, 2005. P. 196-199.
Parhami B. A class of odd-radix chordal ring networks // The CS'J J. Comput. Sci. Eng. 2006. Vol. 4. No. 2-4. P. 1-9.
Stojmenovic I. Multiplicative circulant networks. Topological properties and communication algorithms // Discr. Appl. Math. 1997. Vol.77. P.281-305.
Monakhova E. A. On an extremal family of circulant networks // J. Appl. Industr. Math. 2011. No. 5(4). P. 1-7.
 Новые семейства мультипликативных циркулянтных сетей | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/8

Новые семейства мультипликативных циркулянтных сетей | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/8