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

На правах рукописи

ТЭЙ ЗАР ХТУН

003451324

Разработка алгоритмов и программ имитационного моделирования для решения задач системного анализа на слабосвязанных многопроцессорных системах

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

з О ОНТ 2008

Москва 2008

003451324

Работа выполнена на кафедре вычислительной техники при Московском государственном институте электронной техники (техническом университете).

Научный руководитель

кандидат технических наук, профессор Лунин Сергей Андреевич.

Официальные оппоненты

доктор технических наук, профессор, Лисов Олег Иванович кандидат физико-математических наук,

доцент,

Шебеко Юрий Александрович

Ведущее предприятие

Межведомственный суперкомпыотерный центр РАН, Москва

Защита состоится " с 2008 годи на заседании

диссертационного совета Д212.134.02 ггри Московском государственном институте электронной техники (техническом университете). 124498, Москва, Зеленоград, проезд 4806, МИЭТ.

С диссертацией можно ознакомиться в библиотеке МИЭТ. Автореферат разослан " года.

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

д.т.н., Гуреев А.В.

Общая характеристика работы

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

Применительно к вычислительной технике это означает, что новые задачи, связанные с большими объемами вычислений, которые постоянно возникают в различных сферах человеческой деятельности, стимулируют разработку все более мощных компьютеров. Но, появившись, такой компьютер позволяет использовать более точные математические модели и ставить еще большие задачи. До недавнего времени исследователи для их решения могли использовать только чрезвычайно дорогие суперкомпьютеры. Сегодня многопроцессорные вычислительные системы, обеспечивающие высокую производительность за счет параллельных вычислений, стали доступны широкому кругу исследователей. Кластерная архитектура на сегодняшний день является наиболее востребованной при создании новых высокопроизводительных вычислительных комплексов: в списке самых мощных суперкомпьютеров ТОР500 более 70% систем являются кластерами.

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

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

В задачах анализа система часто рассматривается как некоторая обобщенная модель. Состояние системы можно описать сложной

функцией зависящей от множества переменных .....Zn} , каждая из

которых тоже описывается некоторой функцией, зависящей от времени.

У ~ ! .......

~ /\(Х]> Х 2 .......>*т> О

~ /г(х\>хг>хз>.......О

■^Л = /ЛХ1'Х2 'Х3'........Хт>0

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

^ = Р (2], ,........, )

1111

^ ^г ^ ~ ^тах *Тош1 ~ ^ +

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

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

В работе предлагается способ распределения нагрузки для систем имитационного моделирования, адаптированный для слабосвязанных многопроцессорных вычислителей. К этому классу относятся машины с архитектурами NUMA, DSM, СоРС. Для них характерно то, что время обращения процессора к локальной памяти узла значительно меньше времени обращения к памяти соседнего узла. Это происходит из-за того, что в последнем случае необходимо использовать вместо шины процессора внешнюю коммуникационную среду с большей латентностью и меньшей пропускной способностью.

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

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

1. Анализ методов моделирования, используемых в различных областях человеческой деятельности.

2. Анализ особенностей аппаратных средств систем имитационного моделирования.

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

4. Разработка программы имитационного моделирования, адаптированной для слабосвязанных многопроцессорных систем.

5. Проведение испытаний и анализ эффективности предложенного алгоритма.

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

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

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

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

Положения, выносимые на защиту.

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

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

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

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

5. Результаты экспериментальных исследований, испытаний и анализ эффективности предложенного алгоритма.

Внедрение результатов. Результаты диссертационной работы используются на кафедре вычислительной техники МИЭТ при проведении лабораторных работ по курсу «Высокопроизводительные вычислительные системы».

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Всероссийских межвузовских научно-технических конференциях студентов и аспирантов "Микроэлектроника и информатика - 2005, 2006, 2007", Международной школе-конференции -2005, научной сессии МИФИ - 2007, Всероссийской межвузовской научно-практической конференции молодых ученых, специалистов, преподавателей, аспирантов и студентов "Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем - 2007".

Публикации. По материалам диссертации опубликовано шесть тезисов докладов и три статьи. Получено свидетельство РФ на программу для ЭВМ.

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

Содержание работы

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

В первой главе проводится анализ основных методов моделирования - как средства исследования сложных систем.

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

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

Таблица 1. Виды моделирования.

Статические Внешние воздействия на объект не зависят от времени f{t) = const Динамические Внешние воздействия на объект зависят от времени f(t) Ф const

Непрерывные Состояние системы определяется во всех точках временного интервала Дискретные Состояние системы определяется только в критических точках временного интервала

Детерминированные Параметры модели для заданного момента времени фиксированы Стохастические Параметры модели для заданного момента времени определяются случайным образом = frand (!,)

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

Существует довольно подробная классификация систем моделирования (табл. 1). В диссертации рассматриваются: статические и динамические, непрерывные и дискретные, детерминированные и стохастические, аналитические и имитационные модели. Основное внимание в работе уделяется исследованию моделей, которые можно классифицировать как: имитационные, динамические, непрерывные и стохастические.

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

Имитационное моделирование особенно эффективно в случае, когда:

■ отношения между переменными в модели существенно не линейны, и поэтому аналитические модели трудно или невозможно построить;

■ модель содержит стохастические компоненты;

■ для понимания поведения системы требуется визуализация динамики происходящих в ней процессов;

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

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

Процесс имитационного моделирования не приводит к решению в том виде, как это имеет место в аналитических моделях. Эта особенность позволяет применять механизм симуляции в тех случаях, если:

■ математической постановки задачи не существует или нет аналитических методов ее решения;

« аналитические методы решения имеют очень большую вычислительную сложность (моделирование дает более простой способ решения задачи);

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

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

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

« проектирование и анализ производственных систем;

■ оценка различных систем вооружений и требований к их материально техническому обеспечению;

■ определение требований к оборудованию и протоколам сетей связи;

* определение требований к оборудованию и программному обеспечению различных компьютерных систем;

■ проектирование и анализ работы транспортных систем, например аэропортов, автомагистралей, портов и метрополитена;

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

■ модернизация различных процессов в деловой сфере;

■ определение политики в системах управления запасами;

■ анализ финансовых и экономических систем.

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

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

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

В середине 60-х годов прошлого века появились первые суперкомпьютеры. Это были дорогие, «элитные» машины, стоимость которых достигала десятков миллионов долларов. Конечно, широкого внедрения в повседневную научную практику они не получили. Примерно в середине 80-х годов прошлого века ученые заинтересовались возможностью использования кластерных систем в качестве относительно недорогих заменителей суперкомпьютеров. Благодаря развитию сетевых технологий, появилась возможность соединять вместе несколько рабочих станций, в качестве которых могут использоваться и обычные персональные компьютеры. Сегодня практически любой научный коллектив может использовать для высокопроизводительных вычислений многопроцессорные комплексы, которые лишь незначительно уступает по производительности суперкомпьютерам среднего уровня, но значительно дешевле их. Характеристики некоторых вычислительных систем, представленных в TQP500 (июнь 2008), представлены в табл. 2.

Таблица 2. Примеры высокопроизводительных систем

№ Владелец Компьютер Число проц. Rmax Rpeak

1 DOE/NNSA/LANL (United States) Roadtutmer - BadeCenter QS22/LS21 Cluster, PowerXCell 8i 3.2 Ghz/Opteron DC 1.8 GHz, Voltaire Infmiband (IBM) 122400 1026.00 1375.78

2 DOE/NNSA/LLNL (United States) BlueGene/L - eServer Blue Gene Solution (IBM) 212992 478.20 596.38

3 Argonne National Laboratory (United States) Blue Gene/P Solution (IBM) 163840 450.30 557.06

4 Texas Advanced Computing Center/Univ. of Texas (United States) Ranger - SunBlade x6420, Opteron Quad 2 Ghz, Infmiband (Sun Microsystems) 62976 326.00 503.81

5 DOE/Oak Ridge National laboratory (United States) Jaguar - Cray XT4 QuadCore 2.1 GHz (Cray Inc.) 30976 205.00 260.20

Существует несколько вариантов построения

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

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

Анализ аппаратных средств современных систем моделирования подтверждает, что существует объективная тенденция перехода от последовательных к параллельным и распределённым системам.

Для систем имитационного моделирования это означает, что вычисления выполняются на некотором множестве процессоров. При параллельных расчетах это могут быть узлы многопроцессорной ЭВМ с общей или распределенной памятью. В случае использования кластерных систем со слабой связью узлов можно говорить о распределённом моделировании. При этом слабосвязанными системами (рис. 1) можно считать такие, у которых время доступа к данным, находящимся в

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

Таблица 3. Основные классы высокопроизводительных систем

SMP NUMA КС

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

Примеры HP 9000 V-class Sun HPC 10000 Beowulf-кластеры

Масштаб Малое число узлов. Для построения масштабируемых систем на базе SMP используют архитектуру NUMA Ограничивается возможностями аппаратуры поддержки когерентности кэшей и ОС Число узлов теоретически не ограничено

ОС Единая ОС (обычно UNIX-подобнал) Как в SMP UNIX /Linux, WCCS

Программы POSIX threads, OpenMP Аналогично SMP MPI, MPC

Особенности Простота программирования Необходима локализация данных в узлах системы Эффективность определяется интенсивностью межузловых обменов

Рис. 1 Слабосвязанные многопроцессорные системы 11

Основными причинами перехода на параллельные и распределённые системы в области имитационного моделирования являются следующие:

■ необходимость сокращения времени выполнения имитационного эксперимента;

■ необходимость концентрации значительных ресурсов (например, оперативной памяти) для проведения сложных вычислительных экспериментов;

■ возможность получения новых знаний за счет объединения нескольких имитационных систем в одну распределённую среду имитационного моделирования;

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

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

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

В качестве примера имитационной модели в работе рассматривается модель существования группы живых организмов в природе. Связь параметров модели представлена на рисунке 2. На величину энергии организма (А) оказывают влияние пища (Е), вода (\У) и температура (Т). Количество пищи также зависит от температуры (Т) и наличия воды (\¥). Построим временную цепь событий: Т - - Е - А. В этой цепи Т и \У это параметры, которые зависят только от времени, а Е и А кроме времени, зависят еще и от Т и

Рис. 2. Связь параметров моделирования

В простейшем случае параметры модели могут быть описаны следующими уравнениями:

т; = т;.1±АГвв7-а«/()

е>=Е,.1+А2Е(Щ,Г<)-А2Е(4)

Д. = 4_, + А2А(Е,)-А3А(Моуе) А 2А = А2Е

При последовательном моделировании мы можем проводить расчеты, шаг за шагом опираясь на причинно-следственную связь (рис.3).

•ъ_^_^_з-

А*, А?3 Дг3

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

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

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

Рис. 4. Процесс параллельного моделирования

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

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

Если Р(х+) = Р(х-) = Р(у+) = Р(у-),то

P(a)*2Q{n + m-2)l 4 {п xm) = Q(n + m-2)l2(nxm)

Если количество ячеек п по вертикали равно количеству ячеек т по горизонтали, то выражение преобразуется в:

Р(а)« 4Q(n -1) / 4(и х ri) = Q{n -1) /(я х п) ~ Q / п

Если мы разделим поле размером МхМ на к частей, то п-т -М/к и P(a) = Qxk/М

Результаты исследования миграций 20 объектов для модели размерностью 600*600 приведены в таблице 4.

Таблица 4. Исследование миграций объектов.

Разбиение Число переходов объектов между фрагментами

100 шагов 1 ООО шагов

Расчет Эксперимент Расчет Эксперимент

1 2 3 1 2 3

2*2 6 3 3 4 60 80 76 86

3*3 10 25 22 24 100 190 172 186

4*4 13 33 30 29 130 371 324 363

Отличие расчетных значений числа переходов от практики объясняется тем, что в имитационной модели реализован не равновероятный принцип перемещения объектов. Однако, получаемые значения вполне пригодны для оценки коммуникационных потребностей моделей.

Рис. 5. Вычислительная модель

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

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

На каждом шаге моделирования хост рассылает информацию об объектах всем узлам, по координатам они определяют, находится ли

объект в его зоне или нет. После завершения расчетов каждый узел отправляет хосту новые характеристики «своих» объектов и цикл повторяется.

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

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

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

Программа имитационного моделирования реализована в среде шрС и протестирована на 24-х процессорной кластерной системе.

Для подтверждения масштабируемости алгоритма было проведено исследование влияния числа узлов в системе на время симуляции (при заданном разбиении).

Некоторые результаты приведены на рисунках 6-8.

Рис. 6. Параллельная симуляция (разбиение 2*2)

1 23456789 Число узлов

Рис. 7. Параллельная симуляция (разбиение 3*3)

1 2 3 4 5 6 7 8 9 10 11 12 Число узлов

Рис. 8. Параллельная симуляция (разбиение 4*6)

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

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

Для подтверждения функциональности алгоритма было проведено исследование влияния варианта разбиения поля на результат моделирования.

Результаты моделирования (перемещение объектов на поле размером 600*600) при разбиении модели на 4, 9 и 16 фрагментов показаны на рисунке 7.

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

Рис. 7. Параллельная симуляция. Модель 600*600

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

В заключении приведены основные результаты работы.

Основные результаты работы

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

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

системы за счет разделения данных на две группы - описание объектов исследования и описание среды их существования.

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

4. Разработан программный модуль имитационного моделирования для слабосвязанных многопроцессорных систем и получено свидетельство о его официальной регистрации. Программный модуль реализован в среде mpC Workshop.

5. Эксперименты, проведенные на кластере 25*P-IV 2400, подтвердили практическую эффективность предложенного способа распределения вычислительной нагрузки и функциональность алгоритма имитационного моделирования.

Основные результаты диссертации изложены в работах:

1. Тэй Зар Хтун. Особенности численного интегрирования и моделирования на кластере. //Микроэлектроника и информатика. 12-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. - М.: МИЭТ, 2005, с. 244.

2. Тэй Зар Хтун. Высокопроизводительные вычисления на кластерных вычислительных системах. //Международная школа-конференция по приоритетному направлению «Информационно-телекоммуникационные системы» с участием молодых ученых, аспирантов и студентов стран-членов СНГ. Тезисы докладов. - М.: МИЭТ, 2005, с. 68.

3. Тэй Зар Хтун. Об одном методе повышения эффективности параллельного моделирования. //Микроэлектроника и информатика. 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. - М.: МИЭТ, 2006, с. 178.

4. Лупин С.А., Тэй Зар Хтун. Моделирование экосистемы на параллельных вычислителях. //Системный анализ и информационно-управляющие системы: Сборник научных трудов под редакцией д.т.н., профессора В.А. Бархоткина-М.: МИЭТ, 2006, с. 155-161.

5. Тэй Зар Хтун. Комбинированный метод распределения нагрузки для кластерных вычислительных систем. //Научная сессия. - М.: МИФИ, 2007, с. 134.

6. Тэй Зар Хтун. Использование имитационного моделирования на параллельных вычислительных системах. //Микроэлектроника и информатика. 14-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. - М: МИЭТ, 2007, с. 165.

7. Тэй Зар Хтун. Особенности программной реализации алгоритма имитационного моделирования на многопроцессорной вычислительной системе. //Моделирование, алгоритмизация и программирование при проектировании информационно-управляющих систем: Сборник научных трудов под редакцией д.т.н., профессора В.А. Бархоткина - М.: МИЭТ, 2008, с. 169.

8. Тэй Зар Хтун. Исследование масштабируемости программы имитационного моделирования на МВС. //Всероссийская межвузовская научно-практическая конференция молодых ученых, специалистов, преподавателей, аспирантов и студентов «Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем». - М.: МИЭТ, 2007, с. 168.

9. Зей Яр Вин., Ней Мин Тун., Тэй Зар Хтун. Исследование методов переноса последовательных алгоритмов на параллельные вычислительные платформы. //Вестник тульского государственного университета, серия «Радиотехника и радиооптика», Том IX, Тула. 2007, с 199 - 207.

10. Лупин С.А., Тэй Зар Хтун, Дорошенко Е.С., Свидетельство РФ на программу для ЭВМ 2007 614961 от 11.12.2007 "Параллельная программа моделирования взаимодействия объектов и окружающей среды ParModt" 2008.

Подписано в печать: Заказ К.^9. Тираж^экз. Уч.-изд.л./<?Формат 60x84/16 Отпечатано в типографии МИЭТ(ТУ) 124498, Москва, МИЭТ(ТУ)

Введение.

Глава 1. Моделирование — как средство исследования сложных систем.

1.1 Виды моделирования и их сравнительные характеристики.

1.1.1. Статические и динамические модели.

1.1.2. Непрерывные и дискретные модели.

1.1.3. Детерминированные и стохастические модели.

1.1.4. Аналитические и имитационные модели.

1.2 Имитационное моделирование сложных систем. Основные проблемы.

1.2.1 Система, модели и имитационное моделирование.

1.2.2 Общая характеристика имитационного моделирования.

1.2.3 Основные преимущества имитационного моделирования.

1.2.4 Основные проблемы и этапы.

1.3 Параллельное и распределённое имитационное моделирование.

1.3.1 Мотивация перехода к параллельному и распределённому имитационному моделированию.

1.3.2 Параллельные и распределённые вычислительные системы.

1.3.3 Распределённые системы имитационного моделирования.

1.4 Выводы.

Глава 2. Аппаратные средства систем моделирования. Применение параллельных вычислительных систем для задач моделирования.

2.1 Современные классы ВВС.

2.1.1 Симметричные мультипроцессорные системы (SMP).

2.1.2 Системы с неоднородным доступом к памяти (NUMA).

2.1.3 Кластерные системы.

2.2. Примеры параллельных вычислительных систем.

2.2.1 Суперкомпьютеры.

2.2.2. Кластеры.

2.3 Сети для суперкомпьютеров и кластеров.

2.3.1 Ethernet.

2.3.2 Myrinet.

2.3.3 SCI (Scalable Coherent Interconnect).

2.3.4 QsNet.

2.3.5 Infmiband.

2.4 Влияние архитектурных особенностей ВВС на разработку прикладных программ для имитационного моделирования.

2.5 Выводы.

Глава 3. Распределение нагрузки в задачах моделирования, реализуемых на слабосвязанных ВВС.

3.1 Управление временем в распределённых системах имитации.

3.2 Последовательное моделирование.

3.3 Распределённое моделирование.

3.3.1 Консервативное управление временем.

3.3.2 Оптимистическое управление временем.

3.3.3 Выбор алгоритма для реализации системы моделирования.

3.4 Методы передачи данных в слабосвязанных ВВС.

3.5 Экспериментальная модель.

3.5.1 Последовательная реализация моделирования.

3.5.2 Методы распределения нагрузки.1.

3.5.3 Архитектурные особенности экспериментального кластера.

3.5.4 Особенности программной реализации метода.

3.6 Выводы.

Глава 4. Исследование программного комплекса для параллельного моделирования.101

4.1 Исследование масштабируемости модели.

4.2 Исследование функциональности модели.

4.2.1 Исследование влияния фрагментации поля на результат моделирования.

4.3 Выводы.

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

Применительно к вычислительной технике это означает, что новые задачи, связанные с большими объемами вычислений, которые постоянно возникают в различных сферах человеческой деятельности, стимулируют разработку все более мощных компьютеров. Но, появившись, такой компьютер позволяет использовать более точные математические модели и ставить еще большие задачи. До недавнего времени исследователи для их решения могли использовать только чрезвычайно дорогие суперкомпьютеры. Сегодня многопроцессорные вычислительные системы, обеспечивающие высокую производительность за счет параллельных вычислений, стали доступны широкому кругу исследователей. Кластерная архитектура на сегодняшний день является наиболее востребованной при создании новых высокопроизводительных вычислительных комплексов: в списке самых мощных суперкомпьютеров ТОР500 более 70% систем являются кластерами.

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

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

В задачах анализа система часто рассматривается как некоторая обобщенная модель. Состояние системы можно описать сложной функцией F, зависящей от множества переменных {Z,.Zn), каждая из которых тоже описывается некоторой функцией, зависящей от времени. = 5 ' >.' ^п ) f\ C^l 5 ' '.' Хт ' О (-^1 ' Х2 ' '.' ' О п ~ fn (-^1' Х2 ' '.' Хт ' О

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

Y = F(Z,\, Z2, ,., Zn) i i

Z, t'7 l

Z ^max tTotal ~tY+ ^max

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

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

В работе предлагается способ распределения нагрузки для систем имитационного моделирования, адаптированный для слабосвязанных многопроцессорных вычислителей. К этому классу относятся машины с архитектурами NUMA, DSM, СоРС. Для них характерно то, что время обращения процессора к локальной памяти узла значительно меньше времени обращения к памяти соседнего узла. Это происходит из-за того, что в последнем случае необходимо использовать вместо шины процессора внешнюю коммуникационную среду с большей латентностью и меньшей пропускной способностью.

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

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

1. Анализ методов моделирования, используемых в различных областях человеческой деятельности.

2. Анализ особенностей аппаратных средств систем имитационного моделирования.

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

4. Разработка программы имитационного моделирования, адаптированной для слабосвязанных многопроцессорных систем.

5. Проведение испытаний и анализ эффективности предложенного алгоритма.

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

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

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

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

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

Внедрение результатов. Результаты диссертационной работы используются на кафедре вычислительной техники МИЭТ при проведении лабораторных работ по курсу «Высокопроизводительные вычислительные системы».

На защиту выносятся следующие положения:

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

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

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

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

5. Результаты экспериментальных исследований, испытаний и анализ эффективности предложенного алгоритма.

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

1. Двенадцатая всероссийская межвузовская научно-техническая конференция студентов и аспирантов. «Микроэлектроника и информатика-2005», г. Москва, 2005г.

2. Международная школа-конференция по приоритетному направлению «Информационно-телекоммуникационные системы» с участием молодых ученых, аспирантов и студентов стран-членов СНГ, г. Москва, 2005г.

3. Тринадцатая всероссийская межвузовская научно-техническая конференция студентов и аспирантов. «Микроэлектроника и информатика-2006», г. Москва, 2006г.

4. Научная сессия «МИФИ-2007» г. Москва, 2007г.

5. Четырнадцатая всероссийская межвузовская научно-техническая конференция студентов и аспирантов. «Микроэлектроника и информатика-2007», г. Москва, 2007г.

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

Публикации. По материалам диссертации опубликовано шесть тезисов докладов и три статьи. Получено свидетельство РФ на программу для ЭВМ.

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

4.3 Выводы

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

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

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

Заключение

В результате работы получены следующие основные результаты:

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

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

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

4. Разработан программный модуль имитационного моделирования для слабосвязанных многопроцессорных систем и получено свидетельство о его официальной регистрации. Программный модуль реализован в среде mpC Workshop.

5. Эксперименты, проведенные на кластере 25*P-IV 2400, подтвердили практическую эффективность предложенного способа распределения вычислительной нагрузки и функциональность алгоритма имитационного моделирования.

1. Ю. Г. Карпов. Имитационное моделирование систем. Введение в моделирование с Anylogic 5. Текст. / - СПБ.: БХВ-Петербург, 2006.

2. Имитационное моделирование. Электронный ресурс. / Режим доступа: http: // www. inter face .ru/home. asp? art 1 d= 15 5 7 — Загл. с экрана.

3. Аверилл M.Jloy, В. Дэвид Кельтон. Имитационное моделирование. Текст. / Классика CS. 3-е изд. СПБ.: Питер; Киев: Издательская группа BHV, 2004.

4. Ю.Б. Колесов, Ю.Б. Сениченков. Имитационное моделирование сложных динамических систем. Электронный ресурс. / Режим доступа: http://www.exponenta.ru/soft/others/mvs/dssim.asp

5. Имитационное моделирование. Электронный ресурс. / Режим доступа: http://www. interface.ru/home.asp?artld= 1558 - Загл. с экрана.

6. Компьютерное моделирование. Электронный ресурс. / Режим доступа: http://www.mista.ru/23 .htm

7. AnyLogic платформа для моделирования сложных систем. Электронный ресурс. / - Режим доступа: http://sedok.narod.ru/anylogic.html

8. Замятина Е.Б. Современные теории имитационного моделирования. Программа специального курса. Текст. / Пермь: ПТУ, 2007.

9. Richard М. Fujimoto. Distributed Simulation Systems. Текст. / In Proceedings of the 2003 Winter Simulation Conference S. Chick, P. J. Sanchez, D. Ferrin, andD. J. Morrice, eds. pp. 124-134. 2004.

10. Enver Yucesan, YahChuyn Luo, Chun-Hung Chen, Insup Lee. Distributed Web-based Experiments for optimization. Simulation Practice and Theory 9 Текст. / pp.73-90. 2001.

11. Richard A. Meyer, Rajive Bagrodia. Текст. / Parsec User Manual. Release 1.1., UCLA Parallel Computing Laboratory, 1998.

12. А.И.Миков, Е.Б. Замятина, А.Н.Фирсов. Инструментальные средства удалённого параллельного моделирования. В кн. Proceedings of XXII International Conference "Knowledge-Dialogue-Solution". Текст. / FOI-COMMERCE, Sofia, 2006.

13. B.B. Воеводин, Вл.В. Воеводин. Параллельные вычисления. Текст./ Научное издание. СПБ.: БХВ-Петербург, 2004.

14. Основные классы современных параллельных компьютеров, Лаборатория НИВЦ МГУ. Электронный ресурс. / Режим доступа: http://www.parallel.ru/computers/classes.html

15. Э. Таненбаум. Распределенные системы: принципы и парадигмы. Текст. /- СПб: Питер, 2003. 877 с.

16. Gerard Tel. Introduction to Distributed Algorithms. Second edition. Текст. / Cambridge University Press. 2000. 608 c.

17. J.C.Comfort. The Simulation of Master-Slave Event Set Processor. Simulation. Текст. / 42(3): 117-124, March, 1984.

18. Миков А.И. Моделирование вычислительных систем. Текст. / Учебное пособие по спецкурсу.-Пермь, Перм. ун-т., 1982, 96 с.

19. Е.Киндлер. Языки моделирования. Текст. / М.:Энергоатомиздат.,1985.-288с.

20. Шрайбер Т.Дж.Моделирование на GPSS. Текст. / -М.:Маширостроение, 1980. 592 с.

21. S.W. Reichenthal. The Simulation Reference Markup Language (SRML): a foundation for representing BOMs and supporting reuse, Текст. / Boeing, 2002.

22. B.B. Окольнишников. Представление времени в имитационном моделировании. Вычислительные технологии. Текст. / Т. 10, №5, Сибирское отделение РАН, 2005, стр. 57-77

23. Брейер М. Автоматизация проектирования вычислительных систем. Языки, моделирование и базы данных. Текст. / М.: Мир, 1979.-464с.

24. Томашевский В., Жданова Е. Имитационное моделирование в среде GPSS. Текст. / М.: Бестселлер, 2003-416 с.

25. Т. Дж. Шрайбер, С. Кокс, Дж. О. Хенриксен, П. Лоренц, Дж. Рейтман, И. Стол. GPSS 40 лет: перспективы развития. (Труды конференции WSC-2001, 9-12 декабря 2001 года). Электронный ресурс. / Режим доступа: www.gpss.ru

26. Якимов И. М., Девятков В. В. Развитие методов и систем имитации в СССР и России. (Казань, ноябрь 2001 год). Электронный ресурс. / -Режим доступа: www.gpss.ru

27. Лычкина Н. Н. Опыт применения GPSS в Государственном Университете Управления. (40-летию GPSS посвящается). (Москва, 2002 год). Электронный ресурс. / Режим доступа: wwvv.gpss.ru

28. Андрианов А.Н., Бычков С.П.,Хорошилов А.И. Программирование на языке Симула-67. Текст. / -М.:Наука, 1985.-370с.

29. Симметричные мультипроцессорные системы. Электронный ресурс. / -Режим доступа: http://rsusul.md.mrmet.ru/tutor/method/ml/page04.html

30. А. В. Богданов, В. В. Корхов, В. В. Мареев, Е. Н. Станкова. Архитектуры и топологии многопроцессорных вычислительных систем. Текст. / Курс лекций. Учебное пособие — М.: ИНТУИТ.РУ «Интернет-Университет Информационных Технологий», 2004.

31. Программа ASCI. Электронный ресурс. / Режим доступа: http://www.llnl.gov/asci/

32. Система ASCI White. Электронный ресурс. / Режим доступа: http ://www. llnl.gov/asci/platforms/white/

33. Тор500 List June 2008. Электронный ресурс. / - Режим доступа: http://www.top500.org/lists/2008/06

34. Система МВС-1000. Электронный ресурс. / Режим доступа: http://www.jscc.i-u

35. Суперкомпьютеры Тор 50. Электронный ресурс. / Режим доступа: http:// sup ercomputers.ru/index .php

36. Кластер АСЗ Velocity Cluster. Электронный ресурс. / Режим доступа: http://www.tc.cornell.edu

37. Hewlett-Packard Kayak XU PC workstation. Электронный ресурс. / -Режим доступа: http://www.hp.com/desktops/kayak/

38. NT Supercluster. Электронный ресурс. / Режим доступа: http://archive.ncsa.uiuc.edu/SCD/Hardware/NTCluster/

39. HPVM. Электронный ресурс. / Режим доступа: http://www-csag.ucsd.edu/projects/clusters.html

40. Кластера Thunder. Электронный ресурс. / Режим доступа: http://www.llnl.gov/linux/thunder/

41. Myrinet. Электронный ресурс. / Режим доступа: http://www.myri.com/myrinet/index.html

42. Рыжиков Ю.И. Имитационное моделирование. Теория и технологии. Текст. / -М.:Альтекс, 2004, 384 с.

43. Дал У., Мюрхауг Б., Нюгорд К. Симула-67. Текст. / М.:Мир, 1969.-100с.

44. Л.Н.Лядова. Имитационное моделирование. Методические указания по курсу «Системное и прикладное программное обеспечение» Текст. / /Перм.ун-т; Сост. Л.Н.Лядова.-Пермь, 2003.-60 с.

45. Клейнен Дж. Статистические методы в имитационном моделировании. Текст. /-М.: Статистика, 1978, вып.1. -204 с.

46. Калашников В.В. Организация моделирования сложных систем.- Текст. / М.:3нание, 1982.- 64 с.

47. С.Немнюгин, О.Стесик. Параллельное программирование для многопроцессорных вычислительных систем. Текст. / -СПб.:БХВ-Петербург, 2002.- 400с.

48. К. Ю. Богачев. Основы параллельного программирования. Текст. / М.: БИНОМ. Лаборатория знаний, 2003.

49. А.В. Баранов., А.О. Лацис., М.Ю. Храмцов. Организация многопользовательского режима работы многопроцессорных вычислительных систем. Текст. / Институт прикладной математики им. М.В. Келдыша, Москва 2000.

50. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. Текст. / -М.: МЦНТО, 2002. с 955.

51. Лунин С.А., Посыпкин М.А. Технологии параллельного программирования. Текст. / М.: ИД «ФОРУМ»: ИНФРА - М, 2008. -208 с. (Высшее образование).