Содержание к диссертации
Введение
Глава 1. Анализ современных подходов к разработке и диагностированию распределенных информационно - измерительных комплексов 8
1.1 Особенности организации распределенных вычислений в гидроакустических комплексах 8
1.2 Анализ современных методов разработки и диагностирования информационно-измерительных комплексов 14
1.3 Выводы 23
Глава 2. Оптимизация распределенных вычислительных систем гидроакустических комплексов 24
2.1 Оптимизационный подход к назначению заданий в распределенных вычислительных системах 25
2.2 Оптимальный параллельный алгоритм назначения заданий 33
2.3 Исследование эффективности алгоритмов назначения заданий 35
2.4 Выводы 43
Глава 3. Диагностирование распределенных вычислительных систем гидроакустических комплексов 44
3.1 Дискретно-событийная периодически нестационарная модель 44
3.2 Синтез наблюдаемой и управляемой дискретно-событийной модели с независимыми цепями 56
3.3 Синтез наблюдаемой и управляемой дискретно-событийная модели со слиянием цепей 72
3.4 Построение теста для периодически нестационарной системы 79
3.5 Выводы 82
Глава 4. Результаты практической апробации методов разработки и диагностирования распределенных вычислительных систем современных гидроакустических комплексов 83
4.1 Назначение заданий в ГАК 83
4.2 Разработка средств диагностирования ГАК 101
4.3 Инструментальная среда для синтеза конфигурации распределенной вычислительной системы обработки информации с решением задач назначения и диагностирования 110
4.4 Выводы 141
Заключение 143
Список литературы
- Анализ современных методов разработки и диагностирования информационно-измерительных комплексов
- Оптимальный параллельный алгоритм назначения заданий
- Синтез наблюдаемой и управляемой дискретно-событийной модели с независимыми цепями
- Инструментальная среда для синтеза конфигурации распределенной вычислительной системы обработки информации с решением задач назначения и диагностирования
Анализ современных методов разработки и диагностирования информационно-измерительных комплексов
В настоящем параграфе представлен краткий обзор современных методов организации и диагностирования вычислений в информационно-измерительных комплексах, к числу которых принадлежат и исследуемые в диссертации гидроакустические комплексы.
Назначение заданий при распределенных вычислениях. В настоящей работе под назначением понимается процедура соотнесения с каждым процессором распределенной вычислительной системы некоторого списка решаемых на нем задач. Эта процедура предшествует любым вычислениям в многопроцессорных системах [29, 81, 119]. Иногда в качестве формализации процедуры назначения рассматривается NP-полная (Nondeterministic Polynomial) задача размещения предметов в контейнерах [18, 75, 82, 93], когда множество предметов, каждый из которых характеризуется некоторым весом, необходимо упаковать в контейнеры ограниченной вместимости. Трактуя предметы как задачи, а контейнеры как процессоры, приходим к задаче назначения. Обычно задачу о контейнерах интерпретируют как задачу о назначениях при известном числе процессоров и фиксированных директивных сроках [103]. Для решения задачи о контейнерах предложен целый ряд алгоритмов, которые могут быть интерпретированы как решения задачи назначения. Несмотря на привлекательность «контейнерной» формализации проблемы назначения, следует признать, что она не вполне адекватна в случаях, когда рассматриваются зависимые задачи, связанные некоторым отношением предшествования, и необходимо учитывать затраты на реализацию информационных обменов между процессорами. Кроме того, на практике ввиду высокой сложности оптимальных алгоритмов, как правило, отдают предпочтение простым эвристическим алгоритмам. Действительно, в достаточно типичной для практики создания гидроакустических комплексов, когда число размещаемых задач превышает сотню, применение оптимальных алгоритмов, предполагающих перебор вариантов, оказывается невозможным.
Обычно при разработке процедур назначения используется оптимизационная постановка с критериями, обеспечивающими, например, равномерность загрузки процессоров [82], минимальность необходимого числа процессоров [11] или каналов обмена [82], максимум надежности [11, 53, 89, 122]. Алгоритмы назначения формулируются в рамках различных подходов, среди которых генетический [49, 73, 94, 114], теория игр [80, 121, 124], графовый [15, 104, 105] и ряд других. Последний подход используется и в настоящей работе. В его рамках известны как оптимальные, так и эвристические алгоритмы, среди которых метод бинарного деления, покоординатное деление, рекурсивный метод деления пополам, деление графов с учетом связности [82]. Качество эвристических алгоритмов обычно также оценивается с использованием какого-либо выбранного критерия. Существенным классификационным признаком для процедур назначения является предположение (или отсутствие такового) об априорной известности числа используемых процессоров или каналов обмена. Только в этом случае, например, проблема достижения равномерности загрузки процессоров становится содержательной. Наконец, немаловажным свойством известных процедур является тип отношения предшествования для назначаемых задач. Обычно оно представляется в виде цепочки, иерархии или графа общего вида. Далее множество задач, связанных отношением предшествования, будем называть заданиями.
Для систем реального времени [28, 40] при решении задачи назначения дополнительно должно учитываться ограничение, вызванное периодичностью входного потока данных. Это ограничение сказывается следующим образом. В момент появления очередной порции данных вычислительная система должна всегда иметь возможность взять их в обработку. В результате появляется ограничение по загруженности процессора, определяемое его производительностью на периоде T поступления входной информации. Следует отметить, что широко применяемые при решении задачи назначения генетические алгоритмы [49, 73, 94, 97, 114] в случае систем реального времени снижают свою эффективность из-за появления среди генерируемых вариантов нереализуемых. Характеризуя в целом известные подходы к решению проблемы назначения, можно определить их как существенно комбинаторные. Под этим подразумевается тот факт, что преобладающее значение для их содержания имеют не математически строго обоснованные процедуры, а некоторые эвристические принципы, дополняемые в той или иной степени направленным перебором вариантов. Организация перебора может основываться на методологии генетического подхода [68], динамического программирования [27, 33], ветвей и границ [27] и некоторых других. В качестве известных принципов можно назвать, например: назначение на один процессор смежных задач, т.е. задач, непосредственно обменивающихся информацией; назначение на один процессор в первую очередь пар задач, информационный обмен между которыми наиболее интенсивен (задачи, принадлежащие разным парам, могут быть не смежными).
Подытоживая краткий обзор известных подходов к назначению задач на процессоры распределенной вычислительной системы, отметим следующее. В современной литературе описан широкий спектр алгоритмов. Наибольшее распространение на практике получили эвристические варианты, что связано с высокой размерностью задачи в практически значимых приложениях. Как правило, известные алгоритмы назначения не учитывают особенности систем реального времени и, в частности, гидроакустических систем. Кроме того их описание обычно не сопровождается результатами статистического исследования эффективности, что затрудняет сравнительный анализ. В связи с этим представляется актуальным проведение подобного исследования, результаты которого приведены в следующей главе.
Оптимальный параллельный алгоритм назначения заданий
Воспользуемся следующим алгоритмом автоматического синтеза fE, справедливым для любого графа межмодульных информационных связей. Сведем специальными приемами рассмотрение информационных графов произвольного вида к анализу некоторых стандартных (примитивных) графов, а именно, цепей. По информационному графу найдем множество вычислительных путей, составляющих покрытие его ребер. Под вычислительным путем в данном случае понимается последовательность ребер и вершин, соединяющая некоторый вход информационного графа с его выходом. Для рассматриваемого примера (рисунок 3.1) покрытие обеспечивается двумя путями с ребрами u1y1, у3 и и2, у2,у3,у2,у3. Здесь штрихи используются для обозначения передаваемой в массивах тестовой информации. Второй путь содержит цикл для покрытия информационной обратной связи с выхода системы на вход ПМ2. Сопоставим в модели системы с каждым путем цепь из такого числа динамических звеньев M, через сколько ПМ проходит данный путь. После описанных построений модель системы представляется совокупностью независимых цепей. Можно сказать, что результат вычисления модели формируется как массив значений аргументов, подвергнувшихся независимой обработке.
На рисунок 3.2. представлена модель системы из рассматриваемого примера, где модель ПМ1 содержит одно звено М11, модель ПМ2 - два звена М21 и
М22, а модель ПМ3 - три звена М31, М32и М33. Отметим особенность структуры массива , выдаваемого из ПМ3. В ней можно выделить две части, одна из которых формируется в звеньях М31 и М33 и предназначена для системы диагностирования, другая формируется в М32 и предназначена для ПМ2Попробуем уточнить модели звена, ПМ и системы в целом. Из теории технического диагностирования известно [8, 9, 10], что наибольшей эффективности диагностирования при наименьших затратах можно достичь в случае, когда объект диагностирования - линейный. Кроме того, ясно, что, поскольку речь идет об анализе последовательности событий (последовательности решения задач), то этот алгоритм должен быть динамическим. В результате получаем, что моделью звена должна быть линейная динамическая система: x,(t +1) = fuxu(t) + guuu(t), yu(t) = huxu(t) і = 1,п,1 = Щ, (3. 1) где xi;, иии y, - векторы состояния, входа и выхода, f,, g, и hu - матрицы динамики, входа и выхода /-го звена в модели z-го ПМ, т - число ПМ, тi - число звеньев в ПМi.
Каждое звено модели ПМ обрабатывает информацию лишь от одного массива и по одному и тому же алгоритму. В отличие от звена ПМ в общем случае обрабатывает несколько массивов, а, следовательно, его модель содержит параллельную композицию нескольких звеньев. При этом передаваемые массивы могут иметь разную размерность, определяемую количеством и структурой звеньев, составляющих модель конкретного ПМ. Звенья модели ПМ срабатывают в разные моменты времени и обрабатывают информацию в общем случае по разным алгоритмам. Это означает, что модель ПМ нестационарна.
При конкретизации модели системы учтем, что она состоит из отдельных цепей и, конкретизировав модель цепи, мы в значительной степени конкретизи руем модель системы. Поскольку модель системы распадается на M независимых цепей, то, как следствие, и в алгоритме диагностирования можно для каждой из цепей предусмотреть свою составляющую. Таким образом, задача диагностирования системы сводится к диагностированию цепи. Последняя задача гораздо проще предыдущей, однако и при ее решении возникают определенные трудности. Действительно, хотелось бы с целью упрощения свести анализ в целях диагностирования к анализу динамической системы. При этом существенно, что вопросы диагностирования для динамических систем достаточно подробно изучены.
Рассмотрим цепь, состоящую из L звеньев, каждое из которых описывается уравнениями (3.1). Представим цепь в виде линейной динамической системы, вектором состояния которой является вектор x(t), составленный из векторов состояния звеньев x.(Y) і: = 1,L, входящих в эту цепь.
Эти уравнения описывают L-1 межзвенных обменов и два обмена с СД (прием и выдача информации). Матрицы в этих уравнениях зависят от номера такта (номера обмена), т.е. модель нестационарна. Подтвердим этот факт. Для этого опишем процессы передачи информации между двумя смежными звеньями цепи, приема информации от СД во входное звено цепи и выдачи в СД информации из выходного звена цепи.
Пусть информация передается из звена ПМi в звено ПМj. Из методических соображений запишем сначала преобразование вектора состояния модели при обмене без обработки информации во взаимодействующих ПМ. Это преобразование (3.2) описывается блочной матрицей. Причем в результате преобразования состояния всех звеньев, кроме звена из ПМj, не изменяются. Вектор же состояния звена из ПМj заменяется на вектор состояния звена из ПМi. Факт сохранения состояния ПМ описывается единичной диагональной матрицей E, размещаемой в соответствующем блоке диагонали блочной матрицы.
Синтез наблюдаемой и управляемой дискретно-событийной модели с независимыми цепями
Как было описано в главе 3, тест для системы состоит из двух частей. В первой части система в пространстве состояний последовательно проходит через состояния из выбранного базиса. После попадание в очередное базисное состояние система пребывает в свободном движении. Во второй части теста на вход системы подаются входные векторы из базиса входного пространства.
Вычислительный комплекс обработки информации в гидроакустической станции геологоразведки. Перечень решаемых задач и состав ГАС ГР описан в разделе 4.1. При разработке средств диагностирования в настоящем параграфе было использовано программное обеспечение, описанное в главе 3, которое по виду информационного графа формирует модель системы, состоящую из подмоделей цепей, входящих в покрытие ребер графа, а затем для модели каждой цепи строится тест и соответствующая эталонная реакция. Ин 107 формационный граф ГАС ГР представлен на рисунке 4.9. В покрытие его ребер входят следующие цепи (таблица 4.8). Таблица 4.8
Как было описано в главе 3, тест для системы состоит из двух частей. В первой части система в пространстве состояний последовательно проходит через состояния из выбранного базиса. После попадание в очередное базисное состояние система пребывает в свободном движении. Во второй части теста на вход системы подаются входные векторы из базиса входного пространства.
Инструментальная среда для синтеза конфигурации распределенной вычислительной системы обработки информации с решением задач назначения и диагностирования
Функциональность и структура инструментальной среды. На рисунке 4.14 изображена диаграмма основных вариантов использования разработанной инструментальной среды. При этом ей свойственна дополнительная функциональность, позволяющая: синтезировать случайным образом информационные графы системы (для исследования эффективности алгоритмов назначения); задавать параметры критерия эффективности для решения задачи назначения; задавать варианты покрытия вычислительными путями информационного графа системы; задавать параметры для синтеза алгоритма диагностирования; синтезировать исходный код (на языке С++) шаблонов задач и узлов событийной конфигурации. Инструментальная среда организации распределенной] событийной обработки информации Ввод и редактирование параметров информационного графа «-Ч
Синтез алгоритмов] диагностирования Рисунок 4.14 – Диаграмма вариантов использования инструментальной среды
Инструментальная среда обладает кросс-платформенностью, т.е. возможностью исполнения среды и сборки без внесения каких-либо изменений получаемой распределенной системы обработки информации на вычислительных системах с различными операционными системами.
Структура инструментальной системы. Структура инструментальной среды представлена на рисунке 4.15. Все программные компоненты написаны на языке C/C++. Объём исходного кода для каждого компонента приведен в таблице 4.1.
Результатом работы инструментальной среды является исходный код распределенной системы обработки информации, сформированный с учетом назначения задач на процессоры и требований процедуры диагностирования. После добавления в шаблоны исходного кода функциональных задач полученный проект становится законченным программным продуктом.
Графический интерфейс инструментальной среды. Основу графического интерфейса составляют три окна (окно ввода и редактирования информации, окно информационного графа системы, окно анализа текущей информации), представленные на рисунке 4.16. Все окна объединены по навигации в единое информационное поле, т.е. например, при выборе задачи в окне ввода и редактирования информации, данная задача (как вершина информационного графа) автоматически выделяется в двух остальных окнах.
Меню запуска решения зада Окно ввода ні редактирования информации]
Графический интерфейс позволяет вводить информационный граф разрабатываемой системы, запускать решение любой из задач инструментальной среды, производить анализ результатов. Для учета изменений в системе (например: добавление задачи, изменение состава информационного взаимодействия) в графическом интерфейсе предусмотрен импорт данных из проекта (список файлов Makefile при работе в ОС
Начало работы, ввод и редактирование информационного графа. Начиная работу в инструментальной среде, необходимо создать новый проект или открыть с диска ранее уже созданный проект, а именно: - для создания нового проекта необходимо вызвать меню «Проект/Новый», и в диалоговом окне ввести число задач в системе и установить (при необходимости) флаг случайного формирования информационного графа с заданными свойствами (число базисных циклов); - для открытия сохраненного проекта необходимо вызвать меню «Проект/Открыть», и в открытом окне выбрать название и путь к файлу проекта; - для импорта проекта из исходного кода вызвать меню «Проект/Импорт», и в открытом окне выбрать Makefile (при сборке проекта в ОС Solaris/Linux/Windows) или файл .sln (при сборке проекта в ОС Windows в среде Microsoft Visual Studio 2010). Ввод и изменение параметров проекта пользователь осуществляет в окне ввода и редактирования задач и их параметров, а также в основном окне в закладке “Информационный граф / Матрица смежности” (рисунок 4.17).
Для изменения параметров проекта, например, изменения числа задач или для задания/изменения параметров критерия эффективности назначения необходимо обратиться к меню «Проект/Свойства». В случае если при решении задачи назначения параметры не заданы, пользователю будет предложено ввести необходимую информацию. При отказе от ввода параметры функции эффективности назначения будут заданы по умолчанию.
При добавлении новой информационной связи между задачами необходимо в основном окне (закладка “Информационный граф / Матрица смежности”) выделить необходимую ячейку и ввести положительное число, равное длительности соответствующего обмена. Для удаления информационной связи, вводится нулевое значение.
Решение задачи назначения. Реализация процедуры назначения в инструментальной среде. При решении задачи назначения пользователь вводит исходные данные об информационном графе системы (вес вершины и вес информационного обмена) и задает значения коэффициентов критерия эффективности назначения. Для решения задачи назначения может быть использован один из алгоритмов, описанных в главе 2. Так использование кластерного алго-115 ритма предполагает вызов меню «Назначение/Кластерный алгоритм», остовного алгоритма – «Назначение/Остовный алгоритм», двухэтапных процедур – «Назначение/Кластерный + оптимальный алгоритм» или «Назначе-ние/Остовный + оптимальный алгоритм», оптимального алгоритма – «Назначение/Оптимальный алгоритм». Результаты решения задачи назначения будут выведены в основном окне в закладках с соответствующими названиями.
Вся информация о решении задач назначения различными алгоритмами одновременно выводится пользователю в виде сжатых информационных графов для проведения анализа полученных результатов (рисунке 4.18).
Инструментальная среда для синтеза конфигурации распределенной вычислительной системы обработки информации с решением задач назначения и диагностирования
Класс CSocketServerConn является абстрактным классом сервера и клиента. Отличие UDP протокола от TCP в том, что для передачи данных не требуется предварительно устанавливать соединение, т.е. при обмене данных между узлами нет различия между сервером и клиентом. Класс CSocketServerDgram реализует функции сервера/клиента для обмена данных по UDP соединению. Реализация объекта основывается на двойственности протокола как сервера и клиента. Класс CSocketServerDgram реализует функции сервера/клиента для обмена данных по UDP соединению с возможностью приема данных по multicast адресу. Функции контроля данных. Реализация функций, которые вызываются для проведения проверки значений данных при информационном обмене между задачами. Т.е. функции контроля присущи не только задаче обработки данных, но и системе организации обмена. Наличие и организация контроля данных заставляет разработчика функциональной задачи обработки соблюдать дисциплину проверки данных перед их передачей в другие задачи. Объем проверки определяется разработчиком.
Протоколирование данных/событий. Описание классов которое содержит все необходимые функции по протоколированию данных с заданным приоритетом по объему данных. Содержит объекты по централизованному протоколированию данных, протоколирование в файл, на консоль узла. Функции протоколирования вызываются при информационном обмене данными между задачами. Каждый информационный модуль использующийся в обмене содержит функции записи данных в текстовом и бинарном виде. Включение протоколирования (событий/значений информационного обмена) задается ключами в файле конфигурации системы и не требует повторной сборки проекта. Содержит определение 10 классов.
Управление вычислительным процессом. Набор классов и функций управления вычислительным процессом является связующим звеном между всеми функциональными задачами.
Описание и имплементация классов, которые на основе классов и функций описанных выше, организуют распределенную событийную систему обработки информации. Содержит 56 классов. Классы входящие в состав управления вычислительным процессом являются ядром в организации системы и далее будет приведены сведения по их составу и функциональности, включая основные алгоритмы.
Использование единого подхода по организации событийной системы обработки информации приводит к созданию единой сходной архитектуры всех задач обработки данных. Функциональные задачи представляются объектами, над которыми проводятся манипуляции типа назначение выполнения на заданном процессоре, контроль за времен выполнения, анализ факта событий информационного обмена. Дополнительно, вся функциональность которая связана с синхронизацией информацией при многопоточной организации вычислений вынесены за пределы кода функциональных задач, что позволило как снизить квалификацию программиста при реализации кода задачи так и к упрощению переноса исходного кода программ на другие программно-аппаратные платформы.
Основными классами обеспечения управления вычислительным процессом являются: Класс CComputer абстрактный класс узла. Агрегирует все функциональные объекты управления вычислительным процессом. Класс CComputerRemote содержит информацию об удаленном узле, а именно текущий статус его функционирования и перечень задач которые в входят в данный узел.
Класс CCompuetrLocal является текущим узлом в системе, агрегирует все объекты узла, включает в себя менеджер по управлению соединениями, менеджер синхронизации данных и оповещения о запуске узла, менеджер по приему соединений. При получении события о запуске удаленного узла (от CMsgServer), устанавливает необходимое согласно файлу конфигурации число соединений. Класс CAcceptor реализует функции менеджера для установки соединения. Данный объект является единственным доступом к установке соединения между объектами функциональных задач. Класс СMsgServer реализует функции менеджера по приему/отсылке информационных сообщений о статусе узла, перечень входных данных.
Класс CTimerPool реализует функции диспетчера таймера с установкой события в потоке выполнения кода. Используется в задачах, требующих периодической обработки данных. Например, в задачах периодического опроса состояния аппаратуры.
Класс CTask является абстрактным классом задачи, является родительским классом объектов CTimerPool, CComputer. Его конструкция определяет требования к интерфейсу всех наследованных от него объектов. Класс CTaskComputer является абстрактным классом задачи связанной с текущим узлом.
Класс CTaskConfig содержит информацию о конфигурации задачи, включая, контрольное время, за которое поступившие данные должны быть обработаны, перечень входных/выходных информационных модулей. Класс CTaskProcess является родительским классом всех функциональных объектов. Класс CLinkName содержит данные для однозначного определения источника или потребителя информационного модуля.
Для сведения к минимуму времени на обработку данных при начальном пуске происходит инициализация всех объектов, резервирование всех необходимых ресурсов и установка всех связей согласно файлу конфигурации. Алгоритм начального пуска представлен на рисунках 4.26 - 4.28. Алгоритм обработки информации представлен на рисунке 4.29. В случае если один информационный модуль является входным для нескольких задач, находящихся на одном узле, то применяется алгоритм счетчика ссылок:
