Исследование эффективности алгоритмов синхронизации времени для систем распределенного имитационного моделирования

• Автор: Вознесенская, Тамара Васильевна
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Москва
• Количество страниц: 95 с. : ил.

Содержание.
Введение
1. Постановка задачи
2. Алгоритмы синхронизации модельного времени
2.1 .Проблема единого модельного времени в распределенном
имитационном моделировании
2.2.Строго синхронные АС
2.3.Консервативные АС и АС с синхронизацией взаимодействий... 11 2.4.Оптимистические АС
3. Математическая модель взаимодействия приложения и АС
3.1. Основные принципы построения математической модели
3.2.Математическая модель взаимодействия приложения со строго синхронным АС
3.3.Математическая модель взаимодействия приложения с консервативным АС и с АС с синхронизацией взаимодействий
3.4.Математическая модель взаимодействия приложения с оптимистическим АС
3.4.1. Классический оптимистический АС
3.4.2. Оптимистический АС с временным окном
3.4.3. Оптимистический АС с периодическим сохранением состояний
3.5.Сохранение свойств моделируемого объекта в математической модели
4. Метод сравнения эффективности различных АС
5. Экспериментальное применение метода сравнения эффективности различных АС
5.1. Выбор наиболее эффективного АС для системы распределенного имитационного моделирования БУАЛА
5.2. Архитектура системы распределенного имитационного моделирования
5.3. Результаты м оделирования
Заключение
Приложение 1. Входные данные для статистических экспериментов
Приложение 2. Результаты сравнений АС для имитационных моделей системы БУАЛА
Приложение 3. Результаты статистических экспериментов с использованием математических моделей взаимодействия приложения и АС
Литература
Введение
Важную роль в создании и разработке распределенных вычислительных систем играет имитационное моделирование. Имитационные модели таких систем - сложные ресурсоемкие программные комплексы. Требования ко врёмени их моделирования зачастую становятся критическими. Одним из путей сокращения времени моделирования является использование внутреннего параллелизма моделей. Перспективным направлением распараллеливания имитационных моделей является распределенное имитационное моделирование (РИМ)[4]. Создание распределенной системы имитационного моделирования (РСИМ) требует разработки специального алгоритма синхронизации (АС) распределенно исполняемых частей модели[4].
Отличительной особенностью программ имитационного моделирования ' является то, что поведение всех процессов должно быть согласовано в едином модельном времени, то есть в том времени, в котором “живет” объект моделирования. Говоря об имитационном моделировании, далее везде будем иметь в виду дискретно-событийное имитационное моделирование[47].
Каждое событие в модели имеет вычисляемую в процессе выполнения метку - модельное время его наступления.
Будем рассматривать имитационные модели, которые
1. состоят из множества процессов, взаимодействующих между собой через прием и посылку сообщений;
2. имеют частично упорядоченное в едином модельном времени множество событий [14, 24]: если модельное время события а меньше модельного
•времени события Ь, значит, событие а наступило раньше события Ь, и наоборот; одновременные события, вообще говоря, не упорядочены.
. Последовательный прогон таких моделей происходит следующим образом [47]. Вначале вычисляются временные метки готовых к обработке событий. Такие события заносятся в список (календарь) событий и упорядочиваются по неубыванию модельного времени. Затем модельное время устанавливается равным метке первого события, а само событие

Однако процесс со временем x.mm = min х" может это делать всегда.
1 n=,N
Действительно, поскольку ViVn:w" > 0 и
/т е (1
Т, >Т.
»4-1 г
Оптимистический АС с периодическим сохранением состояний.
В крайнем случае, когда Vne {l
Отличие модели оптимистического АС с периодическим сохранением состояний от модели классического в том, что процессы могут откатиться до времени, меньшего min х". Пусть (х,1 ,х.2
n-,N
последовательность сохраненных состояний некоторого процесса и, пусть х,1 < mm х" < х,2. Во время повторного выполнения участка

Гх' ,min х,;) этот процесс не может ни вызывать откаты других
n=,N ‘
процессов, ни сам откатываться. Значит, за конечное число шагов процесс опять достигнет времени mm х" и двинется дальше. Поэтому
и=1,ЛГ
V/x/: />/, / I <х: Г, > /'
II. В случае отсутствия взаимодействий развитие приложения под управлением как консервативного (также АС с синхронизацией взаимодействий), так и оптимистического АС сводится к свободному независимому развитию N процессов. В этом случае, как видно из формул (3.3) и (3.4.1), математические модели этих АС сводятся к следующей: