Основным недостатком консервативных алгоритмов является то, что приостановка вычислений серьезно снижает эффективность использования параллелизма. Кроме того, возникают тупиковые ситуации (deadlocks), когда подмодели, ожидающие друг от друга сообщения, образуют замкнутый круг и исполнение всей распределенной модели останавливается. Разрешение тупиковых ситуаций требует дополнительных усложнений алгоритма.
Задачей консервативных алгоритмов является предотвращение парадоксов времени. Консервативные алгоритмы предполагают, что между подмоделями используются FIFO каналы передачи данных, то есть адресат получает сообщения в том порядке, в котором их посылал отправитель. Это означает, что если подмоделью в момент времени t получено сообщение, отправленное адресантом в момент модельного времени t + ?t, она не получит в интервале ?t другого сообщения от данного отправителя и может продолжать вычисления в интервале времени ?t не «опасаясь» возникновения «парадокса времени». В том случае, если от какого-либо адресанта нет сообщений, то для предотвращения «парадокса времени» вычисления следует временно остановить до их получения.
Для того чтобы избежать «парадоксов времени», необходима реализация специальных алгоритмов синхронизации. Существуют два основных класса алгоритмов синхронизации модельного времени: консервативные и оптимистические [2, 3, 4].
В случае последовательного (однопоточного) моделирования в пакете AnyLogic, среда моделирования позаботится о том, чтобы происходящие события были упорядочены правильным образом. Когда же мы прибегаем к распределенному (параллельному) моделированию, мы имеем несколько подмоделей, и у каждой из них будет свое текущее модельное время и список событий. Одна подмодель может общаться с другой, например, помощью передачи сообщений. Результатом получения такого сообщения будет возникновение в модели некоторого события. Сложности возникают, если к моменту получения сообщения, предполагающего возникновение события в момент времени t, модельное время уже «ушло» вперед до некоторого момента t + ?t. Будем называть такие ситуации «парадоксом времени» [1].
Исполнение компьютерной дискретно-событийной модели предполагает наличие некоторого множества переменных состояния, характеризующих модель в текущий момент модельного времени, а также списка запланированных событий, которые должны произойти в модели в будущем. В подавляющем большинстве случаев, для дискретно-событийных моделей, разрабатываемых в среде AnyLogic, имеет значение, в каком порядке будут обрабатываться события, происходящие в модельном времени. То есть в том случае, если какое-либо событие произойдет раньше или позже, чем это было запланировано создателем модели, результаты моделирования могут оказаться неверны. Кроме того, как правило, среда моделирования должна обеспечивать такое свойство, как «повторяемость» результатов моделирования (т.е. результаты «прогонов» одной и той же модели с одинаковыми начальными данными должны совпадать).
Важнейшим аспектом при построении распределенной (параллельной) модели является синхронизация отдельных ее частей. Пакет AnyLogic среда для создания преимущественно дискретно-событийных моделей. В данном проекте будет рассматриваться только распределение частей дискретно-событийных моделей, так как при попытке синхронизации моделей, оперирующих с непрерывными сущностями, возникают совершенно иные проблемы, выходящие за рамки данного исследования.
3. Синхронизация распределенных частей модели
В результате исследования инструментов имитационного моделирования по двум критериям (инструмент общего назначения и гибкость) была выбрана программа AnyLogic. AnyLogic основан на языке Java и является инструментом общего назначения.
Вторым критерием для выбора инструмента является гибкость. Для создания библиотеки средств распараллеливания моделей необходимо иметь в самом инструменте собственно возможность создания библиотек, а также достаточные средства для описания библиотечных элементов. Во многих инструментах разработчик ограничен небольшим множеством функций. А для функции распределения модели в инструменте как минимум должны быть средства обмена данными по сети.
Большинство инструментов имитационного моделирования созданы для конкретных областей применения: производство, управление финансами, оптимизация складской логистики. Существует несколько гораздо более гибких инструментов общего назначения, с помощью которых можно описать любые модели. Мы бы не хотели ограничивать множество распределяемых моделей какой-то определенной предметной областью, поэтому выбор инструмента имитационного моделирования осуществлялся из систем общего назначения.
2. Выбор инструмента имитационного моделирования
Целью данного проекта является преодоление трудностей, связанных с распараллеливанием моделей, за счет добавления средств создания распределенных моделей непосредственно в инструмент имитационного моделирования. Это позволит специалисту сфокусировать внимание собственно на создании модели, а не на программировании. От него потребуется только логически разделить модель на части с небольшим объемом взаимодействий. Далее, путем использования библиотечных элементов и простой настройки, такая модель может быть запущена на множестве рабочих станций.
Все наиболее часто используемые инструменты для имитационного моделирования, такие как Arena, Extend, VenSim и др. являются однопоточными приложениями. Поэтому для создания распределенной модели специалисту приходится переносить модель из удобного инструмента разработки моделей в неудобную и чуждую среду программирования. Перенос модели заключается в переносе описания объекта, а также в обеспечении взаимодействия распределенных компонент. Для специалистов по построению имитационных моделей эти задачи стоят далеко от их профессиональной области.
При распределении отдельных частей модели по сети компьютеров части модели выполняются отдельными компьютерами. Теоретически, при условии независимости компонент модели, выигрыш в производительности прямо пропорционален количеству рабочих станций. Если же компоненты модели обмениваются информацией, то ко времени моделирования прибавляется время на осуществление взаимодействия.
Имитационное моделирование в наши дни широко применяется для решения разнообразного круга задач. Компьютерное имитационное моделирование – это имитация поведения объектов реального мира с помощью компьютерной программы. Существует множество программ для описания и выполнения моделей. Часть этих программ создана для определенных предметных областей, часть для создания моделей общего назначения. Независимо от выбора программы, выполнение или имитация модели требует определенных вычислительных ресурсов и занимает время. Требования к объему, точности и функционалу современных имитационных моделей непрерывно возрастают и часто обгоняют технические возможности инструментов для создания моделей. Для таких моделей невозможно выполнить имитацию в разумные сроки, поэтому специалисты используют подходы, позволяющие уменьшить время моделирования. Одним из подходов является уменьшение точности модели, что приводит и к уменьшению точности результатов. В случае, когда уменьшение точности неприемлемо, можно воспользоваться подходом распараллеливания выполнения модели.
Параллельные вычислительные технологии 2009: Труды международной научной конференции. Челябинск: Изд. ЮУрГУ, 2009. С. 542-548.
Кондратьев М.А., Гарифуллин М.В.
Построение распределенных дискретно-событийных моделей в среде AnyLogic
Институт прикладных исследований в цепях поставок и логистике | The Institute for Applied Research in Supply Chain and Logistics
Построение распределенных дискретно-событийных моделей в среде AnyLogic | ИПИ ЦПЛ
Комментариев нет:
Отправить комментарий