Модели и алгоритмы построения оптимальных рёберных отказоустойчивых реализаций вычислительных систем тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Судани Хайдер Хуссейн Карим

• Судани Хайдер Хуссейн Карим
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Судани Хайдер Хуссейн Карим

Введение

1 Модель рёберной отказоустойчивости

1.1 Отказоустойчивость

1.2 Основные определения

1.3 Расширения графов и отказоустойчивость

1.4 Базовый алгоритм построения рёберных расширений

2 Алгоритм построения рёберных расширений

2.1 Перебор суперграфов

2.2 Вложение

2.3 Проверка на рёберное ^-расширение

2.4 Проверка списка на наличие изоморфных копий

2.4.1 Метод прямой проверки на изоморфизм

2.4.2 Метод сравнения полных инвариантов

2.4.3 Метод отбора канонических представителей

3 Усовершенствования базового алгоритма построения минимальных рёберных ^ расширений

3.1 Влияние формы графа на основные задачи

3.2 Маршрутный код

3.3 Распознавание канонического представителя

3.4 Исследование проверки каноничности

3.5 Дерево канонических представителей

3.6 Перечисление суперграфов с ограничениями

4 Параллельные вычисления

4.1 Распараллеливание вычислений

4.2 Вычислительные эксперименты

4.2.1 Параллельная обработка потока графов

4.2.2 Построение расширений графов с заданным количеством вершин

4.2.3 Построение расширений циклов

4.3. Эффективность алгоритмов

4.4 Статистика по расширениям

Заключение

Список условных обозначений и сокращений

Список литературы

Приложение А Свидетельство о государственной регистрации программы для

ЭВМ

Приложение Б Акт о внедрении результатов диссертационной работы

Приложение В Акт об использовании результатов работы в учебном процессе . 128 Приложение Г Исходный код программы

Введение диссертации (часть автореферата) на тему «Модели и алгоритмы построения оптимальных рёберных отказоустойчивых реализаций вычислительных систем»

Введение

Актуальность темы исследования и степень её разработанности. В 1993 году Ф. Харари и Дж. Хейз предложили основанную на графах модель для исследования отказов связей в технической системе [83]. Эта модель была дальнейшим развитием модели, которую предложил Дж. Хейз в 1976 году для исследования отказов элементов технической системы [85]. Системе Е сопоставляется помеченный граф G(E), вершины которого соответствуют элементам системы Е, рёбра - связям между элементами. Если связи являются симметричными, то граф будет неориентированным графом. Если все элементы системы и связи являются однотипными, то граф будет без меток. Модель оказалась удобной для разработки отказоустойчивых вычислительных систем, где элементами являются вычислительные узлы, а связями между элементами -информационные каналы [11]. Вычислительными узлами могут быть ядра, процессоры или компьютеры. В такой системе элементы и связи, как правило, являются однотипными. Под отказом элемента системы Е понимается удаление соответствующей ему вершины из графа системы G(E) и всех связанных с ней ребер. Под отказом связи в системе Е понимается удаление соответствующего ребра (или дуги для ориентированного графа) из графа системы G(E). Много работ посвящено исследованию отказов элементов и несколько меньше работ, в которых исследуются отказы связей. В данной работе мы будет рассматривать только отказы связей.

Система Е* называется рёберной k-отказоустойчивой реализацией (edge fault tolerance) системы Е, если отказ любых k связей системы Е* приводит к графу, в который можно вложить граф системы Е. Построение рёберной k-отказоустойчивой реализации системы Е можно представить себе как введение в неё определенного числа избыточных элементов и связей. При этом предполагается, что в нормальном режиме работы избыточные элементы и связи

маскируются, а в случае отказа происходит реконфигурация системы до исходной структуры [11, 85]. На языке теории графов рёберную ^-отказоустойчивую реализацию системы Е мы будем называть рёберным ^-расширением (Р-£Р) её графа G(E). Автор работы является сотрудником Министерства науки и технологий Ирака, где занимается вопросами, связанными с облачными вычислениями и технологиями связи. Тема отказоустойчивости в этих областях является чрезвычайно важной [45-40]. Исторически вопросы отказоустойчивости вышли на передний план с появлением сложных вычислительных устройств, и первые идеи были реализованы уже в первом поколении ЭВМ [67]. Например, в ЭВМ EDVAC (1949 год) было реализовано два арифметико-логических устройства, результаты которых сравнивались. По мере усложнения вычислительной техники появлялись более сложные методы.

В 1956 году Джон фон Нейман [109] рассматривал, как построить надёжную систему из ненадёжных элементов. Прошло больше 60 лет, и за это время надёжность элементов и связей между ними очень выросла. Например, среднее время наработки на отказ современных процессоров составляет более 100 тысяч часов, обычного жёсткого диска Seagate Barracuda приближается к миллиону часов, а для серии Constellation составляет 1.4 миллиона часов [32]. Первое вычислительное устройство ENIAC использовало около 18000 вакуумных ламп, и это было самое сложное устройство своего времени, которое было чрезвычайно ненадёжным [11, 67]. Сейчас, по-видимому, самыми сложными вычислительными устройствами являются суперкомпьютеры. С 1993 года начал работать проект T0P500, который составляет рейтинг 500 самых мощных общественно известных вычислительных систем мира [107]. Рейтинг обновляется два раза в год - в июне и ноябре. Суперкомпьютер №1 в самом первом рейтинге от июня 1993 года - CM-5/1024 - имел 1024 ядра. В июне 2020 года самым мощным стал японский суперкомпьютер Фугаку с числом ядер 7 299 072 [102, 107]. Такое усложнение систем требует при разработке учитывать отказоустойчивость.

В работе [59] авторы проанализировали отчёты о работе ряда суперкомпьютеров. Анализировались ошибки всех компонент системы: оборудования, программного обеспечения, сети и среды. Интересно, что более половины ошибок приходилось на аппаратное обеспечение, причём среднее время наработки на отказ составляло от 10 до 23 часов. В работе [68] авторы указывают, что, если взять систему из 100 000 современных процессоров со средним временем наработки на отказ несколько лет, то для такой системы среднее время наработки на отказ с учётом только процессоров составит 17.3 дня. Очевидно, что нужно предусмотреть возможность для системы продолжать работу в присутствии отказа элемента или связи между элементами.

В 1971 году А. Авиженис [56] предложил два подхода для повышения надежности вычислительных систем:

1) предотвращение ошибок;

2) отказоустойчивость.

Первое направление связано с уменьшением вероятности возникновения ошибки, то есть в повышении надёжности компонентов системы. Во втором направлении используется введение в систему избыточных структур для придания ей свойств отказоустойчивости. Позднее отказоустойчивость стала рассматриваться как одна из составляющих более общего свойства -гарантоспособности системы [57].

В работе [55] отказоустойчивость определяется как обеспечение системы способностью противостоять ошибке и возможностью продолжать работу в присутствии этой ошибки. Выделяют два уровня отказоустойчивости:

1) полная отказоустойчивость - система продолжает работать в присутствии ошибок без существенной потери функциональных свойств;

2) амортизация отказов - система продолжает работать в присутствии ошибок с частичной деградацией функциональных возможностей.

В данной работе будет рассматриваться только полная отказоустойчивость. Мы будем рассматривать только отказы связей и изучать рёберные расширения

графов. Модель, в которой исследуются отказы элементов, занимается вершинными расширениями графов. Построить рёберную ^-отказоустойчивую реализацию означает добавить к исходной системе определённое количество элементов и связей. Стоимость элементов существенно выше связей, поэтому накладывается ограничение, что дополнительные элементы вводиться не могут, добавляются только дополнительные связи. На языке теории графов это означает, что при построении рёберных ^-расширений новые вершины к графу не добавляются, добавляются только рёбра. Другое ограничение, которое можно рассмотреть, - отсутствие кратных рёбер, то есть будут рассматриваться только простые неориентированные графы. В этом случае не для каждой системы может быть построено рёберное к-расширение. Например, для моделируемой полным графом полносвязной системы, в которой все элементы попарно соединены, нет возможности добавить новые рёбра, поэтому у такой системы не будет рёберного ^-расширения ни при каком натуральном к. Задача определения, какие графы имеют рёберное к-расширение при заданном к, представляет отдельный интерес [11]. Если же рёберное к-расширение существует, то представляет интерес найти расширение с минимальным числом дополнительных связей.

Рёберная к-отказоустойчивая реализация Е* системы Е называется

*

оптимальной, если система Е содержит столько же элементов, сколько и система Е, а среди всех рёберных к-отказоустойчивых реализаций с тем же числом элементов система Е* имеет наименьшее число связей. На языке теории графов рёберную оптимальную к-отказоустойчивую реализацию системы Е мы будем называть минимальным рёберным к-расширением (МР-кР) её графа О(Е). Вместо минимальности числа связей могут рассматриваться и другие ограничения, которые по той или иной причине предпочтительны, например, наличие определённой группы автоморфизмов [76].

В своей первой работе Дж. Хейз [85] предложил схемы построения минимальных вершинных 1 -расширений для цепей и циклов, а также для частного случая помеченного дерева. В следующей работе [83] были получены

аналогичные результаты для минимальных рёберных 1 -расширений. Большой обзор аналитических результатов можно найти в работах [11, 86]. В частности можно отметить результаты по аналитическому построению вершинных ^ расширений для различных классов графов: М.Ф. Каравай [24-27], А.В. Киреева [28], М.А. Кабанов [20], А.А. Долгов [18, 19], О.В. Моденова [13, 14], М.Б. Абросимов [3-11], Ф. Харари и Дж. Хейз [83] и ряд других работ, из которых выделим [66, 69, 70, 80, 85, 86, 106]. Среди работ, посвященных только рёберным расширениям, отметим следующие [5, 7, 69, 71, 83].

М.Б. Абросимов в работе [8] доказал, что задача проверки того, что граф является рёберным ^расширением заданного графа, является №-полной. Это означает, что эффективный поиск минимальных рёберных ^расширений для произвольных графов реализовать, видимо, невозможно. В работе [11] предлагается алгоритм построения минимальных рёберных ^расширений графов, основанный на переборе всех подходящих кандидатов. С помощью программы, реализованной на его основе, были получены минимальные рёберные 1-расширения всех неориентированных графов с числом вершин до 7. Описанный алгоритм сложен для распараллеливания, так как во время поиска необходимо поддерживать список всех найденных рёберных расширений. Алгоритм позволяет строить рёберные расширения для небольших графов. Программная реализация на основе этого алгоритма была использована для построения всех минимальных рёберных 1 -расширений графов с числом вершин до 7, а также для некоторых отдельных графов с большим числом вершин. Существуют методы построения различных графов без непосредственной проверки на изоморфизм, и в этом случае можно не хранить все найденные результаты. В основе таких методов лежит идея оставлять очередного кандидата только в том случае, если его форма является канонической [48, 79]. Существуют различные техники сокращения полного перебора кандидатов, которые в иностранной литературе называют методами Рида-Фараджева и МакКея. Хороший обзор современного состояния по этому вопросу можно найти в работе Г. Бринкман [62], который также является

автором нескольких известных генераторов, в которых реализованы методы построения графов без проверки на изоморфизм. В англоязычной литературе эта техника называется isomorphism rejection. Алгоритмы генерации без проверки на изоморфизм хорошо подходят для распараллеливания.

Наибольшее внимание в исследованиях по отказоустойчивости уделяется изучению отказов элементов, причем в основном рассматривается задача описания вида минимального расширения для определенных графов. Для анализа отказоустойчивых реализаций современных вычислительных систем необходимо уметь находить минимальные расширения для графов с числом вершин 12-16. Известные алгоритмы плохо подходят для распараллеливания и не справляются с таким числом вершин. Необходимы новые подходы к разработке алгоритмов построения минимальных рёберных расширений, которые будут хорошо распараллеливаться. Для этих целей подходит техника генерации без проверки на изоморфизм, однако для задачи построения минимальных рёберных ^-расширений её ранее не удавалось применить. В данной работе это удалось сделать впервые.

Всё вышесказанное определяет актуальность данной работы, а также её цели и задачи.

Цели и задачи. Цели данной работы состоят в разработке и исследовании математической модели рёберно-отказоустойчивой вычислительной системы для решения оптимизационной задачи определения минимального числа дополнительных связей системы, устойчивой к заданному числу отказов связей между элементами, а также построения всех неизоморфных минимальных рёберных ^-расширений заданного графа без проверки на изоморфизм и с возможностью распараллеливания.

Задачи работы:

1. Разработать математическую модель рёберно-отказоустойчивой системы с целью решения задачи определения минимального числа дополнительных связей системы, устойчивой к заданному числу отказов связей между элементами системы, и построения всех минимальных рёберных ^-расширений для соответствующего графа системы.

2. Разработать алгоритмы определения минимального числа дополнительных связей системы, устойчивой к заданному числу отказов связей между элементами системы, и построения всех минимальных рёберных ^расширений для соответствующего графа системы.

3. Провести исследование разработанных алгоритмов, оценить возможность их распараллеливания и эффективность. Проверить корректность работы на известных данных.

4. Разработать программный комплекс, реализующий алгоритмы определения минимального числа связей системы, устойчивой к заданному числу отказов связей между элементами системы, и построения всех её минимальных рёберных ^расширений.

5. Провести вычислительные эксперименты по построению минимальных рёберных ^расширений всех неориентированных графов с числом вершин до 10 для нескольких значений k и проанализировать полученные результаты.

6. Провести вычислительные эксперименты по построению минимальных рёберных 1 -расширений для отдельных наиболее интересных с практической точки зрения графов: решёток, торов.

Объектом исследования является граф, представляющий модель вычислительной системы.

Предметом исследования являются модели и алгоритмы, позволяющие строить для заданного графа все неизоморфные минимальные рёберные Ъ-расширения.

Научная новизна работы заключается в следующем:

1. Предложен подход к исследованию математической модели рёберно-отказоустойчивой системы для решения задачи определения минимального количества дополнительных связей системы, устойчивой к заданному числу отказов связей между элементами системы, и построения минимальных рёберных ^расширений для соответствующего графа системы. Этот подход позволяет

разрабатывать методы решения этих задач с существенным сокращением области поиска решений.

2. Разработаны новые численные методы решения задачи определения минимального числа дополнительных связей системы, устойчивой к заданному числу отказов связей между элементами системы, которые позволяют существенно сокращать область поиска решений.

3. Разработаны алгоритмы построения всех неизоморфных минимальных рёберных ^-расширений графа заданной системы, отличающиеся от известных ранее алгоритмов применением техники исключения изоморфных копий, что обеспечивает возможность разработки более эффективных параллельных алгоритмов и лучшее использование оперативной памяти.

4. Реализованы и исследованы параллельные версии разработанных алгоритмов для построения минимальных рёберных ^-расширений заданного графа. Сравнение с известными аналогами показало увеличение скорости работы в 10 и более раз.

5. Создан программный комплекс для построения всех неизоморфных минимальных рёберных ^-расширений для заданного графа или списка графов на основе алгоритмов данной работы и вычисления минимального числа дополнительных связей системы, устойчивой к заданному числу отказов связей между элементами системы.

6. Построены минимальные рёберные 1 -расширения всех неориентированных графов с числом вершин до 10, а также минимальные рёберные 2-, 3- и 4-расширения для всех неориентированных графов с числом вершин до 9.

7. Построены минимальные рёберные 1 -расширения для некоторых решёток, торов и гиперкубов с числом вершин до 20.

Методология и методы исследования. В работе используются методы дискретной математики, теории графов, теории алгоритмов и комбинаторной оптимизации, в частности специальные методы разработки алгоритмов генерации

структур без проверки на изоморфизм. Оценка качества предложенных алгоритмов проводится с помощью компьютерных экспериментов.

Положения и результаты, выносимые на защиту:

1. Предложен подход к исследованию математической модели отказоустойчивой системы для решения задачи определения минимального количества дополнительных связей системы, устойчивой к заданному числу отказов связей между элементами системы, и нахождения всех неизоморфных минимальных рёберных ^расширений графа соответствующей системы без проверки на изоморфизм.

2. Разработаны алгоритмы определения минимального количества дополнительных связей системы, устойчивой к заданному числу отказов связей между элементами системы, и нахождения всех неизоморфных минимальных рёберных ^расширений графа соответствующей системы без проверки на изоморфизм.

3. Реализованы параллельные алгоритмы определения минимального количества дополнительных связей системы, устойчивой к заданному числу отказов связей между элементами системы, и нахождения всех неизоморфных минимальных рёберных ^расширений графа соответствующей системы без проверки на изоморфизм.

4. Разработан программный комплекс на основе предложенных методов, позволяющий для поданных на вход графов определять минимальное количество дополнительных связей системы, устойчивой к заданному числу отказов связей между элементами системы, и нахождения всех неизоморфных минимальных рёберных ^расширений графа соответствующей системы без проверки на изоморфизм.

5. Построены минимальные рёберные 1 -расширения всех неориентированных графов с числом вершин до 10, минимальные рёберные 2-, 3-и 4-расширения для всех неориентированных графов с числом вершин до 9, а

также минимальные рёберные 1 -расширения для некоторых решёток, торов и гиперкубов с числом вершин до 20.

Теоретическая значимость работы. Предложен новый подход к исследованию математической модели рёберно-отказоустойчивой системы для решения задачи определения минимального количества дополнительных связей системы, устойчивой к заданному числу отказов связей между элементами системы, и нахождения всех неизоморфных минимальных рёберных ^ расширений графа соответствующей системы без проверки на изоморфизм. Разработаны алгоритмы для построения всех неизоморфных минимальных рёберных ^расширений графа с использованием техники исключения изоморфных копий и метода канонических представителей.

Практическая значимость работы. Практическая значимость работы состоит в разработанном программном комплексе для построения минимальных рёберных ^расширений заданного графа на основе алгоритмов, предложенных в работе. В результате проведённых экспериментов удалось построить минимальные рёберные расширения для некоторых решёток и торов с числом вершин до 20. Для 16-вершинного гиперкуба удалось установить, что известное ранее минимальное рёберное 1 -расширение является единственным с точностью до изоморфизма. С помощью разработанного программного комплекса были построены все минимальные рёберные 1 -расширения для графов с числом вершин до 9 и выложены в открытый доступ в онлайн-энциклопедии «Мир графов». Реализованный программный комплекс может быть использован на этапе анализа и разработки вычислительных архитектур, для которых необходимо предусмотреть отказоустойчивость связей между элементами.

Личный вклад автора. Все основные результаты, выносимые на защиту, получены автором лично. Автор участвовал в определении цели работы и постановке задач, самостоятельно разрабатывал все программные части совместного программного комплекса, которые относятся к задаче построения рёберных расширений. Все основные алгоритмы из работы были реализованы как

отдельное приложение, а также как часть программного комплекса FTConstructor, который позволяет для заданного графа строить как рёберные, так и вершинные расширения. Вклад автора в FTConstructor - все программные модули для построения рёберных расширений. В остальных совместных работах автору также принадлежит ведущая роль в вопросах, связанных с рёберными расширениями графов. Результаты данной работы докладывались автором на различных конференциях и семинарах.

Достоверность результатов. Все положения, представленные в диссертации, получены с использованием аппарата дискретной математики и теории графов. Эффективность предложенных алгоритмов подтверждается компьютерными экспериментами. Полученные результаты согласуются с известными экспериментальными и аналитическими результатами.

Апробация результатов исследования. Основные результаты работы докладывались и обсуждались на следующих семинарах и конференциях:

• научный семинар кафедры теоретических основ компьютерной безопасности и криптографии Саратовского национального исследовательского государственного университета имени Н.Г. Чернышевского (Саратов, 2017, 2018, 2019, 2020);

• международная научная конференция «International Conference on Computing, Communication, Control and Automation» (ICCUBEA-2017) (Пуна, Республика Индия, 2017);

• VIII Международная научная конференция «Компьютерные науки и информационные технологии» памяти А.М. Богомолова (Саратов, 2018);

• Всероссийская конференция «XVIII Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» -SIBECRYPT'19» (Томск, 2019);

• XV, XVI, XVII, XVIII Белорусско-российская научно-техническая конференция «Технические средства защиты информации» (Минск, Республика Беларусь, 2017, 2018, 2019, 2020);

• XXVII Международная конференция студентов, аспирантов и молодых учёных «Ломоносов» (Москва, 2020).

Соответствие содержания диссертации избранной специальности

Результаты работы соответствуют специальности 05.13.18 - Математическое моделирование, численные методы и комплексы программ (технические науки) по областям исследования «Разработка новых математических методов моделирования объектов и явлений» (п. 1 паспорта специальности), «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий» (п. 3 паспорта специальности), «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента» (п. 4 паспорта специальности), «Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента» (п. 5 паспорта специальности).

Публикации. По теме диссертации опубликовано 15 работ, в том числе 6 статей в журналах, включенных в Перечень рецензируемых научных изданий, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученой степени кандидата наук (из них 2 статьи в российских научных журналах, входящих в Web of Science), 1 статья в сборнике материалов конференции, представленном в издании, входящем в Scopus, 1 статья в приложении к российскому научному журналу, 6 публикаций в сборниках материалов международной научной и белорусско-российских научно-технических конференций; получено 1 свидетельство о государственной регистрации программы для ЭВМ.

Структура работы. Диссертационная работа состоит из введения, 4 глав, заключения, списка сокращений и условных обозначений, списка использованной литературы и приложений. Работа содержит 149 страниц, 29 рисунков, 20 таблиц, библиографический список из 109 наименований и 4 приложения.

Благодарность. Автор выражает глубокую признательность своему научному руководителю доктору физико-математических наук, доценту Михаилу Борисовичу Абросимову за предложенную тему исследования, помощь в постановке задач, а также за всестороннюю помощь и поддержку при подготовке диссертационной работы.

1 Модель рёберной отказоустойчивости

1.1 Отказоустойчивость

В данной работе мы будем изучать модель для исследования отказоустойчивости связей вычислительной системы, которую в 1993 году предложили Ф. Харари и Дж. Хейз [83]. Эта модель является развитием модели, которую предложил Дж. Хейз в 1976 году для исследования отказов элементов технической системы [85]. Основным объектом исследования в этой модели является граф вычислительной системы. Системе Е сопоставляется помеченный граф G(E), вершины которого соответствуют элементам системы Е, рёбра -связям между элементами. Если связи являются симметричными, то граф будет неориентированным графом. Если все элементы системы и связи являются однотипными, то граф будет без меток. Модель оказалась удобной для разработки отказоустойчивых вычислительных систем, где элементами являются вычислительные узлы, а связями между элементами - информационные каналы [11]. Вычислительными узлами могут быть ядра, процессоры или компьютеры. В такой системе элементы и связи, как правило, являются однотипными. В данной работе мы будем рассматривать именно такие системы, поэтому основным объектом нашего исследования будет неориентированный граф без меток.

Под отказом элемента системы Е понимается удаление соответствующей ему вершины из графа системы G(E) и всех связанных с ней ребер. Под отказом связи в системе Е понимается удаление соответствующего ребра (или дуги для ориентированного графа) из графа системы G(E). В данной работе мы будет рассматривать только отказы связей.

Система Е* называется рёберной k-отказоустойчивой реализацией (edge fault tolerance) системы Е, если отказ любых k связей системы Е* приводит к графу, в который можно вложить граф системы Е. Построение рёберной k-отказоустойчивой реализации системы Е можно представить себе как введение

в неё определенного числа избыточных элементов и связей. При этом предполагается, что в нормальном режиме работы избыточные элементы и связи маскируются, а в случае отказа происходит реконфигурация системы до исходной структуры [11, 85]. На языке теории графов рёберную ^-отказоустойчивую реализацию системы Е мы будем называть рёберным ^-расширением (Р-£Р) её графа С(Е). В следующем разделе приведём основные необходимые определения, связанные с графами.

Список литературы диссертационного исследования кандидат наук Судани Хайдер Хуссейн Карим, 2021 год

Список литературы

1. Абросимов М.Б. Минимальные ^расширения предполных графов // Известия ВУЗов: Математика. - 2003. - № 6(493). - С. 3-11.

2. Абросимов М.Б. Минимальные расширения 4-,5-,6- и 7-вершинных графов. - Саратов гос. ун-т. - Саратов, 2000. - 26с.; Деп. в ВИНИТИ 06.09.2000, № 2352-В00.

3. Абросимов М.Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур : докл. Третьей Всерос. конф. с междунар. участием. Томск, 2000. - С. 59-64.

4. Абросимов М.Б. Минимальные расширения циклов с числом вершин не более одиннадцати. - Саратов: СГУ, 2001. - 17с.; Деп. в ВИНИТИ 14.08.2001, №1869-В2001.

5. Абросимов М.Б. Минимальные рёберные расширения направленных и ориентированных звезд // Прикладная дискретная математика. - 2011. - № 2. -С.77-89.

6. Абросимов М.Б. Минимальные реберные расширения некоторых предполных графов // Прикладная дискретная математика. - 2010. №1. - С. 105117.

7. Абросимов М.Б. О нижней оценке числа ребер минимального рёберного 1-расширения сверхстройного дерева // Изв. Сарат. ун-та. Нов. сер. 2011. - Т. 11. Сер. Математика. Механика. Информатика, вып. 3, ч. 2. - С. 111-117.

8. Абросимов М.Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. - № 88:5. - С. 643-650.

9. Абросимов М.Б. Параллельный алгоритм построения минимальных вершинных и реберных 1-расширений графов / М. Б. Абросимов, Д. А. Зайцев // XII Белорусская математическая конференция: материалы междунар. науч. конф. Минск, 5-10 сентября 2016 г. - Часть 4. - С. 46-47.

10. Абросимов М.Б. Построение минимальных рёберных расширений графа без проверки на изоморфизм / М. Б. Абросимов, Х. Х. К. Судани, А. А. Лобов // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. — 2020. — Т. 20, вып. 1. — С. 105—115.

11. Абросимов М.Б. Графовые модели отказоустойчивости. — Саратов: Издательство Саратовского университета, 2012. — 192 с.

12. Абросимов М.Б. О количестве оптимальных 1-гамильтоновых графов с числом вершин до 26 и 28 / М. Б. Абросимов, С. А. Сухов // Прикладная дискретная математика. Приложение. — 2016. — № 9. — С. 103—105.

13. Абросимов М.Б. Характеризация орграфов с малым числом дополнительных дуг минимального вершинного 1 -расширения / М. Б. Абросимов, О. В. Моденова // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. — 2013. — Т. 13., вып. 2, ч. 2. — С. 3—9.

14. Абросимов М.Б. Характеризация орграфов с тремя дополнительными дугами в минимальном вершинном 1-расширении / М. Б. Абросимов, О. В. Моденова // Прикладная дискретная математика. — 2013. — № 3. — С. 68—75.

15. Богомолов А.М. Алгебраические основы теории дискретных систем / А. М. Богомолов, В. Н. Салий. — М. : Наука, 1997. — 368 с.

16. Бринкман Г. О количестве минимальных расширений циклов с числом вершин до 26 / Г. Бринкман, М. Б. Абросимов // Дискретная математика, теория графов и их приложения: Тез. докл. Междунар. науч. конф. Минск, 11—14 ноября 2013 г. Мн.: Институт математики НАН Беларуси. — 2013. — С. 7—9.

17. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д.Джонсон. — М. : Мир, 1982. — 416 с.

18. Долгов А.А. О семействах точных вершинных ^-расширений графов при к > 1 // Материалы международного молодежного научного форума «Ломоносов-2010». — М. : МАКС Пресс, 2010. — С. 30—32.

19. Долгов А.А. Семейство точных 2-расширений турниров // Прикладная дискретная математика. — 2010. — № 9. — С. 96—99.

20. Кабанов М.А. Об отказоустойчивых реализациях графов // Теоретические задачи информатики и ее приложений. - Саратов : Изд-во Сарат. ун-та, 1997. - Вып.1. - С. 50-58.

21. Камил И.А. К вопросу о параллельных алгоритмах построения минимальных вершинных и рёберных 1-расширений графов / И. А. Камил, Х. Х. Судани, М. Б. Абросимов // Компьютерные науки и информационные технологии : Материалы междунар. науч. конф. - Саратов : Издат. центр «Наука», 2018. - С. 173-176.

22. Камил И.А.К. Построение всех неизоморфных суперграфов без проверки на изоморфизм / И. А. К. Камил, Х. Х. К. Судани, А. А. Лобов, М. Б. Абросимов // Прикладная дискретная математика. - 2020. - № 48. - С.82-92.

23. Камил И.А.К. Построение минимальных расширений графа методом канонических представителей / И. А. К. Камил, Х. Х. К. Судани, А. А. Лобов, М. Б. Абросимов // Прикладная дискретная математика. Приложение. - 2019. -№ 12. - С. 179-182.

24. Каравай М.Ф. Инвариантно-групповой подход к исследованию к-отказоустойчивых структур // Автоматика и телемеханика. - 2000. - № 1. -С. 144-156.

25. Каравай М.Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. I. Одно-отказоустойчивые структуры // Автоматика и телемеханика. - 2004. - № 12. - С. 159-177.

26. Каравай М.Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. II. Решетки и к-отказоустойчивость // Автоматика и телемеханика. -2005. - № 2. - С. 175-189.

27. Каравай М.Ф. Применение теории симметрии к анализу и синтезу отказоустойчивых систем // Автоматика и телемеханика. - 1996. - № 6. - С. 159173.

28. Киреева А.В. Отказоустойчивость в функциональных графах // Упорядоченные множества и решетки. - Саратов : Изд-во Сарат. ун-та, 1995. -Вып. 11. - С. 32-38.

29. Липский В. Комбинаторика для программистов. - М. : Мир, 1988. -

200 с.

30. Официальный сайт Поволжского Регионального Центра Новых Информационных Технологий [Электронный ресурс]. - URL: http://prcnit.sgu.ru (дата обращения: 01.08.2020).

31. Розенфельд М.З. О построении и свойствах некоторых классов сильно регулярных графов // УМН. - 1973. - Т. 28, вып. 3(171). - С. 197-198.

32. Руководство по выбору жесткого диска [Электронный ресурс]. - URL: https://www.seagate.com/files/docs/pdf/ru-RU/whitepaper/mb538-drive-selection-guide-ru.pdf (дата обращения: 01.08.2020).

33. Свидетельство о государственной регистрации программы для ЭВМ № 2011610846. Построитель минимальных вершинных и реберных 1-расширений графов / Абросимов М. Б. (RU); правообладатель: Государственное образовательной учреждение высшего профессионального образования «Саратовский государственный университет имени Н.Г. Чернышевского» (RU). Заявка № 2010615111; заявл. - 20 августа 2010 г.; дата государственной регистрации в Реестре программ для ЭВМ - 19 января 2011 г.

34. Свидетельство о государственной регистрации программы для ЭВМ № 2012661394. Поиск минимальных реберных и вершинных 1-расширений графов / Абросимов М. Б. (RU), Комаров Д. Д. (RU); правообладатель: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Саратовский государственный университет имени Н.Г. Чернышевского» (RU). Заявка № 2012619258; заявл. - 29 октября 2012 г.; дата государственной регистрации в Реестре программ для ЭВМ - 13 декабря 2012 г.

35. Свидетельство о государственной регистрации программы для ЭВМ № 2012612065. Исследование минимальных вершинных 1-расширений орграфов / Абросимов М. Б. (RU), Моденова О. В. (RU); правообладатель: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Саратовский государственный университет имени Н.Г. Чернышевского» (RU). Заявка № 2011660130; заявл. - 27 декабря 2011 г.; дата государственной регистрации в Реестре программ для ЭВМ -22 февраля 2012 г.

36. Свидетельство о государственной регистрации программы для ЭВМ № 2010616497. Исследование минимальных вершинных и реберных 1-расширений цепей с вершинами двух типов / Абросимов М. Б. (RU), Бондаренко П. П. (RU); правообладатель: Государственное образовательной учреждение высшего профессионального образования «Саратовский государственный университет имени Н.Г. Чернышевского» (RU). Заявка № 2010614677; заявл. - 2 августа 2010 г.; дата государственной регистрации в Реестре программ для ЭВМ - 30 сентября 2010 г.

37. Свидетельство о государственной регистрации программы для ЭВМ № 2020614773. Построение оптимальных отказоустойчивых реализаций графов FTConstructor / Абросимов М. Б. (RU), Камил И. А. К. (RU), Судани Х. Х. К. (RU), Лобов А. А. Заявка № 2020612581; заявл. - 27 марта 2020 г.; дата государственной регистрации в Реестре программ для ЭВМ - 24 апреля 2020 г.

38. Свидетельство о государственной регистрации программы для ЭВМ № 2016610073. DSR Generator / Сухов С.А. (RU). Заявка № 2015660808; заявл. 10 ноября 2015 г.; дата государственной регистрации в Реестре программ для ЭВМ -11 января 2016 г.

39. Судани Х.Х.К. Безопасность и надежная среда в системах обеспечения отказоустойчивости / Х. Х. К. Судани, М. Б. Абросимов // Технические средства защиты информации: Тезисы докладов XVII Белорусско-российской научно-

технической конференции, 11 июня 2019 г., Минск. Минск: БГУИР. - 2019. -С. 68.

40. Судани Х.Х.К. Безопасность и техники отказоустойчивости / Х. Х. К. Судани, М. Б. Абросимов // Технические средства защиты информации: Тезисы докладов XVIII Белорусско-российской научно-технической конференции, 9 июня 2020 г., Минск. Минск: БГУИР. - 2020. - С. 74.

41. Судани Х.Х. Повышение доступности системы безопасности при использовании техники отказоустойчивости // Перспективы науки. - 2018. -№ 10(109). - С.125-128.

42. Судани Х.Х. Обеспечение предельной отказоустойчивости параллельных вычислений с интерфейсом передачи сообщений MPI //Современная наука: Серия: Естественные и технические науки. - 2018. - №4 - C. 84-86.

43. Судани Х.Х.К. К вопросу об использовании техники исключения изоморфизма для построения оптимальных рёберно-отказоустойчивых расширений графов // Материалы международного молодежного научного форума «Л0М0Н0С0В-2020» [Электронный ресурс] / Отв.ред. И.А. Алешковский, А.В. Андриянов, Е.А. Антипов. - Электрон. текстовые дан. (1500 Мб.) - М.: МАКС Пресс, 2020. - Режим доступа: https://lomonosov-msu.ru/archive/Lomonosov_2020/index.htm, свободный - Материалы международного молодежного научного форума «ЛОМОНОСОВ-2020».

44. Судани Х.Х.К. Киберугрозы и отказоустойчивость / Х. Х. К. Судани, М. Б. Абросимов // Технические средства защиты информации: Тезисы докладов XVI Белорусско-российской научно-технической конференции, 5 июня 2018 г., Минск. Минск: БГУИР. - 2018. - С. 90.

45. Судани Х.Х.К. Отказоустойчивость и безопасность доступа в облачных вычислениях / Х. Х. К. Судани, М. Б. Абросимов // Южно-Сибирский научный вестник. - 2019. - № 2(26). - С. 55-59.

46. Судани Х.Х.К. Рёберно-отказоустойчивые расширения 8-, 9- и 10-вершинных графов // International Journal of Open Information Technologies. - 2020.

- Vol. 8, № 8. - P. 46-50.

47. Теслер Г.С. Решение проблемы гарантоспособности компьютерных систем в аспекте базисов компьютерной науки // Математичш машини i системи.

- 2008. - № 4. - С. 171-188.

48. Фараджев И.А. (ред) Алгоритмические исследования в комбинаторике. -М.: Наука, 1978. - 190 с.

49. Харченко В.С. Гарантоспособность и гарантоспособные системы : элементы методологии // Радюелектронш i комп'ютерш системи. - 2006. - № 5 -С. 7-19.

50. Харченко В.С. Парадигмы и принципы гарантоспособных вычислений : состояние и перспективы развития // Радюелектронш i комп'ютерш системи. -2009. - № 2(36). - С. 91-100.

51. Энциклопедия «Мир графов» [Электронный ресурс]. -URL:http://graphworld.ru (дата обращения: 01.08.2020).

52. Abrosimov M. Fault Tolerance to Balance for Messaging Layers in Communication Society / M. Abrosimov, K. Sudani, H. Mahajan // 2017 International Conference on Computing, Communication, Control and Automation (ICCUBEA), PUNE, India. - 2017. - P. 423-428.

53. Ajima Y. Tofu: A 6D Mesh/Torus Interconnect for Exascale Computers / Y Ajima, S. Sumimoto, T. Shimizu // IEEE Computer. - 2009. - Vol. 42, № 11. - P. 3640.

54. Ajima Y The Tofu interconnect D / Y. Ajima, T. Kawashima, T. Okamoto, N. Shida, K. Hirai, T. Shimizu // 2018 IEEE International Conference on Cluster Computing (CLUSTER). - 2018. - P. 646-654.

55. Avizienis A. Design of fault-tolerant computers // AFIPS'67 Conf. Proc. -New York : ACM, 1967. - P. 733-743.

56. Avizienis A. Fault-Tolerant Computing: An Overview // IEEE Computer. -1971. - Vol. 4, № 1. - P. 5-8.

57. Avizienis A. Basic Concepts and Taxonomy of Dependable and Secure Computing / A. Avizienis, J.-C. Laprie, B. Randell, C. Landwehr // IEEE Transactions on Dependable and Secure Computing. - 2004. - № 1. - P. 11-33.

58. Babai L. The Graph Isomorphism Problem (Dagstuhl Seminar 15511) / L. Babai, A. Dawar, P. Schweitzer, J. Toran // Dagstuhl Reports. -2016. - Vol. 5, is. 12. - P. 1-17. - DOI: 10.4230/DagRep.5.12.1.

59. Bautista-Gomez L. Reducing Waste in Extreme Scale Systems through Introspective Analysis / L. Bautista-Gomez, A. Gainaru, S. Perarnau, D. Tiwari, S. Gupta, C. Engelmann, F. Cappello, M. Snir // 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). - 2016. - P. 212-221.

60. Bonnici V. A subgraph isomorphism algorithm and its application to biochemical data / V. Bonnici, R. Giugno, A. Pulvirenti, D. Shasha // BMC Bioinformatics. - 2014. - Vol. 14, S13. - P. 1-13. - DOI: 10.1186/1471-2105-14-S7-S13.

61. Brinkmann G. Fast generation of cubic graphs // J. Graph Theory. - 1996. -Vol. 23, № 2. - P. 139-149.

62. Brinkmann G. Isomorphism rejection in structure generation programs // Discrete Mathematical Chemistry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. - 2000. - Vol. 51. - P. 25-38. - DOI: 10.1090/dimacs/051/03.

63. Brinkmann G. Generation of cubic graphs and snarks with large girth / G. Brinkmann, J. Goedgebeur // Journal of Graph Theory. - 2017. - Vol. 86, № 2. - P. 255-272.

64. Brinkmann G. Generation and properties of Snarks / G. Brinkmann, J. Goedgebeur, J. Hagglund, K. Markstrom // Journal of Combinatorial Theory, Series B. - 2013. - Vol. 103, № 4. - P. 468-488.

65. Brinkmann G. Generation of cubic graphs / G. Brinkmann, J. Goedgebeur,

B. D. McKay // Discrete Math. Theor. Comput. Sci. - 2011. - Vol. 13, № 2. - P. 69-80.

66. Bruck J. Fault-tolerant meshes with small degree / J. Bruck, R. Cypher, C. Ho // SIAM J. Comput. - 1997. - Vol. 26, № 6. - P. 1764-1784.

67. Carter W.C. A Survey of Fault Tolerant Computer Architecture and its Evaluation / W. C. Carter, W. G. Bouricius // IEEE Computer. - 1971. - Vol. 4, № 1. -P. 9-16.

68. Casanova H. Computing the Expected Makespan of Task Graphs in the Presence of Silent Errors / H. Casanova, J. Herrmann, Y. Robert // 2016 45th International Conference on Parallel Processing Workshops (ICPPW), Philadelphia, PA. - 2016. - P. 141-150.

69. Chou R.S. 1-edge fault-tolerant designs for meshes / R. S. Chou, L. H. Hsu // Parallel Process. Lett. - 1994. - Vol. 4, № 4. - P. 385-389.

70. Choudum S.A. Optimal fault-tolerant networks with a server / S. A. Choudum, S. Sivagurunathan // Networks. - 2000. - Vol. 35, № 2. - P. 157-160.

71. Chuang Y.-C. Optimal 1-edge fault-tolerant designs for ladders / Y.-

C. Chuang, L. Hsu, C.-H. Chang // Inf. Process. Lett. - 2002. - Vol. 84. - P. 87-92.

72. Colburn C.J. Orderly algorithms for generating restricted classes of graphs / C. J. Colburn, R. C. Read // Journal of Graph Theory. - 1979, Vol. 3, P. 187-195.

73. Colburn C.J. Orderly algorithms for graph generation / C. J. Colburn, R. C. Read // Intern. J. Computer Math. - 1979, Sec.A.7. - P. 167-172.

74. Cook S.A. The complexity of theorem-proving procedures // Proc. 3rd ACM Symposium on Theory of Computing. - 1971. - P. 151-158.

75. Darga P.T. Exploiting structure in symmetry detection for CNF / P. T. Darga, M. H. Liffiton, K. A. Sakallah, I. L. Markov // Proceedings of the 41st Design Automation Conference, 2004. - P. 530-534.

76. Dutt S. Designing fault-tolerant systems using graph automorphisms / S. Dutt, J. P. Hayes // Journal of Parallel and Distributed Computing. - 1991. - Vol. 12. - P. 249-268.

77. Encyclopedia of Parallel Computing / ed. D. A. Padua. - New York : Springer. - 2011. - 2195 p.

78. Fan W. Reconfigurable Fault-tolerance mapping of ternary N-cubes onto chips / W. Fan, J. He, Z. Han, P. Li, R.Wang // Concurrency and Computation: Practice and Experience. - 2020. - Vol. 32, is. 11. - Article number e5659. -DOI: 10.1002/cpe.5659.

79. Faradzev I.A. Constructive enumeration of combinatorial objects // Colloques internationaux C.N.R.S. №260, Problemes Combinatoires et Theorie des Graphes, Orsay 1976. - P. 131-135.

80. Farrag A.A. Designing optimal fault-tolerant star networks / A. A. Farrag, R. J. Dawson // Networks. - 1989. - Vol. 19. - P. 707-716.

81. Grund R. Konstruktion schlichter Graphen mit gegebener Gradpartition // Bayreuther Mathematische Schriften. - 1993. - Vol. 44. - P.73-104.

82. Gurevich Y. From invariants to canonization // Bulletin of the European Association of Theoretical Computer Science. - 1997. - Vol. 63. - P. 115-119.

83. Harary F. Edge fault tolerance in graphs / F. Harary, J. P. Hayes // Networks. -1993. - Vol. 23. - P. 135-142.

84. Harary F. Node fault tolerance in graphs / F. Harary, J. P. Hayes // Networks. -1996. - Vol. 27. - P. 19-23.

85. Hayes J.P. A graph model for fault-tolerant computing system // IEEE Transactions on Computers. - 1976. - Vol. C-25, is. 9. - P. 875-884.

86. Hsu L. H. Graph Theory and Interconnection Networks / L. H. Hsu, C. K. Lin. - New York: CRC Press, 2009. - 720 p.

87. Junttila T. Engineering an efficient canonical labeling tool for large and sparse graphs / T. Junttila, P. Kaski // Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics. - New Jersey, USA, 2007. - P. 135-149.

88. Junttila T. Conflict Propagation and Component Recursion for Canonical Labeling / T. Junttila, P. Kaski // Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms. - Rome, Italy, 2011. - P. 151-162.

89. Kozielski S. Development of High Performance Computing Systems / S. Kozielski, D. Mrozek // Gaj P., Guminski W., Kwiecien A. (eds) Computer Networks. CN 2020. Communications in Computer and Information Science. - Springer, Cham, 2020. - Vol. 1231. - P. 52-63.

90. Land A.H. An automatic method of solving discrete programming problems / A. H. Land, A. G. Doig // Econometrica. - 1960. - Vol. 28, № 3. - P. 497-520.

91. Leighton F.T. Introduction to Parallel Algorithms and Architecture: Arrays,Trees,Hypercubes. - San Mateo, Morgan Kaufmann, 1992. - 852 p.

92. Lopez-Presa J.L. Fast algorithm for graph isomorphism testing / J. L. Lopez-Presa, A. Fernandez Anta // Proceedings of the 8th International Symposium on Experimental Algorithms. - Dortmund, Germany, 2009. - P. 221-232.

93. Lopez-Presa J.L. Conauto-2.0: Fast isomorphism testing and automorphism group computation / J. L. Lopez-Presa, A. Fernandez Anta, L. Nunez Chiroque. - 2011. [Электронный ресурс]. - URL: http://arxiv.org/abs/1108.1060.

94. Lowler E.L. Branch-and-bound methods. A survey / E. L. Lowler, D. E. Wood // J. Op. Res. Soc. America. - 1966. - Vol. 14. - P. 217-282.

95. McKay B.D. Practical graph isomorphism // Congr. Numer. - 1980. - Vol. 30. - P. 45-87.

96. McKay B.D. Isomorph-free exhaustive generation // Journal of Algorithms. -1998. - Vol. 26. - P. 306-324.

97. McKay B.D. Computing automorphisms and canonical labellings of graphs // Combinatorial Mathematics, Lecture Notes in Mathematics. - Springer-Verlag, Berlin, 2006. - Vol. 686. - P. 223-232.

98. McKay B.D. Practical Graph Isomorphism, II / B. D. McKay, A. Piperno // Journal of Symbolic Computation. - 2014. - Vol. 60. - P. 94-112.

99. McKay B.D. Description of graph6, sparse6 and digraph6 encodings [Электронный ресурс]. - URL: http://cs.anu.edu.au/people/bdm/data/formats.txt (дата обращения: 01.08.2020).

100. Meringer M. Fast generation of regular graphs and construction of cages // Journal of Graph Theory. - 1999. - Vol. 30. - P. 137-146.

101. Mukhopadhyaya K. Hamiltonian graphs with minimum number of edges for fault-tolerant topologies / K. Mukhopadhyaya, B. P. Sinha // Inform. Process. Lett. - 1992. - Vol. 44. - P. 95-99.

102. Outline of the Development of the Supercomputer Fugaku [Электронный ресурс] // RIKEN Center for Computational Science. - URL: https://www.r-ccs.riken.jp/en/fugaku/project/outline (дата обращения: 01.08.2020).

103. Read R.C. The graph isomorphism disease / R. C. Read, D. G. Corneil // J. Graph Theoryl. - 1977. - P. 339-363.

104. Read R.C. Every one a winner // Annals of Discrete Mathematics 2. - 1978. - P. 107-120.

105. Sudani H.H. Balance and security for messaging layers / H. H. Sudani, M. B. Abrosimov // Технические средства защиты информации: Тезисы докладов XV Белорусско-российской научно-технической конференции, 6 июня 2017 г. Минск. -Минск: БГУИР, 2017. - С. 77.

106. Sung T.Y. Optimal k-fault-tolerance network for token rings / T. Y. Sung, T. Y. Ho, C. P. Chang, L. H. Hsu // J. Inform. Science and Engineering. - 2000. - № 16. -P. 381-390.

107. T0P500 [Электронный ресурс] // T0P500. - URL: https://www.top500.org/ (дата обращения: 01.08.2020).

108. Ullmann J. An algorithm for Subgraph Isomorphism. Journal of the Association for Computing Machinery. - 1976. - Vol. 23. - P. 31-42.

109. von Neumann J. Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components // Automata Studies, ser. Annals of Mathematics Studies. Princeton, NJ : Princeton University Press, 1956. - Vol. 34. - P. 43-98.

125

Приложение А

(справочное)

Свидетельство о государственной регистрации программы для ЭВМ

В данном приложении представлено изображение полученного свидетельства о государственной регистрации программы для ЭВМ № 2020614773 от 24 апреля 2020 года. Была зарегистрирована программа «Построение оптимальных отказоустойчивых реализаций графов FTConstructor», одной из возможностей которой является построение минимальных рёберных ^-расширений алгоритмами ПРМ, ПРК, ПКР и ДЛР. Для выполнения каждого из алгоритмов используется отдельный исполняемый файл. Сама программа была проверена на работоспособность на операционных системах, основанных на ядре Linux, с установленными библиотеками MPICH, реализующими стандарт MPI. В исходном коде существует зависимость только от стандартной библиотеки C++ и MPI, поэтому можно получить исполняемый файл и для других операционных систем.

127

Приложение Б

(справочное)

Акт о внедрении результатов диссертационной работы

128

Приложение В

(справочное)

Акт об использовании результатов работы в учебном процессе

АКТ

внедрения » учебный процесс кафедры теоретических основ компьютерной безопасности

н криптографии результатов диссертации Судами Хайдера Хуссейна Карима «Модели и алгоритмы построения оптимальных рёберных отказоустойчивых реализаций

вычислительных систем»

Настоящим актом удостоверяется, что результаты диссертационного исследования Х.Х.К. Судани на тему «Модели и алгоритмы построения оптимальных рёберных отказоустойчивых реализаций вычислительных систем» внедрены в учебный процесс кафедры при разработке методических рекомендаций и курсов лекций, а именно:

1) теоретические результаты I лапы 2 и практические результаты главы 4 используются в курсе «Теория графов» для студентов, обучающихся по специальности 10.05.01 «Компьютерная безопасность» (специализация «Математические методы защиты информации»):

2) теоретические результаты глав 2-4 используются в курсе «Теория построения отказоустойчивых систем» для студентов, обучающихся по направлению 09.04.01 «Информатика и вычислительная техника» (профиль подготовки «Сети ЭВМ и телекоммуникации»):

3) ал гори гмы из глав 2-4 и разработанная на их основе программа используются в курсе «Методы оптимизации графовых систем» для студентов, обучающихся по специальности 10.05.01 «Компьютерная безопасность» (специализация «Математические методы защиты информации»).

129

Приложение Г

(справочное) Исходный код программы

В данном приложении указан исходный код некоторых основных частей программы на языке C++11 (стандарт 2011 года).

Файл «enumeration.h» содержит два класса.

Первый класс «subset_enumerator» выполняет перебор части подмножеств. То есть происходит построение «part_index»-ой части элементов с номером «subset_size»-элементных подмножеств заданного «set_size»-элементного множества (всего разделение происходит на «part_count» частей). Разделение на части происходит по элементу с номером «separator».

Второй класс «permutation_enumerator» является шаблоном и реализует перебор префиксного дерева перестановок с возвратом. Это общая часть алгоритмов проверки графа на расширение и на каноничность. Шаблонный параметр «prefix_check_handler_t» должен быть функциональным классом (иметь оператор круглый скобки «( )»). Экземпляр данного класса должен осуществлять отсечение определённых ветвей дерева при переборе. Параметризация нужна для ускорения вызова функции и применения оптимизаций на фазе компиляции. Она даёт преимущество в скорости вызова перед использованием класса «std::function» из файла «functional», так как компилятор может оптимизировать вызов, выполнив подстановку кода (аналогично директиве inline). Для перебора используется следующая схема: сначала используется метод «init», который позволяет найти первую удовлетворяющую ветвь дерева, после используется метод «next», который осуществляет поиск следующей ветви. Если один из методов возвращает значение «false», то все ветви перебраны и дальнейший перебор невозможен.

Текст файла «enumeration.h»:

#ifndef ENUMERATION_H_ #define ENUMERATION_H_

#include <vector>

using namespace std;

class subset_enumerator { private:

int subset_size; int set_size; int separator; int part_index; int part_count; vector<int> subset;

static inline bool next_subset(vector<int> & subset, int start, int subset_size, int set_size) { int i = subset_size - 1;

while (i >= 0 && subset[start + i] == set_size - subset_size + i) --i; if (i < 0) { return false;

}

++subset[start + i]; ++i;

while (i < subset_size) {

subset[start + i] = subset[start + i - 1] + 1; ++i;

}

return true;

}

inline bool next_subpart() {

return next_subset(subset, separator, subset_size - separator,

set_size); }

inline bool next_superpart(int skip) { for (int i = 0; i < skip; ++i) {

if (!next_subset(subset, 0, separator, set_size - subset_size + separator)) {

return false;

}

}

if (separator > 0) {

for (int i = separator; i < subset_size; ++i) { subset[i] = subset[i - 1] + 1;

}

} else {

for (int i = 0; i < subset_size; ++i) { subset[i] = i;

}

}

return true;

}

public:

subset_enumerator() : subset_enumerator(0, 0) {}

subset_enumerator( size_t subset_size, size_t set_size)

: subset_enumerator(subset_size, set_size, 0, 0, 1) {}

subset_enumerator(

size_t subset_size, size_t set_size, size_t separator, size_t part_index, size_t part_count) : subset_size(subset_size) , set_size(set_size) , separator(separator) , part_index(part_index) , part_count(part_count) , subset(subset_size, 0) {}

void set(size_t subset_size, size_t set_size) { this->subset_size = subset_size; this->set_size = set_size; this->subset.resize(subset_size);

}

void set(

size_t subset_size, size_t set_size, size_t separator, size_t part_index, size_t part_count) { this->subset_size = subset_size; this->set_size = set_size; this->separator = separator; this->part_index = part_index; this->part_count = part_count; this->subset.resize(subset_size);

}

inline bool reset() {

if (subset_size > set_size) { return false;

}

for (int i = 0; i < subset_size; ++i) { subset[i] = i;

}

return next_superpart(part_index);

}

inline bool next() {

return next_subpart() || next_superpart(part_count);

}

inline const vector<int> & value() const { return subset;

}

inline int size() const { return subset.size();

}

};

template <class prefix_check_handler_t> class permutation_enumerator {

vector<int> elements; vector<int> next_index; int subset_size; int set_size;

inline bool next from(int i) {

int t; for (;;) {

++next_index[i];

if (next_index[i] >= set_size) { t = elements[i];

for (int j = i + 1; j < set_size; ++j) { elements[j - 1] = elements[j];

}

elements[set_size - 1] = t; --i; if (i < 0) { break;

}

} else {

t = elements[i];

elements[i] = elements[next_index[i]]; elements[next_index[i]] = t; if (is_correct_prefix(elements, i)) { ++i;

if (i < subset_size) {

next_index[i] = i - 1; } else {

return true;

}

}

}

}

return false;

}

public:

prefix_check_handler_t is_correct_prefix;

inline prefix_check_handler_t & handler() { return is_correct_prefix;

}

inline const vector<int> & value() { return elements;

}

permutation_enumerator(prefix_check_handler_t && on_check) : subset_size(-1) , set size(0)

, elements(0)

, is_correct_prefix(on_check) { ;

}

bool init(size_t subset_size, size_t set_size) { if (subset_size > set_size) { return false;

}

this->subset_size = subset_size; this->set_size = set_size; this->elements.resize(set_size); this->next_index.resize(subset_size); for (int i = 0; i < set_size; ++i) { elements[i] = i;

}

next_index[0] = -1; return next_from(0);

}

bool next() {

return next_from(subset_size - 1);

}

};

#endif

В файле «graph.h» находится реализация класса «graph». Данный класс представляет собой описание объекта графа в виде матрицы смежности. Текст файла «graph.h»:

#ifndef GRAPH_H_ #define GRAPH_H_

#include <vector>

using namespace std;

class graph {

public:

vector<vector<int>> matrix;

graph(size_t vertex_count = 0)

: matrix(vertex_count, vector<int>(vertex_count, 0)) {}

graph(const graph & other)

: matrix(other.matrix.begin(), other.matrix.end()) {}

graph(graph && other)

: matrix(move(other.matrix)) {

}

graph & operator =(const graph &) = default; graph & operator =(graph &&) = default;

inline void add_edge(int u, int v) { set_edge(u, v, 1);

}

inline void set_edge(int matrix[u][v] = value; matrix[v][u] = value;

}

u, int v, int value){

inline int edge(int u, int v) const { return matrix[u][v];

}

inline void remove_edge(int u, int v) { set_edge(u, v, 0);

}

inline int degree(int u) const { int deg = 0;

for (int i : matrix[u]) { deg += i;

}

return deg;

}

inline int vertex_count() const {

return static_cast<int>(matrix.size());

}

};

#endif

В файле «extension.h» описывается класс «extension_checker». Данный класс имеет основной метод «check(graph & g)», который проверяет, является ли граф МР-кР графа «g». Параметры «g» и «к» задаются специальными функциями «set_graph» и «set_k» соответственно. Внутренний по отношению к «extension_checker» класс «extension_checker::handler» является параметром шаблона «permutation_handler» для поиска вложений — особого рода отображений множества вершин одного графа на множество вершин другого.

Для осуществления более быстрой проверки вложения используются усечённые списки смежности — для каждой вершины графа «g» составляются массивы, в которые записываются позиции строки матрицы смежности ниже главной диагонали, на которых стоят единицы. Таким образом не нужно каждый раз осуществлять перечисление всех элементов матрицы графа «g», что позволяет ускорить проверку вложения графов с небольшим числом рёбер. Для подготовки массивов используется функция «make_edge_list». Текст файла «enumeration.h»:

#ifndef EXTENSION_H_ #define EXTENSION_H_

#include "graph.h" #include "enumeration.h"

using namespace std;

class extension_checker {

private:

struct handler {

extension_checker & c;

handler(extension_checker & c) : c(c) {} bool operator() (

const vector<int> & p, int i) {

int gv = i; int hv = p[gv];

if (c.g_degrees[gv] > c.ext_degrees[hv]) { return false;

}

for (int gu : c.g_edges[gv]) { if (!c.ext->edge(hv, p[gu])) { return false;

}

}

return true;

}

};

const graph * g; graph * ext; vector<int> g_degrees; vector<int> ext_degrees; vector<pair<int, int>> edges;

permutation_enumerator<handler> edge_prefix_enum; subset_enumerator to_remove; vector<int> use_vertexes;

vector<vector<int>> g_edges;

int k;

public:

extension_checker() : g(nullptr) , ext(nullptr) , g_degrees() , ext_degrees() , edges()

, edge_prefix_enum(handler(*this)) , to_remove(0, 1) , k(0) {

}

static inline void calc_degrees(const graph & h, vector<int> & degrees) {

int n = h.vertex_count(); degrees.resize(n);

for (int i = 0; i < n; ++i) { degrees[i] = h.degree(i);

}

}

static inline void make_edge_list(const graph & g, vector<vector<int>> & edges) {

edges.resize(g.vertex_count()); for (int i = 0; i < g.vertex_count(); ++i) { edges[i].clear();

for (int j = 0; j < i; ++j) { if (g.edge(i, j)) {

edges[i].push_back(j);

}

}

}

}

void set_graph(const graph & g) { this->g = &g;

calc_degrees(g, g_degrees); make_edge_list(g, g_edges);

}

void set_k(int k) { this->k = k;

}

bool check(graph & ext) {

if (ext.vertex_count() < g->vertex_count()) { return false;

}

this->ext = &ext;

calc_degrees(ext, ext_degrees);

edges.clear(); int n = ext.vertex_count(); for (int u = 1; u < n; ++u) { for (int v = 0; v < u; ++v) { if (ext.edge(u, v)) {

edges.push_back(make_pair(u, v));

}

}

int edge_count = static_cast<int>(edges.size());

if (k > edge_count) { return false;

}

to_remove.set(k, edge_count);

if (to_remove.reset()) { do {

const vector<int> & subset = to_remove.value(); for (int i = static_cast<int>(subset.size()) - 1; i >= 0; -i) {

ext.remove_edge(edges[subset[i]].first, edges[subset[i]].second);

--ext_degrees[edges[subset[i]].first]; --ext_degrees[edges[subset[i]].second];

}

bool embedded = edge_prefix_enum.init(g->vertex_count(), ext.vertex_count());

for (int i = static_cast<int>(subset.size()) - 1; i >= 0; -i) {

ext.add_edge(edges[subset[i]].first, edges[subset[i]].second);

++ext_degrees[edges[subset[i]].first]; ++ext_degrees[edges[subset[i]].second];

}

if (!embedded) { return false;

}

} while (to_remove.next());

}

return true;

}

static inline bool subgraph_isomorphism_handler( const vector<vector<int>> & edges, const graph & h,

const vector<int> & g_degrees, const vector<int> & h_degrees, const vector<int> & p, int index) {

int gv = index; int hv = p[gv];

if (g_degrees[gv] > h_degrees[hv]) { return false;

}

for (int gu : edges[gv]) { if (!h.edge(hv, p[gu])) { return false;

}

}

return true;

}

};

#endif

Проверку каноничности М-кода графа реализует метод «check» класс «canonicity_checker». Метод принимает граф «g», количество рёбер в котором должно быть равно количеству рёбер в графе «sg», который устанавливается методом «set_graph». Именно на основе «sg» и строится М-код графа «g». Само построение кода для проверки не нужно, так как сам код взаимооднозначно определяется матрицей смежности графа. Именно матрица смежности используется для проверки. Внутренний класс «canonicity_checker::handler» является параметром для шаблона «permutation_enumerator». Класс «canonicity_checker» описан в файле «canonicity.h»:

#ifndef CANONICITY_H_ #define CANONICITY_H_

#include "enumeration.h" #include "graph.h"

using namespace std;

class canonicity_checker {

private:

struct handler {

static const int NOT_GREATER = 0x7fff;

vector<vector<int>> edges; vector<int> edge_classes_used; const graph * sg; const graph * g; int greater;

handler()

: sg(nullptr) , g(nullptr)

, greater(NOT_GREATER) {

r

}

handler(const handler&) = default; handler(handler&&) = default;

handler& operator=(const handler &) = default; handler& operator=(handler &&) = default;

static inline int compare_row( const graph & g, const vector<int> & p, int i){

for (int j = 0; j < i; ++j) {

int cmp = g.edge(i, j) - g.edge(p[i], p[j]); if (cmp != 0) { return cmp;

}

}

return 0;

}

inline bool operator()(const vector<int> & p, int i) { if (i <= greater) {

greater = NOT_GREATER;

}

int pi = p[i];

for (int j : edges[i]) {

if (!g->edge(pi, p[j])) { return false;

}

}

if (i > greater) { return true;

}

int cmp = compare_row(*g, p, i); if (cmp > 0) { return false;