Содержание к диссертации
ГЛАВА 1. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ РАСПРЕДЕЛЕННЫХ
ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ 16
Задача моделирования распределенных вычислительных систем.. 16
Средства и методы имитационного моделирования 18
Системы имитационного моделирования 23
Технологии распределенных вычислений 25
Технология HL А 30
Синхронизация времени 34
Консервативный алгоритм синхронизации времени 36
Оптимистический алгоритм синхронизации времени 37
1.7. Кластерные системы модульного программирования 39
ГЛАВА 2. СРЕДСТВА И МЕТОДЫ ОРГАТШЗАЦИИ РАСПРЕДЕЛЕННОГО
ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ КСМП 46
Технология распределенного имитационного моделирования кластерных систем модульного программирования 48
Распределенная имитационная модель 60
Коммуникационная библиотека 63
Алгоритм синхронизации времени 68
Обеспечение надежности 72
Аппарат контрольных точек 76
ГЛАВА 3. ИНСТРУМЕНТАЛЬНЫЙ КОМПЛЕКС СИРИУС ДЛЯ
ОРГАНИЗАЦИИ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ 81
Архитектура 81
Конструктор описания предметной области 83
Конструктор описания программно-аппаратной архитектуры 87
Генератор распределенной имитационной модели 95
Исполнительная подсистема 99
Программные аспекты реализации 102
ГЛАВА 4. ІТРИМЕНЕНИЯ ИНСТРУМЕНТАЛЬНОГО КОМПЛЕКСА ПРИ
ПРОЕКТИРОВАНИИ КСМП 106
Проверка гипотезы о законе распределения 106
Пример прогнозирования времени работы модулей КСМП для решения СБУ 111
Пример применения ИК СИРИУС при моделировании работы КСМП для решения СБУ 115
Сравнительный анализ эффектов і юс п і локального и распределенного процессов моделирования 120
ЗАКЛЮЧЕНИЕ 124
ЛИТЕРАТУРА 125
СПИСОК ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ 136
ГЛОССАРИЙ ТЕРМИНОВ 139
ПРИЛОЖЕНИЕ 1. АЛГОРИТМЫ РАБОТЫ КОММУНИКАЦИОННЫХ
МОДУЛЕЙ (КЛИЕНТСКАЯ ЧАСТЬ) 140
ПРИЛОЖЕНИЕ 2. АЛГОРИТМЫ РАБОТЫ КОММУНИКАЦИОННЫХ
МОДУЛЕЙ (СЕРВЕРНАЯ ЧАСТЬ) 143
ПРИЛОЖЕНИЕ 3. СЕГМЕНТ МОДЕЛИРОВАНИЯ СЕТИ ПЕРЕДАЧИ
ДАННЫХ КЛАСТЕРА 154
ПРИЛОЖЕНИЕ 4. ПРИМЕР НАБОРА ДАННЫХ ПОЛУЧЕННЫХ
ЭКСПЕРИМЕНТАЛЬНЫМ ПУТЕМ 160
ПРИЛОЖЕНИЕ 5. РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ ЭЛЕМЕНТОВ
ВЫЧИСЛИТЕЛЬНОГО УЗЛА 162
Введение к работе
Актуальность темы. Развитие информационных технологий, увеличение пропускной способности сетей передачи данных, снижение стоимости комплектующих и постоянный рост требований, исходящих от научно-исследовательских приложений, обу словил тт создание новых вычислительных инфраструктур предназначенных для решения целого класса задач, не предполагающих тесного взаимодействия между параллельными процессами [9].
Такими инфраструктурами называют кластеры, метакомпьютеры, сети GRID и т.д., которые формируются из обычных компьютерных ресурсов (вычислительных узлов), размещенных в Интернет и используемых независимо от своего физического расположения. Вычислительные ресурсы узла включают процессоры, оперативную и внешнюю память, файлы, базы данных и др.
Интеграция некой распределенной вычислительной инфраструктуры и пакета прикладных программ, функциональные модули которого размещены в узлах этой инфраструктуры, привела к появлению нового вида предметно-ориентированных вычислительных комплекс о із — кластерных систем модульного программирования (КСМП) [36].
Распределенная вычислительная инфраструктура, предназначенная для создания и применения рассмотренных выше пакетов программ, представляет собой совокупность территориально распределенных рабочих станций (узлов), коммуникационной сети и промежуточного программного обеспечения, предназначенного для управления процессом решения задач в узлах этой инфраструктуры. Узлы подразделяются па главный (управляющий) узел и подчиненные (вычислительные) узлы.
При создании КСМП ее модули п клиентские части системного программного обеспечения размещаются в вычислительных узлах, а ядро (серверная часть) системного программного обеспечения — в управляющем узле. Набор системных функций КСМП дополняется (по сравнению с традиционными пакетами программ) коммуникативными функциями по передаче сообщений и дан-
ных между узлами, функциями синхронизации выполнения модулей, функциями мониторинга состояния распределенной системы и др.
На этапе проектирования КСМП, помимо концептуальных вопросов ее функционирования (на какие категории пользователей и классы задач она ориентируется), возникает ряд технических вопросов:
какую программно-аппаратную архитектуру выбрать для функционирования КСМП;
какое прикладное программное обеспечение использовать для решения задач в КСМП;
по каким критериям будут оцениваться производительность и надежность этой КСМП;
- какими методами и средствами проводить моделирование ее работы.
Возрастающая сложность, размер и особенности организации моделей
КСМП требуют удобных инструментальных средств описания и анализа таких моделей. Поэтому необходима инструментальная среда, предназначенная для решения следующих задач: определения множества функциональных отношений между объектами исследуемой предметной области и построения соответствующей вычислительной модели; описания программно-аппаратной архитектуры создаваемой системы, включая коммуникационную среду; моделирования процессов формирования постановок исследовательских задач, построения и исполнения планов решения задач.
Исследования в области перспективных технологий программирования (Л. А. Калужнин, А. П. Ершов, М. С. Бургин, И. В. Вельбицкий, В. В. Ивани-щев, Э. X. Тыугу, G. A. Raeder, Chang Shi-Kuo и др.) показывают, что визуальные методы и графический стиль программирования предлагают более естественную форму для выражения алгоритмов и структур данных по сравнению с текстовыми линейными языками (см., например, обзор [65]).
Поэтому необходима разработка и реализация графической среды для описания концептуальной схемы предметной области и программно-аппаратной архитектуры среды функционирования КСМП.
С точки зрения визуализации процессов представления предметно-ориентированных данных, планирования и выполнения вычислений, в КСМП можно выделить несколько групп инструментальных средств, автоматизирующих эти процессы.
Специализированные математические пакеты программ для проведения научных и инженерных расчетов, как. например, Simulink, входящий в пакет Mathlab [12]. Основным назначением подобных систем является проектирование низкоуровневых коммуникационных моделей, моделей обработки сигналов электрических цепей, а также визуализация результатов проводимых в них расчетов. В таких системах построение моделей происходит в интерактивном графическом режиме из набора базовых элементов так называемой библиотеки насіраиваемьіх шаблонов, которые в процессе проектирования могут быть упорядочены в виде иерархий.
CASE-средства [7] (англ. Computer-Aided Software Engineering - автоматизированная разработка программного обеспечения) — системы для проектирования программных средств, комплектующиеся графическим редактором и зачастую использующие язык UML (англ. Unified Modeling Language - унифицированный язык моделирования). Главной задачей этих систем является автоматизация разработки программного обеспечения па различных этапах, включая анализ, формулировку требований, проектирование программ и баз данных, генерацию кода, создание, тестирование, сопровождение и документирование программ. Хотя такие системы и позволяют в наглядной форме описывать предметную область и анализировать ее модель, они зачастую сложны для применения в моделировании КСМП, поскольку требуют описания предметной области «с нуля» и ее доводки на языках более низкого уровня (по сравнению с языками имитационного моделирования) наподобие C++ или Java.
Инструментальные средства разработки пакетов программ с возможностью описания модели предметной области и динамическим планированием вычислительного процесса. Такие системы обладают набором компонентов
многоразового использования, таких как решатель, подсистема организацирі вычислений и функциональные блоки (модули, реализующие конкретные алгоритмы расчетов). Одними из первых разработок можно выделить систему ДИСУППП [40] и ее графический аналог - систему ГРАФ-ПРОЦЕСС [39]. Из систем дальнего зарубежья можно отметить инструментальные средства, акцентирующие внимание на создании моделей путем их сбора из базовых графических примитивов, каждый из которых представляет собой отдельный объект — как, например, в системе G2 [24] или ILOG [76]. Тем не менее применение данных систем требует достаточно высокой программистской квалификации разработчика.
4) Существует также ряд специализированных систем моделирования программно-аппаратного обеспечения сетей передачи данных, например, OPNET [88], QualNet [89], Vantage Predictor [99] и др., предназначенных в первую очередь для проектирования и оптимизации топологической структуры компьютерной сети и обладающих развитыми графическими средствами ее конструирования. Основными типовыми задачами, решаемыми в подобных системах, являются [8]: оптимизация пропускной способности каналов связи, выбор маршрутов, оптимизация топологической структуры, выбор методов управления потоками и определение параметров управления, анализ объемов буферной памяти узлов коммутации, маршрутизации, выбор стратегии буферизации при перегрузках и т. п.
Однако при моделировании КСМП помимо представления сети передачи данных требуется также определение множества функциональных отношений между объектами исследуемой предметной области, постановки исследовательских задач и генерации планов их решения. Функциональные отношения такой модели, реализуемые в реальных системах модулями какого-либо языка программирования, требуются для анализа ее внутреннего параллелизма, моделирования процессов формирования постановок исследовательских задач, построения и исполнения планов их решения. Перечисленные выше системы мо-
делирования не обладают всеми необходимыми средствами для решения подобной задачи. Модифицировать же их с целью расширения круга решаемых в них задач достаточно непросто. В диссертации предлагается разработка и реализация графической инструментальной среды, включающей конструкторы описания предметной и программно-аппаратной архитектуры и устраняющей недостатки перечисленных сред.
КСМП является сложной системой, представляющей совокупность объектов разной природы (пользователей, задач, программно-аппаратных средств, процессов и др.), оперирующих и взаимодействующих между собой. Состояние такой системы в каждый момент времени зависит от большого числа управляющих переменных, случайных событий, законов их распределения, связей между объектами системы и ограничений разных типов.
На практике исследование подобного рода систем зачастую невозможно без применения средств и методов имитационного моделирования [21]. Имитационная модель позволяет воспроизвесги весь процесс функционирования сложной системы с сохранением ее логической структ) ры, связи между событиями этой системы и последовательности протекания их во времени. Имитационное моделирование позволяет учесть большое количество реальных деталей функционирования моделируемого объекта. Применение статистических методов, неизбежное при имитационном моделировании, требует больших затрат машинного времени и вычислительных ресурсов. Одним из путей решения данной проблемы является использование суперкомпыотерной вычислительной техники, в том числе кластерных архитектур.
На сегодняшний день разработаны разные модели, методы и средства распределенного имитационного моделирования (см., например, работы В.В. Окольнишпикова, Р.Л. Смелянского, R.M. Fujimoto, S.Strassburger и др.), в том числе такие известные системы как Мера [29], Диана [44], SLX [80] и др. Для построения среды имитационного моделирования можно использовать универсальные языки программирования, такие как С, Fortran, Ada, Java, или
системы имитационного моделирования GPSS World [68], GPSS/H [73], Arena [84], SLX, SIMPLEX3 [67], AnyLogic [19] и др.
Системы имитационного моделирования по сравнению с универсальными языками программирования [21, 94], обладая средой и специализированными языками, дают ряд значительных преимуществ, таких как существенное сокращение [45] времени разработки имитационных моделей, простота поддержки и их последующей модификации. Более того, такие системы предоставляют высокоуровневые инструменты для работы с параллельными процессами, объектами имитационных моделей, статистические инструменты, обеспечивают более совершенные механизмы обнаружения ошибок и обладают высокоуровневой средой отладки, оперирующей понятиями заявок, устройств обслуживания и объектов.
Поэтому использование готовой системы имитационного моделирования для решения поставленной в диссертации задачи выглядит предпочтительнее. Использование систем в распределенной вычислительной среде (РВС) также налагает ряд требований по выбору систем моделирования, таких как [77]: отказоустойчивость, поддержка механизмов синхронизации времени, организации обмена данными между сегментами распределенной модели, а также наличие самой системы моделирования в свободном доступе. Обеспечение отказоустойчивости распределенного процесса требует дополнительных функциональных возможностей для сохранения/восстановления состояний модели, которые редко встречаются в существующих системах [93]. Базовые возможности для этого имеются в системах GPSS World, GPSS/H и SIMPLEX3, но недостаточно развиты для использования в пакетном режиме, так как требуют разработки управляющих надстроек.
При использовании системы имитационного моделирования на локальном компьютере проблем с синхронизацией времени не возникает. Сложности с синхронизацией времени появляются в случае использования распределенного имитационного моделирования [94], т. е. когда отдельные сегменты модели
размещены на разных узлах вычислительной сети. В этой области известны следующие традиционные подходы к синхронизации времени [77, 93]:
консервативные подходы, в которых обеспечивается поддержка строгих причинно-следственных связей между событиями процесса моделирования;
оптимистические подходы, разрешающие продвижение времени в отдельных сегментах модели независимо друг от друга и осуществляющие откат процесса моделирования в случае нарушения причинно-следственных связей между событиями; для осуществления таких откатов в процессе моделирования необходимы средства поддержки аппарата контрольных точек (КТ);
смешанные подходы, которые комбинируют возможности первых двух подходов.
Следует отметить, что подавляющее большинство широко известных систем имитационного моделирования разрабатывались для использования на локальных компьютерах. По этой причине организация распределенного имитационного моделирования с их помощью попросту становится невозможной, поскольку в них отсутствуют механизмы синхронизации времени среди удаленных сегментов и передачи данных между ними.
Поэтому возникает необходимость в технологии, которая обеспечивала бы взаимодействие распределенных моделирующих программ. Для этого можно рассматривать существующие технологии и коммуникационные библиотеки, такие как CORBA [97], RMI [79], MPI [86] или PVM [78]. Данные технологии разрабатывались для распределенных вычислений, но не для организации распределенного имитационного моделирования [25], о чем говорит отсутствие поддержки протоколов управления временем и его синхронизации. К тому же, эти технологии порождают весьма сложную реализацию, настройку, эксплуатацию и не могут в полной мере удовлетворить необходимому набору требований, предъявляемых при организации распределенного имитационного моделирования [93].
Отдельным подходом, призванным решить многочисленные проблемы построения распределенных систем имитационного моделирования, является архитектура HLA (англ. High Level Architecture — высокоуровневая архитектура) [81]. HLA обладает открытой спецификацией и предлагает ряд преимуществ по сравнению с приведенными выше технологиями, как, например, возможность синхронизации времени и расширенное понятие коммуникации [93]. Основным компонентом HLA является реализация ее инфраструктуры, называемая RTI (англ. Run Time Infrastructure — инфраструктура времени выполнения). В качестве российских систем, где заявлена поддержка архитектуры HLA, можно привести системы AnyLogic и Мера.
Несмотря на многочисленные преимущества, HLA обладает рядом недостатков. Она является достаточно сложным стандартом [94], который требует разработки протоколов обмена от самого разработчика имитационной системы. Первоначальная реализация HLA выполнена внутри военного ведомства на таких языках как C++, Java или АДА, которые не являются традиционными в гражданской сфере имитационного моделирования, где используются специализированные системы с высокоуровневыми языками имитационного моделирования. К тому же, системы на базе HLA имеют предел масштабируемости [85]. В HLA отсутствуют средства обеспечения отказоустойчивости, что становится существенным недостатком при организации моделей, включающих большое число сегментов. Отмечается, что разные реализации HLA не могут взаимодействовать между собой. Разработчики гражданских систем не хотят интегрировать HLA, чтобы их пользователи не имели доступа к системам конкурентов [95], и отказываются от поддержки IILA из-за ее сложности. Бесплатные реализации RTT зачастую перестают поддерживаться производителями и исчезают из свободного доступа, в результате программные разработки, основанные на таких RTI, становятся не работоспособными. Примером тому является система AnyLogic, в которой поддержка HLA базировалась на бесплатных версиях JavaBinding и RTI. С 2002 года производитель прекратил предоставлять про-
граммыое обеспечение для публичных нужд и убрал JavaBindmg и RTI со своего официального сайта. Таким образом, на сегодняшний день отсутствие JavaBinding и RTI в свободном доступе не позволяет реализовать распределенные модели в AnyLogic.
Как следует из всего выше сказанного, является очевидной актуальность создания программного инструментария для анализа КСМП с использованием средств и методов имитационного моделирования.
Цель работы состоит в создании графического инструментального комплекса (ИК) для исследования КСМП с использованием методов распределенного имитационного моделирования и динамического анализа программ.
Объектом исследования являются технологии анализа распределенных вычислительных систем.
Предмет исследования составляют методы и инструментальные средства распределенного имитационного моделирования КСМП.
Методы исследования. При решении поставленных задач использовались методы системного программирования, характерные для автоматизации разработки больших программных комплексов, методы имитационного моделирования, организации распределенных вычислений и динамического анализа программ.
Научная новизна. Предложена технология анализа эффективности функционирования КСМП. обеспечивающая (в отличие от известных) комплексное исследование характеристик как прикладного программного обеспечения, так и аппаратных средств РВС. В основе этой технологии лежат разработанные автором методы и инструментальные средства, обеспечивающие распределенное имитационное моделирование КСМП с применением средств динамического анализа программ.
Практическая значимость. Применение разработанного в диссертации ИК СИРИУС дает возможность специалистам в предметной области самостоятельно, без участия высококвалифицированных системных программистов, описывать предметную область, программно-аппаратную архитектуру распределен-
ной КСМП и проводить имитационные испытания с целью исследования эффективности работы проектируемой КСМП.
Разработанные средства зарегистрированы в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам [3] и применяются для проведения экспериментальных расчетов по плановым НИР в ИДСТУ СО РАН, а также в учебном процессе в Институте математики, экономики и информатики Иркутского государственного университета.
Исследование, разработка и применение представленных в диссертации программных средств выполнялись в рамках интеграционного проекта № 3 СО РАН «Методы, технологии и инструментальные средства создания вычислительной инфраструктуры в Internet» (2003-2005 гг.); проекга СО РАН 3.2.6 «Интегрированные информационно-вычислительные и коммуникационные ресурсы: интеллектпые методы организации, автоматизации разработки и применения» (2004-2006 гг.. блок 1 «Распределенная вычислительная САТУРН-среда»); проекта СО РАН «Разработка научных основ распределенной информационно-аналитической системы на основе ГИС и Веб-технологий для междисциплинарных исследований» междисциплинарной программы 4.5.2 (2007—2009 гг., блок 2 «Интеллектныс методы н инструментальные средства разработки pi комплекси-рования распределенных информационно-вычислительных ресурсов») и проекта РФФИ № 04-07-90358 «Разработка и реализация распределенной вычислительной системы решения булевых уравнений большой размерности».
Достоверность результатов диссертации основывается на анализе исследований отечественных и зарубежных ученых и подтверждается успешным опытом практического применения ИК СИРИУС для моделирования процесса функционирования ряда КСМП, а также для проектирования архитектуры вычислительного кластера вуза.
На защиту выносятся следующие основные результаты:
1. Технология анализа эффективности функционирования КСМП, базирующаяся на построении распределенной имитационной модели КСМП, которая
обеспечивает (в отличие от известных) детальный учет как характеристик предметной области КСМП, так и особенностей программно-аппаратной архитектуры.
Комму?iUKaiji/онная библиотека распределенного имитационного моделирования для систем семейства GPSS, включающая методы синхронизации времени, обмена данными и создания контрольных точек. Реализованная коммуникационная библиотека может быть использована для разработки распределенных GPSS-моделей как в ИК СИРИУС, так и автономно.
ИК СИРИУС обеспечивающий поддержку основных этапов анализа КСМП, включая графическое описание предметной области и программно-аппаратной архитектуры КСМП, а также автоматизацию построения и выполнения на вычислительных кластерах распределенных имитационных GPSS-моделей.
Апробация работы. Основные положения и результаты проделанной работы докладывались на научно-практической конференции «Ляпуновские чтения & Презентация информационных технологий» ( Иркутск, 2004 г.), на IV Всероссийской конференции «Математика, информатика, управление» (Иркутск, 2005 г.), на VI, VII и VIII Школе-семинаре молодых ученых «Математическое моделирование, управление и информационные технологии» (Ангасол-ка, 2005 г.; Зеленый мыс, 2005 г.; Энхалук, 2006 г.), на V и VI Международной научно-практической конференции «Моделирование. Теория, методы и средства» (Новочеркасск, 2005 г., 2006 г.), на V Школе-семинаре «Распределенные и кластерные вычисления» (Красноярск, 2006 г.), на Всероссийской конференции «Инфокоммуникацнонные и вычислительные технологии и системы» (Энхалук, 2006 г.), на XII Байкальской Всероссийской конференции с международным участием «Информационные и математические технологии в пауке и управлении» (Иркутск, 2007 г.), на Международной научной конференции «Параллельные вычислительные технологии (ПАВТ)» (Челябинск, 2007 г.), на VI Международной конференции «Идентификация систем и задачи управления (S1CPRO)» (Москва, 2007 г.), на Международной конференции «Геоинформа-
тика: технологии, научные проекты» (Иркутск, 2008 г.), а также на семинарах ИДСТУ СО РАН.
Публикации и личный вклад автора. По теме диссертации опубликовано 14 печатных работах [2-5, 17, 31, 54-61] (2 статьи в рецензируемы журналах, рекомендованных ВАК для опубликования научных результатов диссертации на соискание ученой степени доктора или кандидата наук, 11 публикаций в трудах региональных, всероссийских и международных конференций). Получено свидетельство [3] об официальной регистрации программы в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (РОСПАТЕНТ). В перечисленных публикациях все результаты, связанные с алгоритмизацией, программной реализацией и вычислительными экспериментами на ЭВМ, получены автором лично. Результаты по моделям и методам организации распределенного имитационного моделирования вычислительных моделей систем получены совместно с А.Г. Феоктистовым и являются неделимыми. Из совместных работ с А.С. Корсуковым, А.В. Лариной и Г.А. Опариным в диссертацию включены только те результаты, которые принадлежат лично автору.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 99 наименований, списка сокращений, глоссария и 5 приложений. Общий объем работы 162 страницы, из них 136 страниц основного текста, включающего 25 рисунков и 10 таблиц.
