Перспективные топологии многопроцессорных вычислительных систем, основанные на графах Кэли, заданных группами периода 4

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