Software & Systems

Системы различной степени обобщенности авторами рассматривались ранее, исследовались разные аспекты их отказоустойчивости [1–4]. Общей чертой этих систем было построение их модели в виде направленного раскрашенного графа, вершины которого представляли некоторые функциональные элементы системы, а дуги – связи между ними. Кроме того, рассматривались различные модели задач, аналогичные моделям систем, а иногда и совпадающие с ними, а также задавался итерационный алгоритм вычисления отказоустойчивости при помощи моделирования процессов разрушения и восстановления узлов исходной системы. Следующим шагом были исследования критических точек отказоустойчивости, также поддержанные программами имитационного моделирования. Вопросы отказоустойчивости растущих систем исследовались и с использованием метода Монте-Карло.

Приводились понятия графов системы и задачи, а также процессов разрушения и восстановления с различными вариациям. Отметим только, что работоспособность системы определяется возможностью вложения графа задачи в граф системы с сохранением типов вершин и направленных связей. Граф задачи соответствует необходимой для решения системе информационных ресурсов. Цель данной работы – описание системы программ, позволяющей проводить анализ наработки на отказ в такой модели вычислительной системы и задачи.

Графы произвольной структуры

Подобные графы, являясь наиболее общим классом графов систем, сложны для изучения вопросов, связанных с отказоустойчивостью. Исследования некоторых свойств таких систем приведены в [1]. Описанные в работе алгоритмы для графов систем произвольного вида реализованы в модуле RelGraph.

Основные возможности программы RelGraph включают различные аспекты визуального редактирования графов, применение алгоритмов генерации и поиска изоморфного подграфа, а также просмотр найденных решений. Представление графической информации в главном окне программы показано на рисунке 1.

Просмотр и редактирование произвольных графов. Программа позволяет добавлять, перемещать и удалять вершины графов с указанием одного из доступных типов вершин. Вершину текущего типа можно добавить при помощи двойного щелчка левой кнопкой мыши на любом свободном месте поля рисования графов. Одинарный щелчок выделяет вершины и дуги. Щелчок правой кнопкой мыши добавляет дугу от выделенной вершины к той, на которой произведен щелчок. Клавиша Del удаляет выделенную вершину и инцидентные ей дуги. Авторы нашли целесообразным написать редактор графов самостоятельно с использованием технологии Windows Presentation Foundation. Редактор графов также поддерживает масштабирование визуализации, что особенно полезно при работе с большими графами. Графы могут быть записаны и считаны из файлов формата XML.

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

Каждый тип вершины обозначен одной или несколькими буквами, которые указываются на изображении вершины в скобках после номера. Тип вершины может изменить только пользователь, цвет выбирается автоматически. В дальнейшем при использовании термина «цвет» в контексте узла графа будем иметь в виду ее тип, а не цвет отображения.

Генерация графов. Программа поддерживает автоматическую генерацию графов четырех типов.

1.   Полный – требуется указать количество вершин и цветов; графы такого типа исследуются в работе [3].

2.   Случайный – требуется указать количество вершин, цветов и среднее количество дуг у вершины.

3.   Планетарный – необходимо указать количество звезд, количество цветов планет и среднее количество планет каждого типа у звезды [1, 3]. Звезды автоматически получают свой отдельный тип, поэтому при генерации планетарного графа реальное количество типов элементов оказывается на единицу больше соответствующего параметра генерации. Исключение могут составить лишь те планетарные графы, при генерации которых не все цвета были использованы в силу вероятностного характера процесса генерации.

4.   Кольцевой – требуется задать лишь количество вершин и цветов [3].

Поиск подграфа в графе системы, изоморфного графу задачи. Данная возможность включает функцию разбиения графов на связные компоненты (рис. 2). Компонента представлена перечнем номеров своих вершин.

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

Основу алгоритма составляют два этапа – поиск возможных вариантов отображения для каждой из вершин графа задачи и перебор полученных вариантов отображения для всех вершин графа задачи [1]. Алгоритм может быть параметризован следующим образом.

Указание частоты проверки допустимости частичного решения. Алгоритм поиска подграфа рекурсивный, поэтому единицей изменения данного параметра является уровень вложенности. Например, при работе с настройками по умолчанию используется значение 2, тем самым показывая, что проверка частичного решения будет производиться через один рекурсивный вызов. Теоретически это значение может вызвать замедление работы в случае, когда перед началом полной проверки частичных решений на втором уровне вложенности накопится большое количество неверных вариантов на первом уровне, которые все придется проверять. Каждое из них будет протестировано с выполнением рекурсивного спуска еще на один шаг и проверкой всех вариантов на новом уровне рекурсии с применением, возможно, неправильного частичного решения. Однако процесс проверки частичного решения еще более сложный, чем последовательный перебор вариантов. Тесты показали, что задание частоты проверки менее двух обычно неэффективно. Значение периода проверки, меньшее или равное единице, указывает алгоритму на необходимость проведения проверки каждого частичного решения.

Запрос предварительной сортировки вершин графа задачи по количеству доступных вариантов вложения в систему (по убыванию или возрастанию). Данная возможность может использоваться, например, для перенесения вершины графа задачи с наибольшим количеством вариантов вложения в начало списка. В противном случае возможно, что большинство вершин графа задачи, имеющих лишь несколько вариантов вложения, обрабатываются первыми, вследствие чего, особенно при редких проверках решений, средний размер проверяемого частичного решения возрастает.

Сортировка вариантов по количеству инцидентных вершин (по убыванию или возрастанию). Данная опция применяется к спискам вариантов отображения вершины графа задачи, определяемых для каждой такой вершины. Здесь используются эмпирические соображения о возможности ускорения алгоритма в том случае, когда первыми проверяются варианты отображения, имеющие наибольшее количество инцидентных вершин. Вершина, связанная лишь с одной или двумя соседними, в среднем оставит меньше вариантов дальнейшего отображения, чем вершина, имеющая большее количество соседей.

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

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

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

Описание комплекта программ для исследования средней наработки планетарных вычислительных систем

Программа RelConsole является консольным приложением Windows, предоставляющим часть функциональности программы RelGraph для использования в пакетном режиме. Формат входных данных программы совпадает с форматом, генерируемым программой RelGenerator. Результаты работы записываются в файл результата – в нем указываются статистические параметры, а также описывается конкретное полученное решение (вложение графа задачи). При использовании программы в пакетном режиме больший интерес представляет файл статистики, который содержит лишь статистические данные и не содержит описание полученного решения.

В файл статистики добавляются следующие значения (слева направо):

·     имя файла, содержащего граф модели задачи, указанный как параметр при запуске программы;

·     имя файла, содержащего граф системы, указанный как параметр при запуске программы;

·     имя файла  настроек, указанного как параметр при запуске программы;

·     количество рекурсий;

·     количество попыток разложения частичного результата;

·     затраченное время;

·     минимальное теоретическое количество склеек;

·     максимальное теоретическое количество склеек;

·     полученное количество склеек;

·     статус теста (OK/FAIL).

Кроме записи результата в файлы, программа возвращает операционной системе код ошибки, который можно использовать из командных файлов для определения наработки в пакетном режиме: 0 – успех, 1 – неудача, 2 – ошибка, не связанная с расчетами (невозможно создать файл и т.п.).

Программа RelGenerator предназначена для создания набора каталогов и файлов с заданиями для RelConsole, моделирующими процесс разрушения планетарной вычислительной системы (ПВС) [1]. Главное окно программы позволяет ввести все исходные параметры в соответствующие поименованные окошки.

Программа позволяет изменять следующие настройки:

– количество звезд, S, для генерации ПВС (от, до);

– количество цветов, C, для генерации ПВС (от, до);

– среднее количество планет, K, каждого цвета у каждой звезды для генерации ПВС (от, до);

– вероятность разрушения, Pd;

– вероятность восстановления, Pf: если пункт не выбран, восстановление не производится;

– средний процент звезд, включаемых в граф модели задачи при генерации задачи по графу ПВС;

– средний процент планет, включаемых в граф модели задачи для каждой звезды при генерации задачи по графу ПВС;

– количество генерируемых задач;

– количество итераций разрушения, Ni;

– количество испытаний, Ne, для каждого набора параметров S, C, K;

– каталог, в котором должны быть созданы командные файлы и XML-файлы графов МЗ и ПВС;

– полный путь к исполняемому файлу RelConsole.exe; введенное значение будет записано в командные файлы в качестве строки вызова программы RelConsole.

Алгоритм программы генерации файлов состоит из следующих шагов.

1.   Создается каталог для размещения файлов и подкаталогов.

2.   Для каждого допустимого набора S, C и K в созданном ранее каталоге создается каталог ПВС с именем sck, где , , – значения соответствующих параметров. Например, для S=2, C=3 и K=4 каталог будет называться s002c03k04.

3.   Для текущих S, C и K генерируется ПВС, граф которой записывается в каталог ПВС в файл с именем _generic.xml. В каталоге ПВС создаются подкаталоги _Destruct и _Soft.

4.   В каталог _Destruct помещается не более Ni файлов с графами разрушенной ПВС (РПВС), полученными в результате последовательного разрушения сгенерированной ранее ПВС. Если ПВС полностью разрушена менее чем за Ni шагов, файлы с пустыми графами для дальнейших итераций не генерируются.

5.   В каталог _Soft помещаются файлы задач, сгенерированные на основе графа ПВС с учетом настроек программы.

6.   Для всех i=0, …, Ne-1 создаются подкаталоги запуска Run, например, Run00000005 для i=5, в каждом каталоге – командный файл _run.cmd. Командный файл состоит из командных блоков следующего вида:

−    запустить RelConsole для soft[rnd].xml, hard[i].xml, sett.xml, где [rnd] – случайное значение от 0 до количества сгенерированных задач без 1, i =0, …, Ne;

−    в случае неудачи дописать собранную статистику в файл stat.csv в каталоге ПВС, дописать значение i+1 в _finish.txt в каталоге ПВС, иначе продолжить.

Указанные блоки записываются для каждого i от 0 до количества сгенерированных ПВС. Если сгенерировано Ne ПВС (граф не был полностью разрушен), то в последнем блоке в _finish.txt дописывается метка [all], обозначающая, что, если вычисления дошли до этой команды, эксперимент был полностью удачным. Если сгенерировано менее Ne ПВС, то после последнего блока добавляется команда записи в _finish.txt значения i+1 и метки [empty], обозначающей полное разрушение графа РПВС.

7.   В каталог ПВС записывается файл _run.cmd, последовательно вызывающий все _run.cmd из каталогов запусков.

8.   В основной каталог записывается файл _run.cmd, последовательно вызывающий все _run.cmd из каталогов ПВС.

В результате работы командных файлов, сгенерированных программой, в каждом каталоге тестов накапливаются файлы результатов для каждого запуска RelConsole и один файл stat.csv со статистикой для данного запуска. В каталоге ПВС сохраняются файлы _finish.txt со значениями наработки и указаниями на полное разрушение или полный успех и stat.csv, являющийся объединением всех stat.csv из каталогов запуска. При таком подходе возможно детально рассмотреть каждый проведенный тест, а также получить обобщенную информацию для каждого набора параметров S, C и K из _finish.txt и stat.csv. Информация в stat.csv описывает сложность проведения экспериментов и количество склеек, в то время как _finish.txt описывает полученные значения наработки. Для дальнейшего анализа результатов работы применяется программа RelCollector.

Программа RelCollector предназначена для сбора и анализа результатов работы командных файлов, сгенерированных при помощи программы RelGenerator. Главное окно программы позволяет ввести все исходные параметры в соответствующие поименованные окошки.

Программа исследует все каталоги, вложенные в указанный пользователем. По имени каталога программа определяет S, C и K, использованные для генерации ПВС. Анализируя информацию, содержащуюся в файлах _finish.txt, программа подсчитывает для каждого S, C и K величины математического ожидания и дисперсии наработки, количество полных успехов и количество полных разрушений. На основании информации из файлов stat.csv программа подсчитывает средние значения количества тестов, рекурсий, минимального, максимального и полученного количества склеек, а также затраченного времени. В файл результата записываются все упомянутые значения, а также формулы линейной регрессии математического ожидания наработки по каждому из параметров S, C и K.

Программа RelStar предназначена для исследования отказоустойчивости ПВС. Главное окно программы позволяет ввести все исходные параметры в соответствующие поименованные окошки.

Возможности программы аналогичны связке из RelConsole + RelGenerator + RelCollector, однако алгоритм поиска подграфа системы, изоморфного графу модели задачи, оптимизирован для случая ПВС. Граф задачи совпадает с графом неразрушенной ПВС, поэтому параметры генерации задачи отсутствуют. При этом программа генерирует статистику, аналогичную результатам работы RelCollector, однако файлы результатов не генерируются, так как алгоритм определяет разложимость графа задачи на граф системы без точного указания отображения для каждой вершины [3]. Несмотря на это, программа имеет возможность генерировать файлы с текстовым описанием графов задачи и РПВС, состоящие из нескольких секций – по количеству неразрушенных планетарных систем. Для каждой планетарной системы указываются номер (id) звезды, а затем количество работоспособных (alive) и отказавших (dead) планет для всех цветов, для которых есть неразрушенные планеты. Отсутствие информации о планетах какого-либо цвета означает, что все планеты этого цвета разрушены.

По окончании работы, вне зависимости от настроек протоколирования, программа генерирует в выбранном каталоге файл finish.csv, содержащий указанные при запуске параметры и результаты счета, включая статистические данные.

Пакет программ для поиска критической вероятности разрушения ПВС

Программа RelCrit предназначена для поиска критической точки отказоустойчивости по заданным параметрам S, C, K, Pdmin, Pdmax, DPd, Pf, Ni, Ne и e [3]. Главное окно программы позволяет ввести все исходные параметры в соответствующие поименованные окошки. Пример окна показан на рисунке 4. Аналогично выглядят и главные окна других модулей.

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

По окончании работы, вне зависимости от настроек протоколирования, программа генерирует в указанном каталоге файл finish.csv, содержащий указанные при запуске параметры и результаты счета. В первой секции указываются заданные при старте расчета параметры. Во второй секции для каждого значения вероятности разрушения Pd указываются полученные статистические данные и результат проверки условия на e [3], подтверждая, что эксперимент при данном Pd считается успешным. В третьей секции указывается полученное значение критической вероятности разрушения или помещается сообщение о том, что критическая точка не найдена.

Программа RelMultiCrit предназначена для поиска критической точки отказоустойчивости по заданным диапазонам изменения параметров S, Pd и Pf и параметрам C, K, Pf, Ni, Ne и e [3]. Главное окно программы позволяет ввести все исходные параметры в соответствующие поименованные окошки.

Алгоритм работы программы является расширенной версией алгоритма RelCrit и позволяет варьировать S, Pd и Pf. Данный модуль поддерживает облегченную версию протоколирования: для каждой пары значений S и Pf создается отдельный файл статистики. Информация о количестве склеек не подсчитывается. По окончании работы программа генерирует в определенном каталоге файл finish.csv, в первой секции которого указываются заданные при старте расчета параметры. Во второй секции располагается матрица полученных значений критической вероятности для указанных Pf и S. Если критическая точка не найдена, критическая вероятность разрушения Pc полагается равной нулю [3].

Исследование растущих систем

Для исследования растущих наборов кольцевых вычислительных систем (КлВС, [4]) предназначена программа RelCircle. Программа позволяет задавать параметры Ni, Ne, Pd, а также указывать диапазоны и шаги изменения любых двух из следующих величин: параметров генерации одной системы (S, C, Pf) и параметров роста набора систем (E0=N, E1=k) [4]. Главное окно программы позволяет ввести все исходные параметры в соответствующие поименованные окошки.

Поля отметок «Vary…» дают возможность выбрать варьируемые параметры, но не более двух. По окончании работы программа создает (или заменяет без предупреждения, если уже существует) файл circle.csv в указанном каталоге. Первый блок файла результатов составляют значения заданных параметров. В таблице приведен пример файла результатов программы, правый столбец содержит описание данных, отсутствующее в генерирующемся файле. Заголовочная секция может изменяться в соответствии с параметрами, выбранными для варьирования.

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

Подытоживая, следует отметить, что модули RelConsole, RelGenerator, RelStar, RelCrit, RelMultiCrit, RelCircle реализованы на C++ с использованием библиотеки MFC, тестировались и применялись в среде Microsoft Windows XP. Модуль RelCollectior реализован на C# (.NET Framework 2.0, Windows Forms). Программа RelGraph создана на C# 2008, .NET Framework 3.5, WPF.

Численные эксперименты проводились авторами с использованием указанных программ в работах [1, 3, 4].

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

Литература

1. Коганов А.В., Сазонов А.Н. Анализ отказоустойчивости вычислительной среды планетарного типа // Математика. Компьютер. Образование: сб. науч. тр. [под ред. Г.Ю. Ризниченко]. М.–Ижевск: НИЦ «Регулярная и хаотическая динамика», 2006. Вып. 13. Ч. 2. С. 235–248.

2. Коганов А.В., Сазонов А.Н. Корпоративные вычислительные сети с разрушением и восстановлением. Фазовый переход в растущих сетях // Математика. Компьютер. Образование: сб. науч. тр. [под ред. Г.Ю. Ризниченко]. М.–Ижевск: НИЦ «Регулярная и хаотическая динамика», 2007. Т. 2. С. 48–59.

3. Коганов А.В., Сазонов А.Н. Анализ критических точек отказоустойчивости вычислительной среды планетарного типа // Программные продукты и системы. 2007. № 3. С. 27–31.

4. Коганов А.В., Сазонов А.Н. Анализ отказоустойчивости наборов кольцевых систем // Программные продукты и системы. 2010. № 2. С. 8–13.