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

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

Применительно к вычислительной технике это означает, что новые задачи, связанные с большими объемами вычислений, которые постоянно возникают в различных сферах человеческой деятельности, стимулируют разработку все более мощных компьютеров. Но, появившись, такой компьютер позволяет использовать более точные математические модели и ставить еще большие задачи. До недавнего времени исследователи для их решения могли использовать только чрезвычайно дорогие суперкомпьютеры. Сегодня многопроцессорные вычислительные системы, обеспечивающие высокую производительность за счет параллельных вычислений, стали доступны широкому кругу исследователей. Кластерная архитектура на сегодняшний день является наиболее востребованной при создании новых высокопроизводительных вычислительных комплексов: в списке самых мощных суперкомпьютеров ТОР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, подтвердили практическую эффективность предложенного способа распределения вычислительной нагрузки и функциональность алгоритма имитационного моделирования.