The 8 reference contexts in paper E. Monakhova A., O. Monahov G., О. Монахов Г., Э. Монахова А. (2016) “Улучшение характеристик класса регулярных сетей с помощью алгоритма эволюционного синтеза // Regular Network Class Features Enhancement Using an Evolutionary Synthesis Algorithm” / spz:neicon:technomag:y:2014:i:0:p:273-283

  1. Start
    3296
    Prefix
    Циркулянтные графы (сети) являются графами Кэли абелевых групп и находят широкое применение при построении и анализе топологий сетей и мультипроцессорных систем, в теории кодирования, распределенных вычислениях, моделировании химических реакций
    Exact
    [1-7]
    Suffix
    . Диаметром графа Gназывается  , max, i j V d Gd i j   где ,d i j - длина кратчайшего пути из вершины i в вершину j графа G. Средним диаметром графа порядка N называется ,, 1 ( , ). (1) av i j V i j dd i j NN    Еще одним показателем для оценки и сравнения топологий сетей (параллельных архитектур, кластерных систем) является ширина бисекции графа
    (check this in PDF content)

  2. Start
    5710
    Prefix
    Пример циркулянтной сети и гиперциркулянтной сети (с двумя классами - четных и нечетных вершин) приведен на рис. 1. Заметим, что класс гиперциркулянтных сетей является подклассом более общего класса ( , )sR N v графов
    Exact
    [1, 8]
    Suffix
    . Отметим также, что, в отличие от циркулянтных сетей, где каждая вершина имеет ребра с одинаковым множеством образующих, в гиперциркулянтных сетях у разных классов вершин может быть разный набор образующих.
    (check this in PDF content)

  3. Start
    6578
    Prefix
    Будем синтезировать оптимальные гиперциркулянтные сети на основе оптимальных циркулянтных сетей с меньшей степенью вершин. Для построения оптимальной гиперциркулянтной сети ( , ,{ }, )imHC N v lk будем использовать циркулянтную сеть C N S; из известных оптимальных семейств
    Exact
    [2,9,10]
    Suffix
    циркулянтных сетей размерности n , с требуемым числом вершин N, с меньшей степенью вершин 2pn v. При этом, множество образующих S циркулянтной сети будет использовано как подмножество образующих гиперциркулянтной сети (для всех классов вершин - одинаковое), а недостающие vp образующих (для каждого класса вершин - свои) будут синтезироваться с помощью оп
    (check this in PDF content)

  4. Start
    7952
    Prefix
    , в использовании в качестве базовых структур (темплейтов) для построения гиперциркулянтов - оптимальных семейств циркулянтных сетей меньшей размерности, и, в-третьих, в применении алгоритма эволюционного синтеза для поиска оптимальных гиперциркулянтов на основе темплейтов. Можно отметить связь нашего подхода с подходом к построению сетей "малого мира"
    Exact
    [11]
    Suffix
    , когда введение некоторой нерегулярности сети приводит к существенному улучшению ее характеристик (таких как диаметр и средний диаметр). 1. Алгоритм эволюционного синтеза оптимальных регулярных сетей Основными методами, используемыми для построения регулярных сетей с минимальным диаметром и/или минимальным средним расстоянием являются локальный поиск, а также переборные и эвристичес
    (check this in PDF content)

  5. Start
    12284
    Prefix
    Предельное число итераций равно 1000, размер популяции изменялся в диапазоне 10 - 100, mutp=0.15, crosp=0.7, указанные параметры выбирались экспериментальным путем. Эволюционный синтез гиперциркулянтов проводился на основе известного
    Exact
    [9,10]
    Suffix
    оптимального семейства двумерных циркулянтных сетей с описанием: ;1,sCN, где N22,41,1(mod 2),2.d sddd   Отметим, что данные результаты были получены на ресурсах Сибирского Суперкомпьютерного центра в ИВМиМГ СО РАН.
    (check this in PDF content)

  6. Start
    12928
    Prefix
    Порядки циркулянтов и гиперциркулянтов в табл. 1 и 2 являются наиболее близкими к числу вершин соответствующих торов. Для сравнения в данных таблицах выбирались известные семейства оптимальных циркулянтов размерности три и четыре
    Exact
    [12]
    Suffix
    . Диаметр k-мерного, 2k, тора с числом вершин 1 k i i Nl   равен 12 k i i l D  dt . Известно, что торы дают меньший диаметр и лучшую производительность, если число вершин в каждом направлении одинаково, то есть ill для всех 1, 2,...,ik.
    (check this in PDF content)

  7. Start
    13479
    Prefix
    В этом случае диаметр тора равен /2D k ldt, а средний диаметр - 2 / 4 av l dk ldt. Точное значение ширины бисекции для k-мерных торов общего вида 12(), ,...,kkl llT, которые имеют il вершин вдоль размерности i для 1, 2,...,ik и где 12...klll  , найдено в
    Exact
    [13]
    Suffix
    : 12 () , ,..., 11 ()2,k k k l llj ij i BW Tl      где  - наименьший индекс, для которого il - четное число (k, если такого индекса нет). Для многомерных циркулянтных и гиперциркулянтных графов в табл. 1 и 2 оценка ширины бисекции получена с помощью программы Mathematica 10.
    (check this in PDF content)

  8. Start
    14507
    Prefix
    Таким образом, оптимизация гиперциркулянтных сетей размерности три является более эффективной, чем введение дополнительной размерности для соответствующих тороидальных структур. Отметим также лучшие структурные показатели у гиперциркулянтных сетей по сравнению с перспективными iBT-сетями, предложенными в
    Exact
    [14]
    Suffix
    для петафлопсных суперкомпьютеров на основе попеременного дополнения тороидальных структур циркулянтными связями. Например, iBT-сеть при степени 8 и числе вершин N= 32400 имеет d=12, avd =7.515, BW=7200, а у гиперциркулянтов при степени 8 и числе вершин N= 32258 имеем d=10, avd =7.23, BW=15852.
    (check this in PDF content)