2 / 13
Г.П. Можаров
42
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 6
казоустойчивых и надежных КСС [3, 5−8]. Наиболее значимые исследования
посвящены анализу и реализации комбинаторных дискретных структур (вклю-
чая КСС), имеющих специфические свойства: высокие отказоустойчивость и
производительность.
Разработка топологий КСС, оптимальных с точки зрения их связности, струк-
турной надежности и отказоустойчивости, является важной и актуальной задачей
[2, 3, 7, 9]. Изучение влияния топологии на процессы, протекающие в КСС, поз-
воляет на самых ранних этапах проектирования получать информацию, имею-
щую принципиальное значение для дальнейших этапов проектирования.
Однако до настоящего времени не существует единой научной методологии по
синтезу отказоустойчивых (имеющих способность к постепенной деградации
структуры) КСС, топология которых может быть представлена циклическим гра-
фом [3, 5, 9]. Практическое использование существующих алгоритмов и моделей
отказоустойчивых КСС обычно приводит к «переупрочненным» вариантам по-
строения циклических КСС и сетей с произвольной структурой [5, 9, 10−13].
В настоящей работе рассмотрен новый класс КСС, использующий для своего
построения комбинаторные уравновешенные неполные блок-дизайны (блок-
дизайн традиционно назывался блок-схемой, однако в настоящее время в связи с
появлением в активном лексиконе русского языка слова «дизайн» представляется
более правильным приводить дословный перевод этого термина: «блок-дизайн»
(
block design
) [1]). Подобные сети хорошо структурированы, имеют высокие отка-
зоустойчивые свойства и свободный параметр, позволяющий согласовывать про-
изводительность и стоимость сети при ограничениях на затраты.
При малом числе узлов (процессоров) и ребер (линий связи) проблема вы-
бора оптимальной топологии КСС решается различными эвристическими ме-
тодами локальной оптимизации. Однако тенденция развития КСС ведет к фор-
мированию топологий, включающих в себя многочисленные узлы и линии свя-
зи. Оптимизация таких топологий с помощью только эвристических методов
может встретиться со значительными вычислительными трудностями [2−6].
В этой связи представляют интерес развитие и использование регулярных мето-
дов анализа и синтеза топологий КСС, основанных на свойствах дискретных
структур и взаимосвязей между комбинаторными объектами различных типов:
матрицами со специальными свойствами, частично упорядоченные множества,
комбинаторные блок-дизайны, ортогональные массивы и трансверсальные ди-
зайны, конечные геометрии и др.
Коммуникационная компьютерная сеть должна соединять (при ограничен-
ном количестве вычислительных ресурсов) большое число процессоров и удо-
влетворять следующему перечню основных требований: иметь малую валент-
ность (небольшое число портов в процессоре); обеспечить простоту, малые за-
траты времени и памяти алгоритма маршрутизации в сети; иметь малую сред-
нюю длину пути; низкую стоимость связи; высокую отказоустойчивость; иметь
возможность постепенной деградации.