|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Разработка высокоэффективного гибридного алгоритма синхронизации времени для распределённого дискретно-событийного имитационного моделированияНИР
- Руководитель НИР: Бахмуров А.Г.
- Участники НИР: Антоненко В.А., Волканов Д.Ю., Глонина А.Б., Кибитова В.Н., Косачева С.А., Костенко В.А.
- Подразделение: Лаборатория вычислительных комплексов
- Срок исполнения: 14 марта 2013 г. - 31 декабря 2015 г.
- Номер договора (контракта, соглашения): 13-07-00751-а
- Номер ЦИТИС: 01201356242
- Тип: Фундаментальная
- Приоритетное направление научных исследований: Информационные технологии, компьютерные сети, распределенные вычисления и защита информации
- ПН России: Информационно-телекоммуникационные системы
- Направление технологического прорыва России: Стратегические информационные технологии
-
Рубрики ГРНТИ:
- 50.51.17 Программное обеспечение процессов проектирования
-
Ключевые слова:
распределенное имитационное моделирование, полунатурное моделирование, синхронизация модельного времени, оптимизация алгоритмов синхронизации времени
-
Описание:
Исходя из свойств распределенной среды дискретно-событийного имитационного моделирования (РС ДСИМ) ДИАНА и требований к алгоритму синхронизации времени для РС ДСИМ, поддерживающих полунатурное моделирование, для реализации в РС ДСИМ ДИАНА выбран спекулятивный алгоритм синхронизации времени с локальными откатами. Предложенный алгоритм является гибридным алгоритмом. Гибридный алгоритм был реализован и было проведено его экспериментальное исследование. В 2014 году были получены следующие результаты: приведено формальное описание гибридного алгоритма, доказана корректность алгоритма, выполнена программная реализация гибридного алгоритма. В результате проведенного экспериментального исследования гибридного алгоритма на тестовых моделях был выделен класс моделей, на которых гибридный алгоритм работает эффективнее классического консервативного алгоритма.
-
Основные результаты:
В 2013 году была поставлена задача выбора эффективного гибридного алгоритма синхронизации времени для распределённых систем дискретно-событийного имитационного моделирования (РС ДСИМ), поддерживающих полунатурное моделирование. Построена математическая модель задачи. Проведён обзор существующих гибридных алгоритмов синхронизации времени в РС ДСИМ. Выделены особенности РС ДСИМ, поддерживающих полунатурное моделирование, влияющие на выбор алгоритма синхронизации времени; на их основе сформированы требования к алгоритму синхронизации. Из существующих гибридных алгоритмов синхронизации времени выбраны алгоритмы, удовлетворяющие требованиям, модификации которых потенциально способны повысить производительность рассматриваемых РС ДСИМ. В 2014 году исходя из свойств распределенной среды дискретно-событийного имитационного моделирования (РС ДСИМ) ДИАНА и требований к алгоритму синхронизации времени для РС ДСИМ, поддерживающих полунатурное моделирование, для реализации в РС ДСИМ ДИАНА выбран спекулятивный алгоритм синхронизации времени с локальными откатами. Предложенный алгоритм является гибридным алгоритмом. Гибридный алгоритм был реализован и было проведено его экспериментальное исследование. Были получены следующие результаты: приведено формальное описание гибридного алгоритма, доказана корректность алгоритма, выполнена программная реализация гибридного алгоритма. В результате проведенного экспериментального исследования гибридного алгоритма на тестовых моделях был выделен класс моделей, на которых гибридный алгоритм работает эффективнее классического консервативного алгоритма. В 2015 году среда дискретно-событийного имитационного моделирования (РС ДСИМ) ДИАНА была модифицирована путём добавления нового алгоритма синхронизации времени. Описание экспериментов с модифицированной системой нашло своё отражение в двух публикациях Результаты исследования производительности алгоритма синхронизации модельного времени в зависимости от характеристик модели и параметров алгоритма показали, что модифицированный гибридный алгоритм эффективен на ряде моделей относительно консервативного и базового гибридного алгоритма. Эти результаты были представлены на седьмой всероссийской научно-практической конференции «Имитационное моделирование. Теория и практика» – «ИММОД-2015» и в публикации в издании из списка ВАК, планируемой к выходу в 2016 году.
- Добавил в систему: Бахмуров Анатолий Геннадьевич
Соисполнители НИР
| МГУ имени М.В.Ломоносова | Координатор |
Источник финансирования НИР
| грант РФФИ |
Этапы НИР
| # | Сроки | Название |
| 1 | 1 января 2013 г.-31 декабря 2013 г. | Разработка высокоэффективного гибридного алгоритма синхронизации времени для распределённого дискретно-событийного имитационного моделирования |
| Результаты этапа: | ||
| 2 | 14 марта 2014 г.-31 декабря 2014 г. | Разработка высокоэффективного гибридного алгоритма синхронизации времени для распределённого дискретно-событийного имитационного моделирования |
| Результаты этапа: Исходя из ранее сформулированных требований к алгоритму синхронизации времени для РС ДСИМ, поддерживающих полунатурное моделирование (возможность работы некоторых компонентов модели по консервативной схеме и высокая эффективность), и особенностей реализации инфраструктуры RTI (CERTI), использующейся РС ДСИМ ДИАНА (отсутствие сервисов, необходимых для работы оптимистических алгоритмов), для реализации был выбран спекулятивный алгоритм с локальными откатами. Данный алгоритм позволяет продвигать логическое время процессов сверх их LBTS. Однако, при отправке сообщения другим процессам, каждый процесс должен ожидать до тех пор, пока не будет гарантировано, что он не получит сообщение с временной меткой, меньшей его текущего времени, то есть до тех пор, пока временная метка отправляемого сообщения не станет меньше, чем LBTS. Таким образом, все откаты будут строго локальными и каскадных откатов не произойдёт. Приведено формальное описание алгоритма в виде псевдокода. Доказана корректность алгоритма. Идея доказательства состоит в следующем. Так как в спекулятивном алгоритме с локальными откатами каждый логический процесс между отправками сообщений продвигает свое логическое время и выполняет откаты согласно оптимистической схеме, а корректность оптимистической схемы доказана, то для доказательства корректности алгоритма синхронизации остается доказать, что каждый процесс за конечное физическое время выполнит действие отправки. Этот факт был сформулирован в виде теоремы и доказан по индукции. Алгоритм был реализован. Экспериментальное сравнение данного алгоритма с консервативным алгоритмом синхронизации было проведение на двух топологиях моделей. В ходе экспериментов варьировалась вероятность отправки сообщений процессом на каждом шаге моделирования. Результаты экспериментов позволили выявить классы моделей, для которых использование реализованного алгоритма приводит к увеличению эффективности. Таким образом, для исследованных топологий получен критерий выбора алгоритма синхронизации между консервативным алгоритмом и спекулятивным алгоритмом с локальными откатами. | ||
| 3 | 1 января 2015 г.-31 декабря 2015 г. | Разработка высокоэффективного гибридного алгоритма синхронизации времени для распределённого дискретно-событийного имитационного моделирования |
| Результаты этапа: В 2015 году среда дискретно-событийного имитационного моделирования (РС ДСИМ) ДИАНА была модифицирована путём добавления нового алгоритма синхронизации времени. Описание экспериментов с модифицированной системой нашло своё отражение в двух публикациях Результаты исследования производительности алгоритма синхронизации модельного времени в зависимости от характеристик модели и параметров алгоритма показали, что модифицированный гибридный алгоритм эффективен на ряде моделей относительно консервативного и базового гибридного алгоритма. Эти результаты были представлены на седьмой всероссийской научно-практической конференции «Имитационное моделирование. Теория и практика» – «ИММОД-2015» и в публикации в издании из списка ВАК, планируемой к выходу в 2016 году. | ||
Прикрепленные к НИР результаты
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".