автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Оптимизация и диагностирование распределенных вычислительных систем гидроакустических комплексов

Грузликов Александр Михайлович

ОПТИМИЗАЦИЯ И ДИАГНОСТИРОВАНИЕ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ ГИДРОАКУСТИЧЕСКИХ КОМПЛЕКСОВ

Специальность: 05.13.01 - Системный анализ, управление и обработка информации (в технических системах)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

005570323

Санкт-Петербург - 2015

005570323

Работа выполнена в государственном научном центре Российской Федерации ОАО «Концерн «ЦНИИ «Электроприбор»

Научный руководитель: доктор технических наук, профессор

Колесов Николай Викторович

Официальные оппоненты: Подкопаев Борис Павлович

доктор технических наук, Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» (СПбГЭТУ), профессор кафедры Радиотехнических систем

Костенко Валерий Алексеевич

кандидат технических наук, МГУ имени М.В. Ломоносова, ведущий научный сотрудник кафедры Автоматизации систем вычислительных комплексов

Ведущая организация: Санкт-Петербургский

государственный университет аэрокосмического приборостроения

Защита состоится 21 мая 2015 г. в 17 часов 30 минут на заседании диссертационного совета Д 212.227.03 при Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики по адресу: 197101 Санкт-Петербург, Кронверкский просп., 49., ауд. 461.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д.49 и на сайте fppo.ifmo.ru . Автореферат разослан «08» апреля 2015 г.

Ученый секретарь диссертационного совета

Дударенко Наталия Александровна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Проблема назначения задач широко освещалась в мировой научно-технической литературе. При этом основополагающие результаты получены в работах Coffman E.G., Martello S., Toth P., Keller H., Топоркова B.B., Костенко В.А. и многих других. Обычно при разработке процедур назначения используется оптимизационная постановка с критериями, обеспечивающими, например, равномерность загрузки процессоров, минимальность необходимого числа процессоров или каналов обмена, максимум надежности и т.п.. Алгоритмы назначения формулируются в рамках различных подходов, начиная с исторически первой задачи о контейнерах и далее с позиций генетической и графовой концепций, теории игр и других. Однако высокая размерность задачи, характерная для практики проектирования ГАК, необходимость проведения вычислений, а иногда и решения самой проблемы назначения в реальном времени делает известные подходы неработоспособными, а продолжение исследований в этом направлении актуальным.

Общеизвестна сложность проблемы обнаружения и диагностирования нарушений в современных информационно-измерительных комплексах, и в гидроакустических комплексах, в частности. Эти вопросы с разных точек зрения активно обсуждаются в литературе на протяжении ряда последних десятилетий. Среди наиболее известных авторов можно назвать Wiilsky A.S., Patton R.J., Frank P.M., Clark R.N., Sampath M., Lafortune S., Teneketzis D., Пархоменко П.П., Мироновского Jl.A., Шумского A.E., Жирабка А.Н., Подкопаева Б.П. Сложность проблемы диагностирования распределенных вычислительных систем определяется не только их высокой размерностью, но и множественностью причин возникновения нарушений. Источником нарушений вычислительного процесса могут быть как отказы аппаратуры, так и ошибки в организации вычислений и в используемых программах, допущенные разработчиками. Понятно, что параллельность вычислений существенно затрудняет необходимые процедуры анализа их корректности, делая непригодными процедуры, ориентированные на последовательные вычисления. Все эти факторы подтверждают значимость диагностического обеспечения распределенных вычислительных систем и актуальность исследований, направленных на его совершенствование.

Цель работы и задачи исследования. Цель исследования состоит в разработке и исследовании эффективных формальных алгоритмов назначения заданий и диагностирования нарушений параллельных вычислений в ГАК.

Для достижения этой цели были решены следующие задачи:

- анализ современных методов назначения задач и диагностирования распределенных вычислительных систем в системах реального времени;

- исследование методов назначения задач на процессоры ГАК;

- разработка подхода к диагностированию распределенных вычислений в ГАК;

- разработка программных средств, поддерживающих процедуры назначения заданий и синтеза средств диагностирования, распределенных вычислений в ГАК;

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

Методы исследования. Для решения поставленных задач использовались методы теории графов, теории управления, теории алгоритмов.

Научная новизна

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

2. Показано, что в области доминирования остовный алгоритм не более чем в 10% случаев, а кластерный алгоритм не более чем в 1% проигрывают оптимальному алгоритму больше 30%.

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

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

Теоретическая и практическая ценность

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

Практическая ценность подтверждается разработкой инструментальной среды, основанной на предложенных алгоритмах и предназначенной для формирования конфигурации событийной распределенной системы обработки информации с решением задач назначения и диагностирования. Апробация среды осуществлена применительно к тренажеру для операторов ГАК «Мостик» и гидроакустической станции геологоразведки (ГАС ГР) «Шотко-сичка-ЭП».

Основные положения, выносимые на защиту:

- научно-техническое обоснование факта наличия для алгоритмов назначения неперекрывающихся областей эффективного применения;

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

- алгоритм синтеза дискретно-событийной динамической модели распределенной вычислительной системы.

Апробация работы. Материалы диссертации докладывались на 6-й и 7-й Всероссийской мультиконференции по проблемам управления (Дивномор-ское, 2013; Санкт-Петербург, 2014), на 6-й Всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (Казань, 2013), на XIX Международном научно-техническом семинаре «Современные технологии в задачах управления, автоматики и обработки информации» (Алушта, 2013), на XXIX конференции памяти выдающегося конструктора гироскопических приборов H.H. Острякова (Санкт-Петербург, 2014), на XII Всероссийском совещании по проблемам управления (Москва, 2014).

Публикации. По материалам диссертации имеется 10 опубликованных работ, из них 3 публикации в ведущих рецензируемых изданиях (2 статьи в научно-техническом журнале «Известия РАН. Теория и системы управления», 1 статья в международном журнале «International Journal of Applied Mathematics and Computer Science»), рекомендуемом ВАК Минобразования и науки РФ, 5 докладов и 2 реферата докладов на всероссийских конференциях.

Структура и объем диссертации. Диссертация состоит из введения, четырех разделов, заключения и списка использованных источников, содержащего 124 наименований. Объем работы составляет 155 страниц, включая 57 рисунков и 17 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении приводится общая характеристика работы — ее актуальность, научная новизна, практическая ценность, сведения об апробации работы и публикациях. Формулируются основные положения, выносимые на защиту.

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

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

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

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

В общем случае граф С(А,В) не является связным и состоит из т

компонент связности Я = ^ | у = 1,«}, которые в дальнейшем будем называть заданиями, т.е. назначению на процессоры подлежат ш независимых заданий т = {т^ | у = 1,/и}. Каждое задание т^ состоит из задач

{т! к | А = 1,/Иу }(/му - число задач в .¡-м задании). Для всех задач известны длительности их исполнения на используемом типе процессора I .¡ = 1>П1> А = 1,/и-}. Все процессоры имеют одинаковую

производительность, а задачи и задания выполняются с одинаковым периодом Т. Причем за время Т любая задача может быть решена на одном процессоре, т.е. е^ < Т, однако все задачи из С(А,В) не могут быть решены

на одном процессоре, т.е.

т mJ

что вынуждает использовать распределенные вычисления.

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

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

3 =а\Р\ + Ь\С\, (1)

где а и Ь - весовые коэффициенты. Распределение задач рассматривается со следующими ограничениями:

1. Суммарное время Е. исполнения задач назначенных на каждый /-й процессор, не может превышать период Т поступления входной информации,

т.е. £, =|>,Л.< Г.

2. Суммарное время О, передачи данных между задачами через каждый 1-й канал не может превышать пропускной способности И канала

обмена на периоде, т.е. О, = < О, где с!1к - длительность к-та обмена в /м канале.

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

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

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

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

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

В процессе исследования формировались статистики примеров, отличающихся от оптимального результата не более чем на 10% и 30%. Длительности задач моделировались в условных единицах как равномерно распределенные в интервале [0.1, 10], аналогично длительности обменов - в интервале [0.1, 5] при допустимой загрузке процессора и канала обмена, равных 10.

% 100

8Q 60 40 20 О

0 2 4 6 8 10 12 14 16

Рисунок 1 - Эффективность алгоритмов назначения при Ь/а = 0,1 На рисунке 1 и 2 приведены ряды статистик, полученных для разных типов графов заданий. Эти рисунки соответствуют разным значениям отношения Ь/а. В первом случае (рисунок 1) Ь/а = 0,1, во втором (рисунок 2) - Ь/а -10. Выбор правильного соотношения между коэффициентами awb определяется рассматриваемым практическим приложением.

i 100 80 60 40 20 0

0 2 4 6 8 1С 12 14 16

Рисунок 2 — Эффективность алгоритмов назначения при b/a = 10

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

% 100 80 60 40 20 0

0.01 0.1 1 10 100 Рисунок 3 - Области эффективного применения для кластерного и остовного алгоритмов

Результаты исследование эффективности алгоритмов назначения показали, что в области доминирования остовный алгоритм не более чем в 10% случаев, а кластерный алгоритм не более чем в 1% проигрывают оптимальному алгоритму больше 30%.

Сравнивая информацию, представленную на рисунках 1 и 2, можно видеть, что эффективность методов зависит от рассматриваемого приложения

(от значения Ь/а). На первом рисунке наблюдается преобладание остовного алгоритма, на втором - кластерного. Этот факт подтверждает рисунок 3, где статистики проигрышей этих алгоритмов по отношению к оптимальному (алгоритму полного перебора) в пределах 10%-ного допуска представлены в зависимости от значения Ь/а. Статистики приведены для древообразных заданий и заданий с пятью циклами.

В представленных данных нет ничего удивительного, поскольку известно, что одни и те же данные при разных критериях могут свидетельствовать как о выигрыше, так и о проигрыше одного алгоритма по отношению к другому.

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

Для пояснения сути предлагаемого подхода рассмотрим информационный граф некоторой гипотетической системы Б (рисунок 4). В системе реализуются три функционально связанных программных модулей (ПМ): ЯЛ/,, ПМ2 и ПМЪ, которые могут быть размещены как на разных процессорах системы, так и на одном. Каждый из ПМ на основе входных данных (г/, - для ПМ1, и2 и у, -для ПМ2, у\ и у2 - для ПМ,) формирует выходные О',, у,и З'з соответственно).

Рисунок 4 - Информационный граф системы

Система диагностирования (СД) формирует для системы 8 тестовые данные, дополняя ими входные данные для ПМ] и ПМ2, и анализирует выходную реакцию Б (ПМ3). В каждом из ПМ - ПМ1, ПМ2 и ЯЛ/3 — реальные информационные слова обрабатываются штатными алгоритмами. Параллельно с этим тестовые информационные слова обрабатываются специальными алгоритмами /т1, /т2 и /т3, реагирующими на события приема/выдачи информации, а результаты их обработки выдаются в составе выходных данных. Поскольку механизм обмена реальными и тестовыми данными в системе является общим, возникает возможность по наблюдаемым в процессе работы тестовым результатам делать вывод о наличии или отсутствии в обменах рассматриваемых нарушений - изменений множеств участвующих в конкретных обменах ПМ.

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

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

м„

«в

У\

М22 Ми

¡Г V-,

М21 м„

0

>'з

Рисунок 5 - Модель для системы Б Представим цепь в виде линейной динамической системы, вектором состояния которой является вектор дг(?), составленный из векторов состояния звеньев х,{() / = 1, £, входящих в эту цепь. Тогда

*(/ +1) = гужо + симо, у(1) = я(¿ио ] = +

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

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

Для окончательной детализации модели распределенной системы необходимо осуществить выбор звеньев для всех цепей. Этот выбор должен гарантировать для каждой из цепей свойства наблюдаемости и управляемости. Достаточные условия, которым должны удовлетворять звенья цепи и выполнение которых гарантирует для цепи свойства наблюдаемости и управляемости, рассмотрены в литературе. Однако применение описанной выше модели распределенной системы, состоящей из независимых цепей, может в некоторых случаях потребовать передачи через канал обмена большого количества информации, что не всегда допустимо. В таких ситуациях целесообразно воспользоваться приемом, заключающимся в обработки нескольких массивов одним звеном (слияние вычислительных путей). Такой вариант отражен штриховой стрелкой на рисунке 5. Здесь массивы у, и у2 (формируемый звеном М22) обрабатываются звеном М}1, а звено МЪ2 исключается. В результате сокращается размерность выходного вектора. В модели со слиянием цепей считается, что последовательно обрабатываются не только разные порции информации, но и одна и та же порция информации в разных цепях, подвергшихся слиянию. Для периодически нестационарной системы со слиянием цепей в диссертационной работе показана возможность описания стационарной моделью.

Утверждение I. Для любой периодически нестационарной системы 5т, которая:

1. состоит из р скалярных цепей, сходящихся в одном скалярном звене (^о'/о'Яо) размерности т0, при этом 1-я цепь содержит I., звеньев

2. описывается моделью

3. имеет на периоде функционирования один сеанс приема информации от СД, описываемый для некоторой последовательности у: матрицами

Г(уг(Ь£ + \)),С(уг(Ь£ +\)),Н(уг(1у + \)), и один сеанс выдачи информации в СД, описываемый матрицами Р(уг (ОУуг(1<ъ)), Н(уг(1.ъ)), существует стационарная система §т

х(к+\) = Ах(к) + Ви{к), у(к) = Сх(к), (3)

которая при любой входной последовательности формирует выходные последовательности, совпадающие с последовательностями цепи на уТ. При

этом к- периоды системы (1), А = Гп(уг) = ГГ^Х/ЛА: + 2)),

1=1

в=о(уг(и +1)), С = Н(уг( ь^Р-ЧгЛ += Н(уг (1£))Л.

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

Утверждение 2. Система полностью наблюдаема и управляема, если

1.все ее цепи и звено (Л0,/0,£0), /0 = /0Р, Л„ = [/„р]т - т-я строка матрицы//, £„ = [/,".?<, /0Р~]ёи - Ли] наблюдаемы и управляемы,

2. характеристические многочлены ^ матриц звеньев / = 1,1,,, 1 = \,р неприводимы,

3. многочлены {(р, | ср, = \\<р 1 = \,р) и характеристический многочлен ^ матрицы /' взаимно просты,

4. < д<р , / = 1,/?, / = 1Д,.

Утверждение 3. Если система (3) наблюдаема (управляема), то система (1) ^-наблюдаема(^-управляема).

Утверждение 4. Если периодически нестационарная система 5т (2) у, -наблюдаема и ^-управляема, и все ее матрицы динамики неособенные, то она полностью наблюдаема и управляема.

В четвертой главе диссертации представлены результаты практической апробации предложенных методов назначения задач и диагностирования распределенных вычислительных систем современных гидроакустических комплексов. Описываются два примера такого применения, среди которых тренажер для операторов ГАК «Мостик-77» и ГАС ГР «Шоткосичка-ЭП».

Приведенные результаты получены с использованием разработанной автором инструментальной среды. Среда позволяет формировать конфигурацию событийной распределенной системы обработки информации с решением задач назначения и диагностирования (рисунок 6). Информационный граф тренажера содержал 23 вершины. К нему были применены все описанные в главе 2 алгоритмы назначения. Результаты применения сведены в таблицу 1. Информационный граф ГАС ГР содержал 10 вершин. Результаты применения сведены в таблицу 2.

Рисунок 6 - Структура разработанной инструментальной среды Таблица 1

Оценка эффективности назначения в ГАК «Мостик-77»

№ Название алгоритма Оценка эффективности

1. Кластерный алгоритм 95

2. 2-х этапная процедура с кластерным алгоритмом 57

3. Остовный алгоритм 58

4. 2-х этапная процедура с остовным алгоритмом 58

5. Оптимальный алгоритм полного перебора 55

Таблица 2

Оценка эффективности назначения в ГАС ГР «Шоткосичка-ЭП»

№ Название алгоритма Оценка эффективности

1. Кластерный алгоритм 14

2. 2-х этапная процедура с кластерным алгоритмом 6

3. Остовный алгоритм 9

4. 2-х этапная процедура с остовным алгоритмом 9

5. Оптимальный алгоритм полного перебора 6

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

При разработке средств диагностирования также была использована разработанная инструментальная среда, которая по виду информационного графа формирует модель системы, состоящую из подмоделей цепей, входящих в покрытие ребер графа, а затем для модели каждой цепи строится тест и соответствующая эталонная реакция. Для графа тренажера в покрытие ребер вошло 26 цепей разной длины. Общая размерность модели равнялась 89. Для графа ГАС ГР в покрытие ребер вошло 10 цепей разной длины. Общая размерность модели равнялась 22.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

2. Показано, что в области доминирования остовный алгоритм не более чем в 10% случаев, а кластерный алгоритм не более чем в 1% проигрывают оптимальному алгоритму больше 30%.

3. Предложен алгоритм диагностирования распределенных вычислительных систем реального времени в рамках концепции тестового диагностирования, отличающийся от известных использованием дискретно-

событийной динамической модели и возможностью обнаруживать в режиме реального времени более широкий класс нарушений.

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

5. Разработана основанная на предложенных алгоритмах инструментальная среда для формирования конфигурации событийной распределенной системы обработки информации с решением задач назначения диагностирования. Апробация среды осуществлена в разработках ОАО «Концерн «ЦНИИ «Электроприбор» применительно к тренажеру для операторов ГАК «Мостик» и гидроакустической станции геологоразведки «Шоткосичка-ЭП».

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях, рекомендуемых ВАК

1. Грузликов, A.M. Графовый подход к назначению заданий в распределенных системах реального времени / A.M. Грузликов, Н.В. Колесов, Ю.М. Скородумов, М.В. Толмачева // Известия РАН. Теория и системы управления, № 5, 2014, С. 84 - 94. - 0.8 / 0.7 п.л.

2. Грузликов, A.M. Нестационарные модели в задачах диагностирования вычислительных систем реального времени / A.M. Грузликов, Н.В. Колесов, Ю.М. Скородумов, М.В. Толмачева // Известия РАН. Теория и системы управления, № 6,2014, С. 94 - 104. - 0.8 / 0.65 п.л.

3. Gruzlikov, A.M. Event Monitoring of parallel computations / A.M. Gru-zlikov, N.V. Kolesov, M.V. Tolmacheva // Int. J. Applied Mathematics and Computer Science, Vol. 25, №2,2015. p.272 - 282. - 0.8 / 0.65 п.л.

Другие публикации

4. Грузликов, A.M. Автоматизированный синтез и анализ средств мониторинга параллельных вычислений / A.M. Грузликов, Н.В. Колесов, М.В. Толмачева // 7-я Российская мультиконференция по проблемам управления, 2014. С.403 - 409. - 0.5 / 0.4 п.л.

5. Грузликов, A.M. Имитационно-аналитическое моделирование при мониторинге параллельных вычислений / A.M. Грузликов, Н.В. Колесов, М.В. Толмачева // Материалы 6-й Всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика», Казань, 2013, С. 123 - 127. - 0.25 / 0.15 п.л.

6. Грузликов, A.M. Использование динамических моделей при мониторинге параллельных вычислений / A.M. Грузликов, Ю.М. Скородумов // Материалы XVI конференции молодых ученых «Навигация и управление движением» / Гироскопия и навигация. 2014. Т. 2. С. 137 - 0.06 / 0.05 п.л.

7. Грузликов, A.M. Организация вычислений в распределенных системах реального времени / A.M. Грузликов, Ю.М. Колесов Н.В., Скородумов, М.В. Толмачева // XIX Международный научно-технический семинар «Современные технологии в задачах управления, автоматики и обработки информацию), Алушта, 18 - 24 сентября 2013 года. С. 210 - 211. - 0.05 / 0.02 п.л.

8. Грузликов, A.M. Назначение заданий при распределенных вычислениях / A.M. Грузликов, Н.В. Колесов, Ю.М. Скородумов, М.В. Толмачева // Материалы 6-й Всероссийской мультиконференции по проблемам управления, Дивноморское, т.4,2013, С. 34 - 38. - 0.25 / 0.15 п.л.

9. Грузликов, A.M. Нестационарные модели в задачах диагностирования вычислительных систем / A.M. Грузликов, Н.В. Колесов, Ю.М. Скородумов, М.В. Толмачева // XII Всероссийское совещание по проблемам управления,

M.: Институт проблем управления им. В.А. Трапезникова РАН, 2014, С.7270 -7281.-0.85/0.7 п.л.

10. Gruzlikov, A.M. Efficiency research of task allocation algorithms in distributed computing systems / A.M. Gruzlikov and Yu.M. Skorodumov // Proceedings of the international conference of young scientists «Automation and control», St. Peterburg, Russia, 21-22 november, 2013, p. 46. - 0.06 / 0.02 п.л.

Подписано в печать 20.03.2015г. Формат А5, Усл. печ. л. 1,0 цифровая печать. Тираж 100 экз.

Отпечатано в ЦОП «Сенная площадь» Россия, г. Санкт-Петербург, ул. Садовая, 40 тел./факс: 438 38 07 е-таЦ: sen@copy.spb.ru