Архив публикаций

Тезисы

XIII-ая конференция

Анализ отказоустойчивости вычислительной среды планетарного типа

Коганов А. В., Сазонов А. Н.

НИИ Системных Исследований РАН, Россия, 117218, г. Москва, Нахимовский пр-т, 36, корп. 1. Тел/факс.: (095) 719-76-81,E-mail: koganow@niisi.msk.ru

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

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

Результаты могут представлять интерес для проектирования отказоустойчивых вычислительных систем.